12023/3/14第9章查找靜態(tài)查找1動態(tài)查找2哈希查找322023/3/141、相關概念關鍵字——是數(shù)據(jù)元素中某個數(shù)據(jù)項的值，它可以標識一個數(shù)據(jù)元素查找表——由同一類型的數(shù)據(jù)元素（或記錄）構成的集合。查找——也叫檢索，是根據(jù)給定的某個值，在表中確定一個關鍵字等于給定值的記錄或數(shù)據(jù)元素查找成功——在查找表中找到關鍵字值等于給定值的記錄。反之查找不成功。第9章查找32023/3/14查詢某個“特定的”數(shù)據(jù)元素是否在表中；查詢某個“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。

2、對查找表常用的操作：靜態(tài)查找表(StaticSearchTable)：對查找表只做前兩種“查找”操作動態(tài)查找表(DynamicSearchTable)：對查找表要進行后兩種“查找”操作42023/3/14明確：查找的過程就是將給定的K值與文件中各記錄的關鍵字項進行比較的過程。所以用比較次數(shù)的平均值來評估算法的優(yōu)劣。稱為平均查找長度（ASL：averagesearchlength）。其中：n是文件記錄個數(shù)；Pi是查找第i個記錄的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i個記錄時所經歷的比較次數(shù)。顯然，ASL值越小，時間效率越高。3、如何評估查找方法的優(yōu)劣？ASL52023/3/149.1靜態(tài)查找表

靜態(tài)查找表可以有不同的表示方法，在不同的表示方法中，實現(xiàn)查找操作的方法也不同。1.1順序查找（順序存儲和鏈式存儲）typdefstruct{KeyTypekey;//關鍵字域…}ElemType；//————靜態(tài)查找表的順序存儲結構———typdefstruct{ElemTypeelem[maxsize];//0號單元留空intlength;//表長度}SSTable；62023/3/14i例01234567891011

513222137566475808892找64iiii比較次數(shù)=5比較次數(shù)：查找第n個元素：1查找第n-1個元素：2……….查找第1個元素：n查找第i個元素：n+1-i順序查找(SequentialSearch)的查找過程：從表的一端開始逐個進行記錄的關鍵字和給定值的比較例：72023/3/14不設置監(jiān)視哨的順序查找算法intSeqSearch（SSTableST,KeyTypekey）/*不用監(jiān)視哨法，在順序表中查找關鍵字等于key的元素*/{i=ST.length;while(i>=1&&ST.elem[i].key!=key)i--;return（i）;}循環(huán)條件i>=1判斷查找是否越界。能否省掉該條件判斷？typdefstruct{KeyTypekey;//關鍵字域

…}ElemType；typdefstruct{ElemTypeelem[maxsize];intlength;}SSTable；82023/3/14i例01234567891011

513222137566475808892找6419監(jiān)視哨iiii比較次數(shù)=12比較次數(shù)：查找第n個元素：1查找第n-1個元素：2……….查找第1個元素：n查找第i個元素：n+1-i查找失?。簄+1技巧：把待查關鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。例：若將待查找的特定值key存入順序表的首部（如0號單元），則順序查找的實現(xiàn)方案為：從后向前逐個比較！i92023/3/14算法實現(xiàn)（含監(jiān)視哨）intSeqSearch（SSTableST,KeyTypekey）/*不用監(jiān)視哨法，在順序表中查找關鍵字等于key的元素*/{i=ST.length;while(i>=1&&ST.elem[i].key!=key)i--;return（i）;}intSearch_Seq(SSTableST,KeyTypekey){ ST.elem[0].key=key;for(i=ST.length;ST.elem[i].key!=key;--i); returni;

}102023/3/14

n

ASL=∑PiCi

i=1討論

如何計算ASL？分析：查找第n個元素所需的比較次數(shù)為1；查找第n-1個元素所需的比較次數(shù)為2；……查找第1個元素所需的比較次數(shù)為n；Pi=1/n(等概率）ASL=(1＋2＋…＋n)Pi==(1+n)/2未考慮查找不成功的情況：查找哨兵所需的比較次數(shù)為n+1這是查找成功的情況時間復雜度為O(n)112023/3/14二、折半查找（又稱二分查找或對分查找）優(yōu)點：算法簡單，且對順序結構或鏈表結構均適用。缺點：

ASL太長，時間效率太低。查找過程：每次將待查記錄所在區(qū)間縮小一半直到查找成功或不成功為止適用條件：采用順序存儲結構的有序表算法實現(xiàn)：先給數(shù)據(jù)排序（例如按升序排好），形成有序表，折半查找時,先求位于查找區(qū)間正中的對象的下標mid，用其關鍵碼與給定值x比較:

ST.elem[mid].key==x，查找成功；

ST.elem[mid].key>x，把查找區(qū)間縮小到表的前半部分，繼續(xù)；

ST.elem[mid].key<x，把查找區(qū)間縮小到表的后半部分，繼續(xù)。如果查找區(qū)間已縮小到一個對象，仍未找到要查找對象，則查找失敗如何改進？討論

順序查找的特點：122023/3/14②運算步驟：(1)low=1,high=11,mid=6，待查范圍是[1,11]；(2)若ST.elem[mid].key<key，說明key[mid+1,high]，則令：low=mid+1;重算mid＝(low+high)/2；.(3)若ST.elem[mid].key>

key，說明key[low,mid-1]，則令：high=mid–1;重算mid；(4)若ST.elem[mid].key=key，說明查找成功，元素序號=mid;結束條件：（1）查找成功：ST.elem[mid].key=key

（2）查找不成功：high<low

（意即區(qū)間長度小于0）解：①先設定3個輔助標志:

low,high,mid，折半查找舉例：Low指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置

已知如下11個元素的有序表：

1234567891011（0513192137566475808892）,請查找關鍵字為21

和70的數(shù)據(jù)元素。顯然有：mid=(low+high)/2132023/3/14lowhighmid例1234567891011513192137566475808892找211234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid142023/3/14例1234567891011513192137566475808892lowhighmid找701234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhighmid1234567891011513192137566475808892lowhigh152023/3/14intSearch_Bin(SSTableST，KeyTypekey){

//置區(qū)間初值low=1;high=ST.length；//循環(huán)查找while(low<=high){mid=(low+high)/2if(key==ST.elem[mid].key)returnmid;//找到待查元素elseif(key<ST.elem.[mid].key)high=mid-1

//繼續(xù)在前半?yún)^(qū)間進行查找elselow=mid+1;

//繼續(xù)在后半?yún)^(qū)間進行查找}return0;

//順序表中不存在待查元素}162023/3/14二分查找的效率（ASL）二分法查找的時間復雜度為O(log2n)，比順序查找快。5131921375619193737565621513描述查找過程的判定樹查找成功時比較的次數(shù)<=判定樹的深度查找不成功的比較次數(shù)？如何計算ASL？172023/3/14外部結點(5,13)(13,19)5131921375619193737565621513查找成功時比較的次數(shù)查找不成功的比較次數(shù)<=判定樹的深度<5(19,21)(21,37)(37,56)>56182023/3/14折半查找算法特點查找效率較順序查找高但只適合有序表，且限于順序存儲結構是否任何情況下都可用折半查找方法?192023/3/14課堂練習（多項選擇）：Ａ．采用鏈式存貯結構 Ｂ．記錄的長度≤128Ｃ．采用順序存貯結構Ｄ．記錄按關鍵字有序√√使用折半查找算法時，要求被查文件：202023/3/14三、分塊查找（索引順序查找）這是一種順序查找的另一種改進方法。先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個子表中的數(shù)值（用關鍵字更準確）都比后一塊中數(shù)值?。ǖ颖韮炔课幢赜行颍?。然后將各子表中的最大關鍵字構成一個索引表，表中還要包含每個子表的起始地址（即頭指針）。索引表最大關鍵字起始地址2212138920334244382448605874498653第1塊第2塊第3塊例：2248861713特點：塊間有序，塊內無序212023/3/14查找步驟分兩步進行：①對索引表使用折半查找法（因為索引表是有序表）；②確定了待查關鍵字所在的子表后，在子表內采用順序查找法（因為各子表內部是無序表）；查找效率：ASL=Lb+Lw對索引表查找的ASL對塊內查找的ASL222023/3/14ASL最大最小兩者之間表結構有序表、無序表有序表分塊有序表

存儲結構順序存儲結構線性鏈表順序存儲結構順序存儲結構線性鏈表查找方法比較順序查找折半查找分塊(索引)查找232023/3/14特點：一、二叉排序樹的定義二、二叉排序樹的插入與刪除三、二叉排序樹的查找性能分析四、平衡二叉樹9.2動態(tài)查找表表結構在查找過程中動態(tài)生成。典型的動態(tài)查找表———二叉排序樹操作：檢索、插入和刪除242023/3/14一、二叉排序樹的定義定義：二叉排序樹或是一棵空樹，或是具有下列性質的二叉樹：若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值它的左、右子樹也分別為二叉排序樹45125333710024619078252023/3/1425二叉排序樹(續(xù))請判斷下面兩棵二叉樹是否屬于排序樹7411026539861021457398√×262023/3/14二叉排序樹又稱二叉查找樹，其查找過程為：當二叉排序樹非空時，首先將給定值和根結點的關鍵字比較，若相等則查找成功，若小于則在左子樹上繼續(xù)查找，若大于則在右子樹上查找。二叉排序樹的查找算法二叉鏈表作為二叉排序樹的存儲結構，程序實現(xiàn)：272023/3/14BiTreeSearchBST(BiTreeT，KeyTypekey){

//在根指針T所指二叉排序樹中遞歸地查找某關鍵字等于key的數(shù)據(jù)元素//若查找成功，則返回指向該數(shù)據(jù)元素結點的指針，否則返回空指針

if((!T)||(key==T->data.key))return(T)；//查找結束elseif(key<T->data.key)return(SearchBST(T->lchild，key))；//在左子樹中繼續(xù)查找elsereturn(SearchBST(T->rchild，key))；//在右子樹中繼續(xù)查找}//SearchBST

282023/3/14

二、二叉排序樹的插入和刪除

二叉排序樹是一種動態(tài)樹表。其特點是：樹的結構通常不是一次生成的，而是在查找過程中，當樹中不存在關鍵字等于給定值的結點時再進行插入。新插入的結點一定是一個新添加的葉子結點，并且是查找不成功時查找路徑上訪問的最后一個結點的左孩子或右孩子結點。二叉排序樹生成：從空樹出發(fā)，經過一系列的查找、插入操作之后，可生成一棵二叉排序樹。292023/3/14294524531290如果改變輸入順序為（24，53，45，45，12，24，90）查找成功,返回查找成功,返回輸入待查找的關鍵字序列=（45，24，53，45，12，24，90）查找成功,返回查找成功,返回查找不成功則插入樹中則生成的二叉排序樹形態(tài)不同2453451290這種既查找又插入的過程稱為動態(tài)查找二叉排序樹的建立（插入）302023/3/14中序遍歷二叉排序樹可得到一個關鍵字的有序序列。這就是說，一個無序序列可以通過構造一棵二叉排序樹而變成一個有序序列，構造樹的過程即為對無序序列進行排序的過程。每次插入的新結點都是二叉排序樹上新的葉子結點。則在進行插入操作時，不必移動其它結點，僅需改動某個結點的指針。這就相當于在一個有序序列上插入一個記錄而不需要移動其它記錄。二叉排序樹既擁有類似于折半查找的特性，又采用了鏈表作存儲結構，因此是動態(tài)查找表的一種適宜表示。結論312023/3/14二叉排序樹的刪除原則：在二叉排序樹上刪除一個結點后依舊要保持二叉排序樹的特性322023/3/14fpPLPR二叉排序樹的刪除(續(xù))假設：*p表示被刪結點；PL和PR

分別表示*p的左、右孩子指針；

*f表示*p的雙親結點；假定*p是*f的左孩子考慮有多少種刪除情況*p為葉子：*p只有一棵子樹（或左或右）：*p有兩棵子樹→刪除此結點時，直接修改*f指針域即可；令PL或PR為*f的左孩子即可；332023/3/14分析設刪除前的中序遍歷序列為：…PL

sp

PRf…//p的直接前驅是s

//s是*p左子樹最右下方的結點希望刪除p后，其它元素的相對位置不變。難點：*p有兩棵子樹時，如何進行刪除操作？fpPLPRs二叉排序樹的刪除(續(xù))342023/3/14FCCLSSLQLPPRQPRFCCLSSLQLPPRQ法2FCCLSSLQLPPRQ法1SSL請從二叉排序樹中刪除結點P二叉排序樹的刪除(續(xù))352023/3/14例805012060110150557053刪除508060120110150557053刪除60805512011015053701042581365刪除1084256135刪除68425513只有右子樹有左右子樹有左右子樹只有左子樹362023/3/141)二叉排序樹上查找某關鍵字等于結點值的過程，其實就是走了一條從根到該結點的路徑。

比較的關鍵字次數(shù)＝此結點的層次數(shù);

最多的比較次數(shù)＝樹的深度（或高度）2)一棵二叉排序樹的平均查找長度為：其中：ni是第i層結點個數(shù)；

m為樹深。?=×=miinnASL1i1三、二叉排序樹的查找性能分析372023/3/14（45，24，53，12，37，93）（12，24，37，45，53，93）452453123793124524375393ASL=1/6[1+2+2+3+3+3]ASL=1/6[1+2+3+4+5+6]382023/3/14最壞情況：插入的n個元素從一開始就有序（單調增或減），

——變成了單支樹的形態(tài)！此時樹的深度為n;ASL=(n+1)/2與線性查找的ASL相同！查找性能分析392023/3/14最好情況：與折半查找中的判定樹相同（即形態(tài)比較均衡）3）對有n個關鍵字的二叉排序樹的平均查找長度:

設每種樹態(tài)出現(xiàn)概率相同，查找每個關鍵字也等概率。樹的深度為：log2n+1；402023/3/14思考：如何提高二叉排序樹的查找效率？ 平衡二叉樹盡量讓二叉樹的形狀均衡412023/3/14四、平衡二叉樹BalancedBinaryTree(AVL樹)定義：n=0，一棵空樹；n>0，一棵左右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1平衡因子BF(BalanceFactor)某結點的BF為其左子樹和右子樹的深度之差平衡二叉樹中所有結點的BF值只取-1,0,1422023/3/141100-110-10102-10100-10-20010對于一棵有n個結點的AVL樹，其高度保持在O(log2n)數(shù)量級，ASL也保持在O(log2n)量級。432023/3/14

前面介紹的所有查找都是基于待查關鍵字與表中元素進行比較而實現(xiàn)的查找方法哈希表它既是一種查找方法，又是一種存貯方法能不能不經過任何比較，一次便能得到所查記錄？442023/3/14哈希表：即散列存儲結構。

散列法存儲的基本思想：建立關鍵字與其存儲位置的對應關系，或者說，由關鍵碼的值決定數(shù)據(jù)的存儲地址。優(yōu)點：查找速度極快（O(1)）,查找效率與元素個數(shù)n無關！例1：若將學生信息按如下方式存入計算機，如：將2001011810201的所有信息存入V[01]單元；將2001011810202的所有信息存入V[02]單元；……將2001011810231的所有信息存入V[31]單元。欲查找學號為2001011810216的信息，便可直接訪問V[16]！一、哈希表的概念452023/3/14例2：有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個元素k的存儲地址H（k）＝k，請畫出存儲結構圖。（注：H（k）＝k稱為散列函數(shù)）解：根據(jù)散列函數(shù)H（k）＝k，可知元素14應當存入地址為14的單元，元素23應當存入地址為23的單元，……，對應散列存儲表（哈希表）如下：討論：如何進行散列查找？根據(jù)存儲時用到的散列函數(shù)H(k)表達式，迅即可查到結果！例如，查找key=9,則訪問H(9)=9號地址，若內容為9則成功；若查不到，應當設法返回一個特殊值，例如空指針或空記錄。地址…9…11…14…232425…39…內點：空間效率低！462023/3/14哈希函數(shù)——在記錄的關鍵字與記錄的存儲地址之間建立的一種對應關系叫~。按照這個思想建立的表為哈希表。

哈希函數(shù)是一種映象，是從關鍵字空間到存儲地址空間的一種映象472023/3/14有6個元素的關鍵碼分別為：（14，23，39，9，25，11）。選取關鍵碼與元素位置間的函數(shù)為H(k)=kmod7通過哈希函數(shù)對6個元素建立哈希表：253923914舉例：6個元素用7個地址應該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！

0123456具有相同函數(shù)值的關鍵字對該哈希函數(shù)來說稱做同義詞(synonym)。哈希函數(shù)的設定很靈活，只要使得任何關鍵字由此所得的哈希函數(shù)值都落在表長允許范圍之內即可；對不同的關鍵字可能得到同一哈希地址，即keyl!=key2，而f(keyl)=f(key2)，這種現(xiàn)象稱沖突482023/3/14所以，構造哈希表必須解決以下兩個問題：1）構造好的哈希函數(shù)（a）所選函數(shù)盡可能簡單，以便提高轉換速度；（b）所選函數(shù)對關鍵碼計算出的地址，應在哈希地址集中大致均勻分布，以減少沖突。2）制定一個好的解決沖突的方案查找時，如果從哈希函數(shù)計算出的地址中查不到關鍵碼，則應當依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。492023/3/14二、哈希函數(shù)的構造方法常用的哈希函數(shù)構造方法有：直接定址法

除留余數(shù)法

乘余取整法數(shù)字分析法平方取中法折疊法隨機數(shù)法

502023/3/14Hash(key)=a·key+b(a、b為常數(shù))優(yōu)點：以關鍵碼key的某個線性函數(shù)值為哈希地址，不會產生沖突.缺點：要占用連續(xù)地址空間，地址集合與關鍵字集合大小相等，空間效率低，適用范圍窄。例：關鍵碼集合為{100，300，500，700，800，900}，選取哈希函數(shù)為Hash(key)=key/100，則存儲結構（哈希表）如下：01234567899008007005003001001、直接定址法512023/3/14特點：某關鍵字的某幾位組合成哈希地址。所選的位應當是：各種符號在該位上出現(xiàn)的頻率大致相同。34705243491487348269634852703486305349805834796713473919例：有一組（例如80個）關鍵碼，其樣式如下：2、數(shù)字分析法討論：①第1、2位均是“3和4”，第3位也只有“

7、8、9”，因此，這幾位不能用，余下四位分布較均勻，可作為哈希地址選用。位號：①②③④⑤⑥⑦②

若哈希地址取兩位（因元素僅80個），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。522023/3/14Hash(key)=keymodp(p是一個整數(shù))特點：以關鍵碼除以p的余數(shù)作為哈希地址。關鍵：如何選取合適的p？技巧：若設計的哈希表長為m，則一般取p≤m且為質數(shù)

（也可以是不包含小于20質因子的合數(shù)）。3、除留余數(shù)法532023/3/14三、沖突處理方法常見的沖突處理方法有：開放定址法（開地址法）鏈地址法（拉鏈法）再哈希法（雙哈希函數(shù)法）建立一個公共溢出區(qū)

542023/3/141、開放定址法（開地址法）設計思路：有沖突時就去尋找下一個空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。具體實現(xiàn)：Hi=(Hash(key)+di)modm(1≤i<m)

其中：

Hash(key)為哈希函數(shù)

m為哈希表長度

di

為增量序列1，2，…m-1，且di=i

1.線性探測法含義：一旦沖突，就找附近（下一個）空地址存入。552023/3/14關鍵碼集為{47，7，29，11，16，92，22，8，3}，設：哈希表表長為m=11；哈希函數(shù)為Hash(key)=keymod11；擬用線性探測法處理沖突。建哈希表如下：解釋：①47、7（以及11、16、92）均是由哈希函數(shù)得到的沒有沖突的哈希地址；012345678910477

△▲△△例：291116922283②Hash(29)=7，哈希地址有沖突，需尋找下一個空的哈希地址：由H1=(Hash(29)+1)mod11=8，哈希地址8為空，因此將29存入。③

另外，22、8、3同樣在哈希地址上有沖突，也是由Hi找到空的哈希地址的。其中3

還連續(xù)移動了三次（二次聚集）562023/3/14線性探測法的優(yōu)點：只要哈希表未被填滿，保證能找到一個空地址單元存放有沖突的元素；線性探測法的缺點：可能使第i個哈希地址的同義詞存入第i+1個哈希地址，這樣本應存入第i+1個哈希地址的元素變成了第i+2個哈希地址的同義詞（二次聚集）

，……，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。解決方案：可采用二次探測法或偽隨機探測法，以改善“堆積”問題。討論：572023/3/14012345678910112234792167298

△▲△△注：只有3這個關鍵碼的沖突處理與上例不同，Hash(3)=3，哈希地址上沖突，由H1=(Hash(3)+12)mod11=4，仍然沖突；H2=(Hash(3)-12)mod11=2，找到空的哈希地址，存入。2.二次探測法Hi=(Hash(key)+di)modm其中：di為增量序列

12，-12，22，-22，…，q2

或

12，22，…，q2

3.若di＝偽隨機序列，就稱為偽隨機探測法關鍵碼集為{47，7，29，11，16，92，22，8，3}582023/3/142、鏈地址法基本思想：將具有相同哈希地址的記錄鏈成一個單鏈表，m個哈希地址就設m個單鏈表，然后用一個數(shù)組將m個單鏈表的表頭指針存儲起來，形成一個動態(tài)的結構。設{47,7,29,11,16,92,22,8,3,50,37,89}的哈希函數(shù)為：Hash(key)=keymod11，用鏈地址法處理沖突，則建表如右圖所示。

例：

01234567891022118934737922971650810注：有沖突的元素可以插在表尾,也可以插在表頭592023/3/143、再哈希法Hi=RHi(key)i=1,2,…，kRHi均是不同的哈希函數(shù)，當產生沖突時就計算另一個哈希函數(shù)，直到沖突不再發(fā)生。優(yōu)點：不易產生聚集；缺點：增加了計算時間。4.建立一個公共溢出區(qū)思路：除設立哈?；颈硗?，另設立一個溢出向量表。 所有關鍵字和基本表中關鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的地址是什么，一旦發(fā)生沖突，都填入溢出表。602023/3/14四、哈希表的查找及性能分析討論：哈希查找的速度是否為真正的O（1）？不是。由于沖突的產生，使得哈希表的查找過程仍然要進行比較，仍然要以平均查找長度ASL來衡量。查找過程：

在哈希表上進行查找的過程和哈希造表的過程基本一致。給定k值，根據(jù)造表時設定的哈希函數(shù)求得哈希地址，若表中此位置上沒有記錄，則查找不成功；否則比較關鍵字否則根據(jù)造表時設定的處理沖突的方法找“下一地址”，直至哈希表中某個位置為“空”或者表中所填記錄的關鍵字等于給定值時為止。若和給定值相等，則查找成功；例已知一組關鍵字(19,14,23,1,68,20,84,27,55,11,10,79)

哈希函數(shù)為：H(key)=keyMOD13,哈希表長為m=16，設每個記錄的查找概率相等，求查找成功時的ASL。(1)用線性探測再散列處理沖突，即Hi=(H(key)+di)MODmH(55)=3沖突，H1=(3+1)MOD16=4

沖突，H2=(3+2)MOD16=5H(79)=1沖突，H1=(1+1)MOD16=2

沖突，H2=(1+2)MOD16=3

沖突，H3=(1+3)MOD16=4

沖突，H4=(1+4)MOD16=5

沖突，H5=(1+5)MOD16=6

沖突，H6=(1+6)MOD16=7

沖突，H7=(1+7)MOD16=8

沖突，H8=(1+8)MOD16=90123456789101112131415ASL=(1*6+2+3*3+4+9)/12=2.514

168275519208479231110H(19)=6H(14)=1H(23)=10H(1)=1沖突，H1=(1+1)MOD16=2H(68)=3H(20)=7H(84)=6沖突，H1=(6+1)MOD16=7

沖突，H2=(6+2)MOD16=8H(27)=1沖突，H1=(1+1)MOD16=2

沖突，H2=(1+2)MOD16=3

沖突，H3=(1+3)MOD16=4H(11)=11H(10)=10沖突，H1=(10+1)MOD16=11

沖突，H2=(10+2)MOD16=12

(2)用鏈地址法處理沖突012345678910111214^127796855198420231011^^^^^^^^^^^^ASL=(1*6+2*4+3+4)/12=1.75關鍵字(19,14,23,1,68,20,84,27,55,11,10,79)632023/3/14哈希法性能分析哈希法中影響關鍵字比較次數(shù)的因素有三個：哈希函數(shù)、處理沖突的方法以及哈希表的裝填因子,哈希表的裝填因子,它標志著哈希表的裝滿程度。越大，表中記錄數(shù)越多，說明表裝得越滿，發(fā)生沖突的可能性就越大，查找時比較次數(shù)就越多。0≤≤1642023/3/14設哈希函數(shù)H（k）=3Kmod11，散列地址空間為0～10，對關鍵字序列（32,13,49,24,38,21,4,12）按下述兩種解決沖突的方法構造哈希表（1）線性探測再散列（2）鏈地址法并分別求出等概率下查找成功時的平均查找長度ASL。例題652023/3/14散列地址012345678910關鍵字

4

12493813243221

比較次數(shù)

1

1121212

ASLsucc=（1+1+1+2+1+2+1+2）/8=11/8662023/3/14012345678910432131249213824ASLsucc=(5+3*2)/8=11/8672023/3/14總結1.順序表、有序表的查找方法。