close

Sökalgoritm för flera objekt (Multiple-Item Search) i C++- Förklaring, exempel och kod

Sökalgoritmen med flera objekt används för att hitta alla förekomster av ett specifikt element i en lista. Till skillnad från sökalgoritmer med ett enda objekt, håller detta tillvägagångssätt reda på flera förekomster av målelementet och returnerar en lista över deras positioner.

Hur det fungerar

  1. Börja från början av listan.
  2. Iterera genom varje element i listan.
  3. Jämför det aktuella elementet med målvärdet.
  4. Om det aktuella elementet är lika med målvärdet, registrera dess position.
  5. Fortsätt till nästa element och upprepa steg 3-4.
  6. Efter att ha itererat igenom hela listan, returnera listan med inspelade positioner.

Exempel

Låt oss överväga en lista med heltal och vi vill hitta alla förekomster av talet 23.

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

  1. Börja från början: 12. Inte önskat nummer.
  2. Flytta till nästa element: 23. Matchning hittad, registrera position som 1.
  3. Flytta till nästa element: 45. Inte önskat nummer.
  4. Flytta till nästa element: 23. Matchning hittad, registrera position som 3.
  5. Flytta till nästa element: 56. Inte önskat nummer.
  6. Flytta till nästa element: 23. Matchning hittad, registrera position som 5.
  7. Flytta till nästa element: 89. Inte önskat nummer.
  8. Flytta till nästa element: 90. Inte önskat antal.
  9. Efter iteration, returnera en lista med positioner: [1, 3, 5].

Exempelkod 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 givna exemplet multipleItemSearch används funktionen för att hitta alla förekomster av talet 23 i en lista med heltal. Resultatet blir en vektor som innehåller positionerna för alla förekomster(positioner börjar från 0).