参照の局所性に基づいて検索を実行するC++プログラム

参照の局所性に基づく検索は、データ要素が再割り当てされるメモリアクセスパターンに依存します。

ここでは、線形検索法を使用して要素を検索します。

アルゴリズム

Begin
   int find(int *intarray, int n, int item)
   intialize comparisons = 0
   for i = 0 to n-1
      Increase comparisons
   if(item == intarray[i])
      Print element with its index
   break
   if(i == n-1)
      Print element not found
   return -1
   Print Total comparisons
   For j = i till i>0
      intarray[j] = intarray[j-1]
      intarray[0] = item
   return 0
End

例

#include<iostream>
using namespace std;
// A function to perform linear search.
// this method makes a linear search.
int find(int *intarray, int n, int item) {
   int i;
   int comparisons = 0;
   // navigate through all items
   for(i = 0;i<n;i++) {
      // count the comparisons made comparisons++;
      // if item found, break the loop
      if(item == intarray[i]) {
         cout<<"element found at:"<<i<<endl;
         break;
      }
      // If index reaches to the end then the item is not there.
      if(i == n-1) {
         cout<<"\nThe element not found.";
         return -1;
      }
   }
   printf("Total comparisons made: %d", comparisons);
   // Shift each element before matched item.
   for(int j = i; j > 0; j--)
      intarray[j] = intarray[j-1];
      // Put the recently searched item at the beginning of the data array.
      intarray[0] = item;
   return 0;
}
int main() {
   int intarray[20]={1,2,3,4,6,7,9,11,12,14,15,16,26,19,33,34,43,45,55,66};
   int i,n;
   char ch;
   // print initial data array.
   cout<<"\nThe array is: ";
   for(i = 0; i < 20;i++)
      cout<<intarray[i]<<" ";
   up:
   cout<<"\nEnter the Element to be searched: ";
   cin>>n;
   // Print the updated data array.
   if(find(intarray,20, n) != -1) {
      cout<<"\nThe array after searching is: ";
      for(i = 0; i <20;i++)
         cout<<intarray[i]<<" ";
   }
   cout<<"\n\nWant to search more.......yes/no(y/n)?";
   cin>>ch;
   if(ch == 'y' || ch == 'Y')
      goto up;
   return 0;
}

出力

The array is: 1 2 3 4 6 7 9 11 12 14 15 16 26 19 33 34 43 45 55 66
Enter the Element to be searched: 26
element found at:12
Total comparisons made: 13
The array after searching is: 26 1 2 3 4 6 7 9 11 12 14 15 16 19 33 34 43 45 55 66

Want to search more.......yes/no(y/n)?y

Enter the Element to be searched: 0

The element not found.

Want to search more.......yes/no(y/n)?n