基于引用局部性执行搜索的 C++ 程序
c++server side programmingprogramming
基于引用局部性的搜索取决于数据元素重新分配的内存访问模式。
这里使用线性搜索方法来搜索元素。
算法
开始 int find(int *intarray, int n, int item) intialize Comparisons = 0 for i = 0 to n-1 增加比较 if(item == intarray[i]) 打印元素及其索引 break if(i == n-1) 打印未找到元素 返回 -1 打印总比较数 对于 j = i 直到 i>0 intarray[j] = intarray[j-1] intarray[0] = item 返回 0 结束
示例
#include<iostream>
using namespace std;
// 执行线性搜索的函数。
// 此方法进行线性搜索。
int find(int *intarray, int n, int item) {
int i;
int Comparisons = 0;
// 浏览所有项目
for(i = 0;i<n;i++) {
// 计算所做的比较 Comparisons++;
// 如果找到项目，则中断循环
if(item == intarray[i]) {
cout<<"element found at:"<<i<<endl;
break;
}
// 如果索引到达末尾，则该项目不存在。
if(i == n-1) {
cout<<"\n未找到元素。";
return -1;
}
}
printf("总共进行了 %d 次比较", 比较);
// 将每个元素移到匹配项之前。
for(int j = i; j > 0; j--)
intarray[j] = intarray[j-1];
// 将最近搜索的项目放在数据数组的开头。
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;
// 打印初始数据数组。
cout<<"\n数组为:";
for(i = 0; i < 20;i++)
cout<<intarray[i]<<" ";
up:
cout<<"\n输入要搜索的元素:";
cin>>n;
// 打印更新后的数据数组。
if(find(intarray,20, n) != -1) {
cout<<"\n搜索后的数组为:";
for(i = 0; i <20;i++)
cout<<intarray[i]<<" ";
}
cout<<"\n\n是否想搜索更多.......是/否(y/n)?";
cin>>ch;
if(ch == 'y' || ch == 'Y')
goto up;
return 0;
}
输出
数组为:1 2 3 4 6 7 9 11 12 14 15 16 26 19 33 34 43 45 55 66 输入要搜索的元素:26 元素位于:12 总比较次数:13 搜索后的数组为:26 1 2 3 4 6 7 9 11 12 14 15 16 19 33 34 43 45 55 66 是否要搜索更多.......是/否(y/n)?y 输入要搜索的元素:0 未找到元素。 是否要搜索更多.......是/否(y/n)?n
