考研数据结构chapt

1、查找表上的基本运算查找表上的基本运算:建立查找表建立查找表create(st, n)查找查找search(st, k)遍历查找表遍历查找表traverse(st)查找结果查找结果:静态查找表静态查找表动态查找表动态查找表一一. 顺序表的查找顺序表的查找 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) 对每块建立一个索引项对每块建立一个索引项, 包含以两项内容包含以两项内容: 关键字项关键字项 : 为该块中最大关键字值为该块中最大关键字值; 指针项指针项 : 为该块第一个记录在表中位置为该块第一个记录在表中位置.3) 所有索引项组成索引表所有索引项组成索引表9.1 9.1 静态查找表静态查找表分块查找表的平均查找长度分块查找表的平均查找长度asl=lb+lw其中其中: lb为查索引表确定所在块的平均

5、查找长度为查索引表确定所在块的平均查找长度; lw为在块内查找记录的平均查找长度为在块内查找记录的平均查找长度;三种查找方法比较三种查找方法比较顺序查找顺序查找折半查找折半查找分块查找分块查找asl大大小小 中中表结构要求表结构要求无无有序表有序表 分段有序分段有序（块之间有序）（块之间有序）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 动态查找表动态查找表3. bst的插入的插入插入原则插入原则：记下查找不成功时比较的最后一个结点的位：记下查找不成功时比较的最后一个结点的位置，将插入结点作为该结点的左或右孩子。置，将插入结点作为该结点的左或右孩子。 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记载上次比较的结点的位置记载上次比较的结点的位置 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 动态查找表动态查找表45145437

9、53902246125例：设例：设bst为空，为空，查找关键字序列为查找关键字序列为45，24，53，45，12，24，90，则经过一系列查找插入操作后，生成的则经过一系列查找插入操作后，生成的bst为：为：9.2 9.2 动态查找表动态查找表4. bst的特点：的特点：(1) 中序遍历中序遍历bst可得到一个关键字的有序序列。可得到一个关键字的有序序列。 如上例：中序遍历结果为：如上例：中序遍历结果为：12 ，24，45，53，90 这是由于这是由于bst中左子树的所有结点的值均小于其根结点的值，中左子树的所有结点的值均小于其根结点的值， 右子树的所有结点的值均大于其根结点的值；右子树的所有

10、结点的值均大于其根结点的值； 而中序遍历又是以而中序遍历又是以l dr顺序访问的。顺序访问的。9.2 9.2 动态查找表动态查找表9.2 9.2 动态查找表动态查找表删除的原则删除的原则：cqcslsclffrfprppqqls cslclprqqlsfsslclfprqqlc(2) s代替代替p，而，而 sl为为qr ;proc del_bstree1 (var bst：bitreptr ；f，p：bitreptr）；）； 删除删除p结点；结点；f 是是p的双亲的双亲 if f=nil then p为根结点为根结点 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不是根结点不是根结点 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)结点中的值为该结点的平衡因子结点中的值为该结点的平衡因子 132413avl avl avl旋转旋转372413非非avl372413avl非非avl903724135390372413旋转旋转旋转旋转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为根结点的为根结点的avl上插入关键字为上插入关键字为k的新结点的新结点插入根结点插入根结点 （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旋转处理后，旋转处理后，b：=c f=nil: t：=b; b指向失去平衡调整后子树根指