亲宝软件园·资讯

展开

c++ 监视哨顺序查找 C++ 实现带监视哨的顺序查找算法

ddl是第一生产力 人气:0

监视哨往往是程序里面的一个变量,如果是对数字排序的话,那么该变量一般是数值型变量。变量的赋值就相当于哨兵,当排序数列中出现与哨兵相等的值或有某种既定关系出现时,就做一种操作,比如说停止排序,或进行下一趟排序。

举例:

顺序检索的算法描述如下

int Search_Sequen(SSTable ST,KeyType key){
//在线性表ST中顺序检索其关键字等于Key的数据元素,
//若找到,函数值为该元素在表中的位置,否则为-1.
ST.element[ST.length].key=key; //设置监视哨
i=0;
while(ST.element[i].key!=key) i++;
if(i<ST.length)
return i;
else
return -1;
}

正文

之前在牛客网上做习题发现的这个独特的顺序查询,第一次听到“监视哨”这个说法,就查了一下

具体实现就是将数组的第0位置空,在查找时将要查找的key插入作为监视哨

这样的好处是不用每次循环都检查查找是否结束,减少了元素比较次数,

最后的返回值要么是元素下标要么是数组第0位(这种情况就是到了监视哨)

以下是我的代码

#include <iostream> 
using namespace std;

template<class T>
int linear_search(T& arr,int key)
{
 int length = sizeof(arr) / sizeof(arr[0]);
 int i = length;
 arr[0] = key;
 while (arr[i] != key)
 {
 i--;
 }
 return i;
}

int main()
{
 int array[] = { 0, 7,9,10,11,15 };
 int len = sizeof(array) / sizeof(array[0]);
 cout << linear_search(array, 10);
 return 0;
}

这里顺带提一下,vs2019会出现一个

error C2760: 语法错误: 意外的令牌“标识符”,预期的令牌为“;”

的错误,具体原理我不是很懂,单给出一个解决办法:

项目->属性->C/C++->语言->符合模式->否

最后给自己提一下醒,数组作为函数参数是传入数组首位的指针,指针是不带有数组其他属性的,

所以要在函数内获得数组的长度,只能用引用和模板的形式传入数组本身,这样就能用sizeof()获取数组长度了

总结

加载全部内容

相关教程
猜你喜欢
用户评论