数据结构第九章.docx

资源描述

数据结构第九章.docx

《数据结构第九章.docx》由会员分享，可在线阅读，更多相关《数据结构第九章.docx（22页珍藏版）》请在冰点文库上搜索。

数据结构第九章.docx

数据结构第九章

第九章查找

9.1基本概念

查找（search）：

又称检索，是数据处理中经常使用的一种重要运算。

查找定义：

在含有几个结点的表R1,R2,……Rn中，给定一个K值，查找关键字K的结点，若找到则查找成功，给出其在表中的位置，否则失败，给出失败信息。

相关问题：

1.数据的存储形式（存储结构）。

2.内查找——查找过程在内存进行。

外查找——查找过程访问外存。

3.衡量一个查找算法优劣标准——平均查找长度。

平均查找长度：

ASL=∑PiCi（i=1…n）

n-----结点个数（记录数）

Pi----第i个结点查找概率（平均1/n）

Ci----第i个结点比较次数

9.2线性表的查找

1.顺序查找

基本思想：

从表的一端，顺序扫描，依次和K比较，相等即找到，否则失败。

该方法即适合顺序存储结构也适于链式存储结构。

存储结构：

typedefstruct

{keytypekey;

datatypeother;

}table;

算法:

intSEQSEARCH（tableR[],keytypeK）

{inti=0;

R[n].key=K;

while（R[i].key!

=K）i++;

if（i==n）return-1;

elsereturni

}

监视哨：

R[n]的设置，省去判定条件中i

for（i=0;i

if（R[i].key==K）returni;

return（-1）;

则此算法效率低于设置监视哨。

算法分析：

ASL=∑PiCi=1/n（1+2+……+n）=（n+1）/2

ASL’=∑PiCi=P1+2P2+……nPn

若Pn<=Pn-1<=……<=p1则ASL’最小。

若预先知道概率分布情况，应按概率大小存放以提高查找效率，一般情况概率并不清楚，可在每次查找成功，就将找到的结点和前趋交换使得经常查找的结点不断前移，便于在后续的查找过程中减少比较次数。

优缺点：

算法简单，对存贮结构无特别要求，但查找效率较低，n较大时不宜采用。

2.二分查找（折半查找）

二分查找效率较高，但要求向量存储结构并预先有序。

基本思想：

R[0]……R[n-1],每次用K与R[mind]比较相等则成功，否则

若R[mind]key>K则在R[0]……R[mind-1]中找

若R[mind]key

如此进行下去……

算法：

intBINSEARCH（tableR[],keytypeK）

{

intlow,mid,high;

low=0;high=n-1;

while（low<=high）

{mid=（low+high）/2;

if（K==R[mid].key）returnmid;

if（K

elselow=mid+1;

}

return-1;

}

例图：

查找K=21，K=85

二叉判定树：

将R[mind]作根，左子表右子表作为左子树右子树。

例图：

算法分析：

设n=2h-1，h=log2（n+1）是满二叉树，nk=2k-1

ASL=∑PiCi=1/n∑Ci=∑k*2k-1/n

=（（n+1）*log2（n+1）-1）/n

≈log2（n+1）-1

优缺点：

效率较高，但要求有序且需数组作存储结构，二分查找特别适用于那种一经建立就很少改动，而又经常查找的线性表，对那些查找少又经常改动的线性表，可采用链式存储结构进行顺序查找。

3.分块查找（索引查找）

将R[n]分成b块，前b-1块中结点个数S=n/b，最后一块结点数<=S，每一块中关键字无序，但前一块中最大key必须小于后一块中最小的，即要求分块有序，抽取块中最大关键字及起始后置构成一个索引表ID[b]。

例图：

基本思想：

首先查找索引表，索引表有序可用二分查找，顺序查找确定待查结点所在的块，在块中作顺序查找。

例如：

查找K=24K=30

索引表：

typedefstruct

{keytypekey;

intaddr;

}IDtable;

IDtableID[b];

算法：

intBLKSEARCH（tableR[],IDtableID[],keytypeK）

{inti,low1,low2,mid,high1,high2;

low1=0;high1=b-1

while（low1

{mid=（low1+high1）/2;

if（K<=ID[mid].key）high1=mid-1;

elselow1=mid+1;

}

if（low1

{low2=ID[low1.addr];

if（low1==b-1）high2=n-1;

elsehigh2=ID[low1+1].addr-1;

for（i=low2;i<=high2;i++）

if（R[i].key==K）returni;

}

return-1;

}

算法分析：

分块是两次查找，故ASL为两次查找的ASL之和。

二分：

ASL（blk）=ASL（bn）+ASL（sq）

≈log2（b+1）-1+（s+1）/2

≈log2（n/（s+1）+s/2

顺序：

ASL（blk）=（b+1）/2+（s+1）/2

≈（s2+2s+n）/2s

当s=sqrt（n）时，ASL取极小值sqrt（n）+1。

分块查找的效率介于顺序和二分之间，实用中可灵活运用。

优缺点：

插入删除较容易，无须移动大量纪录，代价是增加一个辅助空间和初始表分块排序的运算。

9.3树表的查找

1.二叉排序树（二叉查找树）

递归定义：

1.若左子树非空，则左树所有结点的值均小于根结点。

2.若右子树非空，则右树所有结点的值均大于根结点。

3.左右本身又是一个二叉排序树。

重要性质：

按中序遍历该树得到一个递增有序序列。

例图：

结点结构：

typedefstructnode

{keytypekey;

datatypeother;

structnode*lchild,*rchild;

}bstnode;

插入规则：

1.若二叉排序树为空，则待插入结点*s作根插入。

2.若二叉排序树非空，若s->key==t->key,无须插入。

3.若s->keykey，则将*s插入到根的左子树。

若s->key>t->key，则将*s插入到根的右子树。

算法：

bstnode*INSERTBST（bstnode*t,bstnode*s）

{bstnode*f,*p;

p=t;

while（p!

=NULL）

{f=p;

if（s->key==p->key）returnt;

if（s->keykey）p=p->lchild;

elsep=p->rchild;

}

if（t==NULL）returns;

if（s->keykey）f->lchild=s;

elsef->rchild=s;

returnt;

}

例图：

生成算法：

从空开始，每输入一个结点就插入到当前二叉排序树中。

bstnode*CREATBST（）

{

bstnode*t,*s;

keytypekey;

endflag=0;

datatypedata;

t=NULL;

scanf（%d,&key）;

while（key!

=endflag）

{s=malloc（sizeof（bstnode））;

s->lchild=s->rchild=NULL;

s->key=key;

scanf（%d,&data）;

s->data=other;

t=INSERTBST（t,s）;

scanf（%d,&key）;

}

returnt;

}

例图：

二叉排序树的生成过程，构造了一个关键字的有序序列（中序遍历），因此排序树由此得名。

删除规则：

从BST中删去一个结点，并保证仍是BST，先查找

1）若该结点不在BST上，则返回。

2）若该结点在BST上，则该结点为*p，*f是双亲，删除操作可按*p是否有左子树来处理。

①*p没有左子树：

将*p的右子树按BST的特点链接到合适位置。

*p若是根结点：

将*p的右子树为根做新根t=p->rchild。

*p不是根结点：

若*p是*f的左子树，则将*p右子树链接到*f的左子树。

若*p是*f的右子树，则将*p右子树链接到*f的右子树。

若*P的左右子树全空，则将空树链接到*f上。

②*p有左子树：

*p也可能有右子树，要考虑左右子树链接到合适的位置。

1）令*P的左子树直接链接到*f的左（右）链上，而*P得右子树下接到*p前趋*s的右链上，即*s是*p左子树中最右下的结点。

2）以*p的中序前趋*s顶替*p，将*s左子树直接接到*s的双亲结点*q的左链上，然后删去*s。

显然：

1）方法可能增加树的深度，不如2）方法好。

算法：

bstnode*DELBSTNODE（bstnode*t,keytypek）

{bstnode*p,*f,*s,*q;

p=t;f=NULL;

while（p!

=NULL）

{if（p->key==k）break;

f=p;

if（p->key>k）p=p->lchild;

elsep=p->rchild;

}

if（p==NULL）returnt;

if（p->rchild==NULL）

{if（f==NULL）t=p->rchild;

elseif（f->lchild==p）

f->lchild==p->rchild;

else

f->rchild==p->rchild;

free（p）;

}

else{q=p;

s=p->lchild;

while（s->rchild!

=NULL）

{q=s;

s=s->rchild;

}

if（q==p）q->lchild=s->lchild;

elseq->rchild=s->lchild;

p->key=s->key;

p->other=s->other;

free（s）;

}

returnt;

}

二叉排序树上的查找：

二叉排序树是一个有序表，和二分查找类似。

算法：

bstnode*BSTSEARCH（bstnode*t,keytypek）

{

while（t!

=NULL）

{if（t->key==k）returnt;

if（t->key>k）t=t->lchild;;

elset=t->rchild;

}

returnNULL;

}

显然：

①该查找次数不超过树的深度

②二分查找其判定树是唯一的

③含有几个结点的二叉排序树不唯一，结点插入的先后次序不同，所构成的BST形态深度也不同。

例图：

序列a：

45,24,55,12,37,53,60,28,40,70

序列b：

12,24,28,37,40,45,53,55,60,70

ASLa=（1+2*2+3*4+4*3）/10=3

ASLb=（1+2+3+……10）/10=5.5

算法分析：

二叉排序树上的ASL和二叉树的形态有关。

ASL（平均）=O（log2n）

ASL（最坏）=（n+1）/2

ASL（最好）=O（log2n）

就平均性能而言BS，BST查找差不多，但BST的插入和删除十分方便，无须移动大量记录，因此需经常进行插入删除和查找运算的表，宜采用二叉排序树作存储结构。

2.平衡的二叉排序树

平衡二叉树：

形态匀称的二叉树称平衡二叉树，其严格定义是：

或者是空树，或者是任何结点的左子树高度最多相差1的二叉树。

平衡因子：

将二叉树上任何结点的左子树和右子树高度之差称平衡因子。

只可能是-1,0,1。

例图：

性质：

深度为k的平衡二叉树至少有Nk=Nk-1+Nk-2+1个结点。

例如：

如何构造平衡二叉树——AVL树：

基本思想：

每插入一个结点，首先检查是否破坏了平衡性，若是找出其中最小不平衡子树，调整节点之间的连接关系，以达到新的平衡。

①LL型调整操作

②RR型调整操作

③LR型调整操作

④RL型调整操作

AVL树插入算法：

①由于*S的插入而失去平衡时如何找到最小不平衡子树？

②当*S插入树中之后如何修改有关结点的平衡因子？

③如何判别以*a为根的子树是否失去平衡？

插入算法：

调整算法：

算法分析：

含有几个结点的AVL树，高度h=O（log2n）,在AVL树上查找时，比较次数不会超过h，且不能蜕变为单支树，因此查找的T（n）=O（log2n）,但调整过程需要花不少时间，故是否采用AVL树，应时情况而定，一般地，若关键字是随机分布的，且对平均查找长度没有苛求，则可使用二叉排序树。

3.B_树（平衡的多叉树）

B_树用于外部文件的存储组织。

前面所讨论的算法都是内查找算法，它们适用于较小的文件。

当文件很大存放于外存进行查找时，这些查找方法就不适用了。

磁盘管理系统中的目录管理，以及数据库系统中的索引组织多数都采用B_树这种数据结构。

B_树定义：

1.每个结点至多m个孩子；

2.除根和叶之外其余至少右m/2个孩子；

3.根至少有两个孩子（唯一例外是只有一个根的B_树）；

4.所有叶在同一层，且不含任何关键字信息；

5.有K个孩子的非叶恰好包含K-1个关键字。

在B_中每个结点的关键字从小到大排列，叶结点不包含任何关键字信息，且叶子数正好等于树中所包含的关键字总个数加1。

B_树运算：

1.查找

2.插入

3.删除

例图：

B-树上的插入删除操作举例：

1.在3阶B-树上插入关键字63，83，23

插入83

插入63

插入23

2.在3阶B-树上插入关键字23，83，63

插入23

插入83

插入63

3.在3阶B-树上删除关键字50，53

查找效率：

设L+1层的m阶B树包含N个关键字因此有N+1个树叶。

L=1+log[m/2]（（N+1）/2）

若N=1999998，m=199，则L至多等于4，效率很高。

B+树：

B+树是一种常用于文件组织的B_树的变形树，一棵m阶的B+树与m阶的B_树的差异是：

1.有k个孩子的结点必有k个关键字；

2.所有的叶结点包含关键字全部信息及指向记录的指针，从小到大顺序链接；

3.上面各层结点中的关键字，均是下一层相应最大关键字的复写（当然也可采用最小关键字复写原则）。

例图：

通常在B+树上有两个指针，一个指向根结点，另一个指向关键字小的叶子结点。

（实际上B+树已不是严格意义上的树）。

在B+树上进行随机查找、插入和删除的过程，基本上与B_树类似。

只是在查找时，若非终端结点上的关键字等于给定值，并不终止，而是继续向下直到叶子结点。

因此，在B+树中，不管查找成功与否，每次查找都是走了一条从根到叶子结点的路径。

B+树的查找分析类似于B_树。

B+的插入也仅在叶子结点上进行，当结点中的关键字个数分别为「（m+1）/2「和」（m+1）」/2，并且，它们的双亲结点中应同时包含这两个结点的最大关键字。

B+树的删除仅在叶子结点进行。

当叶子结点中的最大关键字被删除时，其在非终端结点中值可以作为一个分界关键字存在。

若因删除而使结点中关键字的个数少于「m/2「时，则和该结点的兄弟结点合并，合并过程和B_树类似。

9.4散列表的查找

前述的讨论中，位置和关键字间没有明确的关系，结点在数据结构中的相对位置是随机的，因此要通过多次比较查找才能确定其位置，散列表可解决这一问题。

1.散列表（哈希表——Hashing）

散列表是一种重要的存储方法，也是常见的查找方法。

基本思想：

以K为自变量找出一种对应关系f（K），认为f（K）为K的存储地址，f为散列函数，f（K）为散列地址。

查找时根据K的值计算地址，然后到相应单元里去找。

例9.1：

例9.2：

例9.3：

简单总结：

1）由K值既得结点的位置，快速，无需查找比较。

2）装填因子α=n/m，n——结点数，m——散列空间。

通常α∈[0.65—0.9]较恰当。

3）散列函数选取原则是尽可能简单，函数值域在表的范围之内，分配较均匀（K不同则f（K）不同——即不冲突）。

4）解决冲突（同义词）

若H（key1）=H（key2），则发生冲突，一旦发生冲突，则应予以解决。

散列查找所面临的问题：

1）选择简单，冲突少的均匀的散列函数。

2）确定一个解决冲突的方法即存储同义词。

2.散列函数的构造方法

1）数字选择法

2）平方取中法

3）折叠法

4）除余法

5）基数转换法

6）随机数法H（key）=ramdom（key）

3.处理冲突的方法

1）开放地址法：

当冲突发生时，使用某种方法在散列表中形成一个探查序列，沿此序列逐个查找，直到找到K或一个开放地址为止，插入时可插入到单元中，查找时碰到空（开放的地址）说明表中没有K。

冲突探查序列查找、插入

形成探查序列的方法不同解决冲突的方法也不同。

设散列表HT的长度为m，结点个数为n：

①线性探查法：

将散列表看成一个环表，若地址d（即H（key）=d）单元发生冲突，则依次探查下述地址：

d+1d+2……m-101……d-1

找到一空单元或找到key为止，给出地址。

若到d，则说明查找或插入失败（表满）。

发生冲突时，求下一个开放地址公式为：

di=（d+1）%mi=1,2,……,s（1<=s<=m-1）

d=H（key）

例题9.4：

关键字序列key=（26,36,41,38,44,15,68,12,06,51,25）

构造散列表，为减少冲突令α<1，暂取α=n/m=0.75，m=n/α=15。

用求余法构造，选P=13（接近15的素数），H（key）%13。

地址

键值

比较

查找成功的ASL=（1+5+……+3）/11=20/11≈1.82

查找不成功ASL=（8+7+……+11）/13=52/13=4

注意：

当H（15）=2，H（68）=3，15与68不是同义词，但被15抢占，这种现象称为堆积（本来不该发生冲突的非同义词也发生了冲突）。

堆积原因：

①散列函数选择不当。

②α过大，造成可选择的地址少，就可能堆积。

下面介绍减少堆积的其他方法：

②二次探查法：

探查序列：

12-1222-2232-32……

即发生冲突时，将同义词来回散列在d=H（key）的两端，求下一个开放地址的公式为：

d2i-1=（d+i2）%m

d2i=（d-i2）%m（1<=i<=（m-1）/2）

优缺点：

可减少堆积，但不容易探查到整个散列表空间。

③随机探查法：

公式为：

di=（d+Ri）%m（1<=i<=m-1）

d=H（key），R1,R2,……,Rm-1是1,2,……,m-1随机序列。

得到随机序列，涉及随机函数的产生问题，实用中常采用移位寄存器的序列代替随机数序列。

设m是2的方幂，K是1到m-1之间的一个整数，产生移位寄存器序列的方法：

1）任取一个R1（1<=R1<=m-1）

2）设已知Ri-1令

Ri=2Ri-1（当2Ri-1

Ri=2Ri-1-m

K（当2Ri-1>=m）

K,m,Ri-1,Ri是二进制表示。

为按位模2加法，与普通加法类似，只是不产生进位。

K需选择合适，才能产生1,2,……,m-1的随机序列。

④双散列函数探查法

使用两个散列函数H1，H2并和m互素的数作为对散列地址的补偿，若H1（key）=d时，发生冲突，再计算H2（key），公式为：

di=（d+iH2（key））%m

定义H2（key）的方法较多，但必须和m互素，才能均匀分布。

若m为素数，则H2（key）取1……m-1任一数均与m互素，因此，

H2（key）=key%（m-2）+1

若m是2的方幂，则H2（key）可取1……之间的任何一个奇数。

2）拉链法：

是将所有关键字为同义词的结点链接在一个单链表中，可定义指针数组HTP[m]，地址为i的结点均插入到以HTP[i]为头指针的单链表中。

例9.5：

查找成功的ASL=（1*7+2*2+3*1+4*1）/11=18/11≈1.64

查找不成功ASL=（1+0+……+4）/13=11/13≈0.85

优点：

1）不会产生堆积，ASL短。

2）结点动态申请适于表长不确定的情况。

3）插入删除易于操作。

4）当α较大时，拉链法所用的空间比开放地址法多。

但α越大，开放地址法所需的探查次数越大，因此拉链法所增加的空间开销是合算的。

4.散列表的查找及分析

给定K值，根据建表时的散列函数H计算地址H（K），若表中该地址对应的空间未被占用，则查找失败，否则比较若相等，查找成功，否则按处理冲突的方法找下一个地址，如此……

线性探查解决冲突的查找和插入算法：

结点定义：

typedefstruct

{keytypekey;

datatypeother;

}hashtable;

hashtableHT[m];

#definenil0

#definem18

intLINSRCH（hashtableHT[],keytypeK）

{intd,i=0;

d=d（K）;

while（（i

=K）&&（HT[d].key!

=nil））

{i++;

d=（d+i）%m;

}

returnd;

}

voidLINSERT（hashtableHT[],hashtables）

{intd;

d=LINSRCH（HT[],s.key）

if（HT[d].key==nil）HT[d]=s;

elseprintf（ERROR）;

}

拉链法解决冲突的查找和插入算法：

结点定义：

typedefstructnodetype

{keytypekey;

datatypeother;

structnodetype*next;

}chainhash;

chainhashHTC[m];

chainhash*C

展开阅读全文