專業(yè)課參考-數(shù)據(jù)結構

11第92第9插入刪去3第9學 專計算 計算 計算 信息工 信息工 第9學 專計算 計算 計算 信息工 信息工 第9查找方法評價：平均查找長度ASLAverageSearchLength)設查找成功的概率為1Pi=1平均查找長度ASLCiiPii6

第9typedeffloatKeyType; typedefintKeyType; typedefchar*KeyType;字符串型typedefstructKeyType }

7第9對數(shù)值型關#defineEQ(a,b)((a)==#defineLT(a,b)((a)<#defineLQ(a,b)((a)<=對字符串型關#defineEQ(a,b)#defineLT(a,b)(strcmp((a),(b))<#defineLQ(a,b)(strcmp((a),(b))<=8靜態(tài)

有序表的查找：折半索引順序表的查找：分塊查

用線性表用順序表表示靜態(tài)用線性鏈表表示靜查找方法：順序typedef ElemType*elem; 0號單元留空intlength;}SSTable

3012345673intSearch_Seq(SSTableST,KeyTypekey{//在順序表ST中順序查找其關鍵字等于key的數(shù)據(jù)元素。若找ST.elem[0].key=key; //“哨兵”for(i=ST.length;!EQ(key,ST.elem[i].Key;--ireturn 若表中不存在待查元素,}301234563例1：key8 n-3n-2n- 查找不成功，i例2：在下表中key8結點 查找成功，in-

n-3n-2n-

9.1.1順序表查無排序要結構：順序、鏈9.1.2有序表查12349.1.2有序表查31224374553617890 1234567893low 1234567893Lowmid intSearch_Bin(SSTableST,KeyTypekey while(low<=high{ifEQ(key,ST.elem[mid].key)returnmid;ifLT(key,ST.elem[mid].key)high=mid-else}return0;//9.1.2有序表查1234569.1.2有序表查52。9.1.2有序表查例1：key9此時ST.elem[mid].key＝10key，因此令high＝mid－1此時ST.elem[mid].key＝8<key，因此9.1.2有序表查例1：key9

48489

mid=2mid=3

9.1.29.1.2例2：key5此時ST.elem[mid].key＝10>key，因此令此時mid=1

489489

此時low>high查h=1low=h此時low>high查此時ST.elem[mid].key＝4<key，因此令折半查找的結構：順序索引

7171 869.1靜態(tài)查找查找方法順序折半查分塊查兩者之表結有序表、無序有序分塊有序結順序結動態(tài) 33二叉排序樹typedefstructBiTNodeemTypestructBiTNode*lchild,*}typedefstruct{KeyType…

BiTreeSearchBST(BiTreeT,KeyTypekey{/*二叉排序樹用二叉鏈表。在根指針T所指二叉排序樹中的指針，否則返回空指針*/p=while(p&&!EQ(key,p->data.key){if(LT(key,T->data.key))p=p->lchild;elsep=p->rchild;}return(p)}BiTreeSearchBST(BiTreeT,KeyTypekey{//將二叉鏈表作為二叉排序樹 if((!T)||EQ(key,T->data.key))return(T);elseif(LT(key,T->data.key)return(SearchBST(T->lchild,key));return(SearchBST(T->rchild,key}//例：二叉排序樹中插入結點40f3結點，并且是查找不成功時查找路徑問的插入新結點的時機： Status(BiTreeT,KeyTypekey,BiTreef,BiTree{//在根指針為T的二叉排序樹中查找關鍵字等于key的元素，若路徑的最末結點，并返回FALSE。f指向T的雙親，初始調(diào)用時if(!T){p=f;returnFALSE;elseif(EQ(key,T->data.key)){p=T;returnTRUE;}elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key,T,p); returnSearchBST(T->rchild,key,T,p);//SearchBST算法StatusInsertBST(BiTree emTypeif(!SearchBST(T,e.key,NULL,p){//s=(BiTree)s->data=e;s->lchild=s-if(!p)T=s; //T為空， elseif(LT(e.key,p->data.key))p->lchild=s; return}elsereturnFALSE;// 算法例1：插入值為280

T

f

f

f

{45，24，53，45，12，24，90生成的二叉排序樹如下對二叉排序樹進行中序遍歷可以得到有序序列二叉樹排序刪除。FpFpP二叉排序樹FpFpP二叉排序樹FpPFpPFF刪除 刪除 S

中序遍歷：PLPSS 中序遍歷：QSPL

中序遍歷：PLSS 中序遍歷：QS

Q中序遍歷：PPRS

S 中序遍歷：PRSS

中序遍歷：QSP

中序遍歷：QS 二叉排序樹沿p左子樹的根C的右子樹分支找到S，S的右子樹為空，將S的左子樹成為S的雙親Q的右子樹，用S取代p 中序遍歷：CLCQLQSLSPPR SP

中序遍歷：CLCQLQSLSPR若C無右子樹，用C取代 P

中序遍歷：CLCPPR

中序遍歷：CLCPR二叉排序樹f->lchild=NULL或f

沿p左子樹的根C的右子樹分支找到S，S的右子樹為空，將S的左子樹成為S的雙親Q的右子樹，用S取代p 若C無右子樹，用C取代 voidDelete(BiTree&p{//從二叉排序樹中刪除結點p，并重接它的左或右子樹if(!p->rchild) //右子樹為空，則只需重接左子樹{q= p=p- free(q);elseifp->lchild){q=p; p=p->rchild; free(q} //左右子樹均不空{(diào)q= s=p-whiles->rchild 定位p{q=s;s=s- p->datas->data;sif(qp)q->rchild=s->lchild;//else q->lchild=s->lchild; deletes;}//Delete算法 刪 刪 60

70

708 7刪 刪77 性能 單支

二叉排序樹的二叉排序樹的適用范平衡二叉AVLG.M.Adelson-VelskyE.M.Landis樹的深度 - 平衡二叉排序

非平衡二叉排序 0A

h-

LL調(diào) h-

h-

h-

h-向右h-

h-

-

-h-

RRh

B0Ah-B0Ah-h-向左0BACh-0BACh--h-

h-

LR調(diào) h-

h-

h-

h-C0B-Ah-h-C0B-Ah-h-h-

- -A B

0AC-0AC-Bh-h-C C

h-

h- h-h-

h-

h-先向右旋再向左 按照如下順序建立平衡二叉樹：10,13,19,7,4,15,24,33,插入10、13、19、7、4、B 19

7

按照如下順序建立平衡二叉樹：10,13,19,7,4,15,24,33,插入10、13、19、7、4、8、A

AC

CA 10

按照如下順序建立平衡二叉樹：10,13,19,7,4,15,24,33,插入10、13、19、7、4、8、15、24、

B C

C

型按照如下順序建立平衡二叉樹：10,13,19,7,4,15,24,33,插入10、13、19、7、4、87487481924RRBA按照如下順序建立平衡二叉樹：10,13,19,7,4,15,24,33,插入10、13、19、7、4、877A4824C7A874 48B 648

648648刪除：28，16，30，21，22對26進行LL調(diào)整，對10進行LR調(diào)8647刪除：28，16，30，21，22對26進行LL調(diào)整，對10進行LR調(diào)8647刪除：28，16，30，21，22對26進行LL調(diào)整，對10進行LR調(diào)整，對26進8647

8647 B-樹的基本動態(tài)B-樹 B+樹(n,a0,k1,a1,k2,a2,……,kn,anB-樹的B-樹是B-樹的B-樹是一種平衡的多路查找 2020cd10bcefg4510ee4525非B-非B-B-B-樹的查找內(nèi)進行順序（或折半）兩個過程交叉進若查找不成功，則返回插入位置B-樹的插入 (A0,K1,……,Ks-1,As-1,Ks,As,Ks+1,……sm/2(A0，K1，……，Ks-1，As-

(As，Ks+1，……2040

6080 2040

20

，20，20， 不能小于m/2-1，否則，要從其左（或右）兄弟結第9被刪關鍵碼所在葉結點不是根結點，且刪nm/2，則直接刪第9弟）nm/2，則可按以下步Ki(1in)下移；大）Ki位置；第9m/2-1，假設該結點有右兄弟，第9 33被刪關鍵

61 3 3若再刪除關鍵 第93第9361613613結點聯(lián)合

刪除刪除結點

刪除結點

刪除2刪除刪除

非葉結點刪階數(shù)一般取得較大）kq組成二元組（k,q）。q是指向(B,)(B,)(E,(A,(F,)(G,(C,)(D,nn(n,k1,a1,k2,a2,……,kn,an

件）葉

2041

60

8510

2736

4651

65799292CHACHABCDH9.3哈希,< 9.3哈希散列法（哈希法）一個確定的函數(shù)關系 9.3哈希散列法（哈希法編地總人12字，

9.3哈希散列法的幾個重要 9.3哈希構造哈希函數(shù)的基運算盡可能盡可能減構造哈希函

9.3哈希構造哈希函

9.3哈希 函數(shù)為H(key)=key%p，p<=mH(key)=9.3哈希擇一個“好”（盡可能少產(chǎn)生）的哈希函數(shù)之外，還需要找到一種“處理“處理”的實際含義是：為產(chǎn)生的地常用的解決的方法：開放地址法，鏈地址法，9.3哈希開散列方法（openhashing，也稱為拉鏈法separate open 9.3哈希解 的方法——鏈地址建立一個鏈表方式 同義詞子表 2例 {19,13,34,02, 529,15,23,5 H(key)=key% 89

9.3哈希解 的方法——開放地址 H1,H2,…, Hi=(H(key)+di)MOD i=1,2,…, 增量9.3哈希解 的方法——開放地址增量di有三種取di=c

最簡單的情況di=12，-12，22,-22,diiH2(key（又稱雙散列函數(shù)探測9.3哈希解 的方法——開放地址例：關鍵字序哈希表表長為12，H(key)key處 開放地址法Hi=(H(key)+di)%01234567892：H(2)=2：H1=(H(key)+1)%11=(2+1)%11=23：H(23)=23：不斷找下一個空位=

5：H(5)=5：下一個空位9

9.3哈希可能產(chǎn)生的 9.3哈希解 的方法——開放地址例：關鍵字序哈希表表長為12，H(key)key處 開放地址法Hi=(H(key)+di)%01234567892：H(2)= 23：H(23)=

5：H(5)=

-1=0

空9.3哈希解 的方法——開放地址H2(key)是另設定的一個哈希函數(shù)，它