c++課件查找課件

8.1基本概念8.2靜態(tài)查找表8.3動態(tài)查找表8.4哈希表第8章查找18.1基本概念若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。(在查找表中)查詢(Searching)特定元素是否在表中。一種數(shù)據(jù)結(jié)構(gòu)[查找：][查找表：]2例、學(xué)生健康情況登記表如下：學(xué)號姓名性別年齡健康情況01王小林男18健康02陳紅女20一般03劉建平男21健康04張立立男17神經(jīng)衰弱…..……..…….…….…….38.1基本概念記錄中某個數(shù)據(jù)項(xiàng)的值，可用來識別一個記錄。主關(guān)鍵字：可以唯一標(biāo)識一個記錄的關(guān)鍵字次關(guān)鍵字：識別若干記錄的關(guān)鍵字如“學(xué)號”如性別=“女”靜態(tài)查找：只查找，不改變集合內(nèi)的數(shù)據(jù)元素。動態(tài)查找：既查找，又改變(增減)集合內(nèi)的數(shù)據(jù)元素。[關(guān)鍵字：][分類：]4（2）對查找表常用的操作查詢某個“特定的”數(shù)據(jù)元素是否在表中；查詢某個“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。

（3)查找方法

查找方法取決于表中數(shù)據(jù)的排列方式;說明：（1）查找的過程給定一個值K，在含有n個記錄的文件中進(jìn)行搜索，尋找一個關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。針對靜態(tài)查找表和動態(tài)查找表的查找方法也有所不同。靜態(tài)查找表動態(tài)查找表5（4）評估查找方法的優(yōu)劣說明：查找的過程就是將給定的K值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為平均查找長度（ASL：averagesearchlength）。其中：n是文件記錄個數(shù)；Pi是查找第i個記錄的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i個記錄時所經(jīng)歷的比較次數(shù)。統(tǒng)計意義上的數(shù)學(xué)期望值[物理意義：]假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為ASL。顯然，ASL值越小，時間效率越高。它用來衡量查找的效率。?×=iiCPASL1=ni68.2靜態(tài)查找表一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┤?、靜態(tài)樹表的查找四、分塊查找（索引順序查找）764查找過程：從表的一端開始逐個進(jìn)行記錄的關(guān)鍵字和給定值的比較算法描述i例找6451319213756647580889201234567891011監(jiān)視哨iiii比較次數(shù)=5[技巧:]

把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這可以加快執(zhí)行速度。一、順序查找（Linearsearch，又稱線性查找）順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。

8①若查不到，返回特殊標(biāo)志，例如返回空記錄或空指針。前例中設(shè)立了“哨兵”，就是將關(guān)鍵字送入末地址使之結(jié)束并返回i=0。[注意：]②

計算順序查找的效率ASL分析：查找第n個元素所需的比較次數(shù)為1；查找第n-1個元素所需的比較次數(shù)為2；……查找第1個元素所需的比較次數(shù)為n；總計全部比較次數(shù)為：1＋2＋…＋n=(1+n)n/2未考慮查找不成功的情況：查找哨兵所需的比較次數(shù)為n+1這是查找成功的情況若求某一個元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），即：ASL＝（1＋n）/2，時間效率為O(n)9對順序結(jié)構(gòu)線性查找！對單鏈表結(jié)構(gòu)如何線性查找？

函數(shù)雖未給出，但也很容易編寫；只要知道頭指針head就可以“順藤摸瓜”；對非線性樹結(jié)構(gòu)如何順序查找?

可借助各種遍歷操作！

③順序查找的思考：10二、折半查找（又稱二分查找或?qū)Ψ植檎遥﹥?yōu)點(diǎn)：算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)：

ASL太長，時間效率太低。先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比:若key小，則縮小至左半部內(nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。改進(jìn)④順序查找的特點(diǎn)：11算法描述lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid12例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid131234567891011513192137566475808892lowhigh1185210741936判定樹：123456789101151319213756647580889214[注意：]①若關(guān)鍵字不在表中，即：查找范圍的上界≤下界時停止查找。②二分查找的效率ASL1次比較就查找成功的元素有1個（20），即中間值；2次比較就查找成功的元素有2個（21），即1/4處（或3/4）處；3次比較就查找成功的元素有4個（22），即1/8處（或3/8）處…4次比較就查找成功的元素有8個（23），即1/16處（或3/16）處………則第m次比較時查找成功的元素會有（2m-1）個；為方便起見，假設(shè)表中全部n個元素＝2m-1個，此時就不討論第m次比較后還有剩余元素的情況了。全部比較總次數(shù)為1×20＋2×21＋3×22＋4×23…＋m×2m—1

＝15平均每個數(shù)據(jù)的查找時間還要除以n，所以：16查找過程可用二叉樹描述：每個記錄用一個結(jié)點(diǎn)表示；結(jié)點(diǎn)中的值為該記錄在表中位置，這個描述查找過程的二叉樹稱為判定樹。n個元素的表的折半查找的判定樹是唯一的，即：判定樹由表中元素個數(shù)決定。

找到有序表中任一記錄的過程就是：走了一條從根結(jié)點(diǎn)到與該記錄相應(yīng)的結(jié)點(diǎn)的路徑。

比較的關(guān)鍵字個數(shù)：為該結(jié)點(diǎn)在判定樹上的層次數(shù)。

查找成功時比較的關(guān)鍵字個數(shù)最多不超過樹的深度d:d=log2n+1(P220注)折半查找效率分析法2：1185210741936判定樹：17對順序表結(jié)構(gòu)編程實(shí)現(xiàn)折半查找算法!例對單鏈表結(jié)構(gòu)如何折半查找？

——無法實(shí)現(xiàn)！因全部元素的定位只能從頭指針head開始對非線性(樹)結(jié)構(gòu)如何折半查找？

——可借助二叉排序樹來查找（屬動態(tài)查找表形式）。

[折半查找的思考：]18三、靜態(tài)樹表的查找[討論：]當(dāng)有序表中各記錄的查找概率不相等時，該如何查找？首先要明確，此時用折半查找法未必最優(yōu)！（參見教材）[改進(jìn)：]若將各記錄概率看作是二叉樹之權(quán)值，則轉(zhuǎn)為研究帶權(quán)路徑長度最小的二叉樹（類似最優(yōu)二叉樹）。靜態(tài)最優(yōu)查找樹算法——時間代價高；實(shí)用算法：近似最優(yōu)查找樹（次優(yōu)查找樹）（參見教材）19四、分塊查找（索引順序查找）這是一種順序查找的另一種改進(jìn)方法。先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個子表中的數(shù)值（用關(guān)鍵字更準(zhǔn)確）都比后一塊中數(shù)值小（但子表內(nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個索引表，表中還要包含每個子表的起始地址（即頭指針）。索引表最大關(guān)鍵字起始地址2212138920334244382448605874498653第1塊第2塊第3塊224886例：2248861713特點(diǎn)：塊間有序，塊內(nèi)無序2012345678910111213141516171822121389203342443824486058745786532248861713索引表查3821分塊查找方法評價22特點(diǎn)：8.3動態(tài)查找表表結(jié)構(gòu)在查找過程中動態(tài)生成。要求：對于給定值key,若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key的記錄。典型的動態(tài)查找表———二叉排序樹二叉排序樹又稱二叉查找樹，是一種動態(tài)樹表。23二叉排序樹的定義或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：

（1）左子樹的所有結(jié)點(diǎn)均小于根的值；（2）右子樹的所有結(jié)點(diǎn)均大于根的值；（3）它的左右子樹也分別為二叉排序樹。2445125333724100619078按中序遍歷：3，12，24，37，45，53，61，78，90，100遞增中序遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列（參看教材229頁的意義）251、二叉排序樹的查找：若根結(jié)點(diǎn)的關(guān)鍵字值等于查找的關(guān)鍵字，成功。否則，若小于根結(jié)點(diǎn)的關(guān)鍵字值，查其左子樹;若大于根結(jié)點(diǎn)的關(guān)鍵字值，查其右子樹。在左右子樹上的操作類似。12225030011020099105230216顯然，在二叉排序樹中查找某結(jié)點(diǎn)其實(shí)是從根結(jié)點(diǎn)出發(fā)走了一條從根到待查結(jié)點(diǎn)的路徑。262.二叉排序樹的插入插入原則：若二叉排序樹為空，則插入結(jié)點(diǎn)應(yīng)為新的根結(jié)點(diǎn)；否則，繼續(xù)在其左、右子樹上查找，直至某個葉子結(jié)點(diǎn)的左子樹或右子樹為空為止，則插入結(jié)點(diǎn)應(yīng)為該葉子結(jié)點(diǎn)的左孩子或右孩子274512533372410061907820例如：在右圖給定的二叉排序樹中插入結(jié)點(diǎn)20283.二叉排序樹的生成從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹。29例:{10，18，3，8，12，2，7，3}101018101831018381018381210183812210183812271018381227330考慮如下兩種不同查找次序的序列構(gòu)成的二叉排序樹，查找次序分別為：4024551237122437405540，24，12，37，5512，24，37，40，55顯然，第i層結(jié)點(diǎn)需比較i次。在等概率的前提下，上述兩圖的平均查找長度為：31由上例分析易知：在二叉排序樹中進(jìn)行查找的平均查找長度和二叉樹的形態(tài)有關(guān)，即:最壞:（n+1)/2（單支樹）最好：log2n（形態(tài)勻稱，與二分查找的判定樹相似）324.二叉排序樹的刪除要刪除二叉排序樹中的p結(jié)點(diǎn)，分三種情況：p為葉子結(jié)點(diǎn)。只需修改p雙親f的指針，令：f->lchild=NULL或f->rchild=NULLp只有左子樹或右子樹p只有左子樹，用p的左孩子代替p(1)(2)p只有右子樹，用p的右孩子代替p(3)(4)p左、右子樹均非空沿p左子樹的根C的右子樹分支找到S，S的右子樹為空，將S的左子樹成為S的雙親Q的右子樹，用S取代p(5)若C無右子樹，用C取代p(6)1,23,45,6平衡二叉樹33SQPLP中序遍歷：QSPLPSQPL中序遍歷：QSPL(2)SPPLQ中序遍歷：PLPSQSPLQ中序遍歷：PLSQ(1)63421815634215刪除1834中序遍歷：PPRSQSPRQ中序遍歷：PRSQ(3)SPPRQ中序遍歷：QSPPRSQPR中序遍歷：QSPR(4)SQPRP6342181215刪除126342181535FPCPRCLQQLSSL中序遍歷：CLC……QLQSLSPPRFFSCPRCLQQLSL中序遍歷：CLC……QLQSL

SPRF(5)FPCPRCL中序遍歷：CLCPPRFFCPRCL中序遍歷：CLCPRF(6)36平衡二叉樹（又稱AVL樹）

1.引入：提高查找速度，避免出現(xiàn)最壞情況（如右圖所示）。40245512371224374055理論上，雖然完全二叉樹的樹型最好，但是構(gòu)造困難，因此查找時常使用平衡二叉樹。平衡因子（平衡度）：結(jié)點(diǎn)的平衡度是結(jié)點(diǎn)的左子樹的高度－右子樹的高度平衡二叉樹：每個結(jié)點(diǎn)的平衡因子都為＋1、－1、0的二叉樹；或者說每個結(jié)點(diǎn)的左右子樹的高度最多差1的二叉樹。[注意：]完全二叉樹必為平衡樹；平衡樹不一定是完全二叉樹。38141253928635360501718730+1+1-1-1-100000000145392863536050171830+1+2-1-100000+1-1是平衡樹不是完全二叉樹不是平衡樹39若在左圖所示的平衡樹中插入數(shù)據(jù)域?yàn)?的結(jié)點(diǎn)。插入之后仍應(yīng)保持平衡二叉樹的性質(zhì)不變。141253928635360501718730+1+1-1-1-100000000平衡樹141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)如何用最簡單、最有效的辦法保持平衡樹的性質(zhì)不變？

2.如何使構(gòu)成的二叉排序樹成為平衡樹？141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)解決方案：不涉及到危機(jī)結(jié)點(diǎn)的父親結(jié)點(diǎn)，即以危機(jī)結(jié)點(diǎn)為根的子樹的高度應(yīng)保持不變（左圖為3）。新結(jié)點(diǎn)插入后，找到第一個平衡度不為0的結(jié)點(diǎn)（如左圖結(jié)點(diǎn)）即可。新插入的結(jié)點(diǎn)和第一個平衡度不為0的結(jié)點(diǎn)（也可能是危機(jī)結(jié)點(diǎn)）之間的結(jié)點(diǎn)，其平衡度皆為0在調(diào)整中，僅調(diào)整那些在平衡度變化的路徑上的結(jié)點(diǎn)（如：），其它結(jié)點(diǎn)不予調(diào)整。仍應(yīng)保持分類二叉樹的性質(zhì)不變。9359141253928635360501718730+1+1-1-1-1000000002+1+1+2原平衡度為0危機(jī)結(jié)點(diǎn)關(guān)鍵：將導(dǎo)致出現(xiàn)危機(jī)結(jié)點(diǎn)的情況全部分析清楚，就可以使得平衡分類二叉樹的性質(zhì)保持不變！14932528635360501718730+1+1-1-1-100000001200

左改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的左子樹上進(jìn)行的調(diào)整）1、LL情況：（LL：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的

左子樹的左子樹上）AB+1h-10+2+1hh-1h-1LL改組BLBRARBA0h0h-1h-1BLBRAR危機(jī)結(jié)點(diǎn)改組前：高度為h+1

中序序列：ABBLBRAR改組后：高度為h+1

中序序列：ABBLBRAR注意：改組后平衡度為0AB2、LR情況：（LR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的

左子樹的右子樹上）情況A：AB+1h-10+2-1h-1LR改組BLAR危機(jī)結(jié)點(diǎn)改組前：高度為h+1

中序序列：注意：改組后平衡度為0,0,-1CBCCLCRh-2h-2h-10+1CB0h-1h-1BLARACRh-2CLh-1-10ABBLARCCLCR改組后：高度為h+1

中序序列：ABBLARCCLCRA情況B：AB+1h-10+2-1h-1LR改組BLAR危機(jī)結(jié)點(diǎn)改組前：高度為h+1

中序序列：注意：改組后平衡度為+1,0,0CBCCRCLh-1h-2h-20-1CB0h-1h-1BLARACLh-1CRh-2+10ABBLARCCRCL改組后：高度為h+1

中序序列：AABBLARCCRCL情況C：AB+10+2-1LR改組危機(jī)結(jié)點(diǎn)改組前：高度為2中序序列：注意：改組后平衡度為0,0,0CBC0ABCA新插入結(jié)點(diǎn)ABC改組后：高度為2中序序列：CB0A00

四種情況的區(qū)分：

如果的平衡度為＋1則為LL型改組；

否則為LR型改組：若的平衡度為＋1、－1、0；則分別為LRA、LRB、LRC型改組。BC

右改組（新插入結(jié)點(diǎn)出現(xiàn)在危機(jī)結(jié)點(diǎn)的右子樹上進(jìn)行的調(diào)整）的情況分析：1、RR情況：（RR：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的

右子樹的右子樹上） 處理圖形和LL鏡象相似2、RL情況：（RL：表示新插入結(jié)點(diǎn)在危機(jī)結(jié)點(diǎn)的

右子樹的左子樹上）

A、處理圖形和LRA鏡象相似

B、處理圖形和LRB鏡象相似

C、處理圖形和LRC鏡象相似一棵高度為6層的平衡二叉樹，除終端結(jié)點(diǎn)外，若每個結(jié)點(diǎn)的平衡因子都為1，則此平衡二叉樹共有____個結(jié)點(diǎn)。20488.4哈希查找表一、哈希表的概念二、哈希函數(shù)的構(gòu)造方法三、沖突處理方法四、哈希表的查找及分析49一、哈希表的概念哈希表：即散列存儲結(jié)構(gòu)。散列存儲的基本思想：

建立關(guān)鍵字與其存儲位置的對應(yīng)關(guān)系，或者說，由關(guān)鍵字的值決定數(shù)據(jù)的存儲地址。優(yōu)點(diǎn)：查找速度極快；查找效率與元素個數(shù)n無關(guān)！例1：若將學(xué)生信息按如下方式存入計算機(jī)，如：將2001011810201的所有信息存入V[01]單元；將2001011810202的所有信息存入V[02]單元；………….將2001011810231的所有信息存入V[31]單元。欲查找學(xué)號為2001011810216的信息，可直接訪問V[16]！50例2：

有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個元素k的存儲地址H（k）＝k，請畫出存儲結(jié)構(gòu)圖。解：根據(jù)散列函數(shù)H（k）＝k，可知元素14應(yīng)當(dāng)存入地址為14的單元，元素23應(yīng)當(dāng)存入地址為23的單元，……，對應(yīng)散列存儲表（哈希表）如下：討論：如何進(jìn)行散列查找？根據(jù)存儲時用到的散列函數(shù)H(k)表達(dá)式，即可查到結(jié)果！例如，查找key=9,則訪問H(9)=9號地址，若內(nèi)容為9則成功；若查不到，應(yīng)當(dāng)設(shè)法返回一個特殊值，例如空指針或空記錄。地址…9…11…14…232425…39…內(nèi)點(diǎn)：空間效率低！51選取某個函數(shù)，依照此函數(shù)，按關(guān)鍵字計算元素的存儲位置，并按此存放；查找時，由同一個函數(shù)對給定值k計算地址，將k與地址單元中元素關(guān)鍵碼進(jìn)行比較，確定查找是否成功。若干術(shù)語哈希方法(雜湊法):52通常關(guān)鍵字的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個哈希地址上，這種現(xiàn)象稱為沖突。哈希函數(shù)哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))按上述思想構(gòu)造的表稱為哈希表(雜湊表)哈希表沖突53有6個元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=kmod7通過哈希函數(shù)對6個元素建立哈希表：253923914[沖突現(xiàn)象舉例：]6個元素用7個地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！012345654所以，哈希方法必須解決以下兩個問題：1）構(gòu)造好的哈希函數(shù)（a）所選函數(shù)盡可能簡單，以便提高轉(zhuǎn)換速度；（b）所選函數(shù)對關(guān)鍵字計算出的地址，應(yīng)在哈希地址集中大致均勻分布，以減少空間浪費(fèi)。2）制定一個好的解決沖突的方案查找時，如果從哈希函數(shù)計算出的地址中查不到關(guān)鍵字，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。55二、哈希函數(shù)的構(gòu)造方法常用的哈希函數(shù)構(gòu)造方法有：直接定址法

除留余數(shù)法

乘余取整法數(shù)字分析法

平方取中法

折疊法隨機(jī)數(shù)法

要求一：n個數(shù)據(jù)原僅占用n個地址，雖然散列查找是以空間換時間，但仍希望散列的地址空間盡量小。要求二：無論用什么方法存儲，目的都是盡量均勻地存放元素，以避免沖突。56Hash(key)=a·key+b(a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵碼key的某個線性函數(shù)值為哈希地址，不會產(chǎn)生沖突.缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。[例：]關(guān)鍵碼集合為{100，300，500，700，800，900}，選取哈希函數(shù)為Hash(key)=key/100，則存儲結(jié)構(gòu)（哈希表）如下：01234567899008007005003001001、直接定址法57Hash(key)=B*(A*keymod1)

(A、B均為常數(shù)，且0<A<1，B為整數(shù))特點(diǎn)：以關(guān)鍵碼key乘以A，取其小數(shù)部分，然后再放大B倍并取整，作為哈希地址。Hash(key)=keymodp(p是一個整數(shù))特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。關(guān)鍵：如何選取合適的p？技巧：若設(shè)計的哈希表長為m，則一般取p≤m且為質(zhì)數(shù)

（也可以是不包含小于20質(zhì)因子的合數(shù)）。3、乘余取整法2、除留余數(shù)法（A*keymod1）就是取A*key的小數(shù)部分[例：]欲以學(xué)號最后兩位作為地址，則哈希函數(shù)應(yīng)為：

H(k)=100*(0.01*kmod1)其實(shí)也可以用法2實(shí)現(xiàn)：H(k)=kmod10058特點(diǎn)：某關(guān)鍵字的某幾位組合成哈希地址。所選的位應(yīng)當(dāng)是：各種符號在該位上出現(xiàn)的頻率大致相同。34705243491487348269634852703486305349805834796713473919例：有一組（例如56個）關(guān)鍵碼，其樣式如下：4、數(shù)字分析法討論：①

第1、2位均是“3和4”，第3位也只有“7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。位號：①②③④⑤⑥⑦②若哈希地址取兩位（因元素僅56個），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。59特點(diǎn)：對關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。理由：因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。[例：]2589的平方值為6702921，可以取中間的029為地址。5、平方取中法606、折疊法

特點(diǎn)：將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些）,然后將這幾部分疊加求和,并按哈希表表長,取后幾位作為哈希地址。適用：每一位上各符號出現(xiàn)概率大致相同的情況。法1：移位法──將各部分的最后一位對齊相加。法2：間界疊加法──從一端向另一端沿分割界來回折疊后，最后一位對齊相加。[例：]元素42751896,用法1：427＋518＋96=1041用法2：42751896—>724+518+69=1311617、隨機(jī)數(shù)法Hash(key)=random(key)(random為偽隨機(jī)函數(shù))適用：關(guān)鍵字長度不等的情況。造表和查找都很方便。①執(zhí)行速度（即計算哈希函數(shù)所需時間）；②關(guān)鍵字的長度；③哈希表的大??；④關(guān)鍵字的分布情況；⑤查找頻率。小結(jié)：構(gòu)造哈希函數(shù)的原則：62三、沖突處理方法1.開放定址法（開地址法）2.鏈地址法（拉鏈法）3.再哈希法（雙哈希函數(shù)法）631、開放定址法（開地址法）設(shè)計思路：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。[具體實(shí)現(xiàn)：]Hi=(Hash(key)+di)modm(1≤i<m)其中：Hash(key)為哈希函數(shù)

m為哈希表長度

di

為增量序列1，2，…m-1，且di=i線性探測法含義：一旦沖突，就找附近（下一個）空地址存入64

優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素；缺點(diǎn)：可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應(yīng)存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞，…，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。解決方案：可采用二次探測法或偽隨機(jī)探測法，以改善“堆積”問題。[討論線性探測法：]65例：表長為11的哈希表中已填有關(guān)鍵字為17，60，29的記錄,H(key)=keyMOD11,現(xiàn)有第4個記錄，其關(guān)鍵字為38，按三種處理沖突的方法，將它填入表中012345678910601729(1)H(38)=38MOD11=5沖突H1=(5+1)MOD11=6沖突H2=(5+2)MOD11=7沖突H3=(5+3)MOD11=8不沖突38(2)H(38)=38MOD11=5沖突H1=(5+12)MOD11=6沖突H2=(5-12)MOD11=4不沖突38(3)H(38)=38MOD11=5沖突設(shè)偽隨機(jī)數(shù)序列為9，則：H1=(5+9)MOD11=3不沖突38線性探測法二次探測法偽隨機(jī)探測法662、鏈地址法(拉鏈法）[基本思想：]

將具有相同哈希地址的記錄鏈成一個單鏈表，m個哈希地址就設(shè)m個單鏈表，然后用一個數(shù)組將m個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結(jié)構(gòu)。67例：已知一組關(guān)鍵字(19,14,23,1,68,20,84,27,55,11,10,79)哈希函數(shù)為：H(key)=keyMOD13,

用鏈地址法處理沖突012345