數(shù)據(jù)結(jié)構(gòu)（2）市公開課一等獎省賽課獲獎?wù)n件

數(shù)據(jù)結(jié)構(gòu)查找數(shù)據(jù)結(jié)構(gòu)（2）第1頁基本概念查找表：由同一類型數(shù)據(jù)元素（或統(tǒng)計）組成集合是一個數(shù)據(jù)結(jié)構(gòu)查詢檢索插入刪除查找靜態(tài)查找表動態(tài)查找表關(guān)鍵字：數(shù)據(jù)元素（或統(tǒng)計）中某個數(shù)據(jù)項值，可用來識別一個統(tǒng)計主關(guān)鍵字：能夠唯一標(biāo)識一個統(tǒng)計次關(guān)鍵字：識別若干統(tǒng)計查找查詢特定元素是否在查找表中查找成功查找不成功輸出該統(tǒng)計或其位置輸出失敗標(biāo)志或位置比如“學(xué)號”比如“女”特定數(shù)據(jù)結(jié)構(gòu)（2）第2頁靜態(tài)查找表次序查找法折半查找法索引查找法…動態(tài)查找表(基于樹查找法)二叉排序樹和平衡二叉樹B樹…哈希表(計算式查找法)查找方法分類數(shù)據(jù)結(jié)構(gòu)（2）第3頁怎樣評定算法優(yōu)劣？討論平均查找長度查找過程?比較次數(shù)平均值其中：n是查找表中統(tǒng)計個數(shù)ASL=∑PiCii=1nPi是查找第i個統(tǒng)計查找概率(通常取等概率,即Pi=1/n)Ci是找到第i個統(tǒng)計時所經(jīng)歷比較次數(shù)顯然，ASL值越小，時間效率越高數(shù)據(jù)結(jié)構(gòu)（2）第4頁查找成功§

9.1靜態(tài)查找表一、次序查找(算法)算法步驟：Step1從最終一個元素開始查找Step2用待查關(guān)鍵字值與各結(jié)點(diǎn)(統(tǒng)計)關(guān)鍵字值逐一比較；若找到相等結(jié)點(diǎn)，則查找成功；不然，查找失敗適用范圍(查找表存放結(jié)構(gòu))：次序/鏈?zhǔn)酱娣沤Y(jié)構(gòu)L=(a1,a2,a3,a4,a5,…,an-1,an)k≠≠≠＝≠≠≠≠查找失敗也可從后往前掃描數(shù)據(jù)結(jié)構(gòu)（2）第5頁以次序表為例：typedefstruct{ElemType*elem;intlength;}SSTable;

intSearch_Seq(SSTableST,KeyTypekey){ST.elem[0].key=key;//哨兵for(i=ST.length;!EQ(ST.elem[i].key,key);--i);returni;}//Search_Seq在次序表ST中，查找關(guān)鍵字與key相同元素；若成功，返回其位置，不然返回0可免去查找過程中每一步都要檢測是否查找完成。當(dāng)n>1000時，查找時間可縮小二分之一若抵達(dá)0號單元才結(jié)束循環(huán)，說明不成功，返回0值（i=0）；成功時返回找到那個元素位置i數(shù)據(jù)結(jié)構(gòu)（2）第6頁性能分析：查找倒數(shù)第1個元素所需比較次數(shù)為：1查找倒數(shù)第2個元素所需比較次數(shù)為：2…查找倒數(shù)第n個元素所需比較次數(shù)為：n總計全部比較次數(shù)為：1+2+…+n=(n+1)n/2若求某一元素平均查找次數(shù)，則當(dāng)除以n等概率ASL=(n+1)/2時間效率為：O(n)查找成功查找失敗時所需比較次數(shù)：n+1優(yōu)點(diǎn)：算法簡單，對次序結(jié)構(gòu)和鏈表結(jié)構(gòu)均適用缺點(diǎn)：ASL太長，時間效率太低(尤其是n很大時)怎樣改進(jìn)？ASL=((n+1)/2+n+1)/2=(n+1)3/4數(shù)據(jù)結(jié)構(gòu)（2）第7頁二、折半查找(算法)先決條件：查找表有序數(shù)據(jù)元素按關(guān)鍵字有序算法思想：將有序序列中點(diǎn)設(shè)置為比較對象，如要找元素值小于該中點(diǎn)元素，則將待查序列縮小為左半部分，不然為右半部分經(jīng)過一次比較將查找區(qū)間縮小二分之一算法步驟：Step1確定查找區(qū)間中間位置：mid=int((low+high)/2)Step2比較待查關(guān)鍵字值與中間位置關(guān)鍵字值：相等大于小于查找成功在后半?yún)^(qū)域折半查找在前半?yún)^(qū)域折半查找Step3重復(fù)以上步驟直至low>high，查找失敗low=mid+1high=mid-1數(shù)據(jù)結(jié)構(gòu)（2）第8頁算法示例：已知以下11個數(shù)據(jù)元素有序表（關(guān)鍵字即為數(shù)據(jù)元素值）：(05,13,19,21,37,56,64,75,80,88,92)現(xiàn)要查找關(guān)鍵字為21和85數(shù)據(jù)元素。key=21513192137566475808892lowhighmidlow=1high=11mid=6比較：21？56<high=mid-1=556513192137lowhighmidlow=1high=5mid=3比較：21？1919>low=mid+1=42137lowhighmidlow=4high=5mid=4比較：21？2121查找成功！=數(shù)據(jù)結(jié)構(gòu)（2）第9頁key=85513192137566475808892lowhighmidlow=1high=11mid=6比較：85？56>low=mid+1=7566475808892lowhighmidlow=7high=11mid=9比較：85？8080>low=mid+1=108892lowhighmidlow=10high=11mid=10比較：85？8888high=mid-1=9<low>high查找不成功！數(shù)據(jù)結(jié)構(gòu)（2）第10頁intSearch_Bin(SSTableST,KeyTypekey){low=1;high=ST.length;while(low<=high){mid=(low+high)/2; ifEQ(key,ST.elem[mid].key)returnmid;elseifLT(key,ST.elem[mid].key)high=mid-1;elselow=mid+1;}return0;}//Search_Seq在有序表ST中折半查找關(guān)鍵字與key相同元素；若成功，返回其位置，不然返回0查找成功，返回該元素在表中位置繼續(xù)在前半?yún)^(qū)域查找繼續(xù)在后半?yún)^(qū)域查找查找失敗，返回0值數(shù)據(jù)結(jié)構(gòu)（2）第11頁性能分析：513192137566475808892前例：可用判定樹(二叉)描述元素在表中位置1234567891011122333344446394171052811key=21查找成功！key=88查找不成功！比較次數(shù)最多不超出log2n+1-110-1111-7-88-96-74-55-61-22-39-103-4數(shù)據(jù)結(jié)構(gòu)（2）第12頁假定有序表長度n=2h-1(h=log2(n+1))，則描述折半查找判定樹是深度為h滿二叉樹樹中層次為1結(jié)點(diǎn)有1個，層次為2結(jié)點(diǎn)有2個，…，層次為h結(jié)點(diǎn)有2h-1個假定表中每個統(tǒng)計查找概率相等(Pi=1/n)查找成功ASLbs=(∑Ci)/n=(∑j×2j-1)/ni=1nj=1h≈log2n特點(diǎn)：折半查找效率比次序查找效率高（尤其是查找表長度很長時）折半查找只能適合用于有序表，而且以次序存放結(jié)構(gòu)存放數(shù)據(jù)結(jié)構(gòu)（2）第13頁三、索引查找(算法)索引表22121389203342443824486058744986532248861713最大關(guān)鍵字起始地址特點(diǎn)：分塊有序key=38？查找效率：ASL=Lb+Lw對索引表對塊內(nèi)查找ASLbs≈log2(n/s+1)+s/2log2n≤ASLbs≤(n+1)/2比如：n=9，s=3，ASLbs=3.5，折半法為3.1，次序法為5s為每塊內(nèi)部統(tǒng)計個數(shù)，n/s即塊數(shù)目折半查找索引表：ASLbs=(n/s+s)+1次序查找索引表：數(shù)據(jù)結(jié)構(gòu)（2）第14頁程序填空：voidSeqSearch(){inta[n],I,x,y;cout<<“建立整數(shù)次序表(以回車為間隔，-1為結(jié)束：)”;for(i=1;i<=MALEN;i++){cin>>a[i];if(a[i]==(1)){y=i;break;}}cout<<“請輸入要查找數(shù)據(jù)：”;cin>>x;i=y-1;while(i>0&&(2))

(3)

if((4))cout<<“沒有找到”;elsecout<<“已找到，在第”<<

<<“個位置上”;}從鍵盤輸入若干整數(shù)，以回車為間隔，以-1為結(jié)束符號，建立一個次序存放線性表，然后按提醒輸入一個待查找數(shù)進(jìn)行查找。若找到，則顯示找到數(shù)據(jù)在線性表中位置；不然顯示“找不到”。數(shù)據(jù)結(jié)構(gòu)（2）第15頁程序設(shè)計：對有序表R[0…n-1]進(jìn)行二分查找，查找成功時返回統(tǒng)計在表中位置；查找失敗時顯示“沒有找到！”。試編寫此程序設(shè)單鏈表結(jié)點(diǎn)是按關(guān)鍵字從小到大排列，試寫出對此鏈表進(jìn)行查找算法。假如查找成功，則返回指向關(guān)鍵字為x結(jié)點(diǎn)指針，不然返回NULL。數(shù)據(jù)結(jié)構(gòu)（2）第16頁§

9.2動態(tài)查找表特點(diǎn)：表結(jié)構(gòu)在查找過程中動態(tài)生成要求：對于給定值key，查找成功查找失敗返回插入經(jīng)典動態(tài)查找表二叉排序樹一、二叉排序樹及其查找過程二、二叉排序樹插入與刪除三、二叉排序樹查找分析四、平衡二叉樹數(shù)據(jù)結(jié)構(gòu)（2）第17頁一、二叉排序樹及其查找過程或是一棵空樹，或是含有以下性質(zhì)非空二叉樹：（1）左子樹全部結(jié)點(diǎn)均小于根值（2）右子樹全部結(jié)點(diǎn)均大于根值（3）它左右子樹也分別為二叉排序樹判斷對錯：二叉排序樹或是空樹，或是這么一棵二叉樹：若左子樹不空，則左孩子小于根結(jié)點(diǎn)若右子樹不空，則有孩子大于根結(jié)點(diǎn)左右子樹也是這么二叉排序樹×試舉例！數(shù)據(jù)結(jié)構(gòu)（2）第18頁例：5261431079854102637891√×中序遍歷二叉樹得到：？技巧：手工判別二叉排序樹方法之一數(shù)據(jù)結(jié)構(gòu)（2）第19頁一棵二叉排序樹結(jié)構(gòu)以下，各結(jié)點(diǎn)值從小到大依次為1-9，請標(biāo)出各結(jié)點(diǎn)值。數(shù)據(jù)結(jié)構(gòu)（2）第20頁一、二叉排序樹及其查找過程給定值與根結(jié)點(diǎn)比較：相等大于小于查找成功查找右子樹查找左子樹52614310798key=4？key=11？查找成功查找失敗數(shù)據(jù)結(jié)構(gòu)（2）第21頁二、二叉排序樹插入與刪除1、插入52614310798例：插入結(jié)點(diǎn)1111何時？怎樣？數(shù)據(jù)結(jié)構(gòu)（2）第22頁生成二叉排序樹例：待查找關(guān)鍵字序列{45,24,53,45,12,24,90}從空樹出發(fā)452453查找成功返回12查找成功返回90中序遍歷此二叉樹得到：1224455390排序！數(shù)據(jù)結(jié)構(gòu)（2）第23頁2、刪除要求：刪除后依舊是二叉排序樹被刪結(jié)點(diǎn)：①是葉子結(jié)點(diǎn)②只有左子樹或右子樹③同時有左右子樹①是葉子結(jié)點(diǎn)①是葉子結(jié)點(diǎn)直接刪除結(jié)點(diǎn)，并使其父結(jié)點(diǎn)指向該結(jié)點(diǎn)指針置空526143107988數(shù)據(jù)結(jié)構(gòu)（2）第24頁②被刪結(jié)點(diǎn)只有左子樹或右子樹刪除結(jié)點(diǎn)，使其父結(jié)點(diǎn)指向該結(jié)點(diǎn)指針指向其左子樹/右子樹（用孩子結(jié)點(diǎn)替換被刪結(jié)點(diǎn)）526143107984只有左子樹6只有右子樹數(shù)據(jù)結(jié)構(gòu)（2）第25頁③被刪結(jié)點(diǎn)同時有左右子樹刪除結(jié)點(diǎn)p：以中序遍歷時直接前驅(qū)s替換被刪除結(jié)點(diǎn)p，然后再刪除該直接前驅(qū)526143107982526143107985sSS1數(shù)據(jù)結(jié)構(gòu)（2）第26頁三、二叉排序樹查找分析最好情況：二叉排序樹為一近似完全二叉樹時，其查找深度為log2n量級，其時間復(fù)雜度為O(log2n)最壞情況：二叉排序樹為近似線性表（如以升序或降序輸入結(jié)點(diǎn)）時，其查找深度為n量級，其時間復(fù)雜度為O(n)“平衡化”數(shù)據(jù)結(jié)構(gòu)（2）第27頁四、平衡二叉樹或是空樹，或是含有以下性質(zhì)二叉樹：AVL樹左右子樹均是AVL樹左子樹和右子樹高度之差絕對值不超出1ABCDE-3-2000高度不平衡CADBE0-1-100高度平衡左子樹高度-右子樹高度平衡因子=AVL樹任一結(jié)點(diǎn)平衡因子只能是-1,0,1數(shù)據(jù)結(jié)構(gòu)（2）第28頁結(jié)構(gòu)平衡二叉排序樹{13,24,37,90,53}132490533700-10-2-1不平衡旋轉(zhuǎn)24133700001-2-2不平衡旋轉(zhuǎn)53902413370-1-2-20不平衡旋轉(zhuǎn)90372413530000-1插入新結(jié)點(diǎn)后，需從插入位置沿通向根路徑回溯，檢驗各結(jié)點(diǎn)平衡因子若在某結(jié)點(diǎn)發(fā)覺不平衡，停頓回溯從發(fā)生不平衡結(jié)點(diǎn)起，沿剛才回溯路徑取直接下兩層結(jié)點(diǎn)單向(右旋、左旋)雙向(先左后右、先右后左)單向左旋先右后左數(shù)據(jù)結(jié)構(gòu)（2）第29頁單向旋轉(zhuǎn)雙向旋轉(zhuǎn)三個結(jié)點(diǎn)處于一條直線上（“/”型或“\”型）ABCABCABCABC單向右旋單向左旋A>B>C三個結(jié)點(diǎn)處于一條折線上（“<”型或“>”型）ACBCAB先左后右ABCABC先右后左ABCABC練習(xí)：（64,5,13,21,19,80,75,37,56）LLRRLRRL數(shù)據(jù)結(jié)構(gòu)（2）第30頁§

9.2動態(tài)查找表B-樹B+樹又稱多路平衡查找樹，在文件系統(tǒng)中有較多應(yīng)用是B-樹一個變形樹，在索引文件組織中有較多應(yīng)用數(shù)據(jù)結(jié)構(gòu)（2）第31頁B-樹一顆m階B-樹或是空樹，或是含有以下要求m叉樹：樹中每個結(jié)點(diǎn)至多有m個孩子結(jié)點(diǎn)除根之外全部非葉子結(jié)點(diǎn)最少有m/2個孩子結(jié)點(diǎn)若根結(jié)點(diǎn)不是葉子結(jié)點(diǎn)，則最少有兩個孩子結(jié)點(diǎn)非葉子結(jié)點(diǎn)結(jié)構(gòu)以下：np0k1p1k2p2…knpn關(guān)鍵字個數(shù)m/2-1≤n≤m-1關(guān)鍵字ki<ki+1指向子樹根結(jié)點(diǎn)指針，pi-1所指子樹中全部結(jié)點(diǎn)關(guān)鍵字均小于kipn所指子樹中全部結(jié)點(diǎn)關(guān)鍵字均大于kn全部葉子結(jié)點(diǎn)都出現(xiàn)在同一層次上至多有m-1個關(guān)鍵字B-樹是全部結(jié)點(diǎn)平衡因子都為0多路查找樹351181784321112713916453473991FFFFFFFFFFFFm=4階數(shù)據(jù)結(jié)構(gòu)（2）第32頁一顆m階B+樹和B-樹差異：有n棵子樹結(jié)點(diǎn)中含有n個關(guān)鍵字(m/2≤n≤m)全部葉子結(jié)點(diǎn)中包含了全部關(guān)鍵字信息及指向含這些關(guān)鍵字統(tǒng)計指針，且葉子結(jié)點(diǎn)本身依關(guān)鍵字大小自小而大次序鏈接全部非葉子結(jié)點(diǎn)可看成是索引部分，結(jié)點(diǎn)中僅含有其子樹中最大或最小關(guān)鍵字不帶信息至多有n-1個關(guān)鍵字m/2-1≤n≤m-1m=3階B+樹兩個頭指針，一個指向根結(jié)點(diǎn)，一個指向關(guān)鍵字最小葉子結(jié)點(diǎn)次序查找隨機(jī)查找數(shù)據(jù)結(jié)構(gòu)（2）第33頁程序設(shè)計：1、實現(xiàn)二叉排序樹及平衡二叉樹建立、查找、插入、刪除等操作。2、已知平衡二叉樹平衡因子，求其深度。數(shù)據(jù)結(jié)構(gòu)（2）第34頁§

9.3哈希表問題提出：線性表和樹表查找都是經(jīng)過各個統(tǒng)計關(guān)鍵字與給定值進(jìn)行大量比較來實現(xiàn)，統(tǒng)計存放位置是由比較次數(shù)確定哈希方法：在統(tǒng)計存放位置與其關(guān)鍵字之間建立一個確定對應(yīng)函數(shù)關(guān)系H()，使每個關(guān)鍵字與存放位置一一對應(yīng)：Address=H(Rec.key)查找：利用哈希函數(shù)及統(tǒng)計關(guān)鍵字計算出統(tǒng)計存放地址直接到指定地址進(jìn)行查找不需經(jīng)過比較，一次存取就能得到所查元素數(shù)據(jù)結(jié)構(gòu)（2）第35頁求關(guān)鍵字第一個和最終一個字母在字母表中序號之和，若比表長大則減去表長例：假設(shè)要建立一張全國30個地域各民族人口統(tǒng)計表，每個地域為一個統(tǒng)計，統(tǒng)計各數(shù)據(jù)項為：編號地域名總?cè)丝跐h族回族…簡單哈希函數(shù)keyBEIJING(北京)TIANJIN(天津)HEBEI(河北)SHANXI(山西)SHANGHAI(上海)SHANDONG(山東)HENAN(河南)SICHUAN(四川)H1(key)H2(key)H3(key)取關(guān)鍵字中第一個字母在字母表中序號求每個漢字第一個拼音字母ASCII碼之和八進(jìn)制形式，然后將其看成是十進(jìn)制再除以表長取余數(shù)，若余數(shù)為0則加表長022008191919081909041728282622030426021323171616沖突不能完全防止，只能盡可能少怎樣結(jié)構(gòu)？哈希表：依據(jù)設(shè)定哈希函數(shù)H(key)和處理沖突方法將一組關(guān)鍵字映像到一個有限連續(xù)地址集上數(shù)據(jù)結(jié)構(gòu)（2）第36頁結(jié)構(gòu)哈希函數(shù)直接定址法數(shù)字分析法平方取中法折疊法除留余數(shù)法要求哈希函數(shù)應(yīng)是簡單，能在較短時間內(nèi)計算出結(jié)果值域：[0,m-1](m為哈希表長)哈希函數(shù)計算出地址應(yīng)能均勻分布在整個地址空間中數(shù)據(jù)結(jié)構(gòu)（2）第37頁直接定址法H(key)=a·key+b取關(guān)鍵字線性函數(shù)a、b為常數(shù)例：H(key)=key-131000適合地址集合大小與關(guān)鍵字集合大小相等情況a=1時，H(key)=key，即用關(guān)鍵字做地址實際應(yīng)用中較少使用數(shù)據(jù)結(jié)構(gòu)（2）第38頁數(shù)字分析法假設(shè)關(guān)鍵字集合中每個關(guān)鍵字都是由s位數(shù)字組成(u1,u2,u3,…,us)分析關(guān)鍵字全體，從中提取分布均勻若干位或它們組合作為地址例：有80個統(tǒng)計，關(guān)鍵字為8位十進(jìn)制數(shù)，哈希地址為兩位十進(jìn)制數(shù)

分析：①只取8，②只取1③只取3、4⑧只取2、5、7

④⑤⑥⑦數(shù)字分布近乎隨機(jī)所以，?、堍茛蔻呷我鈨晌换騼晌慌c另兩位疊加作哈希地址僅適用于事先明確知道表中全部關(guān)鍵碼每一位數(shù)值分布情況完全依賴于關(guān)鍵碼集合，若換一個關(guān)鍵碼集合，選擇哪幾位要重新決定數(shù)據(jù)結(jié)構(gòu)（2）第39頁平方取中法取關(guān)鍵字平方值中間幾位作為哈希地址擴(kuò)大差異能受到整個關(guān)鍵字各位影響例：統(tǒng)計關(guān)鍵字8進(jìn)制(關(guān)鍵字)2哈希地址(217~29)A01000010000010I11001210000210J12001440000440I011601370400370P120614310541310P220624314704314Q121614734741734Q221624741304741Q321634745651745假設(shè)表長為512中間所取位數(shù)由哈希表長決定較慣用數(shù)據(jù)結(jié)構(gòu)（2）第40頁折疊法將關(guān)鍵字分割成位數(shù)相同若干部分(最終部分位數(shù)能夠不一樣)，取它們疊加和(舍去進(jìn)位)作為哈希地址移位疊加間界疊加將分割后幾部分低位對齊相加從一端沿分割界往返折迭，再對齊相加例：關(guān)鍵字為：0442205864，哈希地址位數(shù)為4適合于關(guān)鍵字位數(shù)尤其多，且每一位上數(shù)字分布大致均勻情況數(shù)據(jù)結(jié)構(gòu)（2）第41頁除留余數(shù)法H(key)=keymodp(p≤m)表長質(zhì)數(shù)或不包含小于20質(zhì)原因合數(shù)例：m=25key=(8,16,32,64,128,256,512,1024)p=2?p=7H(key)=(1,2,4,1,2,4,1,2)p=11H(key)=(8,5,10,9,7,3,6,1)p=13H(key)=(8,3,6,12,11,19,5,10)×√√最簡單、最慣用不但可對關(guān)鍵字直接取模，也可在折疊、平方取中后取模數(shù)據(jù)結(jié)構(gòu)（2）第42頁處理沖突方法為產(chǎn)生沖突地址尋找下一個哈希地址開放定址法再哈希法鏈地址法開放定址法Hi=(H(key)+di)modmi=1,2,…,k(k≤m-1)哈希函數(shù)哈希表長增量序列di=1,2,3,…,m-1di=12,-12,22,-22,32,…,±k2,(k≤m/2)偽隨機(jī)數(shù)序列線性探測再散列二次探測再散列偽隨機(jī)探測再散列數(shù)據(jù)結(jié)構(gòu)（2）第43頁開放定址法例：在長度11哈希表中已填相關(guān)鍵字17,60,29統(tǒng)計（哈希函數(shù)H(key)=keymod11），現(xiàn)有第四個統(tǒng)計其關(guān)鍵字為38，怎樣存放？01234567891017602938mod11=55沖突！線性探測再散列38二次探測再散列38偽隨機(jī)探測再散列38偽隨機(jī)數(shù)列9,…優(yōu)點(diǎn)：只要哈希表中有空位，總能找到一個不發(fā)生沖突地址缺點(diǎn)：易產(chǎn)生“二次聚集”數(shù)據(jù)結(jié)構(gòu)（2）第44頁再哈希法Hi=RHi(key)i=1,2,…,k不一樣哈希函數(shù)結(jié)