专业课参考-数据结构

11第92第9插入删去3第9学 专计算 计算 计算 信息工 信息工 第9学 专计算 计算 计算 信息工 信息工 第9查找方法评价：平均查找长度ASLAverageSearchLength)设查找成功的概率为1Pi=1平均查找长度ASLCiiPii6

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

7第9对数值型关#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静态

有序表的查找：折半索引顺序表的查找：分块查

用线性表用顺序表表示静态用线性链表表示静查找方法：顺序typedef ElemType*elem; 0号单元留空intlength;}SSTable

3012345673intSearch_Seq(SSTableST,KeyTypekey{//在顺序表ST中顺序查找其关键字等于key的数据元素。若找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静态查找查找方法顺序折半查分块查两者之表结有序表、无序有序分块有序结顺序结动态 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的双亲，初始调用时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} //左右子树均不空{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调 h-

h-

h-

h-向右h-

h-

-

-h-

RRh

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

h-

LR调 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调整，对10进行LR调8647删除：28，16，30，21，22对26进行LL调整，对10进行LR调8647删除：28，16，30，21，22对26进行LL调整，对10进行LR调整，对26进8647

8647 B-树的基本动态B-树 B+树(n,a0,k1,a1,k2,a2,……,kn,anB-树的B-树是B-树的B-树是一种平衡的多路查找 2020cd10bcefg4510ee4525非B-非B-B-B-树的查找内进行顺序（或折半）两个过程交叉进若查找不成功，则返回插入位置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结点联合

删除删除结点

删除结点

删除2删除删除

非叶结点删阶数一般取得较大）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哈希散列法（哈希法）一个确定的函数关系 9.3哈希散列法（哈希法编地总人12字，

9.3哈希散列法的几个重要 9.3哈希构造哈希函数的基运算尽可能尽可能减构造哈希函

9.3哈希构造哈希函

9.3哈希 函数为H(key)=key%p，p<=mH(key)=9.3哈希择一个“好”（尽可能少产生）的哈希函数之外，还需要找到一种“处理“处理”的实际含义是：为产生的地常用的解决的方法：开放地址法，链地址法，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（又称双散列函数探测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哈希可能产生的 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)是另设定的一个哈希函数，它