《《数据结构（C语言版）》电子教案－赵坚 数据结构09》由会员分享，可在线阅读，更多相关《《数据结构（C语言版）》电子教案－赵坚 数据结构09（84页珍藏版）》请在金锄头文库上搜索。
1、2019/5/25,1,第9章 查找,本章主题：表的查找 教学目的：掌握各种不同的查找表的查找算法和性能分析 教学重点：线性表的查找、树表的查找和哈希表的查找以及 各种查找的性能分析 教学难点：树表的查找,2019/5/25,2,本章学习导读,查找就是在数据集中找出一个“特定元素”。在软件设计中，通常是将待查找的数据元素集按照一定的存储结构存入计算机中，变为计算机可处理的数据结构，从而构成一种新的数据结构查找表。,9.1 基本概念,本章主要系统地讨论了各种查找方法。主要包括线性表的查找、树表的查找和哈希表的查找以及各种查找的性能分析等。通过本章学习，读者应该熟练掌握以下内容： 了解查找及查找表
2、的相关概念 掌握各种不同的查找表的查找算法和性能分析 掌握哈希表的各种构造方法、冲突处理和性能分析,2019/5/25,3,查找表是记录的集合，每个记录至少包含一个关键字。所谓查找就是根据给定的关键字值，在查找表中找出一个记录，该记录的关键字值等于给定的值。 若在查找的同时对表做修改运算（如插入和删除），则相应的表称之为动态查找表，否则称之为静态查找表。 由于查找表的范围和给定的关键字值的不同，查找有两种可能的结果：一种是找到了相应的记录，称为查找成功。通常要求返回该记录的存储位置，以便对该记录作进一步处理；一种是找不到相应的记录，称为查找失败。此时应返回一个能表示查找失败的值。 采用何种查找
3、方法，取决于使用哪种数据结构来表示“表”。即表中记录是按何种方式组织的，根据不同的数据结构采用不同的查找方法。,2019/5/25,4,查找算法中的基本运算是记录的关键字与给定值所进行的比较。其执行时间通常取决于关键字的比较次数，也称为平均查找长度。比较次数的多少就是相应算法的时间复杂度，它是衡量一个查找算法优劣的重要指标。平均查找长度ASL定义为： n 是查找表中记录的个数 Pi 是查找第i个记录的概率 Ci 是找到第i个记录所需进行的比较次数。,2019/5/25,5,9.2 顺序表的静态查找,定义被查找的顺序表类型定义如下：,#define MAXLEN typedef struct K
4、eyType key; /KeyType为关键字的数据类型 infoType data; /其他数据 SeqList;,在顺序表中的查找，根据元素之间是否具有递增（减）特性又可分为三种情况：简单顺序查找、二分查找和分块有序查找。各种情况的查找方法及其性能存在较大差异。,2019/5/25,6,9.2.1 简单顺序查找,基本思想是：从表的一端开始，逐个把每条记录的关键字值与给定值k进行比较。若某个记录关键字值与给定值k相等，则查找成功，返回找到的记录位置。反之，若已查找到表的另一端，仍未找到关键字值与给定值相等的记录，则查找不成功，返回-1。,Typedef int KeyType; int S
5、eqSearch(SeqList A,int n,KeyType k) int i; int find=0; for(i=0;in;i+) if(Ai.key=k) find=1;break; return (find?i:-1);,2019/5/25,7,算法分析,从顺序查找过程可见（不考虑越界比较），顺序查找不论给定值k为何，若第1个记录符合给定值，只要比较1次。若第n个记录符合给定值，要比较n次，即ci=i。若每个记录的查找概率相等，且每次查找都是成功的。则在等概率的情况下，顺序查找的平均查找长度为： 查找成功时的平均比较次数约为表长的一半。若k值不在表中，则须进行n+1次比较之后才能确
6、定查找失败。顺序查找算法的时间复杂性为O(n)。,2019/5/25,8,9.2.2 二分查找,二分查找的基本思想是：首先确定待查记录所在的范围（区域）。假设用变量low和high分别表示当前查找区域的首尾下标。将待查关键字k和该区域的中间元素，其下标为mid=(low+high)2的关键字进行比较。比较的结果有如下三种情况： （1）k=Amid.key：查找成功，返回mid的值。 （2）kAmid.key：说明元素只可能在右边区域（下标从mid+1到high）。因此应在此区域继续取中间位置记录的关键字进行比较。,2019/5/25,9,int BinSearch(SeqList A,int
7、n,KeyType k) int low=0,high=n-1,mid; while(lowk) high=mid-1; else low=high+1; return -1; ,2019/5/25,10,有序表中关键字为（10,15,18,20,26,28,33,36,38,43,49），查找18的示意图。,2019/5/25,11,有序表中关键字为（10,15,18,20,26,28,33,36,38,43,49），查找39的示意图。,2019/5/25,12,算法分析,二分查找算法的计算复杂性可以用二叉树来进行分析。我们把当前查找区间的中间位置上的记录作为根。左子表和右子表中的记录分别作
8、为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树或比较树。,具有11个记录的有序表可用右图所示的判定树来表示。树中每个结点表示一个记录，结点的编号为该记录在表中的位置。找到一个记录的过程就是走了一条从根结点到与该记录结点的路径。和给定值进行比较的次数正好是该结点所在的层次数。,二分查找在查找成功时和给定值进行比较的关键字的个数至多为log2n+1。同理，查找不成功的过程也是走了一条从根结点到某一个终端结点的路径，其所用的比较次数等于树的深度。,2019/5/25,13,在查找概率相同的情况下，Pi=1/n。查找成功的平均查找长度为： 二分查找算法比顺序查找算法平均查找长度为 n
9、/2的比较次数少，查找速度快。虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算，即使采用高效率的排序方法也要花费O(nlog2n)的时间。另外，二分查找只适用顺序存储结构，不适于线性链表结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的记录。 二分查找特别适用于那种一经建立就很少改动，而又经常需要查找的线性表。,2019/5/25,14,9.2.3 分块查找,基本思想是：首先把表长为n的线性表分成b块，前b-1块记录个数为s=n/b，第b块的记录个数小于等于s。在每一块中，结点的存放不一定有序，但块与块之间必须是分块有序的（假定按结点的关键字值递增有序）。
10、即指后一个块中所有记录的关键字值都应比前一个块中所有记录的关键字值大。为实现分块检索，还需建立一个索引表。索引表的每个元素对应一个块，其中包括该块内最大关键字值和块中第一个记录位置的地址指针。显然这个索引顺序表是一个递增有序表。,2019/5/25,15,分块有序表的索引存储表示,2019/5/25,16,索引表结点的数据类型定义如下：,#define MaxIndex typedef struct KeyType key; int link; IdxType; 在这种结构下，查找过程要分为两步：首先查找索引表。因为索引表是有序表，所以可采用二分查找或顺序查找，以确定给定值所在的块。因为块中的
11、记录可以是任意排列的，所以再在已确定的块中进行顺序查找。,2019/5/25,17,分块查找算法如下：,int IdxSerch(SeqList A,IdxType index,int b,KeyType k,int n) /分块查找关键字为k的记录，索引表为index0b-1 int low=0,high=b-1,mid,i; int s=n/b; /每块记录个数 while(low=high) /在索引表中进行二分查找，找到的位置放在low中 mid=(low+high)/2; if(indexmid.keyk) low=mid+1 else high=mid-1; if(lowb) /在
12、顺序表中顺序查找 for(i=indexlow.link;i=indexlow.link+s-1 ,2019/5/25,18,算法分析,由于分块查找实际上是两次查找过程，所以分块查找的平均查找长度是：查找索引表确定给定值所在块内的平均查找长度ASLb与在块的查找关键值的平均查找长度ASLk之和。即ASL=ASLb+ASLk。 若用顺序查找确定所在块，则分块查找成功时的平均查找长度为： 若用二分查找确定所在块，则分块查找成功时的平均查找长度为：,2019/5/25,19,9.3 树表的动态查找,线性表的3种查找方法中二分查找法具有最高的查找效率。但是它只适合于顺序存储，且不能用链表作存储结构。因
13、此，当表的插入或删除操作频繁时，为维护表的有序性，势必要移动表中很多记录。这种由移动记录引起的额外时间开销，就会抵消二分查找的优点。二分查找只适用于静态查找表。若要对动态查找表进行高效率的查找，可采用本节介绍的几种特殊的二叉树或树作为表的组织形式。在这里将它们统称为树表。,2019/5/25,20,9.3.1 二叉排序树,二叉排序树又称为二叉查找树。它或者是空树，或者是满足如下性质的二叉树： （1）若它的左子树非空，则左子树上所有结点的值均小于根结点的值。 （2）若它的右子树非空，则右子树上所有结点的值均大于根结点的值。 （3）它的左、右子树本身又各是一棵二叉排序树。 下图为一棵二叉排序树,2
14、019/5/25,21,二叉排序树结点的存储结构定义如下,typedef struct node KeyType key; /结点中的关键字 struct node *lchild,*rchild; /左、右孩子指针 BsTree;,1二叉排序树的插入 基本思想是：若二叉排序树为空，将待插入的结点作为根结点。否则，若待插入结点的关键字值和根结点关键字值进行比较。若小于，则作为根结点左子树插入，否则作为右子树插入。其非递归算法描述为：,2019/5/25,22,void InsertBstree(BsTree *BST,KeyType k) BsTree *f,*p=*BST; /p的初值指向根
15、记录 while(p!=NULL) /查找插入位置 if(p-key=k) return; /树中已有k，无须插入 f=p; /f保存当前查找的记录 if(p-keyk) p=p-lchild; else p=p-rchild; p=(BsTree *)malloc(sizeof(BsTree); p-key=k;p-lchild=p-rchild=NULL; /创建一个新记录 if(*BST=NULL) *BST=p; /原树为空，新插入的记录为新的根 else if(kkey) f-lchild=p; /原树非空时将*p作为*f的左孩子插入 else f-rchild=p; ,2019/5
16、/25,23,2二叉排序树的查找 基本思想是： （1）当二叉树为空树时，检索失败。 （2）如果二叉排序树根结点的关键字等于待检索的关键字，则检索成功。 （3）如果二叉排序树根结点的关键字小于待检索的关键字，则在根结点的右子树中用相同的方法继续检索。 （4）如果二叉排序树根结点的关键字大于待检索的关键字，则在根结点的左子树中用相同的方法继续检索。,2019/5/25,24,非递归算法：,BsTree *BstSeareh(BsTree *BST,KeyType k ,BsTree *parent) BsTree *p=BST,*q=NULL; /p指向根结点，q指向*p的双亲结点 while(p!=NULL) if(k=p-key) /查找
