算法與數(shù)據(jù)結(jié)構(gòu)課件查找

第7章查找7.1根本概念與術(shù)語(yǔ)7.2靜態(tài)查找表7.3動(dòng)態(tài)查找表7.4哈希表7.5典型例題17.1根本概念與術(shù)語(yǔ)—以圖書(shū)信息表為例書(shū)號(hào) 書(shū)名 作者 出版社 定價(jià)015010C程序設(shè)計(jì)譚浩強(qiáng)清華大學(xué)出版社 26.00 015024 數(shù)據(jù)結(jié)構(gòu)嚴(yán)蔚敏清華大學(xué)出版社22.00 015025 離散數(shù)學(xué)左孝凌上?？茖W(xué)技術(shù)文獻(xiàn)出版社14.00 015080計(jì)算機(jī)操作系統(tǒng)湯子瀛西安電子科技大學(xué)出版社24.00

關(guān)鍵碼：表中的每個(gè)數(shù)據(jù)元素有假設(shè)干屬性〔項(xiàng)〕，某個(gè)項(xiàng)或組合項(xiàng)的值就稱(chēng)為關(guān)鍵碼，它可以標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。主關(guān)鍵碼：能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵碼。其他的屬性那么稱(chēng)為次關(guān)鍵碼。查找結(jié)果唯一查找結(jié)果不唯一27.1根本概念與術(shù)語(yǔ)查找表用于查找的數(shù)據(jù)集合。具有同一類(lèi)型的數(shù)據(jù)元素〔或記錄〕組成的集合。對(duì)查找表進(jìn)行的操作查詢(xún)某個(gè)“特定的〞數(shù)據(jù)元素是否在查找表中；檢索某個(gè)“特定的〞數(shù)據(jù)元素的各種屬性；在查找表中插入一個(gè)數(shù)據(jù)元素；從查找表中刪去某個(gè)數(shù)據(jù)元素；根據(jù)操作的不同，查找表可分為：靜態(tài)查找表：僅對(duì)查找表進(jìn)行前兩種操作，不能被改變；動(dòng)態(tài)查找表：除進(jìn)行“查找〞操作外，可能還要向表中插入數(shù)據(jù)元素或刪除數(shù)據(jù)元素，可以被改變。3根本概念查找：根據(jù)給定的某個(gè)值，在查找表中確定一個(gè)其關(guān)鍵碼等于給定值的數(shù)據(jù)元素〔或記錄〕。查找成功：查找表中存在滿(mǎn)足條件的數(shù)據(jù)元素；查找結(jié)果為：整個(gè)記錄的信息，或指示該記錄在查找表中的位置；查找不成功：查找表中不存在滿(mǎn)足條件的數(shù)據(jù)元素；查找結(jié)果為：“空記錄〞或者“空指針〞。4平均查找長(zhǎng)度〔AverageSearchLength〕:與給定值進(jìn)行比較的關(guān)鍵碼個(gè)數(shù)的期望值衡量查找算法性能的主要依據(jù)對(duì)于長(zhǎng)度為n的查找表，查找成功時(shí)的平均查找長(zhǎng)度為：平均查找長(zhǎng)度()表中記錄的個(gè)數(shù)找到第i個(gè)記錄時(shí)，需要進(jìn)行的比較次數(shù)查找第i個(gè)記錄的概率5查找表中的元素是無(wú)序的，元素間不存在邏輯關(guān)系。為了查找的方便，需在數(shù)據(jù)元素間人為地加上一些關(guān)系，即以另一種數(shù)據(jù)結(jié)構(gòu)來(lái)表示查找表。組織查找表的方法靜態(tài)查找表〔線(xiàn)性表、索引結(jié)構(gòu)〕動(dòng)態(tài)查找表〔樹(shù)表〕哈希表〔散列表〕

6靜態(tài)查找表上的三種查找方法：

(1)順序查找

(2)折半查找

(3)分塊查找7.2靜態(tài)查找表77.2.1靜態(tài)查找表結(jié)構(gòu)以順序表作為存儲(chǔ)結(jié)構(gòu)#defineMaxSize100//表中最多記錄個(gè)數(shù)typedefstruct{ KeyTypekey; ∥關(guān)鍵碼字段…… ∥其他字段}ElemType;typedefstruct{ElemTypedata[MaxSize+1];intlength; }SqList;8從表的一端開(kāi)始，順序掃描線(xiàn)性表，依次將掃描到的關(guān)鍵碼與給定值kx相比較；假設(shè)相等，那么查找成功，給出數(shù)據(jù)元素在表中的位置；假設(shè)整個(gè)表檢測(cè)完，仍未找到與kx相等的關(guān)鍵碼，那么查找失敗，給出失敗信息。7.2.2順序查找intSeqSearch1(SqListL,KeyTypekx){i=1;while(i<=L.length&&L.data[i].key!=kx)i++;if(i<=L.length)returni;elsereturn0;}教材有誤9順序查找中使用監(jiān)測(cè)哨intSeqSearch2(SqListL，KeyTypekx){∥在順序表L中順序查找關(guān)鍵碼為kx的數(shù)據(jù)元素，成功那么∥返回其位置，失敗返回0，注：0號(hào)單元用作監(jiān)視哨 L.data[0].key=k；∥設(shè)置監(jiān)測(cè)哨 for(i=L.length；L.data[i].key!=kx；i--)； ∥從表尾向前查找 returni；}10關(guān)鍵碼之間的比較次數(shù)取決于所查記錄在表中的位置。假設(shè)查找表中第1個(gè)記錄，僅需比較一次；而查找表中最后一個(gè)記錄時(shí)，需比較n次。查找成功時(shí)，順序查找的平均查找長(zhǎng)度為：思考：不成功時(shí)的平均查找長(zhǎng)度是多少？順序查找的平均查找長(zhǎng)度=11順序查找總結(jié)優(yōu)點(diǎn)：算法簡(jiǎn)單且適用面廣。對(duì)表的結(jié)構(gòu)無(wú)任何要求，無(wú)論記錄是否按關(guān)鍵字有序均可應(yīng)用，而且上述所有討論對(duì)線(xiàn)性鏈表也同樣適用。缺點(diǎn):平均查找長(zhǎng)度較大，特別是當(dāng)n很大時(shí)，查找效率低。

12又稱(chēng)為二分查找，要求線(xiàn)性表中的數(shù)據(jù)元素按關(guān)鍵碼升序或降序排列。思想：取中間位置的元素作為比較對(duì)象；假設(shè)給定值與中間位置元素的關(guān)鍵碼相等，那么查找成功；假設(shè)給定值小于中間元素的關(guān)鍵碼，那么在左半?yún)^(qū)繼續(xù)查找；假設(shè)給定值大于中間元素的關(guān)鍵碼，那么在右半?yún)^(qū)繼續(xù)查找；不斷重復(fù)上述查找過(guò)程，直到查找成功，或所查找的區(qū)域無(wú)數(shù)據(jù)元素，查找失?。?.2.3有序表的折半查找13例如:key=64的查找過(guò)程lowhighmidlow

mid

high

midlow指示查找區(qū)間的下界;high指示查找區(qū)間的上界;mid=(low+high)/214查找關(guān)鍵碼為18的數(shù)據(jù)元素031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhigh031015192528405583↑↑↑lowmidhighhighlow15intBinary_Search(SqListL，KeyTypekx){/*在表L中查找關(guān)鍵碼為kx的數(shù)據(jù)元素，假設(shè)找到返回該元素在表中的位置，否那么，返回0*/ intmid,low,high； low=1；high=L.length；/*①設(shè)置初始區(qū)間*/ while(low<=high)/*②表空測(cè)試*/ {/*非空，進(jìn)行比較測(cè)試*/ mid=(low+high)/2；/*③得到中點(diǎn)*/ if(kx==L.data[mid].key) return(mid)；/*查找成功*/ if(kx<L.data[mid].key)high=mid-1；/*調(diào)整到左半?yún)^(qū)*/ elselow=mid+1；/*調(diào)整到右半?yún)^(qū)*/ } return0;}折半查找的算法16折半查找的遞歸算法intSearchBin2(RecTyper[n+1],KeyTypek,intlow,inthigh){∥在有序表r[1..n]中遞歸折半查找關(guān)鍵字為k的結(jié)點(diǎn)，成功那么返回∥數(shù)據(jù)元素的位置，失敗返回0if(low>high)return0;mid=(low+high)/2;if(k==r[mid].key)returnmid;∥找到待查元素elseif(k>r[mid].key)returnSearchBin2(r,k,mid+1,high);∥繼續(xù)在后半?yún)^(qū)間查找elsereturnSearchBin2(r,k,low,mid-1);∥繼續(xù)在前半?yún)^(qū)間查找}∥SearchBin217折半查找過(guò)程可用二叉樹(shù)來(lái)描述：把當(dāng)前查找區(qū)間的中間位置上的記錄作為根；左子表和右子表中的記錄分別作為根的左子樹(shù)和右子樹(shù)。9個(gè)結(jié)點(diǎn)的判定樹(shù)判定樹(shù)〔比較樹(shù)〕52713684918帶外部結(jié)點(diǎn)的判定樹(shù)527136849-11-22-35-66-77-83-44-58-99-19對(duì)于給定11個(gè)數(shù)據(jù)元素的有序表{2,3,10,15,20,25,28,29,30,35,40}，采用折半查找，試問(wèn)：(1)假設(shè)查找給定值為20的元素，將依次與表中哪些元素比較？(2)假設(shè)查找給定值為26的元素，將依次與哪些元素比較？(3)假設(shè)查找表中每個(gè)元素的概率相同，求查找成功時(shí)的平均查找長(zhǎng)度和查找不成功時(shí)的平均查找長(zhǎng)度。舉例20(2)假設(shè)查找給定值為26的元素,依次與25,30,28元素比較,共比較3次。(3)在查找成功時(shí),會(huì)找到圖中某個(gè)圓形結(jié)點(diǎn),那么成功時(shí)的平均查找長(zhǎng)度：(1)假設(shè)查找給定值為20的元素,依次與表中25,10,15,20元素比較,共比較4次。在查找不成功時(shí),會(huì)找到圖中某個(gè)方形結(jié)點(diǎn),那么不成功時(shí)的平均查找長(zhǎng)度：21折半查找總結(jié)優(yōu)點(diǎn)：效率比順序查找高比較次數(shù)少，查找速度快，平均性能好缺點(diǎn)：要求查找表有序僅限于順序存儲(chǔ)結(jié)構(gòu)22237.2.4分塊查找又稱(chēng)索引順序查找，是對(duì)順序查找的改進(jìn)。將順序表分成假設(shè)干個(gè)子表B1、B2、…、Bn，并要求當(dāng)i<j時(shí)，Bi中記錄的關(guān)鍵碼都小于Bj中記錄的關(guān)鍵碼。記錄的這種排列方式稱(chēng)為分塊有序。分塊之后，另建一個(gè)線(xiàn)性表，稱(chēng)為索引表。每個(gè)子表在索引表中有一項(xiàng)，稱(chēng)為索引項(xiàng)。索引項(xiàng)中包括兩個(gè)域，一個(gè)域存放子表中的最大關(guān)鍵碼，另一個(gè)域存放子表的第一個(gè)記錄在線(xiàn)性表中的位置。最大關(guān)鍵字255689起始地址1611

10525201856342932476872618489索引表24分塊查找例如索引表最大關(guān)鍵字255689起始地址1611

10525201856342932476872618489步驟①確定待查記錄所在的子表：用給定值kx在索引表中檢測(cè)索引項(xiàng)，依次與索引表中的關(guān)鍵碼進(jìn)行比較?？捎庙樞虿檎曳ɑ蛘郯氩檎曳ㄟM(jìn)行。②在相應(yīng)子表內(nèi)進(jìn)行順序查找，查找關(guān)鍵碼為kx的記錄。25分塊查找性能分析平均查找長(zhǎng)度假設(shè)用順序查找確定所在的塊：假設(shè)用折半查找確定所在的塊：平均查找長(zhǎng)度不僅和表的總長(zhǎng)度有關(guān)，而且和所分的子表的個(gè)數(shù)有關(guān)。26靜態(tài)查找表總結(jié)順序查找適用于任何線(xiàn)性表，但效率較低；分塊查找不需要對(duì)全部的數(shù)據(jù)元素排序，它的插入刪除在塊內(nèi)進(jìn)行，由于不要求有序，操作比較容易，其主要代價(jià)是增加一個(gè)輔助數(shù)組的存儲(chǔ)空間和將初始順序表分塊排序的操作；折半查找效率最高，但要求查找表有序且順序存儲(chǔ)，故插入刪除時(shí)必須移動(dòng)元素，這種由移動(dòng)元素引起的額外時(shí)間開(kāi)銷(xiāo)，就會(huì)抵消折半查找的優(yōu)點(diǎn)。也就是說(shuō)，折半查找只適用于靜態(tài)查找表。假設(shè)要對(duì)動(dòng)態(tài)查找表進(jìn)行高效率的查找，可采用下面介紹的幾種特殊的二叉樹(shù)或樹(shù)作為表的組織形式。27二叉排序樹(shù)：或者是一棵空樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù)：假設(shè)左子樹(shù)不空，那么左子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵碼值均小于根結(jié)點(diǎn)的關(guān)鍵碼值；假設(shè)右子樹(shù)不空，那么右子樹(shù)上所有結(jié)點(diǎn)的關(guān)鍵碼值均大于根結(jié)點(diǎn)的關(guān)鍵碼值；左、右子樹(shù)也都是二叉排序樹(shù)。7.3動(dòng)態(tài)查找表30125332394187189中序遍歷序列為：3，12，18，23，30，53，71，89，9428二叉排序樹(shù)的查找過(guò)程假設(shè)二叉排序樹(shù)為空，那么查找失敗；否那么：1〕假設(shè)給定值等于根結(jié)點(diǎn)的關(guān)鍵碼值，查找成功；2〕假設(shè)給定值小于根結(jié)點(diǎn)的關(guān)鍵碼值，那么繼續(xù)在左子樹(shù)上進(jìn)行查找；3〕假設(shè)給定值大于根結(jié)點(diǎn)的關(guān)鍵碼值，那么繼續(xù)在右子樹(shù)上進(jìn)行查找；2950308020908540358832查找關(guān)鍵字50,505035,503040355090,5080909530用二叉鏈表存儲(chǔ)二叉排序樹(shù)typedefstructBiTNode{ElemTypedata;∥數(shù)據(jù)元素structBiTNode*lchild,*rchild;

∥左、右孩子指針}BiTNode,*BiTree;

31二叉排序樹(shù)非遞歸查找算法BSTreeSearchBST2(BSTreet,KeyTypek){//在根指針t所指二叉排序樹(shù)中非遞歸查找某關(guān)鍵字//等于k的數(shù)據(jù)元素，假設(shè)查找成功，那么返回指向//該數(shù)據(jù)元素結(jié)點(diǎn)的指針，否那么返回空指針p=t;while(p!=NULL&&p->key!=k){if(k<p->key)p=p->lchild;elsep=p->rchild;}returnp;}//SearchBST232intsearchBST(BiTreeT,KeyTypekx,BiTree*p,BiTree*q){/*在二叉排序樹(shù)T上查找關(guān)鍵碼為kx的元素，假設(shè)找到，返回1，且p指向該結(jié)點(diǎn)，q指向其父結(jié)點(diǎn)；否那么，返回0，且q指向查找失敗的最后一個(gè)結(jié)點(diǎn)*/ *p=T; while(*p) /*從根結(jié)點(diǎn)開(kāi)始查找*/ { if((*p)->data.key==kx) return1; else if((*p)->data.key>kx)/*kx大于當(dāng)前結(jié)點(diǎn)*q的元素關(guān)鍵碼*/ {*q=*p;*p=(*p)->lchild;}/*將當(dāng)前結(jié)點(diǎn)*q的右子女置為新根*/ else {*q=*p;*p=(*p)->rchild;}/*將當(dāng)前結(jié)點(diǎn)*q的左子女置為新根*/ } return0;}33intsearchBST_rc(BiTreeT,KeyTypekx,BiTree*p,BiTree*q){/*在二叉排序樹(shù)T上查找關(guān)鍵碼為kx的元素，假設(shè)找到，返回1；且p指向該結(jié)點(diǎn)，q指向其父結(jié)點(diǎn)，否那么，返回0，且q指向查找失敗的最后一個(gè)結(jié)點(diǎn)*/if(!T)return0;elseif(kx==T->data.key){p=T;return1;}elseif(kx<T->data.key)searchBST_rc(T->lchild,kx,p,&T);elsesearchBST_rc(T->rchild,kx,p,&T);}二叉排序樹(shù)遞歸查找算法34二叉排序樹(shù)的查找分析123456425136二叉排序樹(shù)的平均查找長(zhǎng)度是O()

最好情況：二叉排序樹(shù)的形態(tài)和折半查找的判定樹(shù)相同最壞情況：二叉排序樹(shù)為單支樹(shù)，和順序查找相同35二叉排序樹(shù)的插入步驟：〔1〕假設(shè)二叉排序樹(shù)是空樹(shù)，那么k成為二叉排序樹(shù)的根；〔2〕假設(shè)二叉排序樹(shù)非空，那么將k與二叉排序樹(shù)的根進(jìn)行比較，如果k的值等于根結(jié)點(diǎn)的值，那么停止插入；如果k的值小于根結(jié)點(diǎn)的值，那么將k插入左子樹(shù)；如果k的值大于根結(jié)點(diǎn)的值，那么將k插入右子樹(shù)。36二叉排序樹(shù)的插入351545504025102030插入新結(jié)點(diǎn)2828插入新結(jié)點(diǎn)4242插入在查找的根底上進(jìn)行；每次結(jié)點(diǎn)的插入，都要從根結(jié)點(diǎn)出發(fā)搜索插入位置，然后把新結(jié)點(diǎn)作為葉子結(jié)點(diǎn)插入。37二叉排序樹(shù)的插入算法voidinsertBST(BiTree*T,KeyTypekx){/*在二叉排序樹(shù)*T上插入關(guān)鍵碼為kx的結(jié)點(diǎn)*/BiTreep,q,s; p=q=NULL;if(!searchBST(*T,kx,&p,&q));//插入在查找不成功時(shí)進(jìn)行{s=(BiTree)malloc(sizeof(BiTNode));/*申請(qǐng)結(jié)點(diǎn)，并賦值*/s->data.key=kx;s->lchild=NULL;s->rchild=NULL;if(!*T)*T=s; /*向空樹(shù)中插入時(shí)*/else{if(q->data.key>kx)q->lchild=s;/*插入結(jié)點(diǎn)為q的左孩子*/elseq->rchild=s; /*插入結(jié)點(diǎn)為q的左孩子*/}}}3839從空二叉樹(shù)開(kāi)始，每讀入一個(gè)元素，就建立一個(gè)新的結(jié)點(diǎn)，調(diào)用插入算法將它插入到當(dāng)前已生成的二叉排序樹(shù)中。二叉排序樹(shù)的創(chuàng)立123532264520(g)(b)32(c)3226(d)322645(a)?32264535(e)3226451235(f)序列:32,26,45,35,12,20,1240一組關(guān)鍵字為{25,18,46,2,53,39,32,4,74,67,60,11}。按表中的元素順序依次插入到一棵初始為空的二叉排序樹(shù)中,畫(huà)出該二叉排序樹(shù),并求在等概率的情況下查找成功的平均查找長(zhǎng)度。解：生成的二叉排序樹(shù)如右圖所示。舉例41void

CreateBST(BiTree

*T)/*從鍵盤(pán)輸入元素的值，創(chuàng)立相應(yīng)的二叉排序樹(shù)*/{KeyTypekx;

*T=NULL;

scanf("%d",&kx);

while(kx!=ENDKEY)

/*EDNKEY為自定義常量*/

{

insertBST(T,kx);

scanf("%d",&kx);

}}二叉排序樹(shù)的創(chuàng)立算法〔略〕42平衡二叉樹(shù)〔AVL樹(shù)〕形態(tài)勻稱(chēng)的二叉排序樹(shù)，使平均查找長(zhǎng)度接近最小平衡因子：結(jié)點(diǎn)的左、右子樹(shù)深度之差平衡二叉樹(shù)：或者是一棵空二叉樹(shù)，或者是具有以下性質(zhì)的二叉樹(shù)：二叉樹(shù)中任一結(jié)點(diǎn)的平衡因子的絕對(duì)值不超過(guò)1即平衡二叉樹(shù)中每個(gè)結(jié)點(diǎn)的平衡因子只能取-1，0，101-1001-11010043不平衡的二叉樹(shù)例如210-1001-20100044構(gòu)造平衡二叉樹(shù)插入一個(gè)結(jié)點(diǎn)時(shí)，首先檢查是否破壞了樹(shù)的平衡性，如果因插入結(jié)點(diǎn)破壞了二叉排序樹(shù)的平衡，那么找出其中的最小不平衡子樹(shù)。最小不平衡子樹(shù)離插入結(jié)點(diǎn)最近，且平衡因子的絕對(duì)值大于1的祖先結(jié)點(diǎn)，因?yàn)榇私Y(jié)點(diǎn)失去平衡，使得該結(jié)點(diǎn)的祖先結(jié)點(diǎn)也可能隨之失去平衡。所以，失衡后應(yīng)該調(diào)整以該結(jié)點(diǎn)為根的子樹(shù)。45方法：在插入過(guò)程中，采用平衡旋轉(zhuǎn)技術(shù)例如:依次插入的關(guān)鍵字為5,4,2,8,6,95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)構(gòu)造平衡二叉樹(shù)LLRL46426589426895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字9RR構(gòu)造平衡二叉樹(shù)47總結(jié)以上討論的各種查找表的共同特點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)位置和它的關(guān)鍵碼之間不存在確定的關(guān)系，查找時(shí)需要進(jìn)行一系列對(duì)關(guān)鍵碼的比較；查找算法建立在比較的根底上，平均查找長(zhǎng)度不為零對(duì)于頻繁使用的查找表，希望ASL=0只有一個(gè)方法：預(yù)先知道所查關(guān)鍵碼在表中的位置即要求：數(shù)據(jù)元素的存儲(chǔ)位置和其關(guān)鍵碼之間存在一種確定的關(guān)系。487.4.1哈希表與哈希方法哈希表(HashTable)又稱(chēng)散列表，是除順序存儲(chǔ)結(jié)構(gòu)、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和索引存儲(chǔ)結(jié)構(gòu)之外的又一種存儲(chǔ)線(xiàn)性表的存儲(chǔ)結(jié)構(gòu)。哈希函數(shù)：將關(guān)鍵碼值轉(zhuǎn)換成存儲(chǔ)位置的函數(shù)，又稱(chēng)散列函數(shù)。addr(Ri)＝H(key)哈希表：根據(jù)哈希函數(shù)建立的表；其根本思想是：以記錄的關(guān)鍵碼值為自變量，根據(jù)哈希函數(shù)，計(jì)算出對(duì)應(yīng)的哈希地址，并在此存儲(chǔ)該記錄的內(nèi)容。當(dāng)對(duì)記錄進(jìn)行查找時(shí)，再根據(jù)給定的關(guān)鍵碼值，用同一個(gè)哈希函數(shù)計(jì)算出給定關(guān)鍵碼值對(duì)應(yīng)的存儲(chǔ)地址，隨后進(jìn)行訪問(wèn)。哈希表即是一種存儲(chǔ)形式，又是一種查找方法，通常將這種查找方法稱(chēng)為哈希查找。7.4哈希表49對(duì)于兩個(gè)關(guān)鍵字ki和kj(i≠j),有ki≠kj(i≠j),但H(ki)=H(kj)。這種現(xiàn)象稱(chēng)為哈希沖突。沖突：不同的關(guān)鍵碼映射到了同一個(gè)地址上的現(xiàn)象。同義詞：映射到同一哈希地址上的關(guān)鍵碼。同義詞沖突是很難防止的。哈希方法需要解決兩個(gè)問(wèn)題：如何構(gòu)造哈希函數(shù)？如何處理沖突？沖突的概念50好的哈希函數(shù)函數(shù)本身要便于計(jì)算，盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度；對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)大致均勻分布，以盡可能減少?zèng)_突常用的哈希函數(shù)的構(gòu)造方法有：直接定址法除留余數(shù)法數(shù)字分析法平方取中法折疊法7.4.2常用的哈希函數(shù)構(gòu)造方法511、直接定址法取關(guān)鍵碼的某個(gè)線(xiàn)性函數(shù)值為哈希地址。即

H(key)=a*key+b

其中a，b為常數(shù)，調(diào)整a與b的值可以使哈希地址取值范圍與存儲(chǔ)空間范圍一致。【舉例】解放后每年出生人口的調(diào)查表。H(key)=key+(-1949)地址01…51年份19491950…2000人數(shù)…………522、除留余數(shù)法取關(guān)鍵碼除以p的余數(shù)作為哈希地址：h(key)=keymodp通常p取小于等于哈希表長(zhǎng)的最大素?cái)?shù)。如表長(zhǎng)為12，那么p可取11，假設(shè)關(guān)鍵字為22，18，9，35，那么對(duì)應(yīng)哈希地址為0，7，9，2。533、數(shù)字分析法抽取關(guān)鍵字中某幾位隨機(jī)性較好的數(shù)位，然后把這些數(shù)位拼接起來(lái)作為哈希地址。所抽取的位數(shù)取決于哈希表的表長(zhǎng)。有如下關(guān)鍵字：〔設(shè)哈希表長(zhǎng)度為100〕8046532680722426808136578013655780587657可取關(guān)鍵字的3、4位〔5、6位〕或4位+6位的值作為哈希地址。544、平方取中法取關(guān)鍵字平方后的中間幾位為哈希地址。由于平方后的中間幾位數(shù)與原關(guān)鍵字的每一位數(shù)字都相關(guān)，只要原關(guān)鍵字的分布是隨機(jī)的，以平方后的中間幾位數(shù)作為哈希地址一定也是隨機(jī)分布?！蚕吕O(shè)哈希表長(zhǎng)為512=29〕標(biāo)識(shí)符關(guān)鍵字(關(guān)鍵字)2哈希地址A01000010000010I11001210000210J12001440000440I011601370400370P120614310541310P220624314704314555、折疊法折疊法是將較長(zhǎng)的關(guān)鍵字從左到右分割成位數(shù)相同的幾段(最后一段的位數(shù)可以少一些)，然后把這幾段疊加并舍去進(jìn)位，得到的結(jié)果作為哈希地址。有兩種疊加的方法：移位疊加和間界疊加。例如：關(guān)鍵字從左到右按3個(gè)位數(shù)一段分割，共得到5個(gè)段。12320324111220699+移位疊加：12330224121120897+間界疊加：567.4.3處理沖突的方法解決沖突的實(shí)際含義是：為產(chǎn)生沖突的關(guān)鍵字尋找下一個(gè)哈希地址解決方法開(kāi)放定址法拉鏈法〔鏈地址法〕兩種方法的區(qū)別是：發(fā)生沖突的元素是存儲(chǔ)在相同數(shù)組空間的另外一個(gè)地址里〔閉散列〕還是數(shù)組空間之外〔開(kāi)散列〕的其他空間571.開(kāi)放定址法根本思想：把所有的元素存儲(chǔ)在哈希表數(shù)組中每個(gè)元素經(jīng)哈希函數(shù)計(jì)算出來(lái)的地址稱(chēng)為基地址。如果要插入一個(gè)元素x，而x的基地址已被某個(gè)同義詞占用，那么根據(jù)某種策略將x存儲(chǔ)在數(shù)組的另一個(gè)位置。探測(cè)：沖突發(fā)生時(shí)，在沖突位置的附近尋找可存放記錄的“下一個(gè)〞空位置的過(guò)程Hi＝(H(key)+di)％mi=1,2,…,k(k≤m-1)線(xiàn)性探測(cè)法、二次探測(cè)法、雙哈希函數(shù)探測(cè)法58線(xiàn)性探測(cè)法根本思想：當(dāng)發(fā)生沖突時(shí)，從沖突位置的下一個(gè)單元順序?qū)ふ铱纱娣庞涗浀目諉卧?，只要找到一個(gè)空位，就把元素放入此空位中。順序查找時(shí)，我們把哈希表看成一個(gè)循環(huán)表，即如果到最后一個(gè)位置也沒(méi)有找到空單元，那么回到表頭開(kāi)始繼續(xù)查找。此時(shí)，如果仍然未找到空位，那么說(shuō)明哈希表已滿(mǎn)，需要進(jìn)行溢出處理。di的取值為：1，2，3，…，m-159關(guān)鍵字集合

{19,01,23,14,55,68,11,82,36}設(shè)定哈希函數(shù)H(key)=keyMOD11(表長(zhǎng)=11)190123145568假設(shè)采用線(xiàn)性探測(cè)法處理沖突118236112136251012345678910線(xiàn)性探測(cè)法例如ASLsucc＝〔1＋1+2+1＋3+6+2+5+1〕/9=22/9ASLunsucc＝〔10＋9+8+7+6+5+4+3+2+1+1〕/11=56/11600123456

198268

1436

01

ASLsucc

=(6×1+2×2+3)/9=13/9{19,01,23,14,55,68,11,82,36}表長(zhǎng)為7，H(key)=keyMOD7所有哈希地址相同的記錄鏈接在同一鏈表中

23

11

552.拉鏈法〔鏈地址法〕ASLunsucc＝〔2＋3+2+1+2+4+2〕/7=16/761散列表的查找及分