數(shù)據(jù)結(jié)構(gòu)查找

數(shù)據(jù)結(jié)構(gòu)課件查找第一頁(yè)，共四十頁(yè)，編輯于2023年，星期三

查找中用到如下的基本概念。例如8.1查找基本的概念2列表關(guān)鍵字查找平均查找長(zhǎng)度基本查找方法第二頁(yè)，共四十頁(yè)，編輯于2023年，星期三姓名學(xué)號(hào)性別年齡班級(jí)健康黃佳9831男18計(jì)98良好錢(qián)昌9832女17計(jì)98一般王羽9833男19計(jì)98近視高甜9834女18計(jì)98一般………………………………列表：由同一類(lèi)型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。關(guān)鍵字：數(shù)據(jù)元素的某個(gè)數(shù)據(jù)項(xiàng)的值，用它可標(biāo)識(shí)列表中的一個(gè)或一組數(shù)據(jù)元素查找：根據(jù)給定的關(guān)鍵字值，在列表中確定一個(gè)其關(guān)鍵字與給定值相同的數(shù)據(jù)元素，并返回該數(shù)據(jù)元素在列表中的位置。第三頁(yè)，共四十頁(yè)，編輯于2023年，星期三平均查找長(zhǎng)度定義：為確定數(shù)據(jù)元素在列表中的位置，需和給定關(guān)鍵值進(jìn)行比較的關(guān)鍵值個(gè)數(shù)的期望值，稱為查找算法在查找成功時(shí)的平均查找長(zhǎng)度Pi是查找第i個(gè)元素概率，Ci是為找到第i個(gè)元素進(jìn)行的比較次數(shù)第四頁(yè)，共四十頁(yè)，編輯于2023年，星期三順序查找法5折半查找分塊查找法8.2基于線性表的查找法第五頁(yè)，共四十頁(yè)，編輯于2023年，星期三 8.2.1順序查找法1、數(shù)據(jù)類(lèi)型的定義#defineLiST_SIZE20Typedefstruct{KeyTypekey;OtherTypeother_data;}RecordType;Typedefstruct{RecordTyper[LIST_SIZE+1];//r[0]為工作單元

intlength;}RecordList第六頁(yè)，共四十頁(yè)，編輯于2023年，星期三2、順序查找法設(shè)置監(jiān)視哨intSeqSearch(RecordListl,KeyTypek)//在順序表l中順序查找關(guān)鍵字等于k的元素，若找到，則函數(shù)值為該元素在表中的位置，否則為0.{l.r[0].key=k;i=l.length;while(l.r[i].key!=k)i--;return(i);}不設(shè)監(jiān)視哨

intSeqSearch(RecordListl,KeyTypek)//不用監(jiān)視哨，在順序表中查找關(guān)鍵字等于k的元素

i=l.length;while(i>=1&&l.r[i].key!=k)i--;if(i>1)return(i);elsereturn(0);}第七頁(yè)，共四十頁(yè)，編輯于2023年，星期三3、性能分析

假設(shè)列表長(zhǎng)度為n，那么查找第i個(gè)數(shù)據(jù)元素需要進(jìn)行n-i+1次比較，即Ci=n-i+1。又假設(shè)查找每個(gè)數(shù)據(jù)元素的概率相等，即Pi=1/n,則順序查找算法的平均查找長(zhǎng)度為：第八頁(yè)，共四十頁(yè)，編輯于2023年，星期三 8.2.2折半查找法1、折半查找定義折半查找法又稱二分查找法，這種方法對(duì)待查找的列表有兩個(gè)要求:⑴列表必須是順序存儲(chǔ)結(jié)構(gòu)⑵列表必須按關(guān)鍵字大小有序排列學(xué)號(hào)姓名平均成績(jī)其它0001

王一90.2…….0002張三70…………………………0032李四75.5……0034

劉四80.0…………………….…….0060錢(qián)五68…….第九頁(yè)，共四十頁(yè)，編輯于2023年，星期三2、基本過(guò)程

將表中間位置記錄的關(guān)鍵字與需要查找的關(guān)鍵字比較

如果兩者相等，則查找成功;

否則利用中間記錄將表分成前、后兩個(gè)子表;

如果列表中間位置記錄的關(guān)鍵字大于要查找關(guān)鍵字，則進(jìn)一步查找前一子表

否則進(jìn)一步查找后一子表。第十頁(yè)，共四十頁(yè)，編輯于2023年，星期三3、算法IntBinSrch(RecordListl,KeyTypek)//在有序表中折半查找其關(guān)鍵字等于k的元素，若找到，則函數(shù)返回值為該元素在表中的位置d{low=1;high=l.length;

//置區(qū)間初值While(low<=high){mid=(low+high)

if(k==l.r[mid].key)return(mid)

//找到待查元素elseif(k<l.r[mid].key)high=mid-1;elselow=mid+1;

}

return(0);}第十一頁(yè)，共四十頁(yè)，編輯于2023年，星期三4、性能分析

折半查找過(guò)程可用一二叉判定樹(shù)描述。二叉判定樹(shù)結(jié)構(gòu)：樹(shù)中每一結(jié)點(diǎn)對(duì)應(yīng)表中一記錄，結(jié)點(diǎn)值設(shè)為記錄在列表中的位置序號(hào)。61215182225283546586012345678101163124597810119第十二頁(yè)，共四十頁(yè)，編輯于2023年，星期三4、性能分析

從根到被查結(jié)點(diǎn)路徑關(guān)鍵字比較次數(shù)為被查結(jié)點(diǎn)層次數(shù)

假設(shè)表的長(zhǎng)度n=2h-1,則相應(yīng)判定樹(shù)必為深度是h的滿二叉樹(shù)，h=log2(n+1)

又假設(shè)每個(gè)記錄的查找概率相等，則折半查找成功時(shí)的平均查找長(zhǎng)度為

樹(shù)中層次為1的結(jié)點(diǎn)有1個(gè)，層次為2的結(jié)點(diǎn)有2個(gè)，層次為h的結(jié)點(diǎn)有2h-1個(gè)第十三頁(yè)，共四十頁(yè)，編輯于2023年，星期三5、二叉判定樹(shù)舉例(Apr,Aug,Dec,Feb,Jan,July,june,Mar,May,Nov,Oct,Sep)JulyDecAugAprFebJanMayJuneMarOctSepNov其在等概率(1/12)的情況下，查找成功的平均查找長(zhǎng)度：ASL＝（1+2*2+3*4+4*5)/12=3.1第十四頁(yè)，共四十頁(yè)，編輯于2023年，星期三算法優(yōu)點(diǎn)比較次數(shù)少查找速度快平均性能好算法缺點(diǎn)待查表為有序表插入、刪除困難第十五頁(yè)，共四十頁(yè)，編輯于2023年，星期三 8.2.3分塊查找法1、對(duì)所查表的要求⑴將列表分成若干塊（子表），一般情況下，塊的長(zhǎng)度均勻，最后一塊可不滿⑵每塊內(nèi)元素?zé)o序⑶塊與塊間有序1814122582832453658608871

0

1234567891011122558880510索引表第十六頁(yè)，共四十頁(yè)，編輯于2023年，星期三2、基本思想⑴構(gòu)造一索引表⑵將待查關(guān)鍵字K與索引表中的關(guān)鍵字進(jìn)行比較，以確定待查記錄所在的塊。⑶用順序查找法，在相應(yīng)塊內(nèi)查找關(guān)鍵字為K的元素第十七頁(yè)，共四十頁(yè)，編輯于2023年，星期三3、平均查找長(zhǎng)度

設(shè)查找索引表的平均查找長(zhǎng)度LB，相應(yīng)塊內(nèi)順序查找的平均查找長(zhǎng)度LW，則平均查找長(zhǎng)度：ASLbs=LB+Lw

假定將長(zhǎng)度為n的表分成b塊，每塊內(nèi)含s個(gè)元素，則b=n/s.

假定表中每個(gè)元素的查找概率相等，則每個(gè)索引項(xiàng)的查找概率為1/b,塊內(nèi)每個(gè)元素的查找概率為1/s,則有順序法平均查找長(zhǎng)度折半法平均查找長(zhǎng)度第十八頁(yè)，共四十頁(yè)，編輯于2023年，星期三查找方法比較順序查找折半查找分塊查找ASL最大最小兩者之間表結(jié)構(gòu)有序表，無(wú)序表有序表分塊有序表存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)，線性鏈表順序存儲(chǔ)結(jié)構(gòu)，順序存儲(chǔ)結(jié)構(gòu)，線性鏈表第十九頁(yè)，共四十頁(yè)，編輯于2023年，星期三課堂練習(xí)例1：折半查找有序表（4，6，10，12，20，30，50，70，88，100），若查找元素58，則它將依次與表中那些元素比較，查找結(jié)果失敗。例2：對(duì)于具有144個(gè)記錄的文件，若采用分塊查找，且每塊長(zhǎng)度為8,則平均查找長(zhǎng)度為多少？第二十頁(yè)，共四十頁(yè)，編輯于2023年，星期三二叉排序樹(shù)21平衡二叉排序樹(shù)B樹(shù)8.3基于樹(shù)的查找法第二十一頁(yè)，共四十頁(yè)，編輯于2023年，星期三 8.3.1二叉排序樹(shù)1、定義二叉排序樹(shù)或者是一棵空樹(shù)，或者是具有如下性質(zhì)的二叉樹(shù)：⑴若它的左子樹(shù)非空，則左子樹(shù)上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值⑵若它的右子樹(shù)非空，則右子樹(shù)上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值⑶它的左右子樹(shù)也分別為二叉排序樹(shù)503020104025238090858835是二叉排序樹(shù)66不21第二十二頁(yè)，共四十頁(yè)，編輯于2023年，星期三2、二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)取二叉鏈表作為二叉排序樹(shù)的存儲(chǔ)結(jié)構(gòu)TypedefstructBiTNode{

KeyTypeKey;structBiTnode*lchild,*rchild}BiTNode,*BSTree第二十三頁(yè)，共四十頁(yè)，編輯于2023年，星期三3、二叉排序樹(shù)的插入【算法思想】5030802090854035883250505030403550508090⑴若二叉樹(shù)是空，則新結(jié)點(diǎn)Ｓ是二叉樹(shù)的根⑵若二叉樹(shù)非空，則將S.key與二叉排序樹(shù)根結(jié)點(diǎn)的關(guān)鍵字進(jìn)行比較：a.若S.key的值等于根結(jié)點(diǎn)的值，則停止插入；b.若S.key的值小于根結(jié)點(diǎn)的值，則將Ｓ插入左子樹(shù)；c.若S.key的值大于根結(jié)點(diǎn)的值，則將Ｓ插入右子樹(shù)；20328588第二十四頁(yè)，共四十頁(yè)，編輯于2023年，星期三VoidInsertBST(BSTree*bst,KeyTypekey)//若在二叉排序樹(shù)中不存在關(guān)鍵字等于key的元素，插入該元素{Bitrees;If(*bst==NULL)

//遞歸結(jié)束條件

Elseif(key<(*bst)->key)

//將s插入左子樹(shù)Elseif(key>(*bst)->key)

//將s插入右子樹(shù)}s=(BSTree)malloc(sizeof(BSTNode))s->key=key;s->lchild=NULL;s->rchild=NULL;*bst=s;InsertBST(&((*bst)->lchild),key);InsertBST(&((*bst)->rchild),key);第二十五頁(yè)，共四十頁(yè)，編輯于2023年，星期三BSTNode*InsertBST(BSTreeroot,KeyTypekey)//若在二叉排序樹(shù)中不存在關(guān)鍵字等于key的元素，插入該元素if(root==NULL）s=(BSTree)malloc(sizeof(BSTNode))s->key=key;s->lchild=NULL;s->rchild=NULL;root=s;else{p=root;//建立新結(jié)點(diǎn)

r=(BSTree)malloc(sizeof(BSTNode));r->key=key;r->lchild=NULL;r>rchild=NULL;二叉排序樹(shù)插入的非遞歸算法第二十六頁(yè)，共四十頁(yè)，編輯于2023年，星期三if(q->key==key)return;

if(q->key>key)q->lchild=r;//插入r做q的左孩子else

q->rchild=r;//插入r做q的右孩子}returnroot;}while(p)//尋找新結(jié)點(diǎn)的插入位置

{q=p;if(p->key>key)p=p->lchild;elsep=p->rchild;}第二十七頁(yè)，共四十頁(yè)，編輯于2023年，星期三一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹(shù)而變成一個(gè)有序序列每次插入的新結(jié)點(diǎn)都是二叉排序樹(shù)上新的葉子結(jié)點(diǎn)插入時(shí)不必移動(dòng)其它結(jié)點(diǎn)，僅需修改某個(gè)結(jié)點(diǎn)的指針結(jié)論第二十八頁(yè)，共四十頁(yè)，編輯于2023年，星期三50308020908540358832例如:二叉排序樹(shù)查找關(guān)鍵字==50,505035,503040355090,50809095,第二十九頁(yè)，共四十頁(yè)，編輯于2023年，星期三4、二叉排序樹(shù)的查找算法若二叉排序樹(shù)為空，則查找不成功；否則⑴若給定值等于根結(jié)點(diǎn)的關(guān)鍵字，則查找成功；⑵若給定值小于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在左子樹(shù)上進(jìn)行查找；⑶若給定值大于根結(jié)點(diǎn)的關(guān)鍵字，則繼續(xù)在右子樹(shù)上進(jìn)行查找。第三十頁(yè)，共四十頁(yè)，編輯于2023年，星期三BSTreeSearchBST(BSTreebst,KeyTypekey){//在根結(jié)點(diǎn)bst所指的二叉排序樹(shù)中，遞歸查找關(guān)鍵字等于key的元素，若查找成功，返回指向該元素結(jié)點(diǎn)的指針，否則返回空指針if(!bst)Elseif(bst->key==key)Elseif(bst->key>key)elseReturnNULL

Returnbst//查找成功ReturnSearchBST(bst->lchild,key);//在左子樹(shù)中繼續(xù)查找ReturnSearchBST(bst->rchild,key);//在右子樹(shù)中繼續(xù)查找}第三十一頁(yè)，共四十頁(yè)，編輯于2023年，星期三BSTreeSearchBST(BSTreebst,KeyTypekey){//在根結(jié)點(diǎn)bst所指的二叉排序樹(shù)中，查找關(guān)鍵字等于key的元素，若查找成功，返回指向該元素結(jié)點(diǎn)的指針，否則返回空指針{BSTreeq;q=bst;While(q){if(q->key==key)returnq;if(q->key>key)q=q->lchild;elseq=q->rchild;}returnNULL;}第三十二頁(yè)，共四十頁(yè)，編輯于2023年，星期三BSTNode*DelBST(BSTreet,KeyTypek){//在二叉排序樹(shù)t中刪除關(guān)鍵字為K的結(jié)點(diǎn)BSTNode*p,*f,*s,*q;P=t;f=NULL;While(p){if(p->key==k)break;f=p;if(p->key>k)p=p->lchild;elsep=p->rchild;}If(p==NULL)returnt//若找不到，返回原二叉樹(shù)第三十三頁(yè)，共四十頁(yè)，編輯于2023年，星期三If(p->lchild==NULL){if(f==NULL)t=p->rchild;elseif(f->lchild==p)f->lchild=p->rchild;elsef->rchild=p->rchild;free(p);第三十四頁(yè)，共四十頁(yè)，編輯于2023年，星期三Else{q=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}if(q==p)q->lchild=s->lchild;elseq->rchild=s->lchild;p->key=s->key;free(s);}}//DelBST第三十五頁(yè)，共四十頁(yè)，編輯于2023年，星期三368.4計(jì)算式查找法－哈希法哈希表的相關(guān)定義哈希函數(shù)的構(gòu)造方法