close

Multiple-Item Search (Multiple-Item Search) Algoritme i C++- Forklaring, Eksempel og Kode

Søgealgoritmen med flere elementer bruges til at finde alle forekomster af et specifikt element på en liste. I modsætning til enkelt-element søgealgoritmer holder denne tilgang styr på flere forekomster af målelementet og returnerer en liste over deres positioner.

Hvordan det virker

  1. Start fra begyndelsen af ​​listen.
  2. Gentag gennem hvert element på listen.
  3. Sammenlign det aktuelle element med målværdien.
  4. Hvis det aktuelle element er lig med målværdien, skal du registrere dets position.
  5. Fortsæt til næste element og gentag trin 3-4.
  6. Når du har gentaget hele listen, returnerer du listen over registrerede positioner.

Eksempel

Lad os overveje en liste over heltal, og vi ønsker at finde alle forekomster af tallet 23.

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

  1. Start fra begyndelsen: 12. Ikke det ønskede antal.
  2. Flyt til næste element: 23. Match fundet, optag position som 1.
  3. Flyt til næste element: 45. Ikke det ønskede tal.
  4. Flyt til næste element: 23. Match fundet, optag position som 3.
  5. Flyt til næste element: 56. Ikke det ønskede tal.
  6. Flyt til næste element: 23. Match fundet, optag position som 5.
  7. Flyt til næste element: 89. Ikke det ønskede tal.
  8. Flyt til næste element: 90. Ikke det ønskede tal.
  9. Efter iteration returneres en liste over positioner: [1, 3, 5].

Eksempelkode i 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;  
}

I det givne eksempel multipleItemSearch bruges funktionen til at finde alle forekomster af tallet 23 i en liste over heltal. Resultatet vil være en vektor, der indeholder positionerne for alle forekomster(positioner starter fra 0).