考研數(shù)據(jù)結(jié)構(gòu)chapt

1、查找表上的基本運(yùn)算查找表上的基本運(yùn)算:建立查找表建立查找表create(st, n)查找查找search(st, k)遍歷查找表遍歷查找表traverse(st)查找結(jié)果查找結(jié)果:靜態(tài)查找表靜態(tài)查找表動(dòng)態(tài)查找表動(dòng)態(tài)查找表一一. 順序表的查找順序表的查找 func seqsrch(r:sqlisttp; k:keytype):integer; r0.key:=k; i:=n; while ri.key k do i:=i-1; return(i) endf; seqsrch: : func seqsrch(r:sqlisttp; k:keytype):integer; r0.key:=k; i:

2、=n; while ri.key k do i:=i-1; return(i) endf; seqsrchfunc seqsrch2(r:sqlisttp; k:keytype):integer; rn+1.key:=k; i:=1; while ri.key k do i:=i+1; if i=n+1 then return(0) else return(i) endf; seqsrch2func seqsrch(r:sqlisttp; k:keytype):integer; r0.key:=k; i:=n; while ri.key k do i:=i-1; return(i) endf;

3、 seqsrch二二. 有序表的查找有序表的查找查找表中記錄按關(guān)鍵字有序排列的表查找表中記錄按關(guān)鍵字有序排列的表. 即即: ri.keyrmid.key: low:=mid+1; k=rmid.key: found:=true; krmid.key: low:=mid+1; k=rmid.key: found:=true; krmid.key: high:=mid-1; endc; if found then return(mid) else return(i) endf; binsrch三三. 索引順序表的查找索引順序表的查找(分塊查找分塊查找)索引表索引表 : 1) 按表中記錄的關(guān)鍵字分塊

4、按表中記錄的關(guān)鍵字分塊, r1,r2,rl要求要求: 第第rk 塊中的所有關(guān)鍵字塊中的所有關(guān)鍵字 rk+1塊中的所有關(guān)鍵字塊中的所有關(guān)鍵字 k=1,2,l-1, 稱(chēng)為稱(chēng)為“分塊有序分塊有序”2) 對(duì)每塊建立一個(gè)索引項(xiàng)對(duì)每塊建立一個(gè)索引項(xiàng), 包含以?xún)身?xiàng)內(nèi)容包含以?xún)身?xiàng)內(nèi)容: 關(guān)鍵字項(xiàng)關(guān)鍵字項(xiàng) : 為該塊中最大關(guān)鍵字值為該塊中最大關(guān)鍵字值; 指針項(xiàng)指針項(xiàng) : 為該塊第一個(gè)記錄在表中位置為該塊第一個(gè)記錄在表中位置.3) 所有索引項(xiàng)組成索引表所有索引項(xiàng)組成索引表9.1 9.1 靜態(tài)查找表靜態(tài)查找表分塊查找表的平均查找長(zhǎng)度分塊查找表的平均查找長(zhǎng)度asl=lb+lw其中其中: lb為查索引表確定所在塊的平均

5、查找長(zhǎng)度為查索引表確定所在塊的平均查找長(zhǎng)度; lw為在塊內(nèi)查找記錄的平均查找長(zhǎng)度為在塊內(nèi)查找記錄的平均查找長(zhǎng)度;三種查找方法比較三種查找方法比較順序查找順序查找折半查找折半查找分塊查找分塊查找asl大大小小 中中表結(jié)構(gòu)要求表結(jié)構(gòu)要求無(wú)無(wú)有序表有序表 分段有序分段有序（塊之間有序）（塊之間有序）78100619012372484553算法描述為：算法描述為： func bstsrch (t:bitreptr ; k:keytype):bitreptr; 查找不成功時(shí)返回查找不成功時(shí)返回nil if (t=nil) cor (t.key=k) then return(t) else if t.ke

6、yk then return(bstsrch(t.rchild, k) else return(bstsrch(t. lchild, k) endf bstsrch 9.2 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表3. bst的插入的插入插入原則插入原則：記下查找不成功時(shí)比較的最后一個(gè)結(jié)點(diǎn)的位：記下查找不成功時(shí)比較的最后一個(gè)結(jié)點(diǎn)的位置，將插入結(jié)點(diǎn)作為該結(jié)點(diǎn)的左或右孩子。置，將插入結(jié)點(diǎn)作為該結(jié)點(diǎn)的左或右孩子。 proc insbst (var bst :bitreptr; k:keytype); f:=nil ; found:=false; f:= srch_bstree (f, bst, k, found

7、) if not found then ins_bstree(f, bst, k) endp;insbstfunc srch_bstree (var f:bitreptr; bst:bitreptr; k:keytype; var found:boolean):bitreptr; if bst=nil then found:=false; return(f) else if t.key=k then found:=true; return(bst) else f:=bst; f記載上次比較的結(jié)點(diǎn)的位置記載上次比較的結(jié)點(diǎn)的位置 if t.keyk then return(srch_bstree(

8、f, bst.rchild, k, found) else return(srch_bstree(f, bst.lchild, k, found) endf srch_bstree proc ins_bstree(var f, bst:bitreptr; k:keytype); new(s); s.key:=k; s.lchild:=nil; s.rchild:=nil; if bst=nil then bst:=s else if kf.key then f.lchild:=s else f.rchild:=sendp;ins_bstree9.2 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表45145437

9、53902246125例：設(shè)例：設(shè)bst為空，為空，查找關(guān)鍵字序列為查找關(guān)鍵字序列為45，24，53，45，12，24，90，則經(jīng)過(guò)一系列查找插入操作后，生成的則經(jīng)過(guò)一系列查找插入操作后，生成的bst為：為：9.2 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表4. bst的特點(diǎn)：的特點(diǎn)：(1) 中序遍歷中序遍歷bst可得到一個(gè)關(guān)鍵字的有序序列?？傻玫揭粋€(gè)關(guān)鍵字的有序序列。 如上例：中序遍歷結(jié)果為：如上例：中序遍歷結(jié)果為：12 ，24，45，53，90 這是由于這是由于bst中左子樹(shù)的所有結(jié)點(diǎn)的值均小于其根結(jié)點(diǎn)的值，中左子樹(shù)的所有結(jié)點(diǎn)的值均小于其根結(jié)點(diǎn)的值， 右子樹(shù)的所有結(jié)點(diǎn)的值均大于其根結(jié)點(diǎn)的值；右子樹(shù)的所有

10、結(jié)點(diǎn)的值均大于其根結(jié)點(diǎn)的值； 而中序遍歷又是以而中序遍歷又是以l dr順序訪問(wèn)的。順序訪問(wèn)的。9.2 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表9.2 9.2 動(dòng)態(tài)查找表動(dòng)態(tài)查找表刪除的原則刪除的原則：cqcslsclffrfprppqqls cslclprqqlsfsslclfprqqlc(2) s代替代替p，而，而 sl為為qr ;proc del_bstree1 (var bst：bitreptr ；f，p：bitreptr）；）； 刪除刪除p結(jié)點(diǎn)；結(jié)點(diǎn)；f 是是p的雙親的雙親 if f=nil then p為根結(jié)點(diǎn)為根結(jié)點(diǎn) case plchild=nil and prchild=nil：bst：=

11、nil； plchild=nil：bst：= prchild； prchild=nil：bst：= plchild； eles s：= plchild ； while s rchild nil do s：= s rchild ； bst：= plchild； s rchild：= prchild； endc cslclprqqlscslclprpqsqlelse p不是根結(jié)點(diǎn)不是根結(jié)點(diǎn) case p rchild=nil：f lchild：= p lchild： p lchild= nil：f lchild：= p rchild； else s：= p lchild； while s rchi

12、ldnil do s:= s rchild； s lchild：= p rchild； f lchild：= p lchild； endcendp；del_bstree1 459353371224 122437455393 asl(a)=1/6（1+2+2+3+3+3）=14/6asl(b)=1/6（1+2+3+4+5+6）=21/6 1001(a)01-1002(c)0100-11-1(b)結(jié)點(diǎn)中的值為該結(jié)點(diǎn)的平衡因子結(jié)點(diǎn)中的值為該結(jié)點(diǎn)的平衡因子 132413avl avl avl旋轉(zhuǎn)旋轉(zhuǎn)372413非非avl372413avl非非avl903724135390372413旋轉(zhuǎn)旋轉(zhuǎn)旋轉(zhuǎn)旋轉(zhuǎn)9

13、053372413avl3790532413 ll0aarbrh-1h-10bblhh2aaarh-11bbrblh-1hh+1l+12aarh-1-1bblclh-1h-1 h+11chh-2crlr0carh-10bblclh-1h-1-1ah-2cr-2aalblh-1h-1-1bhbrrr0bblalh-10abrrl0cbr0aalcl-1bh-2cr1bbrh-1-2aalh-1clh-11ch-2cr(3) 為了得到平衡樹(shù)，需作如下處理為了得到平衡樹(shù)，需作如下處理 在在t為根結(jié)點(diǎn)的為根結(jié)點(diǎn)的avl上插入關(guān)鍵字為上插入關(guān)鍵字為k的新結(jié)點(diǎn)的新結(jié)點(diǎn)插入根結(jié)點(diǎn)插入根結(jié)點(diǎn) （3）判）判a為

14、根的子樹(shù)是否失去平衡為根的子樹(shù)是否失去平衡 balanced:=true; caes abf=0： abf：=d 原來(lái)為原來(lái)為0, 插入后為插入后為d abf+d=0：abf：=0 原來(lái)為原來(lái)為1(-1),插入插入-1/1后為后為0 else 失去平衡失去平衡 if d=+1 then case bbf= 1：ll-rotation bbf=-1：lr-rotation endc； else case bbf=-1：rr-rotation bbf= 1：rl-rotation endc； balanced：=false endc；if not balanced then case rl，lr旋轉(zhuǎn)處理后，旋轉(zhuǎn)處理后，b：=c f=nil: t：=b; b指向失去平衡調(diào)整后子樹(shù)根指