《数据结构》课件第8章(查找表)11.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《《数据结构》课件第8章(查找表)11.ppt》由用户(momomo)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课件 查找 11
- 资源描述:
-
1、 查找表:查找表:是一种以集合为逻辑结构,以查找为核心运是一种以集合为逻辑结构,以查找为核心运 算,同时包括其他运算的数据结构。算,同时包括其他运算的数据结构。8.1 8.1 基本概念基本概念查找表查找表静态查找表静态查找表动态查找表动态查找表1.建表:建表:Create(st)2.查找:查找:Search(st,k)3.读表元:读表元:Get(st,pos)2.查找:查找:Search(st,k)3.读表元:读表元:Get(st,pos)1.初始化:初始化:Initiate(st)4.插入:插入:Insert(st,k)5.删除:删除:Delete(st,k)8.2 8.2 静态查找表静态查
2、找表1)1)顺序表上的查找:顺序表上的查找:以顺序表作为存储结构,然后在这以顺序表作为存储结构,然后在这个存储结构上实现静态查找表的基本运算。个存储结构上实现静态查找表的基本运算。顺序表类型定义如下:顺序表类型定义如下:#define maxsize 静态查找表的表长静态查找表的表长typedef struct keytype key;/关键字关键字 /其他域其他域 rec;typedef rec sqtablemaxsize+1;int n;/最后一个数据元素的下标最后一个数据元素的下标顺序查找过程:顺序查找过程:假定该查找表有假定该查找表有n n个记录,首先将要查个记录,首先将要查找的那个
3、关键字赋给实际上并不存在的第找的那个关键字赋给实际上并不存在的第n+1n+1个记录个记录的关键字域,然后从头开始一个一个的向下查找,用的关键字域,然后从头开始一个一个的向下查找,用i i来计数来计数,查到就送出来看查到就送出来看i i是第几个,若是第几个,若i=ni=n,则查找,则查找成功,若成功,若i=n+1i=n+1则查找失败。则查找失败。void seqsrch(sqtable r,keytype k)/在长度为在长度为n的表的表r中查找关键字为中查找关键字为k的元素,的元素,rn为表尾的扩为表尾的扩 充充;i指示查找结果指示查找结果 rn.key=k;i=0;/给监督哨赋值给监督哨赋值
4、 while(ri.key!=k)i+;if(ikrmid.keyk,则,则k k必在较低标号的那一半表中,必在较低标号的那一半表中,令令high=mid-1high=mid-13)3)若若rmid.keykrmid.keyhigh(lowhigh(查查 找失败找失败)为止。为止。例:给出表元素关键字为:例:给出表元素关键字为:05,13,19,21,37,56,64,75,80,88,921.查找关键字查找关键字k=21 的情况的情况(1)low=1;high=11;mid=(1+11)div 2=605 13 19 21 37 56 64 75 80 88 92lowmidhigh因为因为
5、rmid.keyk,所以向左找,令,所以向左找,令high=mid-1=5(2)low=1;high=5;mid=(1+5)div 2=305 13 19 21 37 56 64 75 80 88 92lowmidhigh因为因为rmid.keyk,所以向右找,令,所以向右找,令low=mid+1=4(3)low=4;high=5;mid=(4+5)div 2=405 13 19 21 37 56 64 75 80 88 92lowmidhigh因为因为rmid.key=k,查找成功,所查元素在表中的序号为,查找成功,所查元素在表中的序号为mid 的值的值(1)low=1;high=11;mi
6、d=(1+11)div 2=6因为因为rmid.keyk,所以向右找,令,所以向右找,令low=mid+1=7(2)low=7;high=11;mid=(7+11)div 2=905 13 19 21 37 56 64 75 80 88 92lowmidhigh因为因为rmid.keyk,所以向左找,所以向左找,high=mid-1=92.查找关键字查找关键字k=85 的情况的情况05 13 19 21 37 56 64 75 80 88 92lowmidhigh因为因为lowhigh,所以查找失败,所以查找失败void Binsrch(sqtable r,keytype k)/在长度为在长度
7、为n的有序表的有序表r中查找关键字为中查找关键字为k的元素,查到后输出的元素,查到后输出 low=1;high=n;/置初值置初值 while(lowrmid.key)low=mid+1;/向右找向右找 else high=mid-1;/向左找向左找 if(lowhigh)printf(no succn);/lowhigh,查找不成功,查找不成功Void BinSearch(sqtable r;keytype k;int l,h)low=l;high=h;if highrmid.key:low=mid+1;BinSearch(r,k,low,high);break;case k=rmid.ke
8、y:printf(succ i=%dn,mid);return;case krmid.key:high=mid-1;BinSearch(r,k,low,high);break;递归算法描述如下:递归算法描述如下:算法的性能分析:算法的性能分析:以上面的以上面的11个元素的查找表为例,找到第个元素的查找表为例,找到第6个元素仅需比较个元素仅需比较1次;找到第次;找到第3个和第个和第9个元素需比较个元素需比较2次;找到第次;找到第1,4,7和和10个元素需个元素需比较比较3次;找到第次;找到第2,5,8和和11个元素需比较个元素需比较4次。上面的查找过程可次。上面的查找过程可以用下图所示的一棵二叉
9、树来表示。以用下图所示的一棵二叉树来表示。6391471011258树中每一个结点表示树中每一个结点表示表中的一个数据元素,表中的一个数据元素,结点中的值为该元素结点中的值为该元素在表中的位置在表中的位置折半查找的最大查找长度为折半查找的最大查找长度为 log2n+1 找到元素的过程:正好是从根节点一直走到某个节点的路径,找到元素的过程:正好是从根节点一直走到某个节点的路径,因此所用的比较次数最多等于树的深度。由此看来,无论元素找因此所用的比较次数最多等于树的深度。由此看来,无论元素找到或找不到到或找不到,查找某一元素的比较次数最多等于树的深度,即查找某一元素的比较次数最多等于树的深度,即 l
10、og2n+1 。那么引出一个问题,折半查找的平均查找长度是多少那么引出一个问题,折半查找的平均查找长度是多少?ASLnS=CiPi=1/njASLnS=CiPi=1/nj*2 2j-j-1 i=1i=1n nj=1j=1h h=(n+1/n)=(n+1/n)*loglog2 2(n+1)-1(n+1)-1那么表的长度一定为那么表的长度一定为n=2n=2h h-1,-1,我们假定表中每个元素的查我们假定表中每个元素的查找概率相等找概率相等.(Pi=1/n),.(Pi=1/n),则平均查找长度为则平均查找长度为:我们用深度为我们用深度为h h的满二叉树描述折半查找来进行分析。的满二叉树描述折半查找
11、来进行分析。满二叉树的特点是:满二叉树的特点是:层次为层次为1 1的结点有的结点有1 1个个;层次为层次为2 2的结点有的结点有2 2个个;,层次为层次为h h的结点为的结点为2 2h-1h-1 个个 。若是满二叉树则节点数若是满二叉树则节点数n=2n=2h h-1-13)3)分块查找分块查找:这种查找方法是表里的元素均匀的分这种查找方法是表里的元素均匀的分成若干块,块与块之间是有序的,块中的元素是成若干块,块与块之间是有序的,块中的元素是无序的,这种查找方法又称为索引顺序查找。无序的,这种查找方法又称为索引顺序查找。在分块查找中对每一块建立一个索引项,其中包括两项内容:在分块查找中对每一块建
12、立一个索引项,其中包括两项内容:关键字项关键字项(其值为最大关键字或最小关键字其值为最大关键字或最小关键字)和指针项和指针项(指示该块指示该块的第的第1 1个记录在表中的位置个记录在表中的位置)。索引表按关键字有序,表分块有序。索引表按关键字有序,表分块有序。分块有序:指第二块中所有记录的关键字均大于分块有序:指第二块中所有记录的关键字均大于(或小于或小于)第第一块中最大一块中最大(或最小或最小)关键字,第三块中的所有关键字均大于关键字,第三块中的所有关键字均大于(或或小于小于)第二块中的最大第二块中的最大(或最小或最小)关键字关键字,以此类推。以此类推。例例:有一个表有一个表,各元素的关键字
13、为各元素的关键字为:22,12,13,9,8,33,42,44,38,24,48,60,58,74,47 22,12,13,9,8,33,42,44,38,24,48,60,58,74,47 把它平均分成三块,按上升的次序排列,如下图所示:把它平均分成三块,按上升的次序排列,如下图所示:2212139833424438244860587447123456789101112131415第一块第一块第二块第二块第三块第三块1611224474关键字表关键字表小小大大指针表指针表:应该指向各块的第一个关键字。应该指向各块的第一个关键字。分成三块分成三块每块每块5 5个个关键字关键字分块查找的方法分块
14、查找的方法:1)1)由于索引表按关键字有序,则确定由于索引表按关键字有序,则确定k k在哪一块的查找在哪一块的查找 可以用顺序查找,也可用折半查找。可以用顺序查找,也可用折半查找。分块查找的平均查找长度应该是前两者之和:分块查找的平均查找长度应该是前两者之和:即:即:ASLASLbsbs=Lb+Lw=Lb+Lw用顺序查找方法用顺序查找方法,确定所在的块确定所在的块,则则 Lb=1/bj Lb=1/bj j=1j=1b b用顺序查找方法用顺序查找方法,查找的元素所在位置查找的元素所在位置,则则Lw=1/siLw=1/sii=1i=1s s 已知表的长度为已知表的长度为n,n,分成分成b b小块小
15、块,每块有每块有s s个元素个元素,那那么么b=n/s.b=n/s.若表中各元素的查找概率相等若表中各元素的查找概率相等,那么每块的那么每块的查找概率为查找概率为1/b,1/b,块中每个元素的查找概率为块中每个元素的查找概率为1/s.1/s.Lb:Lb:为查找所在块的平均查找长度。为查找所在块的平均查找长度。Lw:Lw:为块中查找元素的平均查找长度。为块中查找元素的平均查找长度。2)2)块中的记录是任意排列的,在块中只能用顺序查找。块中的记录是任意排列的,在块中只能用顺序查找。ASL ASLbsbs=1/bj+1/si=(b+1)/2+(s+1)/2=1/bj+1/si=(b+1)/2+(s+
16、1)/2 =1/2(n/s+s+2)=1/2(n/s+s)+1 =1/2(n/s+s+2)=1/2(n/s+s)+1 j=1j=1b bi=1i=1s s可以证明可以证明:当当s=s=时,平均查找长度最小时,平均查找长度最小=+1=+1由上式可以看出,分块查找的平均查找长度不仅和表由上式可以看出,分块查找的平均查找长度不仅和表的长度的长度n n有关,而且和每一块中的元素个数有关,而且和每一块中的元素个数s s有关。有关。n nn n用折半查找确定所在的块,则分块查找的平均查找长用折半查找确定所在的块,则分块查找的平均查找长度为度为ASLASLbs bs=log=log2 2(b+1)-1+(s
17、+1)/2(b+1)-1+(s+1)/2 =log =log2 2(n/s+1)+(s-1)/2(n/s+1)+(s-1)/2三种查找方法的比较三种查找方法的比较:就就平均查找长度平均查找长度而言,折半查找最小,分块查找次而言,折半查找最小,分块查找次之,顺序查找最大。之,顺序查找最大。就就表的结构表的结构而言,顺序查找对有序表和无序表均可而言,顺序查找对有序表和无序表均可应用,折半查找仅适用有序表,而分块查找要求表中数应用,折半查找仅适用有序表,而分块查找要求表中数据是分块有序的,即需要把表分成若干块,块与块之间据是分块有序的,即需要把表分成若干块,块与块之间的记录按关键字有序。的记录按关键
18、字有序。就就表的存储结构表的存储结构而言,顺序查找和分块查找对两种而言,顺序查找和分块查找对两种存储结构存储结构-向量和链表均适用,而折半查找只适用于以向量和链表均适用,而折半查找只适用于以向量做存储结构的的表,这就要求表中的元素基本不变,向量做存储结构的的表,这就要求表中的元素基本不变,否则,当进行插入和删除运算时为保持表的有序性,便否则,当进行插入和删除运算时为保持表的有序性,便要移动元素,这在一定程度上降低折半查找的效率。要移动元素,这在一定程度上降低折半查找的效率。8.3 8.3 动态查找表动态查找表二叉排序树:二叉排序树:或者是一棵空树,或者是具有下列性质的或者是一棵空树,或者是具有
19、下列性质的二叉树:二叉树:1)1)若它的左子树不空,则它的左子树上所有结点的若它的左子树不空,则它的左子树上所有结点的值均小于根结点的值;值均小于根结点的值;2)2)若它的右子树不为空,则它的右子树上所有结点若它的右子树不为空,则它的右子树上所有结点的值均大于或等于它的根结点的值;的值均大于或等于它的根结点的值;3)3)它的左、右子树均为二叉排序树。它的左、右子树均为二叉排序树。二叉排序树的构造方法:二叉排序树的构造方法:设设R=R1,R2,R=R1,R2,Rn,Rn为一数列为一数列,按下面的原则建立二叉树:按下面的原则建立二叉树:1)1)令令R1R1为二叉树的根;为二叉树的根;2)2)若若R
20、2R1R2R1,则令,则令R2R2为为R1R1的左子树的根结点,否则令的左子树的根结点,否则令 R2R2为为R1R1的右子树的根结点;的右子树的根结点;3)3)对对R3,R4,R3,R4,RnRn重复上述步骤重复上述步骤2)2);例:给定例:给定R=10,18,3,8,12,2,7,3R=10,18,3,8,12,2,7,3按上面的原则构造二按上面的原则构造二 叉排序树如下:叉排序树如下:R4R7R2R2R2R2比比R1R1大大1018R3R3R1R3R110183R4R1 R4R3 R4R3 右边右边101838R5R5R1 R5R1 右边右边R5R2 R5R2 左边左边10183812R6
21、R6R1 R6R1 左边左边R6R3 R6R3 左边左边101838122R1R1为根节点为根节点R1101018381227R7R1 R7R3 R7R3 右边右边R&R4 R&R4 左边左边10183812273R8R8R1 R8R3 R8R3 右边右边R8R4 R8R4 左边左边R8R7 R8datadata)bsinsert(s,t-lchild);else bsinsert(s,t-rchild);/bsinsertvoid sortree(m,rm,p)/建立一个有建立一个有m个结点个结点ri(0=idata=r0;q-lchild=NULL;q-rchild=NULL;p=q;fo
22、r(i=1;idata=ri;q-lchild=NULL;q-rchild=NULL;bsinsert(q,p);/sorttree二叉排序树的查找二叉排序树的查找 已知要找的那个记录的关键字已知要找的那个记录的关键字k,k,从根结点的关键字从根结点的关键字开始比较,有下列三种情况:开始比较,有下列三种情况:1)1)若两者相等若两者相等,则说明查找成功则说明查找成功,根结点的记录为所根结点的记录为所找记录找记录;2)2)若若k k小于根结点的关键字,则继续查找左子树小于根结点的关键字,则继续查找左子树;3)3)若若k k大于根结点的关键字,则继续查找右子树大于根结点的关键字,则继续查找右子树;
23、4)4)若二叉树为空,则查找失败。若二叉树为空,则查找失败。void sortsrch(bitreptr t,ElemType k)/在指针在指针t所指的二叉排序树中,查找关键字为所指的二叉排序树中,查找关键字为k的结点的结点 if t=NULL printf(“unsucc”);/树已空查找不成功树已空查找不成功 else if(k=t-key)printf(“succ”);outdata();/查找成功,并输出信息查找成功,并输出信息 else if(kkey)sortsrch(t-lchild,k);else sortsrch(t-rchild,k);非递归算法如下:非递归算法如下:vo
24、id search(bitreptr I,bitreptr t,ElemType k)/在二叉排序树在二叉排序树t中查找中查找k。每个结点有三个字段:。每个结点有三个字段:lchild,key,rchild。若。若k不不/在在t中,则送回中,则送回B=1。否则送回。否则送回i,结果,结果i-key=k。/设设lchild(空二叉树)(空二叉树)=rchild(空二叉树)(空二叉树)=0 i=t;B=1;/当当B=0时,查找成功,否则失败时,查找成功,否则失败 while(i!=NULL)&(B=1)if(kkey)i=i-lchild;/查找左子树查找左子树 else if(k=i-key)B
25、=0;printf(“succ%d”,i);else i=i-rchild;/查找右子树查找右子树 /search二叉排序树在查找过程中的插入、删除二叉排序树在查找过程中的插入、删除1)二叉排序树的插入:二叉排序树的插入:给定关键字给定关键字x,x,如果如果x x在二叉排序树中,送在二叉排序树中,送 出指向出指向x x所在结点的指针,否则将所在结点的指针,否则将x x插入到二叉排序树的合适位插入到二叉排序树的合适位 置上。置上。void BST(bitreptr&t,ElemType x)/在二叉排序树中查找一个结点的关键字在二叉排序树中查找一个结点的关键字x,若,若x已不在表中,则将它放在适
展开阅读全文