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

數(shù)據(jù)結(jié)構(gòu)第8章查找主要內(nèi)容8.1查找的基本概念8.2二分法查找8.3基于索引表的分塊查找8.4散列8.5二叉排序樹和平衡二叉樹查找，也稱為檢索。在我們?nèi)粘Ｉ钪?，隨處可見查找的實(shí)例。如查找某人的地址、電話號(hào)碼；查某單位45歲以上職工等，都屬于查找范疇。本書中，我們規(guī)定查找是按關(guān)鍵字進(jìn)行的，所謂關(guān)鍵字(key)是數(shù)據(jù)元素(或記錄)中某個(gè)數(shù)據(jù)項(xiàng)的值，用它可以標(biāo)識(shí)(或識(shí)別)一個(gè)數(shù)據(jù)元素。例如，描述一個(gè)考生的信息，可以包含：考號(hào)、姓名、性別、年齡、家庭住址、電話號(hào)碼、成績(jī)等關(guān)鍵字。但有些關(guān)鍵字不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素，而有的關(guān)鍵字可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素。如剛才的考生信息中，姓名不能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(因有同名同姓的人)，而考號(hào)可以唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素(每個(gè)考生考號(hào)是唯一的，不能相同)。我們將能唯一標(biāo)識(shí)一個(gè)數(shù)據(jù)元素的關(guān)鍵字稱為主關(guān)鍵字，而其它關(guān)鍵字稱為輔助關(guān)鍵字或從關(guān)鍵字。8.1查找的基本概念——若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；——否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表查找查找成功查找不成功靜態(tài)查找動(dòng)態(tài)查找關(guān)鍵字主關(guān)鍵字次關(guān)鍵字——由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合?！樵?Searching)特定元素是否在表中?！徊檎?，不改變集合內(nèi)的數(shù)據(jù)元素?！炔檎遥指淖儯ㄔ鰷p）集合內(nèi)的數(shù)據(jù)元素。——記錄中某個(gè)數(shù)據(jù)項(xiàng)的值，可用來識(shí)別一個(gè)記錄

(預(yù)先確定的記錄的某種標(biāo)志)

——可以唯一標(biāo)識(shí)一個(gè)記錄的關(guān)鍵字例如“學(xué)號(hào)”例如“女”是一種數(shù)據(jù)結(jié)構(gòu)——識(shí)別若干記錄的關(guān)鍵字8.1查找的基本概念因?yàn)椴檎沂菍?duì)已存入計(jì)算機(jī)中的數(shù)據(jù)所進(jìn)行的操作，所以采用何種查找方法，首先取決于使用哪種數(shù)據(jù)結(jié)構(gòu)來表示“表”，即表中結(jié)點(diǎn)是按何種方式組織的。為了提高查找速度，我們經(jīng)常使用某些特殊的數(shù)據(jù)結(jié)構(gòu)來組織表。因此在研究各種查找算法時(shí)，我們首先必須弄清這些算法所要求的數(shù)據(jù)結(jié)構(gòu)，特別是存儲(chǔ)結(jié)構(gòu)。查找有內(nèi)查找和外查找之分。若整個(gè)查找過程全部在內(nèi)存進(jìn)行，則稱這樣的查找為內(nèi)查找；反之，若在查找過程中還需要訪問外存，則稱之為外查找。我們僅介紹內(nèi)查找。8.1查找的基本概念查找條件、查找操作和查找結(jié)果查找條件：數(shù)據(jù)元素（包含關(guān)鍵字key）。查找操作：比較元素相等，T類的equals(Object)

查找結(jié)果：查找成功，查找不成功。查找是刪除、替換等操作的基礎(chǔ)8.1查找的基本概念（2）對(duì)查找表常用的操作有哪些？查詢某個(gè)“特定的”數(shù)據(jù)元素是否在表中；查詢某個(gè)“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。

（3)有哪些查找方法？

查找方法取決于表中數(shù)據(jù)的排列方式;討論：（1）查找的過程是怎樣的？

給定一個(gè)值K，在含有n個(gè)記錄的文件中進(jìn)行搜索，尋找一個(gè)關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。例如查字典針對(duì)靜態(tài)查找表和動(dòng)態(tài)查找表的查找方法也有所不同?！疤囟ǖ摹?關(guān)鍵字8.1查找的基本概念明確：查找的過程就是將給定的K值與文件中各記錄的關(guān)鍵字項(xiàng)進(jìn)行比較的過程。所以用比較次數(shù)的平均值來評(píng)估算法的優(yōu)劣。稱為平均查找長(zhǎng)度（ASL：averagesearchlength）。其中：n是文件記錄個(gè)數(shù)；Pi是查找第i個(gè)記錄的查找概率（通常取等概率,即Pi=1/n）;Ci是找到第i個(gè)記錄時(shí)所經(jīng)歷的比較次數(shù)。統(tǒng)計(jì)意義上的數(shù)學(xué)期望值物理意義：假設(shè)每一元素被查找的概率相同，則查找每一元素所需的比較次數(shù)之總和再取平均，即為ASL。顯然，ASL值越小，時(shí)間效率越高。（4）如何評(píng)估查找方法的優(yōu)劣？?=×=niiiCPASL18.1查找的基本概念針對(duì)靜態(tài)查找表的查找算法主要有：

一、順序查找（線性查找）二、二分查找（二分或?qū)Ψ植檎遥┤?、分塊查找（索引順序查找）線性表查找8.1查找的基本概念順序查找（sequentialsearch，又稱線性查找--linearsearch）即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。

對(duì)順序結(jié)構(gòu)如何線性查找？對(duì)單鏈表結(jié)構(gòu)如何線性查找？對(duì)非線性樹結(jié)構(gòu)如何順序查找?順序查找8.1查找的基本概念順序查找的基本思想順序查找是一種最簡(jiǎn)單的查找方法，它的基本思想是：從表的一端開始，順序掃描線性表，依次將掃描到的結(jié)點(diǎn)關(guān)鍵字和待找的值Ｋ相比較，若相等，則查找成功，若整個(gè)表掃描完畢，仍末找到關(guān)鍵字等于Ｋ的元素，則查找失敗。順序查找既適用于順序表，也適用于鏈表。若用順序表，查找可從前往后掃描，也可從后往前掃描，但若采用單鏈表，則只能從前往后掃描。另外，順序查找的表中元素可以是無序的。順序查找的存儲(chǔ)結(jié)構(gòu)要求8.1查找的基本概念8.1查找的基本概念順序查找順序表查找的算法實(shí)現(xiàn)線性表的順序查找intsearch(Tkey)//順序表SeqList<T>Node<T>search(Tkey)//SinglyList<T>DoubleNode<T>search(Tkey)//CirDoublyList<T>8.1查找的基本概念非線性表的順序查找BinaryNode<T>search(Tkey)//BinaryTree<T>TreeNode<T>search(Tkey)//Tree<T>順序表查找的算法實(shí)現(xiàn)8.1查找的基本概念優(yōu)點(diǎn)：算法簡(jiǎn)單，且對(duì)順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點(diǎn)：ASL太長(zhǎng)，時(shí)間效率太低。討論：順序查找的特點(diǎn)：討論

：如何計(jì)算ASL？分析：查找第1個(gè)元素所需的比較次數(shù)為1；查找第2個(gè)元素所需的比較次數(shù)為2；……查找第n個(gè)元素所需的比較次數(shù)為n；總計(jì)全部比較次數(shù)為：1＋2＋…＋n=(1+n)n/2未考慮查找不成功的情況：查找哨兵所需的比較次數(shù)為n+1這是查找成功的情況若求某一個(gè)元素的平均查找次數(shù)，還應(yīng)當(dāng)除以n（等概率），即：ASL＝（1＋n）/2，時(shí)間效率為O(n)順序查找8.1查找的基本概念順序查找8.1查找的基本概念排序線性表的順序查找算法及效率//排序線性表，覆蓋，采用T類的compareTo(T)方法（實(shí)現(xiàn)java.lang.Comparable<T>接口）比較對(duì)象相等和大小。intsearch(Tkey)//SortedSeqList<T>Node<T>search(Tkey)//SortedSinglyList<T>DoubleNode<T>search(Tkey)

//SortedCirDoublyList<T>8.1查找的基本概念提高查找效率的措施基本原則是縮小查找范圍。數(shù)據(jù)元素排序：以事先準(zhǔn)備時(shí)間換取查找時(shí)間。排序線性表建立索引：以空間換取時(shí)間。字典采用順序存儲(chǔ)結(jié)構(gòu)，事先按字母排序并建立多級(jí)索引。散列存儲(chǔ)建立二叉排序樹8.1查找的基本概念這是一種容易想到的查找方法:先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至右半部?jī)?nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。對(duì)順序表結(jié)構(gòu)如何編程實(shí)現(xiàn)二分查找算法？

對(duì)單鏈表結(jié)構(gòu)如何二分查找？對(duì)非線性(樹)結(jié)構(gòu)如何二分查找？

8.2二分法查找②運(yùn)算步驟：(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，說明查找成功，元素序號(hào)=mid;結(jié)束條件：（1）查找成功：ST.elem[mid].key=key

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

（意即區(qū)間長(zhǎng)度小于0）解：①先設(shè)定3個(gè)輔助標(biāo)志:

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

已知如下11個(gè)元素的有序表：

（0513192137566475808892）,請(qǐng)查找關(guān)鍵字為21和85的數(shù)據(jù)元素。顯然有：mid=(low+high)/2二分查找演示8.2二分法查找二分查找：（1）mid=(low+high)/2」

（2）比較ST.elem[mid].key==key?

如果ST.elem[mid].key==key，則查找成功，返回mid值如果ST.elem[mid].key>key，則置high=mid-1

如果ST.elem[mid].key<key，則置low=mid+1(3)重復(fù)計(jì)算mid以及比較ST.elem[mid].key與key，當(dāng)low>high時(shí)，表明查找不成功，查找結(jié)束。8.2二分法查找二分查找舉例8.2二分法查找二分查找算法實(shí)現(xiàn)publicclassSortedArray{//已知value數(shù)組元素按升序排序，在begin～end范圍內(nèi)，二分法查找關(guān)鍵字為key元素，若查找成功返回下標(biāo)，否則返回-1；若begin、end越界，返回-1publicstatic<TextendsComparable<?superT>>

intbinarySearch(T[]value,intbegin,intend,Tkey)

publicstatic<TextendsComparable<?superT>>intbinarySearch(T[]value,Tkey)}8.2二分法查找publicstaticintcount=0;//統(tǒng)計(jì)比較次數(shù)，計(jì)算ASL成功

//已知value數(shù)組元素按升序排序，在begin～end范圍內(nèi)，二分法查找關(guān)鍵字為key元素，若查找成功返回下標(biāo)，否則返回-1；

//若begin、end越界，返回-1。若key==null，Java拋出空對(duì)象異常。

publicstatic<TextendsComparable<?superT>>intbinarySearch(T[]value,intbegin,intend,Tkey){count=0;//統(tǒng)計(jì)比較次數(shù)，計(jì)算ASL成功

while(begin<=end)//邊界有效

{intmid=(begin+end)/2;//取中間位置，當(dāng)前比較元素位置

System.out.print("["+mid+"]="+value[mid]+"？");//顯示比較中間結(jié)果，可省略

count++;if(pareTo(value[mid])==0)//兩對(duì)象相等

returnmid;//查找成功

if(pareTo(value[mid])<0)//key對(duì)象較小

end=mid-1;//查找范圍縮小到前半段

elsebegin=mid+1;//查找范圍縮小到后半段

}return-1;//查找不成功

}//已知value數(shù)組元素按升序排序，二分法查找關(guān)鍵字為key元素，若查找成功返回下標(biāo)，否則返回-1publicstatic<TextendsComparable<?superT>>intbinarySearch(T[]value,Tkey){returnbinarySearch(value,0,value.length-1,key);}二分查找算法實(shí)現(xiàn)8.2二分法查找【思考題8-1】二分查找的遞歸算法publicstaticintbinarySearch(int[]value,intkey,intbegin,intend){if(begin<=end)

{intmid=(begin+end)/2;

if(value[mid]==key)returnmid;

if(key<value[mid])

returnbinarySearch(value,key,begin,mid-1);

returnbinarySearch(value,key,mid+1,end);

}return-1;}8.2二分法查找查找過程可用二叉樹描述：每個(gè)記錄用一個(gè)結(jié)點(diǎn)表示；結(jié)點(diǎn)中值為該記錄在表中位置，這個(gè)描述查找過程的二叉樹稱為判定樹。n個(gè)元素的表的二分查找的判定樹是唯一的，即：判定樹由表中元素個(gè)數(shù)決定。

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

比較的關(guān)鍵字個(gè)數(shù)：為該結(jié)點(diǎn)在判定樹上的層次數(shù)。二分查找效率分析法8.2二分法查找二叉判定樹二分查找算法分析8.2二分法查找查找成功的情形查找不成功的情形從有序表構(gòu)造出的二叉查找樹(判定樹)

若設(shè)n=2h-1，則描述對(duì)分查找的二叉查找樹是高度為h

的滿二叉樹。2h=n+1,h=log2(n+1)。第1層結(jié)點(diǎn)有1個(gè)，查找第1層結(jié)點(diǎn)要比較1次；第2層結(jié)點(diǎn)有2個(gè)，查找第2層結(jié)點(diǎn)要比較2次；…，8.2二分法查找查找成功時(shí)比較的關(guān)鍵字個(gè)數(shù)最多不超過樹的深度d:d=log2n+1

若所有結(jié)點(diǎn)的空指針域設(shè)置為一個(gè)指向一個(gè)方形結(jié)點(diǎn)的指針，稱方形結(jié)點(diǎn)為判定樹的外部結(jié)點(diǎn)；對(duì)應(yīng)的，圓形結(jié)點(diǎn)為內(nèi)部結(jié)點(diǎn)。

查找不成功的過程就是走了一條從根結(jié)點(diǎn)到外部結(jié)點(diǎn)的路徑。二分查找效率分析法8.2二分法查找習(xí)題8-9二分法查找{5,17,20,32,43,55,61,61*,72,96}，查找96、35、61，分別與哪些元素比較？畫出相應(yīng)的二叉判定樹，計(jì)算和。查找96，比較{43,61*,72,96}查找35，比較{43,17,20,32}8.2二分法查找習(xí)題8-9二分法查找首次出現(xiàn)元素查找61，比較{43,61*}查找72*，比較{43,72}8.2二分法查找分塊查找（索引順序查找）這是一種順序查找的另一種改進(jìn)方法。先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個(gè)子表中的數(shù)值（用關(guān)鍵字更準(zhǔn)確）都比后一塊中數(shù)值小（但子表內(nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個(gè)索引表，表中還要包含每個(gè)子表的起始地址（即頭指針）。索引表最大關(guān)鍵字起始地址2212138920334244382448605874498653第1塊第2塊第3塊例：2248861713特點(diǎn)：塊間有序，塊內(nèi)無序8.3基于索引表的分塊查找索引與分塊查找索引項(xiàng)完全索引表不完全索引分塊查找查找索引表在一塊中查找key8.3基于索引表的分塊查找查找步驟分兩步進(jìn)行：①對(duì)索引表使用二分查找法（因?yàn)樗饕硎怯行虮恚?；②確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因?yàn)楦髯颖韮?nèi)部是無序表）；查找效率：ASL=Lb+Lw對(duì)索引表查找的ASL對(duì)塊內(nèi)查找的ASLS為每塊內(nèi)部的記錄個(gè)數(shù)，n/s即塊的數(shù)目例如當(dāng)n=9，s=3時(shí)，ASLbs=3.5,而二分法為3.1,順序法為58.3基于索引表的分塊查找字典的分塊查找【例8.1】判斷一個(gè)字符串是否為Java關(guān)鍵字。8.3基于索引表的分塊查找PublicclassKeyWordprivatestaticString[]keywords={"abstract","boolean",……};

//排序主表privatestaticclassIndexItemimplementsComparable<IndexItem>//索引項(xiàng){charfirst;//首字符

intbegin,end;//塊的始末下標(biāo)

publicIndexItem(charfirst,intbegin,intend)

publicStringtoString()publicintcompareTo(IndexItemitem)比較相等和大小}privatestaticIndexItem[]index;//索引表static//創(chuàng)建擴(kuò)充索引表；靜態(tài)初始化塊，類加載時(shí)執(zhí)行一次publicstaticbooleanisKeyword(Stringstr)//判斷str是否關(guān)鍵字8.3基于索引表的分塊查找支持插入和刪除操作的索引結(jié)構(gòu)及其分塊查找（1）以排序順序表存儲(chǔ)缺點(diǎn)：順序查找插入或刪除，移動(dòng)8.3基于索引表的分塊查找各塊分散存儲(chǔ)，鏈?zhǔn)剿饕秉c(diǎn)：塊滿，擴(kuò)容8.3基于索引表的分塊查找塊單鏈表存儲(chǔ)8.3基于索引表的分塊查找考慮：如果邊查找邊插入刪除（動(dòng)態(tài)查找），采用以上方法有什么缺點(diǎn)？？？如何解決？？？線性查找

8.3基于索引表的分塊查找

在線性表、樹結(jié)構(gòu)中查找紀(jì)錄是通過與關(guān)鍵字的“比較”完成的：順序查找，比較的結(jié)果為“=”或“≠”非順序查找，比較的結(jié)果為“<”，“=”，“>”

散列的思想：根據(jù)紀(jì)錄的關(guān)鍵字直接找到記錄的存儲(chǔ)位置，即為關(guān)鍵字和記錄的存儲(chǔ)位置建立一個(gè)對(duì)應(yīng)關(guān)系f，使每個(gè)關(guān)鍵字和結(jié)構(gòu)中一個(gè)唯一的存儲(chǔ)位置相對(duì)應(yīng)。對(duì)應(yīng)關(guān)系f為散列函數(shù)，按該思想建立的表為散列表。散列技術(shù)（HASH）8.4散列

根據(jù)設(shè)定的哈希函數(shù)H(key)和處理沖突的方法將一組關(guān)鍵字映像到一個(gè)有限的連續(xù)的地址集（區(qū)間）上，并以關(guān)鍵字在地址集中的“像”作為紀(jì)錄在表中的存儲(chǔ)位置，這種表便稱為哈希表，這一影像過程稱為哈希造表或散列，所得存儲(chǔ)位置稱哈希地址或散列地址。哈希（HASH）表的定義：8.4散列散列方法在表項(xiàng)的存儲(chǔ)位置與它的關(guān)鍵字之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系Hash()，使每個(gè)關(guān)鍵字與結(jié)構(gòu)中一個(gè)唯一存儲(chǔ)位置相對(duì)應(yīng)：

Address＝Hash(Rec.key)在查找時(shí)，首先對(duì)表項(xiàng)的關(guān)鍵字進(jìn)行函數(shù)計(jì)算，把函數(shù)值當(dāng)做表項(xiàng)的存儲(chǔ)位置，在結(jié)構(gòu)中按此位置取表項(xiàng)比較。若關(guān)鍵字相等，則查找成功。在存放表項(xiàng)時(shí)，依相同函數(shù)計(jì)算存儲(chǔ)位置，并按此位置存放。8.4散列選取某個(gè)函數(shù)，依該函數(shù)按關(guān)鍵字計(jì)算元素的存儲(chǔ)位置，并按此存放；查找時(shí)，由同一個(gè)函數(shù)對(duì)給定值k計(jì)算地址，將k與地址單元中元素關(guān)鍵碼進(jìn)行比較，確定查找是否成功。通常關(guān)鍵碼的集合比哈希地址集合大得多，因而經(jīng)過哈希函數(shù)變換后，可能將不同的關(guān)鍵碼映射到同一個(gè)哈希地址上，這種現(xiàn)象稱為沖突。哈希方法(雜湊法)哈希函數(shù)(雜湊函數(shù))哈希表(雜湊表)

沖突哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希函數(shù)(雜湊函數(shù))按上述思想構(gòu)造的表稱為哈希表(雜湊表)

8.4散列有6個(gè)元素的關(guān)鍵碼分別為：（14，23，39，9，25，11）。選取關(guān)鍵碼與元素位置間的函數(shù)為H(k)=kmod7通過哈希函數(shù)對(duì)6個(gè)元素建立哈希表：253923914沖突現(xiàn)象舉例：6個(gè)元素用7個(gè)地址應(yīng)該足夠!H(14)=14%7=011H(25)=25%7=4H(11)=11%7=4有沖突！01234568.4散列散列函數(shù)與沖突散列函數(shù)i=hash(key)沖突8.4散列（裝填因子通常取值0.75）所以，哈希方法必須解決以下兩個(gè)問題：1）構(gòu)造好的哈希函數(shù)（a）所選函數(shù)盡可能簡(jiǎn)單，以便提高轉(zhuǎn)換速度；（b）所選函數(shù)對(duì)關(guān)鍵碼計(jì)算出的地址，應(yīng)在哈希地址集中大致均勻分布，以減少空間浪費(fèi)。2）制定一個(gè)好的解決沖突的方案查找時(shí)，如果從哈希函數(shù)計(jì)算出的地址中查不到關(guān)鍵碼，則應(yīng)當(dāng)依據(jù)解決沖突的規(guī)則，有規(guī)律地查詢其它相關(guān)單元。在哈希查找方法中，沖突是不可能避免的，只能盡可能減少。8.4散列哈希函數(shù)的構(gòu)造方法常用的哈希函數(shù)構(gòu)造方法有：直接定址法除留余數(shù)法

乘余取整法數(shù)字分析法平方取中法折疊法隨機(jī)數(shù)法要求一：n個(gè)數(shù)據(jù)原僅占用n個(gè)地址，雖然散列查找是以空間換時(shí)間，但仍希望散列的地址空間盡量小。要求二：無論用什么方法存儲(chǔ)，目的都是盡量均勻地存放元素，以避免沖突。8.4散列Hash(key)=a·key+b(a、b為常數(shù))優(yōu)點(diǎn)：以關(guān)鍵碼key的某個(gè)線性函數(shù)值為哈希地址，不會(huì)產(chǎn)生沖突.缺點(diǎn)：要占用連續(xù)地址空間，空間效率低。

例：關(guān)鍵碼集合為{100，300，500，700，800，900}，選取哈希函數(shù)為Hash(key)=key/100，則存儲(chǔ)結(jié)構(gòu)（哈希表）如下：01234567899008007005003001001、直接定址法8.4散列哈希函數(shù)的構(gòu)造方法Hash(key)=keymodp(p是一個(gè)整數(shù))特點(diǎn)：以關(guān)鍵碼除以p的余數(shù)作為哈希地址。關(guān)鍵：如何選取合適的p？技巧：若設(shè)計(jì)的哈希表長(zhǎng)為m，則一般取p≤m且為質(zhì)數(shù)

（也可以是不包含小于20質(zhì)因子的合數(shù)）。2、除留余數(shù)法散列表長(zhǎng)度8163264128256最大素?cái)?shù)71331611272518.4散列哈希函數(shù)的構(gòu)造方法Hash(key)=B*(A*keymod1)

(A、B均為常數(shù)，且0<A<1，B為整數(shù))特點(diǎn)：以關(guān)鍵碼key乘以A，取其小數(shù)部分，然后再放大B倍并取整，作為哈希地址。3、乘余取整法（A*keymod1）就是取A*key的小數(shù)部分例：欲以學(xué)號(hào)最后兩位作為地址，則哈希函數(shù)應(yīng)為：

H(k)=100*(0.01*k%1)其實(shí)也可以用法2實(shí)現(xiàn)：H(k)=k%1008.4散列哈希函數(shù)的構(gòu)造方法特點(diǎn)：某關(guān)鍵字的某幾位組合成哈希地址。所選的位應(yīng)當(dāng)是：各種符號(hào)在該位上出現(xiàn)的頻率大致相同。34705243491487348269634852703486305349805834796713473919例：有一組（例如80個(gè)）關(guān)鍵碼，其樣式如下：4、數(shù)字分析法討論：①第1、2位均是“3和4”，第3位也只有“

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

若哈希地址取兩位（因元素僅80個(gè)），則可取這四位中的任意兩位組合成哈希地址，也可以取其中兩位與其它兩位疊加求和后，取低兩位作哈希地址。8.4散列哈希函數(shù)的構(gòu)造方法特點(diǎn)：對(duì)關(guān)鍵碼平方后，按哈希表大小，取中間的若干位作為哈希地址。理由：因?yàn)橹虚g幾位與數(shù)據(jù)的每一位都相關(guān)。例：2589的平方值為6702921，可以取中間的029為地址。5、平方取中法8.4散列哈希函數(shù)的構(gòu)造方法6、折疊法特點(diǎn)：將關(guān)鍵碼自左到右分成位數(shù)相等的幾部分（最后一部分位數(shù)可以短些），然后將這幾部分疊加求和，并按哈希表表長(zhǎng)，取后幾位作為哈希地址。適用于：每一位上各符號(hào)出現(xiàn)概率大致相同的情況。法1：移位法──將各部分的最后一位對(duì)齊相加。法2：間界疊加法──從一端向另一端沿分割界來回折疊后，最后一位對(duì)齊相加。例：元素42751896,用法1：427＋518＋96=1041

用法2：42751896—>724+518+69=13118.4散列哈希函數(shù)的構(gòu)造方法7、隨機(jī)數(shù)法Hash(key)=random(key)(random為偽隨機(jī)函數(shù))適用于：關(guān)鍵字長(zhǎng)度不等的情況。造表和查找都很方便。8.4散列哈希函數(shù)的構(gòu)造方法①執(zhí)行速度（即計(jì)算哈希函數(shù)所需時(shí)間）；②關(guān)鍵字的長(zhǎng)度；③哈希表的大??；④關(guān)鍵字的分布情況；⑤查找頻率。小結(jié)：構(gòu)造哈希函數(shù)的原則：8.4散列哈希函數(shù)的構(gòu)造方法常見的沖突處理方法有：開放定址法（開地址法）鏈地址法（拉鏈法）再哈希法（雙哈希函數(shù)法）建立一個(gè)公共溢出區(qū)8.4散列沖突處理1、開放定址法（開地址法）設(shè)計(jì)思路：有沖突時(shí)就去尋找下一個(gè)空的哈希地址，只要哈希表足夠大，空的哈希地址總能找到，并將數(shù)據(jù)元素存入。具體實(shí)現(xiàn)：Hi=(Hash(key)+di)modm(1≤i<m)

其中：

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

m為哈希表長(zhǎng)度

di

為增量序列1，2，…m-1，且di=i1.線性探測(cè)法含義：一旦沖突，就找附近（下一個(gè)）空地址存入。開放定址法建立散列表演示8.4散列沖突處理關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}，設(shè)：哈希表表長(zhǎng)為m=11；哈希函數(shù)為Hash(key)=keymod11；擬用線性探測(cè)法處理沖突。建哈希表如下：解釋：①47、7（以及11、16、92）均是由哈希函數(shù)得到的沒有沖突的哈希地址；012345678910477△▲△△例：291116922283②Hash(29)=7，哈希地址有沖突，需尋找下一個(gè)空的哈希地址：由H1=(Hash(29)+1)mod11=8，哈希地址8為空，因此將29存入。③

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

還連續(xù)移動(dòng)了兩次（二次聚集）8.4散列沖突處理線性探測(cè)法的優(yōu)點(diǎn)：只要哈希表未被填滿，保證能找到一個(gè)空地址單元存放有沖突的元素；線性探測(cè)法的缺點(diǎn)：可能使第i個(gè)哈希地址的同義詞存入第i+1個(gè)哈希地址，這樣本應(yīng)存入第i+1個(gè)哈希地址的元素變成了第i+2個(gè)哈希地址的同義詞，……，因此，可能出現(xiàn)很多元素在相鄰的哈希地址上“堆積”起來，大大降低了查找效率。解決方案：可采用二次探測(cè)法或偽隨機(jī)探測(cè)法，以改善“堆積”問題。討論：8.4散列沖突處理仍舉上例，關(guān)鍵碼集為{47，7，29，11，16，92，22，8，3}改用二次探測(cè)法處理沖突，建表如下：012345678910112234792167298△▲△△注：只有3這個(gè)關(guān)鍵碼的沖突處理與上例不同，Hash(3)=3，哈希地址上沖突，由H1=(Hash(3)+12)mod11=4，仍然沖突；H2=(Hash(3)-12)mod11=2，找到空的哈希地址，存入。2.二次探測(cè)法Hi=(Hash(key)±di)modm其中：Hash(key)為哈希函數(shù)

m為哈希表長(zhǎng)度，m要求是某個(gè)4k+3的質(zhì)數(shù)；

di為增量序列

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

3.若di＝偽隨機(jī)序列，就稱為偽隨機(jī)探測(cè)法8.4散列沖突處理2、鏈地址法(拉鏈法）基本思想：將具有相同哈希地址的記錄鏈成一個(gè)單鏈表，m個(gè)哈希地址就設(shè)m個(gè)單鏈表，然后用一個(gè)數(shù)組將m個(gè)單鏈表的表頭指針存儲(chǔ)起來，形成一個(gè)動(dòng)態(tài)的結(jié)構(gòu)。

設(shè){47,7,29,11,16,92,22,8,3,50,37,89}的哈希函數(shù)為：Hash(key)=keymod11，用拉鏈法處理沖突，則建表如右圖所示。

例：

01234567891022118934737922971650810注：有沖突的元素可以插在表尾,也可以插在表頭8.4散列沖突處理鏈地址法散列數(shù)組同義詞單鏈表計(jì)算i=hash(key)，O(1)

查找插入刪除8.4散列沖突處理圖8.12（a）鏈地址法散列表（a）散列表滿，元素個(gè)數(shù)=散列表容量×裝填因子8.4散列沖突處理圖8.12（b）

散列表擴(kuò)充容量（b）添加10，擴(kuò)充散列表容量為原2倍，各元素重新存儲(chǔ)8.4散列沖突處理習(xí)題8-12散列表采用鏈地址法設(shè)初始容量length為10；散列函數(shù)hash(key)=key%length；裝填因子為0.75，散列數(shù)組容量以2倍擴(kuò)充。關(guān)鍵字序列{16,75,60,43,54,90,46,31,27,88,64,50}構(gòu)造散列表，分別畫出擴(kuò)容前和最終狀態(tài)圖，計(jì)算。8.4散列沖突處理習(xí)題解答8-128.4散列沖突處理3、再哈希法（雙哈希函數(shù)法）Hi=RHi(key)i=1,2,…，kRHi均是不同的哈希函數(shù)，當(dāng)產(chǎn)生沖突時(shí)就計(jì)算另一個(gè)哈希函數(shù)，直到?jīng)_突不再發(fā)生。優(yōu)點(diǎn)：不易產(chǎn)生聚集；缺點(diǎn)：增加了計(jì)算時(shí)間。4.建立一個(gè)公共溢出區(qū)思路：除設(shè)立哈希基本表外，另設(shè)立一個(gè)溢出向量表。 所有關(guān)鍵字和基本表中關(guān)鍵字為同義詞的記錄，不管它們由哈希函數(shù)得到的地址是什么，一旦發(fā)生沖突，都填入溢出表。8.4散列沖突處理構(gòu)造鏈地址法的散列表publicclassHashSet<T>//散列表類{privateSinglyList<T>[]table; //散列表，同義詞單鏈表對(duì)象數(shù)組

publicHashSet(intlength)

publicHashSet()

privateinthash(Tx)//散列函數(shù)

publicTsearch(Tkey)//查找

publicbooleanadd(Tx)

//插入publicvoidremove(Tkey)//刪除}【思考題8-3】實(shí)現(xiàn)contains(key)、toString()等。8.4散列T類定義對(duì)象的散列碼privateinthash(Tx)//散列函數(shù){intkey=Math.abs(x.hashCode());//對(duì)象散列碼returnkey%this.table.length;}publicclassObject{inthashCode()//對(duì)象散列碼，約定對(duì)象到int的一對(duì)一映射}publicfinalclassInteger

//子類{publicinthashCode()//整數(shù)對(duì)象散列碼是其值，覆蓋

{returnvalue;}}8.4散列【例8.2】使用散列表表示元素互異的集合

//產(chǎn)生n個(gè)互異的隨機(jī)數(shù)publicstaticInteger[]randomDifferent(intn,intsize){Integer[]values=newInteger[n];HashSet<Integer>set=newHashSet<Integer>();//互異，查找不成功時(shí)插入set}8.4散列散列映射映射映射（Map）是指實(shí)現(xiàn)數(shù)學(xué)中“映射”概念的集合。元素結(jié)構(gòu)結(jié)構(gòu)如下，關(guān)鍵字不能重復(fù)。映射元素（關(guān)鍵字，值）提供從關(guān)鍵字到值的映射功能，即根據(jù)關(guān)鍵字查找值。8.4散列映射接口Map<K,V>

//映射接口，K、V指定映射元素的關(guān)鍵字和值的數(shù)據(jù)類型publicinterfaceMap<K,V>{booleanisEmpty();//判空

int

size();//元素個(gè)數(shù)

StringtoString();//描述字符串

Vget(Kkey);//關(guān)鍵字key映射的值

Vput(Kkey,Vvalue);//添加元素(鍵,值)；關(guān)鍵字相同，替換

Vremove(Kkey);//刪除關(guān)鍵字為key元素

booleancontainsKey(Kkey); //包含

voidclear();//刪除所有元素

Object[]values();//返回包含值集合的數(shù)組}8.4散列散列映射的實(shí)現(xiàn)publicclassKeyValue<K,V>//映射元素類{finalKkey;//關(guān)鍵字，最終變量

Vvalue;//值

publicKeyValue(Kkey,Vvalue)publicStringtoString()//描述串“(關(guān)鍵字,值)”publicfinalinthashCode()//散列碼publicbooleanequals(Objectobj)//僅比較關(guān)鍵字}8.4散列散列映射類//散列映射類，實(shí)現(xiàn)Map<K,V>接口publicclassHashMap<K,V>implementsMap<K,V>{HashSet<KeyValue<K,V>>set;//散列表publicHashMap(intlength)publicHashMap()publicbooleanisEmpty()//判空publicVget(Kkey)//關(guān)鍵字key映射的值publicVput(Kkey,Vvalue)//添加映射元素publicVremove(Kkey)//刪除publicHashSet<K>keySet()//返回關(guān)鍵字集合}8.4散列【例8.3】采用散列映射，統(tǒng)計(jì)文本中各字符的出現(xiàn)次數(shù)Huffman算法已知給定文本的字符集合和權(quán)值集合。設(shè)字符串為“classHash”，8.4散列

例給定關(guān)鍵字序列11，78，10，1，3，2，4，21，試分別用順序查找、二分查找、二叉排序樹查找、散列查找(用線性探查法和拉鏈法)來實(shí)現(xiàn)查找，試畫出它們的對(duì)應(yīng)存儲(chǔ)形式(順序查找的順序表，二分查找的判定樹，二叉排序樹查找的二叉排序樹及兩種散列查找的散列表)，并求出每一種查找的成功平均查找長(zhǎng)度。散列函數(shù)H(k)=k%11。順序查找的順序表（一維數(shù)組）如圖9-8所示，從圖9-8可以得到順序查找的成功平均查找長(zhǎng)度為：ASL=(1+2+3+4+5+6+7+8)/8=4.5；8.4散列二分查找的判定樹（中序序列為從小到大排列的有序序列）如圖9-9示，從圖9-9可以得到二分查找的成功平均查找長(zhǎng)度為：ASL=(1+2*2+3*4+4)/8=2.625；8.4散列二叉排序樹（關(guān)鍵字順序已確定，該二叉排序樹應(yīng)唯一）如圖9-10所示，從圖9-10可以得到二叉排序樹查找的成功平均查找長(zhǎng)度為：ASL=(1+2*2+3*2+4+5*2)=3.125；8.4散列線性探查法解決沖突的散列表如圖9-11所示，從圖9-11可以得到線性探查法的成功平均查找長(zhǎng)度為：ASL=（1+1+2+1+3+2+1+8）/8=2.375；8.4散列10^4^3^278^11^21^1012345678910拉鏈法解決沖突的散列表如圖9-12所示。從圖9-12可以得到拉鏈法的成功平均查找長(zhǎng)度為：ASL=(1*6+2*2)/8=1.25。圖9-12拉鏈法的散列表8.4散列一、二叉排序樹（Binary Sort Tree）的定義（a）（b）練：下列2種圖形中，哪個(gè)不是二叉排序樹？--或是一棵空樹；或者是具有如下性質(zhì)（BST性質(zhì)）的非空二叉樹：

（1）左子樹的所有結(jié)點(diǎn)均小于根的值；（2）右子樹的所有結(jié)點(diǎn)均大于或等于根的值；（3）它的左右子樹也分別為二叉排序樹。討論：對(duì)(a)中序遍歷后的結(jié)果是什么？二叉排序樹8.5二叉排序樹和平衡二叉樹二、二叉排序樹的特點(diǎn)由BST性質(zhì)可得：元素可比較相等和大小，關(guān)鍵字互不相同。結(jié)點(diǎn)，左子樹元素均小于該結(jié)點(diǎn)，右子樹元素均大于該結(jié)點(diǎn)。左、右子樹也是二叉排序樹。中根次序遍歷，升序序列。二叉排序樹8.5二叉排序樹和平衡二叉樹【思考題8-4】畫出關(guān)鍵字序列為{1,2,3}的所有形態(tài)的二叉排序樹。//答見教案二叉排序樹8.5二叉排序樹和平衡二叉樹將1～9填入如圖所示的二叉樹中，構(gòu)造一棵二叉排序樹，計(jì)算。習(xí)題8-19二叉排序樹8.5二叉排序樹和平衡二叉樹三、二叉排序樹的插入與刪除將數(shù)據(jù)元素構(gòu)造成二叉排序樹的優(yōu)點(diǎn)：①查找過程與順序結(jié)構(gòu)有序表中的二分查找相似，查找效率高；②中序遍歷此二叉樹，將會(huì)得到一個(gè)關(guān)鍵字的有序序列（即實(shí)現(xiàn)了排序運(yùn)算）；③如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點(diǎn)上，而且插入或刪除時(shí)只需修改指針而不需移動(dòng)元素。注：若數(shù)據(jù)元素的輸入順序不同，則得到的二叉排序樹形態(tài)也不同！——這種既查找又插入的過程稱為動(dòng)態(tài)查找。二叉排序樹既有類似于二分查找的特性，又采用了鏈表存儲(chǔ)，它是動(dòng)態(tài)查找表的一種適宜表示。二叉排序樹8.5二叉排序樹和平衡二叉樹4524531290如果待查找的關(guān)鍵字序列輸入順序?yàn)椋海?4，53，45，45，12，24，90），2453451290查找成功，返回查找成功，返回討論1：二叉排序樹的插入和查找操作則生成二叉排序樹的過程為：例：輸入待查找的關(guān)鍵字序列=（45，24，53，45，12，24，90）則生成的二叉排序樹形態(tài)不同：查找成功，返回查找成功，返回二叉排序樹8.5二叉排序樹和平衡二叉樹二叉排序樹的構(gòu)造過程：從空樹出發(fā)，依次插入R1～

Rn各數(shù)據(jù)值：（1）如果二叉排序樹是空樹，則插入結(jié)點(diǎn)就是二叉排序樹的根結(jié)點(diǎn)；（2）如果二叉排序樹是非空的，則插入值與跟結(jié)點(diǎn)比較，若小于根結(jié)點(diǎn)的值，就插入到左子樹中去；否則插入到右子樹中。算法實(shí)現(xiàn)：不要求二叉排序樹8.5二叉排序樹和平衡二叉樹二叉排序樹的查找&插入算法如何實(shí)現(xiàn)？查找算法靜態(tài)查找算法動(dòng)態(tài)查找算法（插入）二叉排序樹8.5二叉排序樹和平衡二叉樹二叉排序樹的靜態(tài)查找思想：從根開始若key==p.data，則查找成功返回；若key<p.data，則查找p的左子樹；否則查找p的右子樹。重復(fù)執(zhí)行②，直到p為空，查找不成功。二叉排序樹8.5二叉排序樹和平衡二叉樹二叉排序樹8.5二叉排序樹和平衡二叉樹二叉排序樹的動(dòng)態(tài)查找算法查找算法：若二叉排序樹為空，則返回插入位置，否則，先拿根結(jié)點(diǎn)值與待查值進(jìn)行比較，若相等，則查找成功，若根結(jié)點(diǎn)值大于待查值，則進(jìn)入左子樹重復(fù)此步驟，否則，進(jìn)入右子樹重復(fù)此步驟。插入算法：若二叉排序樹為空，則被查結(jié)點(diǎn)為新的根節(jié)點(diǎn)；否則，作為一個(gè)新的葉子結(jié)點(diǎn)插入在由查找返回的位置上。算法：不做要求二叉排序樹8.5二叉排序樹和平衡二叉樹插入40二叉排序樹8.5二叉排序樹和平衡二叉樹構(gòu)造二叉排序樹{54,18,12,81,99,36,12,76,57,6,66,40}二叉排序樹8.5二叉排序樹和平衡二叉樹習(xí)題8-20畫出由以下關(guān)鍵字序列構(gòu)造的一棵二叉排序樹，計(jì)算。{50,16,74,60,43,16,90,46,31,29, 88,71,64,13,65}二叉排序樹8.5二叉排序樹和平衡二叉樹二叉樹的三叉鏈表結(jié)點(diǎn)類publicclassTriNode<T>{publicTdata;

publicTriNode<T>parent,left,right;

publicTriNode(Tdata,TriNode<T>parent,TriNode<T>left,TriNode<T>right)

publicTriNode(Tdata)publicTriNode()publicStringtoString()publicbooleanisLeaf()}二叉排序樹8.5二叉排序樹和平衡二叉樹二叉排序樹類publicclassBinarySortTree<TextendsComparable<?superT>>{TriNode<T>root;//根

BinarySortTree()//構(gòu)造空樹BinarySortTree(T[]values)booleanisEmpty()TriNode<T>searchNode(Tkey)//查找結(jié)點(diǎn)Tsearch(Tkey)//查找元素booleanadd(Tx)//插入}二叉排序樹8.5二叉排序樹和平衡二叉樹中根次序迭代遍歷TriNode<T>first(TriNode<T>p)TriNode<T>next(TriNode<T>p)StringtoString()二叉排序樹8.5二叉排序樹和平衡二叉樹【思考題8-5】BinarySortTree<T>類的成員方法voidinorderPrevious()//中根次序遍歷（逆序）TriNode<T>last(TriNode<T>p)//p子樹最后一個(gè)結(jié)點(diǎn)TriNode<T>previous(TriNode<T>p)//p的前驅(qū)結(jié)點(diǎn)booleancontains(Tkey)//判斷否包含keyvoidaddAll(T[]values)//插入values數(shù)組元素voidclear() //刪除所有元素intsize() //元素個(gè)數(shù)Object[]toArray()//包含所有元素的數(shù)組二叉排序樹8.5二叉排序樹和平衡二叉樹【例8.4】使用二叉排序樹表示互異的排序集合

//產(chǎn)生n個(gè)互異的排序的隨機(jī)數(shù)，范圍是0～size-1，返回二叉排序樹

publicstaticBinarySortTree<Integer>random(intn,intsize)二叉排序樹8.5二叉排序樹和平衡二叉樹（1）p是葉子結(jié)點(diǎn)

（2）p是1度結(jié)點(diǎn)，刪除12、36二叉排序樹刪除二叉排序樹8.5二叉排序樹和平衡二叉樹（3）p是2度結(jié)點(diǎn)，刪除54；插入54publicTremove(Tkey)二叉排序樹刪除二叉排序樹8.5二叉排序樹和平衡二叉樹二叉排序樹的查找性能分析二叉排序樹