《數(shù)據(jù)結(jié)構(gòu)查找》PPT課件.ppt

《《數(shù)據(jù)結(jié)構(gòu)查找》PPT課件.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《《數(shù)據(jù)結(jié)構(gòu)查找》PPT課件.ppt（59頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第八章 查找,81 查找的基本概念 82 順序表查找 83 索引查找 84 樹(shù)表查找 85 散列表查找,8查找的基本概念,1查找表 查找表（Search Table）是由記錄序列組成的文件或線性表。 2查找表上常見(jiàn)的操作 （1）查詢某個(gè)“特定的”記錄是否在查找表中；（2）檢索某個(gè)“特定的”記錄的信息；（3）在查找表中插入記錄；（4）在查找表中刪除記錄。根據(jù)在查找表上實(shí)施的操作不同，可將查找表分為。 3靜態(tài)查找表和動(dòng)態(tài)查找表 靜態(tài)查找表只做前兩項(xiàng)統(tǒng)稱為“查找”的操作，在查找的過(guò)程中不再動(dòng)態(tài)地改變查找表，即不做插入和刪除記錄的操作；動(dòng)態(tài)查找表的表結(jié)構(gòu)本身是在查找過(guò)程中動(dòng)態(tài)生成的，即在查找過(guò)程中同時(shí)

2、插入查找表中不存在的記錄，或者從表中刪除已經(jīng)存在的某個(gè)記錄。,4查找依據(jù)：一般是把記錄的關(guān)鍵字作為查找的依據(jù) 5查找（Search）的定義：給定某個(gè)特定值k，在查找表中找出關(guān)鍵字等于給定值k的記錄，若找到，則查找成功，返回該記錄在表中的序號(hào)；否則查找不成功，給出查找失敗的信息。 6評(píng)價(jià)查找算法的效率 平均查找長(zhǎng)度ASL（Average Search Length），其計(jì)算公式為： 其中，n是記錄的個(gè)數(shù)；Ci是找到第i個(gè)記錄需要進(jìn)行的比較次數(shù)；Pi是查找第i個(gè)記錄的概率，這里P1=P2=Pi=Pn=1/n。 7查找表常用的存儲(chǔ)方式：順序、鏈接、索引和散列四種來(lái)存儲(chǔ)。本章共介紹了四類查找方法，即順

3、序表查找、索引查找、樹(shù)表查找、散列表查找。,82順序表查找,順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ)的查找表，就是順序表。 順序表的存儲(chǔ)結(jié)構(gòu)用C語(yǔ)言描述如下： #define N 100 typedef struct KeyType key; DataType other; RecType ; RecType RN+1; N是記錄的個(gè)數(shù)；R0閑置的主要原因?yàn)椋?（1）使下標(biāo)和記錄序號(hào)對(duì)應(yīng)； （2）留作他用，比如用作監(jiān)視哨。 基于順序表的查找兩種方法：順序查找和二分查找,821順序查找,順序查找（Sequential Search）又稱線性查找，是最簡(jiǎn)單、最基本的查找方法。 順序查找的基本思想是：從表的一端開(kāi)始，依次將

4、每個(gè)記錄的關(guān)鍵字與給定值k進(jìn)行比較，若某個(gè)記錄的關(guān)鍵字與k相等，表明查找成功，并給出記錄在表中的位置（序號(hào)）；若整個(gè)表檢測(cè)完，仍未找到與k相等的關(guān)鍵字，表明查找失敗，給出查找失敗的信息。,順序查找算法的C函數(shù)如下 ：,int seqSearch(RecType R , KeyType k) /*在數(shù)組R中順序查找關(guān)鍵字等于k的記錄，若找到返回記錄序號(hào)，否則返回0*/ int i； R0.key = k; /*R0用作監(jiān)視哨*/ i=N; /*從表的尾端向前查找 */ while（Ri.key!=k） i-； return i； ,順序查找算法的性能分析,平均查找長(zhǎng)度 查找成功時(shí)，平均查找長(zhǎng)度為

5、： 查找不成功時(shí)，與關(guān)鍵字的比較次數(shù)總是n+1次。 查找算法的平均時(shí)間復(fù)雜度O(n)。 優(yōu)缺點(diǎn) 優(yōu)點(diǎn)是算法簡(jiǎn)單，可以方便地插入記錄。 缺點(diǎn)是當(dāng)n很大時(shí)，平均查找長(zhǎng)度較大，查找效率較低。 順序查找方法不僅適用于順序表，也同樣適合于單鏈表。,822 二分查找,二分查找（Binary Search）又稱折半查找，是一種效率較高的查找方法。二分查找要求順序表是有序表 二分查找的基本思想是：初始時(shí)，查找區(qū)間為整個(gè)有序表，取查找區(qū)間的中間記錄作為比較對(duì)象，若中間記錄的關(guān)鍵字與給定值相等，則查找成功；若給定值小于中間記錄的關(guān)鍵字，則在中間記錄的前半?yún)^(qū)繼續(xù)查找；若給定值大于中間記錄的關(guān)鍵字，則在中間記錄的后半

6、區(qū)繼續(xù)查找。不斷重復(fù)上述查找過(guò)程，直至新區(qū)間中間記錄的關(guān)鍵字等于給定值，則查找成功，或者查找區(qū)間不斷縮小直到為空，表明查找失敗。,二分查找的具體查找步驟為： （1）設(shè)變量low和high表示查找區(qū)間的起始和終端下標(biāo)，初始時(shí)查找區(qū)間是R1RN，low取值為1，high取值為N。設(shè)變量mid表示查找區(qū)間中間位置的下標(biāo)，計(jì)算公式：mid= (low+hign)/2 （2）當(dāng)lowhigh（查找區(qū)間非空）時(shí)，求mid= (low+hign)/2，進(jìn)行如下比較： 若k=Rmid.key，查找成功，返回記錄在表中位置 若kRmid.key，則low=mid+1，在后半?yún)^(qū)繼續(xù)查找 （3）當(dāng)lowhigh時(shí)，

7、查找區(qū)間為空，說(shuō)明查找失敗,例8.一個(gè)有序表中有13個(gè)記錄，記錄的關(guān)鍵字序列為（7，14，18，21，23，29，31，35，38，42，46，49，52），給定值k分別為14和22，在表中查找關(guān)鍵字與k相等的記錄。, low=1 high=13 mid=7 low=1 high=6 kRmid，調(diào)整到后半?yún)^(qū)：low=mid+1 mid=2 k=Rmid，查找成功，返回找到的記錄序號(hào)2 查找k=14的過(guò)程示意圖,0 1 2 3 4 5 6 7 8 9 10 11 12 13, low=1 high=13 mid=7 low=1 high=6 kRmid，low=mid+1 mid=5 low=

8、high=4 kRmid，low=mid+1 lowhigh 查找區(qū)間為空，查找失敗。 查找k=22的過(guò)程示意圖,0 1 2 3 4 5 6 7 8 9 10 11 12 13,二分查找非遞歸算法的C函數(shù)： int binarySearch(RecType R , KeyType k) /*用二分查找法在數(shù)組R中查找關(guān)鍵字為k的記錄，若找到返回該記錄的位置，否則返回0。*/ int low, hign, mid; low=1; high=N; /*設(shè)置初始查找區(qū)間*/ while(low=high) /*查找區(qū)間非空*/ mid=(low+high)/2; /*計(jì)算查找區(qū)間中間位置的下標(biāo)*/

9、if(k=Rmid.key) return mid; /*查找成功，返回記錄的位置*/ else if(kRmid.key) high=mid-1; /*調(diào)整到前半?yún)^(qū)*/ else low=mid+1; /*調(diào)整到后半?yún)^(qū)*/ return 0; ,二分查找過(guò)程判定樹(shù),例8.1的二分查找過(guò)程對(duì)應(yīng)的判定樹(shù),查找成功情況下的平均查找長(zhǎng)度為： ASL=（1+22+34+46）/13=36/13。,查找不成功情況下的判定樹(shù),查找不成功時(shí)的平均查找長(zhǎng)度ASL為： ASL不成功=（32+412）/14=54/14。,二分查找性能分析,二分查找的平均查找長(zhǎng)度 以樹(shù)高為k的滿二叉樹(shù)為例，樹(shù)中共有n=2k-1個(gè)結(jié)

10、點(diǎn)，第i層有2i-1個(gè)結(jié)點(diǎn)，則二分查找的平均查找長(zhǎng)度為： 二分查找算法的平均時(shí)間復(fù)雜度為O(log2n),二分查找的特點(diǎn) 優(yōu)點(diǎn)：比較次數(shù)相對(duì)較少，查找效率較高。 缺點(diǎn)：在查找之前需要建立有序表，二分查找要求順序存儲(chǔ)有序表，因而在表中插入或刪除記錄都需要移動(dòng)大量的記錄， 二分查找方法適合于數(shù)據(jù)相對(duì)穩(wěn)定的靜態(tài)查找表。 二分查找只適合順序存儲(chǔ)結(jié)構(gòu)，而不適合鏈接存儲(chǔ)結(jié)構(gòu)。,83 索引查找,索引查找是建立在索引存儲(chǔ)結(jié)構(gòu)上的查找方法。 例如在英文字典里查找某個(gè)單詞的過(guò)程就是一個(gè)索引查找。把字典看作是索引查找的對(duì)象，其中，字典的正文是主要部分，稱作是主表，字母索引表是為了方便查找而建立的索引，稱作是索引表。

11、,831 索引表的組織,索引存儲(chǔ)的基本思想是：除了存儲(chǔ)主表的記錄外，還要為主表建立一個(gè)或若干個(gè)附加的索引表。索引表用來(lái)標(biāo)識(shí)主表記錄的存儲(chǔ)位置，它由若干個(gè)被稱為索引項(xiàng)的數(shù)據(jù)元素組成。 索引項(xiàng)的一般形式為（索引關(guān)鍵字，地址），索引關(guān)鍵字是記錄的某個(gè)數(shù)據(jù)項(xiàng)，一般會(huì)是記錄的關(guān)鍵字，地址是用來(lái)標(biāo)識(shí)一個(gè)或一組記錄的存儲(chǔ)位置。 若一個(gè)記錄對(duì)應(yīng)一個(gè)索引項(xiàng)，則該索引表為稠密索引（Dense Index）。若一組記錄對(duì)應(yīng)一個(gè)索引項(xiàng)，則該索引表為稀疏索引（Sparse Index）。,例8.2 為表8.1所示的通訊錄建立索引表。,（1）稠密索引： 稠密索引為每個(gè)記錄建立索引項(xiàng)（索引關(guān)鍵字，地址） 主表：0 1 2

12、3 4 5 6 7 8 9 索引表：,1）稀疏索引：把主表的記錄按照某種規(guī)則劃分為幾個(gè)子表，然后再為每個(gè)子表建立索引項(xiàng)（索引關(guān)鍵字，地址） 按照所在院系劃分，可以有4個(gè)子表，分別為：法學(xué)院LA1=（1001，1002，1003），理學(xué)院LA2=（1004，1005），外語(yǔ)學(xué)院LA3=（1006，1007，1008），藝術(shù)學(xué)院LA4=（1009，1010）。 索引表： 這種按照主表的非關(guān)鍵字建立的索引表稱為輔助索引表。,832 分塊查找,分塊查找（Block Search）又稱索引順序查找，是對(duì)順序查找方法的一種改進(jìn)。 分塊查找要求對(duì)順序存儲(chǔ)的主表建立索引： （1）主表“分塊”有序：將主表劃分為

13、幾個(gè)子表，即分塊，塊內(nèi)可以無(wú)序，但塊與塊之間必須有序，即前一個(gè)塊中的最大關(guān)鍵字必須小于后一個(gè)塊中的最小關(guān)鍵字； （2）建立有序的索引表：為每一塊建立索引項(xiàng)，索引項(xiàng)包括：每一塊中的最大關(guān)鍵字和每一塊在主表中的起止位置。 由于主表分塊有序，所以索引表一定是個(gè)遞增的有序表。 分塊查找的基本思想是： 首先在索引表中查找與給定值k對(duì)應(yīng)的索引項(xiàng)，以確定下一步的查找在主表中的哪個(gè)分塊中進(jìn)行；然后在分塊中繼續(xù)查找與給定值k對(duì)應(yīng)的記錄。,設(shè)：記錄的關(guān)鍵字序列為（14，31，8，22，18，43，62，49，35，52，88，78，71，83）實(shí)現(xiàn)分塊查找 。,下標(biāo) 0 1 2,關(guān)鍵字 起始下標(biāo) 結(jié)束下標(biāo),索引表

14、,數(shù)組R 下標(biāo),主表,1 2 3 4 5 6 7 8 9 10 11 12 13 14,索引表存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述如下： # define MAXSIZE 10 typedef KeyType IndexType; typedef struct IndexType index; /*IndexType是索引關(guān)鍵字的類型*/ int start,end; /*子表在主表中的起始下標(biāo)和結(jié)束下標(biāo)*/ IndexTable; /*IndexTable是索引項(xiàng)的類型*/ IndexTable IndexMAXSIZE; /*MAXSIZE的值應(yīng)該大于索引項(xiàng)數(shù)*/,實(shí)現(xiàn)分塊查找算法的C函數(shù)： int bl

15、ockSearch(RecType R, IndexTable Index, int m, KeyType k) /*在主表R和長(zhǎng)度為m的索引表Index中查找關(guān)鍵字為k的記錄，查找成功返回記錄序號(hào)，否則返回0*/ int i,j; for(i=0;im;i+) /*在索引表中順序查找與k對(duì)應(yīng)的索引項(xiàng)*/ if (k=Indexi.index) break; if (im) /*在第i個(gè)子表中順序查找關(guān)鍵字為k的記錄*/ for (j= Indexi.start;j= Indexi.end;j+) if (k=Rj.key) return j; return 0; ,分塊查找性能分析：,分塊查

16、找的平均查找長(zhǎng)度 設(shè)n個(gè)記錄的查找表分為m個(gè)子表，且每個(gè)子表均有t個(gè)元素，則t= n/m。 當(dāng)m取 時(shí)，ASL= +1達(dá)到了最小值， 平均時(shí)間復(fù)雜度為O（ ） 分塊查找的性能介于順序查找和二分查找之間，分塊查找可以方便地進(jìn)行插入和刪除記錄的操作，不僅查找效率較高，還適合動(dòng)態(tài)查找表使用。,84 樹(shù)表查找,樹(shù)表，是查找表的一種樹(shù)形組織形式，并且使用鏈接方式進(jìn)行存儲(chǔ)。 樹(shù)表查找既具有二分查找的效率，同時(shí)還能高效率地實(shí)現(xiàn)插刪。 本節(jié)主要介紹二叉排序樹(shù)和B-樹(shù)。,841 二叉排序樹(shù),二叉排序樹(shù)（Binary Sort Tree）又稱二叉查找樹(shù)（Binary Search Tree），它或者是一棵空樹(shù)，或

17、者是具有下列性質(zhì)的二叉樹(shù)： （1）若左子樹(shù)不空，則左子樹(shù)上 所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值； （2）若右子樹(shù)不空，則右子樹(shù)上 所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值； （3）左、右子樹(shù)也都是二叉排序樹(shù)。 對(duì)二叉排序樹(shù)做中序遍歷得到的 結(jié)點(diǎn)序列是一個(gè)有序序列。,圖8.6 一棵二叉排序樹(shù),二叉排序樹(shù)存儲(chǔ)結(jié)構(gòu)的C語(yǔ)言描述如下： typedef struct node KeyType key; /*關(guān)鍵字域*/ DataType other; /*其他數(shù)據(jù)項(xiàng)域*/ struct node *lchild,*rchild; /*左、右指針域*/ BstNode;,1二叉排序樹(shù)的查找,二叉排序樹(shù)的查找過(guò)程為： （1）

18、若二叉排序樹(shù)為空，查找失敗。 （2）若二叉排序樹(shù)非空，將給定值k與根結(jié)點(diǎn)的關(guān)鍵字比較，如果相等，查找成功；否則，當(dāng)k小于根結(jié)點(diǎn)的關(guān)鍵字時(shí)，查找將在左子樹(shù)上繼續(xù)進(jìn)行；當(dāng)k大于根結(jié)點(diǎn)的關(guān)鍵字時(shí)，查找將在右子樹(shù)上繼續(xù)進(jìn)行。 （3）在子樹(shù)上的查找與前面的查找過(guò)程相同。,二叉排序樹(shù)查找算法的C函數(shù)： BstNode * searchBst(BstNode *t, KeyType k) /*已知二叉排序樹(shù)的根結(jié)點(diǎn)*t，在其中查找關(guān)鍵字為k的記錄，若找到返回結(jié)點(diǎn)的地址，否則返回空地址*/ while (t!=NULL) if (t-key=k) return t; if (t-key k) t=t-lchi

19、ld; else t=t-rchild; return NULL; ,2二叉排序樹(shù)的插入及建立,二叉排序樹(shù)中插入一個(gè)結(jié)點(diǎn)的過(guò)程如下：設(shè)待插入結(jié)點(diǎn)為*s，若二叉排序樹(shù)為空，則將新結(jié)點(diǎn)*s作為根結(jié)點(diǎn)插入；若二叉排序樹(shù)非空，比較結(jié)點(diǎn)*s與根結(jié)點(diǎn)的關(guān)鍵字，可分為三種情況： （1）若s-key與根結(jié)點(diǎn)的關(guān)鍵字相等，說(shuō)明樹(shù)中已經(jīng)存在該結(jié)點(diǎn)，不用插入； （2）若s-key小于根結(jié)點(diǎn)的關(guān)鍵字，則將*s插入到根結(jié)點(diǎn)的左子樹(shù)中； （3）若s-key大于根結(jié)點(diǎn)的關(guān)鍵字，則將*s插入到根結(jié)點(diǎn)的右子樹(shù)中。 在左、右子樹(shù)中的插入過(guò)程和二叉排序樹(shù)的插入過(guò)程是相同的。如此進(jìn)行下去，直到左子樹(shù)或右子樹(shù)為空時(shí)，新結(jié)點(diǎn)*s作為葉子

20、結(jié)點(diǎn)插入到二叉排序樹(shù)中。,一棵二叉排序樹(shù)插入結(jié)點(diǎn)60,63,55,90,42,58,70,98,45,10,67,83,二叉排序樹(shù)上插入運(yùn)算的C函數(shù)： BstNode *insertNode (BstNode *t, BstNode *s) /*在根結(jié)點(diǎn)為*t的二叉排序樹(shù)上插入新結(jié)點(diǎn)*s ，并返回根結(jié)點(diǎn)*t */ BstNode *p,*q; if (t=NULL) return s; /*二叉排序樹(shù)為空，新結(jié)點(diǎn)為根結(jié)點(diǎn)*/ p=t; /*二叉排序樹(shù)非空，開(kāi)始查找插入位置*/ while(p) q=p; if(s-key= p-key) return t; /*二叉排序樹(shù)中已經(jīng)存在該結(jié)點(diǎn)*/

21、if(s-key key) p=p-lchild; /*在子樹(shù)中尋找插入位置*/ else p=p-rchild; if (s-key key) q-lchild=s; /*插入新結(jié)點(diǎn)*/ else q-rchild=s; return t; ,建立一棵二叉排序樹(shù)的過(guò)程就是逐個(gè)插入新結(jié)點(diǎn)的過(guò)程，反復(fù)調(diào)用插入運(yùn)算即可。 例8.3設(shè)記錄的關(guān)鍵字序列為（63，90，70，55，67，42，98，83，10，45，58），依次插入各個(gè)關(guān)鍵字，建立一棵二叉排序樹(shù)。,建立二叉排序樹(shù)的算法的C函數(shù)如下： BstNode *creatBst() /*建立一棵二叉排序樹(shù)，返回這棵樹(shù)的根結(jié)點(diǎn)*/ BstNode

22、*root,*s; KeyType key; DataType data; root=NULL; scanf(“%d”, /*返回根結(jié)點(diǎn)*/ ,3二叉排序樹(shù)的刪除,設(shè)待刪除結(jié)點(diǎn)為*p，其雙親結(jié)點(diǎn)為*f，以下分三種情況進(jìn)行討論。 （1）*p結(jié)點(diǎn)為葉子結(jié)點(diǎn)。 只需將被刪結(jié)點(diǎn)的雙親結(jié)點(diǎn)相應(yīng)指針域置為空即可，這種情況最簡(jiǎn)單。 （2）*p結(jié)點(diǎn)為單分支結(jié)點(diǎn)。 *p結(jié)點(diǎn)只有一棵子樹(shù)。若只有左子樹(shù)，根結(jié)點(diǎn)為*pl；或者只有右子樹(shù)，根結(jié)點(diǎn)為*pr，此時(shí)，只需用*pl或*pr替換*p結(jié)點(diǎn)即可，這種情況也比較簡(jiǎn)單。 （3）*p結(jié)點(diǎn)為雙分支結(jié)點(diǎn)。 *p結(jié)點(diǎn)既有左子樹(shù)，又有右子樹(shù)，其根結(jié)點(diǎn)分別為*pl和*pr。這種情況

23、下刪除*p結(jié)點(diǎn)比較復(fù)雜，可按中序遍歷保持有序的原則進(jìn)行調(diào)整，有兩種調(diào)整方法：第一種方法，把*p的右子樹(shù)鏈接到*p的中序遍歷前趨結(jié)點(diǎn)的右指針域上，*p的中序前趨結(jié)點(diǎn)是它的左子樹(shù)最右下結(jié)點(diǎn)，其右指針域一定為空，從而使得*p結(jié)點(diǎn)的右子樹(shù)為空，變成單分支點(diǎn)，然后用*pl 替換*p結(jié)點(diǎn)；第二種方法，用*p結(jié)點(diǎn)的中序前趨結(jié)點(diǎn)（中序后繼結(jié)點(diǎn)）的值替換*p結(jié)點(diǎn)的值，然后刪除*p的中序前趨結(jié)點(diǎn)（中序后繼結(jié)點(diǎn)）。*p的中序前趨（中序后繼）不是葉子結(jié)點(diǎn)就是單分支結(jié)點(diǎn)，可以按照（1）或（2）的方法將它刪除。,（a） 一棵二叉排序樹(shù) （b） 第一種方法刪除結(jié)點(diǎn)20,（c） 第二種方法刪除結(jié)點(diǎn)20 （d） 第二種方法刪除

24、結(jié)點(diǎn)36,4二叉排序樹(shù)查找性能分析,二叉排序樹(shù)的形態(tài)與結(jié)點(diǎn)的插入順序有關(guān) 如結(jié)點(diǎn)的插入順序?yàn)椋?3,90,70,55,67,42,98,10,45,58,構(gòu)成的二叉排序樹(shù)如圖 (a) ASL=(1+22+34+43)/10=2.9 如果插入順序?yàn)椋?0,42,45,55,58,63,67,70,90,98,構(gòu)成的二叉排序樹(shù)如圖 (b) ASL=(1+2+3+4+5+6+7+8+9+10) /10=5.5,(a),(b),二叉排序樹(shù)的查找效率與樹(shù)的形態(tài)有關(guān)。 最好情況下，平均查找長(zhǎng)度大約為log2n，時(shí)間復(fù)雜度為O(log2n)。 最壞的情況下，平均查找長(zhǎng)度為(n+1) /2，時(shí)間復(fù)雜度為O(n

25、)。 查找運(yùn)算的平均時(shí)間復(fù)雜度仍為O(log2n)。 二叉排序樹(shù)的平均查找性能與二分查找近似，查找效率較高，同時(shí)使用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，它的插入和刪除操作也較為方便，所以二叉排序樹(shù)非常適合作動(dòng)態(tài)查找表。,85 散列表查找,順序表、索引表和樹(shù)表中，記錄的存儲(chǔ)位置與記錄的關(guān)鍵字之間不存在確定的關(guān)系，在表中查找記錄需要進(jìn)行一系列的比較，所以查找效率主要取決于查找過(guò)程中執(zhí)行的比較次數(shù)。 如果記錄的存儲(chǔ)位置與關(guān)鍵字之間有某種確定的關(guān)系，在理想的情況下，記錄的存儲(chǔ)位置與關(guān)鍵字存在一一對(duì)應(yīng)關(guān)系，則可以不通過(guò)比較就能找到對(duì)應(yīng)的記錄。本節(jié)探討的散列表查找就是這樣的查找方法。,851 散列表的概念,散列存儲(chǔ)是專為查找而

26、設(shè)計(jì)的存儲(chǔ)結(jié)構(gòu)，它的基本思想是：以表中每一個(gè)記錄的關(guān)鍵字k為自變量，通過(guò)某個(gè)函數(shù)Hash(k)計(jì)算出函數(shù)值，把這個(gè)值解釋為記錄的存儲(chǔ)位置，將記錄存儲(chǔ)在Hash(k)所指的位置上。散列存儲(chǔ)實(shí)現(xiàn)了關(guān)鍵字到存儲(chǔ)地址的轉(zhuǎn)換，所以也稱關(guān)鍵字地址轉(zhuǎn)換法。 散列表：使用散列存儲(chǔ)方式存儲(chǔ)的線性表，也稱作哈希表（Hash Table）。 散列存儲(chǔ)中使用的函數(shù)Hash(k)，稱為散列函數(shù)（哈希函數(shù)），Hash(k)的值稱為散列地址（哈希地址）。,若有一個(gè)長(zhǎng)度為9的線性表，其中記錄的關(guān)鍵字序列為（23，15，36，99，6，14，65，93，75），使用散列存儲(chǔ)方式存儲(chǔ)該線性表 .,0 6 14 15 23 36

27、65 75 93 98 99,(1)直接定址法 設(shè)散列函數(shù)Hash1(key)=key,將線性表存儲(chǔ)在長(zhǎng)度為100的數(shù)組空間上，散列表的存儲(chǔ)情況如圖所示。 直接定址法一般形式為：Hash(key)=akey+b，其中，a、b為常數(shù)，這里a為1，b為0。 設(shè)線性表的長(zhǎng)度為n，散列表（一維數(shù)組）的長(zhǎng)度為m，則稱=n/m為散列表的裝填因子。 裝填因子的取值區(qū)間為0.60.9比較合適。本例中n=9，m=100，則為0.09，顯然這樣的散列函數(shù)是不可取的，在實(shí)際應(yīng)用中較少使用。,（2）除留余數(shù)法 散列函數(shù)為 Hash2（key）=key % 11，將線性表存儲(chǔ)在長(zhǎng)度為11的數(shù)組中，則每個(gè)記錄的散列地址為

28、： Hash2(23)=23%11=1 Hash2(15)=15%11=4 Hash2(36)=36%11=3 Hash2(99)=99%11=0 Hash2(6)=6%11=6 Hash2(14)=14%11=3 Hash2(65)=65%11=10 Hash2(93)=93%11=5 Hash2(75)=75%11=9 一般地，若某個(gè)散列函數(shù)Hash(k)對(duì)于不相等的關(guān)鍵字key1和key2，得到相同的散列地址，則稱該現(xiàn)象為沖突。發(fā)生沖突的兩個(gè)不同的關(guān)鍵字key1和key2被稱為同義詞，這里36和14就是同義詞。,如何設(shè)計(jì)一個(gè)好的散列函數(shù)和確定一種解決沖突的辦法，是散列存儲(chǔ)方式中需要解決的

29、兩個(gè)最重要問(wèn)題。,852 散列函數(shù)的設(shè)計(jì),散列函數(shù)的設(shè)計(jì)原則是：計(jì)算簡(jiǎn)單，節(jié)省時(shí)間；函數(shù)值取值范圍合理，避免空間的浪費(fèi)，保證在合理的取值區(qū)間；散列地址盡可能均勻地分布在散列空間上，避免太多的沖突。,1數(shù)字分析法 例8.5有一組由7位數(shù)字組成的關(guān)鍵字，使用數(shù)字分析法設(shè)計(jì)散列函數(shù)。,2除留余數(shù)法 Hash(key)=key % p （p是一個(gè)整數(shù)） 若線性表的長(zhǎng)度為n，散列表的長(zhǎng)度為m，則一般選取p為質(zhì)數(shù)，且 npm。根據(jù)裝填因子的取值區(qū)間為0.60.9，p應(yīng)為1.1n1.7n之間的一個(gè)質(zhì)數(shù)。,3平方取中法 平方取中法是對(duì)關(guān)鍵字取平方后，按散列空間的大小，取中間的若干位作為散列地址。 例8.6 有

30、一組關(guān)鍵字為0100，0111，0101，1001，0011，取平方的結(jié)果是：0010000，0012321，0010201，1002001，0000121，如果散列空間的長(zhǎng)度為1000，則可取中間的三位作為散列地址100，123，102，020，001。,4折疊法 折疊法是將關(guān)鍵字自左到右分成位數(shù)相等的幾部分，最后一部分位數(shù)可以短些，然后將這幾部分疊加求和，并根據(jù)散列表的表長(zhǎng)，選取后幾位作為散列地址。 例8.7 已知關(guān)鍵字 key=5326248725，散列表長(zhǎng)度為1000，使用折疊法計(jì)算散列地址。 按照每三位為一部分來(lái)分割關(guān)鍵字，關(guān)鍵字分割為如下四組： 532 624 872 5 532

31、624 872 + 5 2033 Hash(key)=033 折疊法適合于關(guān)鍵字的位數(shù)較多，而散列地址的位數(shù)較少，同時(shí)關(guān)鍵字中的每一位的取值又較集中的情況。,853 解決沖突的方法,1開(kāi)放地址法 所謂開(kāi)放地址法，就是散列地址單元一旦發(fā)生了沖突，就按照某種方法尋找下一個(gè)開(kāi)放地址。開(kāi)放地址是指該地址單元為空，可以存儲(chǔ)記錄。 尋找開(kāi)放地址的方法有很多，它們的區(qū)別是形成的探測(cè)序列不同。,（1）線性探測(cè)法 線性探測(cè)法的基本思想是：將散列表看成一個(gè)首尾相接的環(huán)形表，設(shè)散列表的長(zhǎng)度為m，當(dāng)向散列表中插入關(guān)鍵字為key的記錄時(shí)，若地址d=Hash (key)的單元為空，即將記錄存入該地址單元。若發(fā)生沖突，則依

32、次探測(cè)下列地址單元：d+1，d+2，m-1，0，1，d-1，直到找到一個(gè)空的地址單元，然后將記錄存入其中?；蛘咴谔綔y(cè)過(guò)程中，遇到關(guān)鍵字為key的記錄，說(shuō)明表中已有該記錄，無(wú)需插入。如果按照這種探測(cè)序列搜索整個(gè)散列表后又回到了地址空間d，則說(shuō)明散列表已滿。 線性探測(cè)法計(jì)算下一個(gè)開(kāi)放地址的公式為： Hi=（Hash（key）+i）% m 其中：i取整數(shù)，取值范圍 1im-1；m為散列表的長(zhǎng)度。,例8.8 依次向長(zhǎng)度為11的散列表（數(shù)組R）中插入關(guān)鍵字為 47，7，29，11，16，92，22，8，3的記錄，散列函數(shù)為：Hash（key）=key % 11，用線性探測(cè)法處理沖突。散列表的存儲(chǔ)結(jié)構(gòu)如圖

33、所示。,8,29,7,3,16,92,47,22,11,下標(biāo) 0 1 2 3 4 5 6 7 8 9 10,47，7，11，16，92沒(méi)有發(fā)生沖突；29，22，8 發(fā)生沖突，由H1=(Hash(k)+1) % 存入其中；Hash(3)發(fā)生沖突，H1=(Hash(3)+1) % 11=4，仍然沖突；H2=(Hash(3)+ 2) % 11=5，仍然沖突；H3=(Hash(3)+3) % 11=6，找到空的地址單元R6，存入其中。,在例子8.8中，成功查找到每一個(gè)記錄需要與關(guān)鍵字的比較次數(shù) 如表所示。,查找成功時(shí)，它的平均查找長(zhǎng)度為： ASL=（1+1+1+1+1+1+2+2+4）/9=14/91

34、.56 查找不成功時(shí)，它的平均查找長(zhǎng)度為： ASL不成功=（3+2+1+8+7+6+5+4+3+2+1）/11=42/113.8,2鏈地址法 鏈地址法就是把發(fā)生沖突的同義詞記錄用單鏈表鏈接起來(lái)，散列表中的每一個(gè)單元不是用來(lái)存儲(chǔ)記錄，而是存儲(chǔ)單鏈表的頭指針。所有散列地址相同（沖突）的記錄都存儲(chǔ)在同一個(gè)單鏈表中。由于單鏈表每一個(gè)結(jié)點(diǎn)是動(dòng)態(tài)生成的，所以插入和刪除記錄非常方便。散列表的長(zhǎng)度只要與散列函數(shù)的取值范圍對(duì)應(yīng)即可。,例8.9 已知關(guān)鍵字序列和例8.8相同，散列函數(shù)仍為Hash(key)=key % 11，使用鏈地址法處理沖突，用頭插法向單鏈表中插入結(jié)點(diǎn)。 查找成功時(shí)的平均查找長(zhǎng)度 ASL=(6

35、1+23)/9=12/91.33 查找不成功時(shí)的平均查找長(zhǎng)度： ASL=(2+0+0+2+1+1+0+2+ 1+0+0)/11=9/110.82,結(jié)論： （1）散列表中的平均查找長(zhǎng)度要比順序查找和二分查找小。 查找表的長(zhǎng)度n=9，散列表的平均查找長(zhǎng)度分別為： 線性探測(cè)法：ASL=14/91.56 鏈地址法：ASL=12/91.33 順序查找和二分查找的平均查找長(zhǎng)度分別為：ASL=(9+1)/2=5 ASL=(1+22+34+42)/9=25/92.78 （2）散列表的平均查找長(zhǎng)度與散列函數(shù)的設(shè)計(jì)、沖突的解決方法有關(guān)。 同樣一組關(guān)鍵字，不同的散列函數(shù)使得沖突的發(fā)生頻繁程度不同，導(dǎo)致平均查找長(zhǎng)度是

36、不同的。 同樣一組關(guān)鍵字，設(shè)定相同的散列函數(shù)，但用不同的沖突解決方法構(gòu)造散列表，其平均查找長(zhǎng)度仍然是不同的。,（3）一般情況下，當(dāng)散列函數(shù)的設(shè)計(jì)方法相同時(shí)，散列表的平均查找長(zhǎng)度與裝填因子有關(guān)。裝填因子反映了散列空間的裝滿程度，越小，發(fā)生沖突的可能性就越小，查找時(shí)與關(guān)鍵字比較的次數(shù)較少；反之，越大，發(fā)生沖突的可能性就越大，查找時(shí)與關(guān)鍵字比較的次數(shù)就越多。但越小，造成空間的浪費(fèi)也越大。 （4）散列表的優(yōu)點(diǎn)：關(guān)鍵字與記錄的存儲(chǔ)地址存在確定的對(duì)應(yīng)關(guān)系，使得插入和查找操作效率很高，所以散列表是較優(yōu)的動(dòng)態(tài)查找表。 散列表的缺點(diǎn)：根據(jù)關(guān)鍵字計(jì)算散列地址的操作需要一定的時(shí)間開(kāi)銷；散列表存儲(chǔ)方式浪費(fèi)存儲(chǔ)空間；在散列存儲(chǔ)結(jié)構(gòu)中，無(wú)法體現(xiàn)出記錄之間的邏輯關(guān)系。,