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

1、查找表上的基本運算查找表上的基本運算:建立查找表建立查找表create(st, n)查找查找search(st, k)遍歷查找表遍歷查找表traverse(st)查找結(jié)果查找結(jié)果:靜態(tài)查找表靜態(tài)查找表動態(tài)查找表動態(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二二. 有序表的查找有序表的查找查找表中記錄按關鍵字有序排列的表查找表中記錄按關鍵字有序排列的表. 即即: 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) 按表中記錄的關鍵字分塊

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

5、查找長度為查索引表確定所在塊的平均查找長度; lw為在塊內(nèi)查找記錄的平均查找長度為在塊內(nèi)查找記錄的平均查找長度;三種查找方法比較三種查找方法比較順序查找順序查找折半查找折半查找分塊查找分塊查找asl大大小小 中中表結(jié)構(gòu)要求表結(jié)構(gòu)要求無無有序表有序表 分段有序分段有序（塊之間有序）（塊之間有序）78100619012372484553算法描述為：算法描述為： func bstsrch (t:bitreptr ; k:keytype):bitreptr; 查找不成功時返回查找不成功時返回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 動態(tài)查找表動態(tài)查找表3. bst的插入的插入插入原則插入原則：記下查找不成功時比較的最后一個結(jié)點的位：記下查找不成功時比較的最后一個結(jié)點的位置，將插入結(jié)點作為該結(jié)點的左或右孩子。置，將插入結(jié)點作為該結(jié)點的左或右孩子。 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é)點的位置記載上次比較的結(jié)點的位置 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 動態(tài)查找表動態(tài)查找表45145437

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

10、結(jié)點的值均大于其根結(jié)點的值； 而中序遍歷又是以而中序遍歷又是以l dr順序訪問的。順序訪問的。9.2 9.2 動態(tài)查找表動態(tài)查找表9.2 9.2 動態(tài)查找表動態(tài)查找表刪除的原則刪除的原則：cqcslsclffrfprppqqls cslclprqqlsfsslclfprqqlc(2) s代替代替p，而，而 sl為為qr ;proc del_bstree1 (var bst：bitreptr ；f，p：bitreptr）；）； 刪除刪除p結(jié)點；結(jié)點；f 是是p的雙親的雙親 if f=nil then p為根結(jié)點為根結(jié)點 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é)點不是根結(jié)點 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é)點中的值為該結(jié)點的平衡因子結(jié)點中的值為該結(jié)點的平衡因子 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) 為了得到平衡樹，需作如下處理為了得到平衡樹，需作如下處理 在在t為根結(jié)點的為根結(jié)點的avl上插入關鍵字為上插入關鍵字為k的新結(jié)點的新結(jié)點插入根結(jié)點插入根結(jié)點 （3）判）判a為

14、根的子樹是否失去平衡為根的子樹是否失去平衡 balanced:=true; caes abf=0： abf：=d 原來為原來為0, 插入后為插入后為d abf+d=0：abf：=0 原來為原來為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)整后子樹根指