華科數(shù)據(jù)結(jié)構(gòu)課件查找表由同一類型數(shù)據(jù)元素記錄組成集合

數(shù)據(jù)結(jié)

第九查找表由同一類型的數(shù)據(jù)元素（記錄）組成的集合。 男 男女 女1234n數(shù)據(jù)項

數(shù)據(jù)項

數(shù)據(jù)項關(guān)鍵字 可以標識一個記錄的數(shù)據(jù)主關(guān)鍵字:次關(guān)鍵字:查 靜態(tài)查找:查詢某個特定的元素，檢查某個特定的數(shù)據(jù)元素的屬性,不新元素或刪除元素(記錄)。 動態(tài)查找:在查找過程中，同時查找表中不存靜態(tài)查找**那契查找法；插值查找法動態(tài)查找**BB+哈希(Hash)平均查找長 查找一個記錄時比較關(guān)鍵字次nASL=∑Pir[iCir[i0123監(jiān)視監(jiān)視 順序表與順序查找例1元素類型為記錄(結(jié)構(gòu))#definemaxsize100100typedefstructnode{keytypekeycharname[6]；// }ElemType；typedefstruct{ElemTypeelem[maxsize+1]；//maxsize+1//elem[0int}SSTable;SSTableST1,ST2;例2#definemaxsize100100typedefinemType；typedefstruct{ElemTypeelem[maxsize+1]；//maxsize+1int}SSTable;SSTableST1,ST2;監(jiān)視6 maxsize順序查找法(sequentialsearchelem[n].key,elem[n-1].key，...,elem[i].key＝k(1≤i≤n)，intsequsearch(SSTableST,keytype{inti=ST.length；//從第nwhile(i>=1&&k!=Si ifprintf(”success\n”)；//查找成功elseprintf(”fail\n”)；//查找失敗return }算法2：假定使用監(jiān)視哨基本思想k=elem[i].key,(0≤i≤n)，則停止比較。如果i>0,則查找成功；否則,查找失敗。intsequsearch(SSTableST,keytypek){inti=ST.length； while(k!=Sem[i].key)i return }3若查找成功:最少為1,最多為n即P1P2Pn=1/n

nn

= n in=1n

...使用監(jiān)視哨elem[0],不使用監(jiān)視哨elem[0],Pi=1/(2*n),則1 n+1 ASL=--∑Ci+---=---+---=3(n+1)/42ni=1 有序的順序表的查找與折半查找折半查找(binarysearch,對半查找，二分查找假定2↑2

↑ ↑

↑

5555lowmid假定55↑

↑

↑

5 5

5↑

↑

8↑

k=40（續(xù)5 5

lowmid5 5

lowmid5 5 5 ↑ 5low5 lowmid

5k=22（5 5midhig5 lowmid

5 5

midhig

hig<low,查找失3半查找算法intbinsrch(SSTableST,keytype{intlow,mid,hig；while(low<=hig){ if(k<S elseif(k==Sem[mid].key) elselow=mid+1；//查右子表｝if(Sprintf("success\n”return}{ return}}折半查找算法intbinsrch(SSTableST,keytype{intlow,mid,hig；low=1；hig=ST.length；while{if(k<Sem[mid].key)hig=mid-1；//查左子表elseif(k==Sem[mid].key)returnmid； elselow=mid+1； ｝return0 }63984263984267911n=15,滿二叉

n=12,非滿二叉若n=2k1,則判定樹為滿二叉樹,其深度為假定Pi=1/n(i=1,2,...,n),比較關(guān)鍵字的次數(shù)：ASL=--- ASL=--- n 設n=15ASL=------log2(15+1)- 對任意的ASL≈----log2(n+1)-1=O(log2n) 設n=12,ASL=-----------------------=--≈6399-6399-6-3--639 1-2-6391-2--5-7-8-10-n=12，判定

n=11，加外部結(jié)點的判定第一第二第四

key它數(shù)據(jù)索引23456789分塊

首地址大1234分塊表"按塊有序",索引表"按key有序"查找方法與確定kASL(1)=Lb=--2ASL(2)=Lw=--2 ASL=Lb+Lw=---+---=--(b+s)+1=--(--+ ASLmin=√n+1=O(√n二叉排序樹(二叉查找樹(1如果二叉樹的任一結(jié)點大于其非空左的所有結(jié)點，而小于其非空右的所有結(jié)點，則這棵二叉樹稱為二叉排序樹。85853885

（2）設輸入序列為44 課堂練習55 ASL=---------------------=--≈ (3)二叉排序樹的結(jié)左 右struct{{intkey }datastructnode*lchild,*rchild；//左右的指}(4)1個元素到二叉排序樹的算structnode*intree(structnode*emType{if {t=(structnode*)malloc(sizeof(structnode))； t->lchild=t->rchild=NULL；//為葉子結(jié)點}elseif(x.key<t-return}二叉排序樹的(返回值失敗：NULL成功：非NULL，結(jié)點指針遞歸算structnode*search_tr(structnode*tkeytype{if(t==NULL)returnNULL； if(k==t-returntif(k<t-returnsearch_tr(t->lchild,k)；//查左returnsearch_tr(t->rchild,k)；}非遞歸算structnode*search_tree(structnode*t,keytype{whileif(k==t-returnt； if(k<t- return }算法分最好情況(為滿二叉樹ASL=---log2(n+1)-1=O(log2n情況平均值 ASL≈O(log245606575滿二叉 單枝ASL=(15+1)/15*log2(15+1)- 結(jié)點的平衡因子：結(jié)點的左右的深度之差小于等于1-210100 -210100- - 0 平衡二叉樹、二叉排序樹、平衡二叉排序樹的區(qū)別35-5035-500204506004865-170-45068-2

80- - 45 850 68平衡二叉

二叉排序

平衡二叉排序順序表，對數(shù)據(jù)元素的一般有兩種形式哈希(Hash)表和哈希儲一般是不連續(xù)的。過Hash函數(shù)計算出的根據(jù)設定的哈希函數(shù)H(k)和處理的方法設K1和K2K1≠K2,H(K1)=H(K2K1,K2為同義詞,K2與K1為發(fā)生了∵5和22是同義詞,5和22發(fā)生直接定址

例1序1234(地12341234H(key)=key地H(）=例2序男王偉男女王偉女男王偉男女王偉女12 4nH(keykey200040地H(學號號例3序號23456

=ABCCADDATFOXYABZOO key除以pH(key)=keyMODp H(key)=key%p p<=mp為接近m的質(zhì)數(shù)(素數(shù))或不包含小于20的質(zhì)因子的合數(shù)，如例1m=130,H(key)=key%01 例2設m=256 取p=251H(key)=key%251 0～20H(K)=K%輸入關(guān)鍵字序列：39,22,21,37,36,38,19,解決的方法關(guān)鍵字 19與38,再與22,存入

1234517與36,再與37,存入HT[19]56與37,再與17,存入HT[20]55與36,再與37,17,56,再38,39,21,22,19,存入HT[5]對于H(k)=k19，所有的19a+b為同義如

12345平方取中 取關(guān)鍵字平方后的中間某幾位為哈H(k)=取k2例.設哈希表為HT[0..99],哈希函數(shù)為H(K)=取k2的中間2位數(shù),輸入關(guān)鍵字序3列：39,21,6,36,38,13,散列法解決,構(gòu)造HT[0..99] 6折疊0101設表地址范圍為650+439+725321+486+097003+600+7004.折疊移位折疊法(移位設表地址范圍為056+439+527123+486+790300+600+007

01

HT[0..kk隨機數(shù)靈活構(gòu)造哈希函例.設哈希表為HT[0..40],哈希函數(shù)為H(K)=取k2的中間2位數(shù)K6K6

66如何解決開放地址法為q,Ri已存入HT[0..m-1]中的HT[q]中，則RXHTq+1,q+2,...,m-1,0,1,...,q-中尋找一個空位，叫做線性探HT[0..m-線性探測再散 1q- m-課堂練習：設H(k)=k的首字母在字母表中的序號,用線性 表HT[0..28]。 11 12 3 4 65 66 7 8 9 10 11 12 13

例H(k)=k的首字母在字母表中的序號，用線性探測再散列法解決，依次用下列關(guān)鍵字，造哈希表HT[0..281A1A12434456178934

AA1234567RiRjijHT[qq+12,q-12,q+22,q-22,...,q+i2,q-i2,...中尋找一個空位，叫做二次探測再散列。X和A為同義詞，散列地址為50,GECABDF0XXXXXXXXGECABDFX0鏈地址 設H(k)=k的首字母在字母表中的序號,用下列關(guān)鍵字造哈希A14A144134123456789

∧CAD∧CAD∧∧∧∧A∧23DEC4DEC∧∧∧∧鏈地址例 設H(k)=k的首字母在字母表中的序號,用下列關(guān)鍵字造哈希表HT[1..26]A14A144134123456789

A∧CADA∧CAD∧∧∧∧ANT23∧4∧∧∧∧∧建立公共