快捷導(dǎo)航

C++ 實(shí)現(xiàn)帶監(jiān)視哨的順序查找算法

更新時(shí)間：2020年03月26日 15:21:13 作者：ddl是第一生產(chǎn)力

這篇文章主要介紹了C++ 實(shí)現(xiàn)帶監(jiān)視哨的順序查找算法，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下

監(jiān)視哨往往是程序里面的一個(gè)變量，如果是對(duì)數(shù)字排序的話，那么該變量一般是數(shù)值型變量。變量的賦值就相當(dāng)于哨兵，當(dāng)排序數(shù)列中出現(xiàn)與哨兵相等的值或有某種既定關(guān)系出現(xiàn)時(shí)，就做一種操作，比如說(shuō)停止排序，或進(jìn)行下一趟排序。

舉例：

順序檢索的算法描述如下

int Search_Sequen(SSTable ST,KeyType key){
//在線性表ST中順序檢索其關(guān)鍵字等于Key的數(shù)據(jù)元素，
//若找到，函數(shù)值為該元素在表中的位置，否則為-1.
ST.element[ST.length].key=key; //設(shè)置監(jiān)視哨
i=0;
while(ST.element[i].key!=key) i++;
if(i<ST.length)
return i;
else
return -1;
}

正文

之前在?？途W(wǎng)上做習(xí)題發(fā)現(xiàn)的這個(gè)獨(dú)特的順序查詢，第一次聽(tīng)到“監(jiān)視哨”這個(gè)說(shuō)法，就查了一下

具體實(shí)現(xiàn)就是將數(shù)組的第0位置空，在查找時(shí)將要查找的key插入作為監(jiān)視哨

這樣的好處是不用每次循環(huán)都檢查查找是否結(jié)束，減少了元素比較次數(shù)，

最后的返回值要么是元素下標(biāo)要么是數(shù)組第0位(這種情況就是到了監(jiān)視哨)

以下是我的代碼

#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會(huì)出現(xiàn)一個(gè)

error C2760: 語(yǔ)法錯(cuò)誤: 意外的令牌“標(biāo)識(shí)符”，預(yù)期的令牌為“;”

的錯(cuò)誤，具體原理我不是很懂，單給出一個(gè)解決辦法：

項(xiàng)目->屬性->C/C++->語(yǔ)言->符合模式->否

最后給自己提一下醒，數(shù)組作為函數(shù)參數(shù)是傳入數(shù)組首位的指針，指針是不帶有數(shù)組其他屬性的，

所以要在函數(shù)內(nèi)獲得數(shù)組的長(zhǎng)度，只能用引用和模板的形式傳入數(shù)組本身，這樣就能用sizeof()獲取數(shù)組長(zhǎng)度了

總結(jié)

到此這篇關(guān)于C++ 實(shí)現(xiàn)帶監(jiān)視哨的順序查找的文章就介紹到這了,更多相關(guān)c++ 監(jiān)視哨順序查找內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: