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

數(shù)據(jù)結(jié)構(gòu)課程的內(nèi)容數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第1頁。9.1基本概念9.2靜態(tài)查找表9.3動態(tài)查找表9.4哈希表第9章查找教材第8、11和12章省略，因《操作系統(tǒng)》課程會涉及。數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第2頁。9.1基本概念——若表中存在特定元素，稱查找成功，應(yīng)輸出該記錄；——否則，稱查找不成功（也應(yīng)輸出失敗標(biāo)志或失敗位置）查找表查找查找成功查找不成功靜態(tài)查找動態(tài)查找關(guān)鍵字主關(guān)鍵字次關(guān)鍵字——由同一類型的數(shù)據(jù)元素（或記錄）構(gòu)成的集合。——查詢(Searching)特定元素是否在表中。——只查找，不改變集合內(nèi)的數(shù)據(jù)元素?！炔檎?，又改變（增減）集合內(nèi)的數(shù)據(jù)元素?！涗浿心硞€數(shù)據(jù)項的值，可用來識別一個記錄

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

——可以唯一標(biāo)識一個記錄的關(guān)鍵字例如“學(xué)號”例如“女”是一種數(shù)據(jù)結(jié)構(gòu)——識別若干記錄的關(guān)鍵字?jǐn)?shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第3頁。（2）對查找表常用的操作有哪些？查詢某個“特定的”數(shù)據(jù)元素是否在表中；查詢某個“特定的”數(shù)據(jù)元素的各種屬性；在查找表中插入一元素；從查找表中刪除一元素。

（3)有哪些查找方法？

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

給定一個值K，在含有n個記錄的文件中進(jìn)行搜索，尋找一個關(guān)鍵字值等于K的記錄，如找到則輸出該記錄，否則輸出查找不成功的信息。例如查字典針對靜態(tài)查找表和動態(tài)查找表的查找方法也有所不同。“特定的”=關(guān)鍵字?jǐn)?shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第4頁。（4）如何評估查找方法的優(yōu)劣？明確：查找的過程就是將給定的K值與文件中各記錄的關(guān)鍵字項進(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值越小，時間效率越高。數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第5頁。針對靜態(tài)查找表的查找算法主要有：9.2靜態(tài)查找表靜態(tài)查找表的抽象數(shù)據(jù)類型參見教材P216。一、順序查找（線性查找）二、折半查找（二分或?qū)Ψ植檎遥┤㈧o態(tài)樹表的查找四、分塊查找（索引順序查找）數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第6頁。一、順序查找（Linearsearch，又稱線性查找）（1）順序表的機內(nèi)存儲結(jié)構(gòu)：typedefstruct{

ElemType*elem;

//表基址，0號單元留空。表容量為全部元素

intlength;

//表長，即表中數(shù)據(jù)元素個數(shù)}SSTable;順序查找：即用逐一比較的辦法順序查找關(guān)鍵字，這顯然是最直接的辦法。

對順序結(jié)構(gòu)如何線性查找？見下頁之例或教材P216；對單鏈表結(jié)構(gòu)如何線性查找？函數(shù)雖未給出，但也很容易編寫；只要知道頭指針head就可以“順藤摸瓜”；對非線性樹結(jié)構(gòu)如何順序查找?可借助各種遍歷操作！數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第7頁。（2）算法的實現(xiàn)：技巧：把待查關(guān)鍵字key存入表頭或表尾（俗稱“哨兵”），這樣可以加快執(zhí)行速度。例：若將待查找的特定值key存入順序表的首部（如0號單元），則順序查找的實現(xiàn)方案為：從后向前逐個比較！intSearch_Seq(SSTableST,KeyTypekey){

//在順序表ST中，查找關(guān)鍵字與key相同的元素；若成功，返回其位置信息，否則返回0

ST.elem[0].key=key;

//設(shè)立哨兵，可免去查找過程中每一步都要檢測是否查找完畢。當(dāng)n>1000時，查找時間將減少一半。

for(i=ST.length;ST.elem[i].key!=key;--i);

//不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++)

returni;

//若到達(dá)0號單元才結(jié)束循環(huán)，說明不成功，返回0值(i=0)。成功時則返回找到的那個元素的位置i。}//Search_Seq數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第8頁。9大家有疑問的，可以詢問和交流可以互相討論下，但要小聲點數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第9頁?！祷靥厥鈽?biāo)志，例如返回空記錄或空指針。前例中設(shè)立了“哨兵”，就是將關(guān)鍵字送入末地址ST.elem[0].key使之結(jié)束并返回i=0。討論②查找效率怎樣計算？——用平均查找長度ASL衡量。討論①查不到怎么辦？討論③如何計算ASL？分析：查找第1個元素所需的比較次數(shù)為1；查找第2個元素所需的比較次數(shù)為2；……查找第n個元素所需的比較次數(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)數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第10頁。二、折半查找（又稱二分查找或?qū)Ψ植檎遥﹥?yōu)點：算法簡單，且對順序結(jié)構(gòu)或鏈表結(jié)構(gòu)均適用。缺點：ASL太長，時間效率太低。這是一種容易想到的查找方法。先給數(shù)據(jù)排序（例如按升序排好），形成有序表，然后再將key與正中元素相比，若key小，則縮小至右半部內(nèi)查找；再取其中值比較，每次縮小1/2的范圍，直到查找成功或失敗為止。對順序表結(jié)構(gòu)如何編程實現(xiàn)折半查找算法？

——見下頁之例，或見教材（P219）對單鏈表結(jié)構(gòu)如何折半查找？

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

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

如何改進(jìn)？討論④順序查找的特點：數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第11頁。②運算步驟：(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;結(jié)束條件：（1）查找成功：ST.elem[mid].key=key

（2）查找不成功：high<low（意即區(qū)間長度小于0）解：①先設(shè)定3個輔助標(biāo)志:low,high,mid，折半查找舉例：Low指向待查元素所在區(qū)間的下界high指向待查元素所在區(qū)間的上界mid指向待查元素所在區(qū)間的中間位置

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

（0513192137566475808892）,請查找關(guān)鍵字為21

和85的數(shù)據(jù)元素。顯然有：mid=(low+high)/2數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第12頁。討論①若關(guān)鍵字不在表中，怎樣得知和停止？——典型標(biāo)志是：當(dāng)查找范圍的上界≤下界時停止查找。討論②二分查找的效率（ASL）1次比較就查找成功的元素有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

＝推導(dǎo)過程數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第13頁。三、分塊查找（索引順序查找）這是一種順序查找的另一種改進(jìn)方法。先讓數(shù)據(jù)分塊有序，即分成若干子表，要求每個子表中的數(shù)值（用關(guān)鍵字更準(zhǔn)確）都比后一塊中數(shù)值?。ǖ颖韮?nèi)部未必有序）。然后將各子表中的最大關(guān)鍵字構(gòu)成一個索引表，表中還要包含每個子表的起始地址（即頭指針）。索引表最大關(guān)鍵字起始地址第1塊第2塊第3塊224886例：特點：塊間有序，塊內(nèi)無序數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第14頁。查找步驟分兩步進(jìn)行：①對索引表使用折半查找法（因為索引表是有序表）；②確定了待查關(guān)鍵字所在的子表后，在子表內(nèi)采用順序查找法（因為各子表內(nèi)部是無序表）；查找效率：ASL=Lb+Lw對索引表查找的ASL對塊內(nèi)查找的ASLS為每塊內(nèi)部的記錄個數(shù)，n/s即塊的數(shù)目例如當(dāng)n=9，s=3時，ASLbs=3.5,而折半法為3.1,順序法為5數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第15頁。特點：一、二叉排序樹的定義二、二叉排序樹的插入與刪除三、二叉排序樹的查找分析四、平衡二叉樹9.3動態(tài)查找表表結(jié)構(gòu)在查找過程中動態(tài)生成。要求：對于給定值key,若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回；否則插入關(guān)鍵字等于key的記錄。典型的動態(tài)表———二叉排序樹數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第16頁。一、二叉排序樹的定義（a）（b）練：下列2種圖形中，哪個不是二叉排序樹？----或是一棵空樹；或者是具有如下性質(zhì)的非空二叉樹：

（1）左子樹的所有結(jié)點均小于根的值；（2）右子樹的所有結(jié)點均大于根的值；（3）它的左右子樹也分別為二叉排序樹。討論：對(a)中序遍歷后的結(jié)果是什么？數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第17頁。二、二叉排序樹的查找、插入與刪除將數(shù)據(jù)元素構(gòu)造成二叉排序樹的優(yōu)點：①查找過程與順序結(jié)構(gòu)有序表中的折半查找相似，查找效率高；②中序遍歷此二叉樹，將會得到一個關(guān)鍵字的有序序列（即實現(xiàn)了排序運算）；③一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程。④如果查找不成功，能夠方便地將被查元素插入到二叉樹的葉子結(jié)點上，而且插入或刪除時只需修改指針而不需移動元素。注：若數(shù)據(jù)元素的輸入順序不同，則得到的二叉排序樹形態(tài)也不同！——這種既查找又插入的過程稱為動態(tài)查找。二叉排序樹既有類似于折半查找的特性，又采用了鏈表存儲，它是動態(tài)查找表的一種適宜表示。數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第18頁。4524531290如果待查找的關(guān)鍵字序列輸入順序為：（24，53，45，45，12，24，90），2453451290查找成功，返回查找成功，返回討論1：二叉排序樹的插入和查找操作則生成二叉排序樹的過程為：例：輸入待查找的關(guān)鍵字序列=（45，24，53，45，12，24，90）則生成的二叉排序樹形態(tài)不同：查找成功，返回查找成功，返回數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第19頁。二叉排序樹的查找&插入算法如何實現(xiàn)？查找算法參見教材P228算法9.5（a）;插入算法參見教材P228算法9.5（b)_9.6;一種“二合一”的算法如下：數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第20頁。BiTreeSearchBST（BiTreeT,KeyTypekey）{//若查找成功，則返回指向該數(shù)據(jù)元素結(jié)點的指針，否則返回空指針

if((!T)||EQ(key,T—>data.key))return(T)；

//查找結(jié)束

elseifLT(key,T—>data.key)//在左子樹中繼續(xù)查找

return(SearchBST(T—>lchild,key))；

elsereturn(SearchBST(T—>rchild,key))；

//在右子樹中繼續(xù)查找

}//SearchBST數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第21頁。StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){

if(!T){p=f；returnFALSE；}//查找不成功

elseifEQ(key,T—>data.key){p=T；returnTRUE；}//查找成功

elseifLT(key,T—>data.key)returnSearchBST(T—>lchild,key,T,p);//在左子樹中繼續(xù)查找

elsereturnSearchBST(T—>rchild,key,T,p);//在右子樹中繼續(xù)查找}//SearchBST數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第22頁。StatusInsertBST(BiTree&T,ElemTypee){if(!SearchBST(T,e.key,NULL,p))//查找不成功

{s=(BiTree)malloc(sizeof(BiTNode))；

s—>data=e；s—>lchild=s—>rchild=NULL；//建立新結(jié)點

if(!p)T=s；//T為空樹

elseifLT(e.key,p—>data.key)p—>lchild=s；//被插結(jié)點*s為左孩子

elsep—>rchild=s；//被插結(jié)點*s為右孩子

returnTRUE；

}elsereturnFALSE；//樹中已有關(guān)鍵字相同的結(jié)點，不再插入}//InsertBST數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第23頁。對于二叉排序樹，刪除樹上一個結(jié)點相當(dāng)于刪除有序序列中的一個記錄，刪除后仍需保持二叉排序樹的特性。（對鏈表進(jìn)行刪除操作是很方便的）討論2：二叉排序樹的刪除操作如何刪除一個結(jié)點？假設(shè)：*p表示被刪結(jié)點的指針；PL和PR分別表示*P的左、右孩子指針；*f表示*p的雙親結(jié)點指針；并假定*p是*f的左孩子；則可能有三種情況：PR為*S的右子樹；SL為Q（*S的雙親結(jié)點）右孩子*p為葉子：刪除此結(jié)點時，直接修改*f指針域即可；*p只有一棵子樹（或左或右）：令PL或PR為*f的左孩子即可；*p有兩棵子樹：情況最復(fù)雜→數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第24頁。*p有兩棵子樹時，如何進(jìn)行刪除操作？分析：設(shè)刪除前的中序遍歷序列為：….spPR….

//顯然p的直接前驅(qū)是s希望刪除p后，其它元素的相對位置不變。有兩種解決方法：法1：令*p的左子樹為*f的左子樹，*p的右子樹為*s的右子樹；//即FL=PL;FR=PR;法2：令*s代替*p//

*s為*p左子樹最右下的葉子見課本P230圖9.9數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第25頁。FCCLSSLQLPPRQPRFCCLSSLQLPPRQ法2:FCCLSSLQLPPRQ法1:例：請從下面的二叉排序樹中刪除結(jié)點P。SSL數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第26頁。四、平衡二叉樹平衡二叉樹又稱AVL樹，它是具有如下性質(zhì)的二叉樹：為了方便起見，給每個結(jié)點附加一個數(shù)字，給出該結(jié)點左子樹與右子樹的高度差。這個數(shù)字稱為結(jié)點的平衡因子balance。這樣，可以得到AVL樹的其它性質(zhì)：即|左子樹深度-右子樹深度|≤1左、右子樹是平衡二叉樹；所有結(jié)點的左、右子樹深度之差的絕對值≤1數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第27頁。(a)平衡樹(b)不平衡樹例：判斷下列二叉樹是否AVL樹？任一結(jié)點的平衡因子只能?。?1、0或

1；如果樹中任意一個結(jié)點的平衡因子的絕對值大于1，則這棵二叉樹就失去平衡，不再是AVL樹；對于一棵有n個結(jié)點的AVL樹，其高度保持在O(log2n)數(shù)量級，ASL也保持在O(log2n)量級。00011-1-120001-1數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第28頁。如果在一棵AVL樹中插入一個新結(jié)點，就有可能造成失衡，此時必須重新調(diào)整樹的結(jié)構(gòu)，使之恢復(fù)平衡。我們稱調(diào)整平衡過程為平衡旋轉(zhuǎn)。現(xiàn)分別介紹這四種平衡旋轉(zhuǎn)。平衡旋轉(zhuǎn)可以歸納為四類：

LL平衡旋轉(zhuǎn)

RR平衡旋轉(zhuǎn)

LR平衡旋轉(zhuǎn)

RL平衡旋轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第29頁。若在A的左子樹的左子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要進(jìn)行一次順時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）ABCABC1）LL平衡旋轉(zhuǎn)：AB數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第30頁。若在A的右子樹的右子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要進(jìn)行一次逆時針旋轉(zhuǎn)。(以B為旋轉(zhuǎn)軸）2）RR平衡旋轉(zhuǎn)：ABCABCAB數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第31頁。若在A的左子樹的右子樹上插入結(jié)點，使A的平衡因子從1增加至2，需要先進(jìn)行逆時針旋轉(zhuǎn)，再順時針旋轉(zhuǎn)。(以插入的結(jié)點C為旋轉(zhuǎn)軸）ABCABABC3）LR平衡旋轉(zhuǎn)：ABC數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第32頁。若在A的右子樹的左子樹上插入結(jié)點，使A的平衡因子從-1增加至-2，需要先進(jìn)行順時針旋轉(zhuǎn)，再逆時針旋轉(zhuǎn)。(以插入的結(jié)點C為旋轉(zhuǎn)軸）4）RL平衡旋轉(zhuǎn)：ABABCABCABC數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第33頁。013037024例：請將下面序列構(gòu)成一棵平衡二叉排序樹：

（13，24，37，90，53）013037-113024-124-213需要RR平衡旋轉(zhuǎn)(繞B逆轉(zhuǎn),B為根）090-124-137053190-237需要RL平衡旋轉(zhuǎn)(繞C先順后逆）037090053037090053

數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第34頁。9.4哈希查找表一、哈希表的概念二、哈希函數(shù)的構(gòu)造方法三、沖突處理方法四、哈希表的查找及分析數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第35頁。一、哈希表的概念哈希表：即散列存儲結(jié)構(gòu)。

散列法存儲的基本思想：建立關(guān)鍵碼字與其存儲位置的對應(yīng)關(guān)系，或者說，由關(guān)鍵碼的值決定數(shù)據(jù)的存儲地址。優(yōu)點：查找速度極快（O(1)）,查找效率與元素個數(shù)n無關(guān)！例1：若將學(xué)生信息按如下方式存入計算機，如：將2001011810201的所有信息存入V[01]單元；將2001011810202的所有信息存入V[02]單元；……將2001011810231的所有信息存入V[31]單元。欲查找學(xué)號為2001011810216的信息，便可直接訪問V[16]！數(shù)據(jù)結(jié)構(gòu)查找-PPT全文共55頁，當(dāng)前為第36頁。例2：

有數(shù)據(jù)元素序列(14，23，39，9，25，11)，若規(guī)定每個元素k的存儲地址H（k）＝k，請畫出存儲結(jié)構(gòu)圖。（注：H（k）＝k稱為散列函數(shù)）解：根據(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è)法返回一個特殊值，例如空指針或空記錄。