close

Algorithmus zur Suche nach mehreren Elementen (Multiple-Item Search) in C++ – Erklärung, Beispiel und Code

Der Algorithmus zur Suche nach mehreren Elementen wird verwendet, um alle Vorkommen eines bestimmten Elements in einer Liste zu finden. Im Gegensatz zu Suchalgorithmen für einzelne Elemente verfolgt dieser Ansatz mehrere Vorkommen des Zielelements und gibt eine Liste ihrer Positionen zurück.

Wie es funktioniert

  1. Beginnen Sie am Anfang der Liste.
  2. Durchlaufen Sie jedes Element in der Liste.
  3. Vergleichen Sie das aktuelle Element mit dem Zielwert.
  4. Wenn das aktuelle Element dem Zielwert entspricht, notieren Sie seine Position.
  5. Fahren Sie mit dem nächsten Element fort und wiederholen Sie die Schritte 3-4.
  6. Nachdem Sie die gesamte Liste durchlaufen haben, geben Sie die Liste der aufgezeichneten Positionen zurück.

Beispiel

Betrachten wir eine Liste von ganzen Zahlen und wollen alle Vorkommen der Zahl 23 finden.

Liste: {12, 23, 45, 23, 56, 23, 89, 90}

  1. Beginnen Sie von vorne: 12. Nicht die gewünschte Zahl.
  2. Zum nächsten Element wechseln: 23. Übereinstimmung gefunden, Position als 1 eintragen.
  3. Zum nächsten Element wechseln: 45. Nicht die gewünschte Zahl.
  4. Zum nächsten Element wechseln: 23. Übereinstimmung gefunden, Position als 3 eintragen.
  5. Gehen Sie zum nächsten Element: 56. Nicht die gewünschte Zahl.
  6. Zum nächsten Element wechseln: 23. Übereinstimmung gefunden, Position als 5 eintragen.
  7. Gehen Sie zum nächsten Element: 89. Nicht die gewünschte Zahl.
  8. Zum nächsten Element wechseln: 90. Nicht die gewünschte Zahl.
  9. Geben Sie nach der Iteration eine Liste mit Positionen zurück: [1, 3, 5].

Beispielcode in C++ 

#include <iostream>  
#include <vector>  
  
std::vector<int> multipleItemSearch(const std::vector<int>& arr, int target) {  
    std::vector<int> positions;  
  
    for(int i = 0; i < arr.size(); ++i) {  
        if(arr[i] == target) {  
            positions.push_back(i);  
        }  
    }  
  
    return positions;  
}  
  
int main() {  
    std::vector<int> numbers = {12, 23, 45, 23, 56, 23, 89, 90};  
    int target = 23;  
  
    std::vector<int> result = multipleItemSearch(numbers, target);  
  
    std::cout << "Occurrences of " << target << " found at positions: ";  
    for(int pos: result) {  
        std::cout << pos << ";  
    }  
    std::cout << std::endl;  
  
    return 0;  
}

Im gegebenen Beispiel multipleItemSearch wird die Funktion verwendet, um alle Vorkommen der Zahl 23 in einer Liste von ganzen Zahlen zu finden. Das Ergebnis ist ein Vektor, der die Positionen aller Vorkommen enthält(Positionen beginnen bei 0).