數(shù)據(jù)結(jié)構(gòu)a第06章(編輯修改稿)
2024-08-20 17:38 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 ， 仍無(wú)相等則搜索 失敗 。 85 14 78 42 23 查找 42 恭喜?。? 85 14 78 42 23 查找 52 遺憾?。∧暇┼]電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 無(wú)序表的順序搜索 template class T ResultCode ListSetT::Search(Tamp。 x)const { for (int i=0。in。i++) if (l[i]==x) { x=l[i]。 return Success。 //搜索成功 } return NotPresent。 //搜索失敗 } 程序 ： 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 有序表的順序搜索 基本方法：最右邊設(shè)置 哨兵 。 搜索 成功 的方法與無(wú)序表完全相同；找到表中某一關(guān)鍵字值大于待查找關(guān)鍵字 ， 則搜索 失敗 。 85 14 78 42 23 查找 42 恭喜??！ 85 14 78 42 23 查找 52 遺憾??！ ∞ ∞ 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 有序表的順序搜索 template class T ResultCode ListSetT::Search(Tamp。 x)const { //當(dāng) l[i]的關(guān)鍵字值大于等于 x的關(guān)鍵字值時(shí) ， 出循環(huán) for (int i=0。l[i]x。i++)。 if (l[i]==x) { x=l[i]。return Success。 //搜索成功 } return NotPresent。 //搜索失敗 } // l[i]x amp。amp。 in 程序 ： 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 平均搜索長(zhǎng)度 搜索中所需的關(guān)鍵字值之間的比較次數(shù)的期望值，被稱為搜索算法的 平均搜索長(zhǎng)度( average search length ASL) 。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 求成功搜索的平均搜索長(zhǎng)度，需要給定表中元素 ai被搜索的概率 pi。設(shè)表長(zhǎng)為 n，假定每個(gè)元素的搜索概率是相等的，即 pi=1/n，則程序 在搜索成功時(shí)的平均搜索長(zhǎng)度為： 2 11)1(1110????? ?????nininA S LniniS程序 在搜索失敗時(shí)的平均搜索長(zhǎng)度為： nA S L F ?南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 設(shè)有序表為 （ a0,a1,…,an－ 1） ， 通?？梢约俣ù樵氐闹滴挥?a0之前 ， a0與 a1之間 ，a1與 a2之間 ,…,an2與 an－ 1之間以及 an－ 1之后的共 n+1個(gè)區(qū)間內(nèi)的概率是相等的 。 程序： 22ni1n 11)1i(1n 11A SL1n1in0iF ????????? ?????結(jié)論： 無(wú)序表和 有序表在搜索成功時(shí) ASL相同；但是在搜索失敗時(shí) ， 有序表的 ASL是無(wú)序表的一半 ， 效率高 。 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 二分搜索 南京郵電大學(xué)計(jì)算機(jī)學(xué)院 2022年 1月 二分搜索算法 設(shè)有一個(gè)長(zhǎng)度為 n的有序表 ： （ a0， a1， ?， an1） 要求在表中搜索與給定元素 x有相同關(guān)鍵字值的元素 。 若 n=0， 則顯然搜索失?。蝗?n0， 則可將有序表分解成若干個(gè)子表 ， 最簡(jiǎn)單的做法是分成兩個(gè)子表 。 以元素 am為劃分點(diǎn) ， 將表分成如下兩個(gè)子表： （ a0， ?， am1） 和 （ am＋ 1， ?， an1） 將 am的關(guān)鍵字值與指定元素 x的關(guān)鍵字值作比較 ，比較結(jié)果有三種可能性： 南京郵電大學(xué)計(jì)算機(jī)學(xué)院
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1