- 任務(wù)描述
- 相關(guān)知識(shí)
- 編程要求
- 測(cè)試說(shuō)明
任務(wù)描述
本關(guān)要求通過(guò)補(bǔ)全函數(shù)BSL_FindKey來(lái)實(shí)現(xiàn)在已排序的順序表中查找關(guān)鍵碼值為key的結(jié)點(diǎn)并返回該結(jié)點(diǎn)的編號(hào)。
相關(guān)知識(shí)
折半查找通常是針對(duì)順序存儲(chǔ)的線性表，線性表的結(jié)點(diǎn)按關(guān)鍵碼從小到大排序，后面稱之為折半查找的順序表。為了簡(jiǎn)化討論，假設(shè)折半查找的順序表中每個(gè)結(jié)點(diǎn)只含一個(gè)關(guān)鍵碼，關(guān)鍵碼為整數(shù)。圖 1 給出了一個(gè)存儲(chǔ)了 4 個(gè)關(guān)鍵碼的折半查找的順序表的存儲(chǔ)結(jié)構(gòu)圖。
下面描述了線性表順序存儲(chǔ)的一種實(shí)現(xiàn)方案。該實(shí)現(xiàn)方案的示意圖為：
指針pkey是存儲(chǔ)關(guān)鍵碼的連續(xù)空間的起始地址，順序表中當(dāng)前的關(guān)鍵碼的個(gè)數(shù)由len給出，該順序表中最多可存儲(chǔ)max個(gè)關(guān)鍵碼。
將pkey、len、max組織成一個(gè)結(jié)構(gòu)，該結(jié)構(gòu)定義為：
struct BSeqList{int* pkey; // 指向關(guān)鍵碼數(shù)組的指針int len; // 當(dāng)前元素個(gè)數(shù)int max; // 線性表的最大元素?cái)?shù)};
只要給定指向該結(jié)構(gòu)的一指針blist，就可對(duì)線性表進(jìn)行操作。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-497683.html
對(duì)折半查找的順序表定義如下操作，各個(gè)操作函數(shù)的功能詳見(jiàn)下面給出的代碼文件 BSlist.cpp 的代碼框架：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-497683.html
BSeqList* BSL_Create(int size);void BSL_Free(BSeqList* blist);int BSL_InsKey(BSeqList* blist, int key);int BSL_FindKey(BSeqList* blist, int key);int BSL_DelKey(BS
到了這里，關(guān)于頭歌（C語(yǔ)言）-數(shù)據(jù)結(jié)構(gòu)與算法-查找-第1關(guān)：實(shí)現(xiàn)折半查找的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
