数据结构及算法查找.ppt
《数据结构及算法查找.ppt》由会员分享,可在线阅读,更多相关《数据结构及算法查找.ppt(96页珍藏版)》请在三一办公上搜索。
1、第 7 章 查找技术,本章的主要内容是:,查找的基本概念线性表的查找技术树表的查找技术散列表的查找技术,1.查找的基本概念,查找:在具有相同类型的记录构成的集合中找出满足给定条件的记录。,7.1 概述,查找表:具有相同类型的记录构成的集合,1.查找的基本概念,关键码:可以标识一个记录的某个数据项。键值:关键码的值。主关键码:可以唯一地标识一个记录的关键码。次关键码:不能唯一地标识一个记录的关键码。,7.1 概述,1.查找的基本概念,7.1 概述,数据结构里的查找主要通过给定值和查找表中记录的关键码进行比较查找的结果:若在查找集合中找到了与给定值相匹配的记录,则称查找成功;否则,称查找失败。,给
2、定值 k=0004,静态查找:不涉及插入和删除操作的查找。动态查找:涉及插入和删除操作的查找。,7.1 概述,1.查找的基本概念,静态查找适用于:查找集合一经生成,便只对其进行查找,而不进行插入和删除操作,或经过一段时间的查找之后,集中地进行插入和删除等修改操作;动态查找适用于:查找与插入和删除操作在同一个阶段进行,例如当查找成功时,要删除查找到的记录,当查找不成功时,要插入被查找的记录。,7.1 概述,1.查找的基本概念,查找结构:面向查找操作的数据结构,即查找基于的数据结构。,集合中元素之间不存在明显的组织规律,不便查找。,查找技术的分类,7.2 线性表的查找技术,查找技术,线性表的查找技
3、术(静态),树表的查找技术(动态),散列表的查找技术,1.静态查找技术,静态查找特点:不涉及插入和删除操作的查找.主要采用线性查找结构.顺序查找折半查找,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,T r10,7.2 线性表的查找技术,1.1顺序查找,基本思想:从线性表的一端向另一端逐个将关键码与给定值进行比较,若相等,则查找成功,返回该记录在表中的位置;若整个表检测完仍未找到与给定值相等的关键码,则查找失败,给出失败信息。,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,7.2 线性表的查找技术,例:
4、查找k35 或 k=22,r10,顺序查找(线性查找),7.2 线性表的查找技术,int SeqSearch1(int r,int n,int k)/数组r1 rn存放查找集合 i=n;while(i0,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,基本思想:设置“哨兵”。哨兵就是待查值,将它放在查找方向的尽头处,免去了在查找过程中每一次比较后都要判断查找位置是否越界,从而提高查找速度。,7.2 线性表的查找技术,改进的顺序查找,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,例:查找k35,哨兵,35,
5、基本思想:设置“哨兵”。哨兵就是待查值,将它放在查找方向的尽头处,免去了在查找过程中每一次比较后都要判断查找位置是否越界,从而提高查找速度。,7.2 线性表的查找技术,改进的顺序查找,10 15 24 6 12 35 40 98 55,0 1 2 3 4 5 6 7 8 9,例:查找k25,25,int SeqSearch2(int r,int n,int k)/数组r1 rn存放查找集合 r0=k;i=n;while(ri!=k)i-;return i;,7.2 线性表的查找技术,改进的顺序查找,平均查找长度:将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为:,其中
6、:n:问题规模,查找集合中的记录个数;pi:查找第i个记录的概率;ci:查找第i个记录所需的关键码的比较次数。,7.1 概述,查找算法的性能,查找算法时间性能通过关键码的比较次数来度量。,7.2 线性表的查找技术,顺序查找的性能:,平均查找长度:将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。计算公式为:,查找算法时间性能通过关键码的比较次数来度量。,平均查找长度较大,特别是当待查找集合中元素较多时,查找效率较低。,7.2 线性表的查找技术,顺序查找的缺点:,算法简单而且使用面广。对表中记录的存储没有任何要求,顺序存储和链接存储均可;对表中记录的有序性也没有要求,无论记录是否按
7、关键码有序均可。,顺序查找的优点:,1.2折半查找,使用条件:线性表中的记录必须按关键码有序;必须采用顺序存储。,基本思想:在有序表中,取中间记录作为比较对象,若给定值与中间记录的关键码相等,则查找成功;若给定值小于中间记录的关键码,则在中间记录的左半区继续查找;若给定值大于中间记录的关键码,则在中间记录的右半区继续查找。重复上述过程,直到查找成功,或所查找的区域无记录,查找失败。,7.2 线性表的查找技术,折半查找的基本思想,7.2 线性表的查找技术,r1 rn,k,rmid-1 rmid rmid+1,比较,如果k rmid左半区继续查找,如果k rmid右半区继续查找,例:查找值为k=1
8、4的记录的过程:,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,3114,1814,714,14=14,7.2 线性表的查找技术,mid=(low+high)/2,mid=(low+high)/2;如果k等于rmid,则查找成功如果k小于rmid,则 high=mid-1;否则low=mid+1;,例:查找值为k=22的记录的过程:,0 1 2 3 4 5 6 7 8 9 10 11 12 13,7 14 18 21 23 29 31 35 38 42 46 49 52,3122,1822,2322,
9、2122,7.2 线性表的查找技术,lowhigh,mid=(low+high)/2,mid=(low+high)/2;如果k等于rmid,则查找成功如果k小于rmid,则 high=mid-1;否则low=mid+1;,int BinSearch1(int r,int n,int k)/数组r1 rn存放查找集合 low=1;high=n;while(lowrmid)low=mid+1;else return mid;/查找成功 return 0;/查找失败,7.2 线性表的查找技术,折半查找非递归算法,int BinSearch2(int r,int low,int high,int k)
10、/数组r1 rn存放查找集合 if(lowhigh)return 0;/递归终止 else mid=(low+high)/2;if(krmid)return BinSearch2(r,mid+1,high,k);/在右半查找 else return mid;/查找成功,7.2 线性表的查找技术,折半查找递归算法,折半查找判定树,判定树:折半查找的过程可以用二叉树来描述,树中的每个结点对应有序表中的一个记录,结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树,简称判定树。,7.2 线性表的查找技术,当n=0时,折半查找判定树为空;当n0时,折半查找判定树的根结点是有
11、序表中序号为mid=(n+1)/2的记录,根结点的左子树是与有序表r1 rmid-1相对应的折半查找判定树,根结点的右子树是与rmid+1 rn相对应的折半查找判定树。,7.2 线性表的查找技术,判定树的构造方法,7.2 线性表的查找技术,判定树的构造方法,根结点是序号为mid=(n+1)/2的记录根结点的左子树是r1 rmid-1的判定树根结点的右子树是rmid+1 rn的判定树,1-5,7-11,1-2,4-5,7 14 18 21 23 29 31 35 38 42 46,1 2 3 4 5 6 7 8 9 10 11,对n个结点的判定树,深度,查找成功:在表中查找任一记录的过程,即是从
12、判定树根结点到该记录结点的路径,比较次数等于该记录结点在树中的层数,7.2 线性表的查找技术,内部结点,外部结点,判定树的构造方法,1-5,7-11,1-2,4-5,7 14 18 21 23 29 31 35 38 42 46,1 2 3 4 5 6 7 8 9 10 11,查找失败的过程就是走了一条从根结点到外部结点的路径,和给定值进行比较次数等于该路径上内部结点的个数,查找5,查找10,具有n个结点的折半查找判定树的深度为,7.2 线性表的查找技术,折半查找性能分析,问题规模是n,折半查找的平均查找长度(假设树高度是K):,第j层,结点数2j-1,每个结点比较j次,练习,查找技术的分类,
13、7.2 线性表的查找技术,查找技术,线性表的查找技术(静态),树表的查找技术(动态),散列表的查找技术,顺序查找和折半查找的缺陷?,2.树查找技术,树查找特点:查找结构是采用树结构,有序的树结构可根据一个无序的查找表动态生成,并且查找过程中可以对树结构进行插入和删除操作.二叉排序树平衡二叉树,7.3 树表的查找技术,2.1二叉排序树,二叉排序树(也称二叉查找树):或者是一棵空的二叉树,或者是具有下列性质的二叉树:如果它的左子树不空,则左子树上所有结点的值均小于根结点的值;如果它的右子树不空,则右子树上所有结点的值均大于根结点的值;它的左、右子树也都是二叉排序树。,7.3 树表的查找技术,二叉排
14、序树 非二叉排序树,二叉排序树,7.3 树表的查找技术,中序遍历二叉排序树可以得到一个按关键码有序的序列,二叉排序树,主要操作:1)查找2)构造3)插入4)删除,7.3 树表的查找技术,注意:插入和删除后,仍然是一棵二叉排序树,无序序列:63,55,90,42,58,70,二叉排序树的存储结构,以二叉链表形式存储:,7.3 树表的查找技术,二叉排序树的存储结构,以二叉链表形式存储,类声明如下:,class BiSortTree public:BiSortTree(int a,int n);BiSortTree();void InsertBST(BiNode*root,BiNode*s);voi
15、d DeleteBST(BiNode*p,BiNode*f);BiNode*SearchBST(BiNode*root,int k);private:BiNode*root;,7.3 树表的查找技术,例:在二叉排序树中查找关键字值k为35,95的过程:,7.3 树表的查找技术,50,30,20,80,90,85,88,40,35,32,2.1.1二叉排序树的查找,50,30,20,80,90,85,88,40,35,32,root,root,BiNode*SearchBST(BiNode*root,int k),二叉排序树的查找,在二叉排序树中查找给定值k的过程是:,若root是空树,则查找失
16、败;若kroot-data,则查找成功;否则 若kroot-data,则在root的左子树上查找;否则 在root的右子树上查找。上述过程一直持续到k被找到或者待查找的子树为空,如果待查找的子树为空,则查找失败。,7.3 树表的查找技术,root,BiNode*SearchBST(BiNode*root,int k),BiNode*BiSortTree:SearchBST(BiNode*root,int k)if(root=NULL)return NULL;else if(root-data=k)return root;else if(kdata)return SearchBST(root-l
17、child,k);else return SearchBST(root-rchild,k);,7.3 树表的查找技术,二叉排序树的查找,1)若root是空树,则查找失败;2)若kroot-data,则查找成功;3)若kroot-data 则在root的左子树上查找;否则在root的右子树上查找。,2.1.2二叉排序树的插入,分析:新插入的结点必为一个新的叶子结点,其插入位置由查找过程得到。,7.3 树表的查找技术,void InsertBST(BiNode*,例:插入值为98的结点,63,55,90,58,70,root,root,若二叉排序树为空树,则新插入的结点为新的根结点;否则,如果新插
18、入结点值小于根结点值,则把结点插入到根结点的左子树,否则插入到根结点的右子树。,void BiSortTree:InsertBST(BiNode*,7.3 树表的查找技术,二叉排序树的插入算法,若二叉排序树为空树,则新插入的结点为新的根结点;否则,如果新插入结点值小于根结点值,则把结点插入到根结点的左子树,否则插入到根结点的右子树。,2.1.3二叉排序树的构造,从空的二叉排序树开始,依次给每个数据分配一个结点,插入该结点。,例:关键码集合为63,90,70,55,58,二叉排序树的构造过程为:,7.3 树表的查找技术,63,BiSortTree:BiSortTree(int r,int n)r
19、oot=NULL;for(i=0;i;s-data=ri;s-lchild=s-rchild=NULL;InsertBST(root,s);,7.3 树表的查找技术,二叉排序树的构造算法,一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列;每次插入的新结点都是二叉排序树上新的叶子结点;找到插入位置后,不必移动其它结点,仅需修改某个结点的指针;新插入的结点没有破坏原有结点之间的关系。,小 结:,7.3 树表的查找技术,2.1.4二叉排序树的删除,在二叉排序树上删除某个结点之后,仍然保持二叉排序树的特性。,分三种情况讨论:被删除的结点是叶子;被删除的结点只有左子树或者只有右子树;被删除的结点
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 算法 查找
链接地址:https://www.31ppt.com/p-3787996.html