《《数据结构（C++描述）》-李根强-电子教案 第8章》由会员分享，可在线阅读，更多相关《《数据结构（C++描述）》-李根强-电子教案 第8章（67页珍藏版）》请在金锄头文库上搜索。
1、第8章 查找,数据结构（C+描述）,目录,84 散列查找,83 树表查找,8.1 查找的基本概念,82 线性表的查找,退出,8.1 查找的基本概念,查找，也称为检索。在我们日常生活中，随处可见查找的实例。如查找某人的地址、电话号码；查某单位45岁以上职工等，都属于查找范畴。本书中，我们规定查找是按关键字进行的，所谓关键字(key)是数据元素(或记录)中某个数据项的值，用它可以标识(或识别)一个数据元素。例如，描述一个考生的信息，可以包含：考号、姓名、性别、年龄、家庭住址、电话号码、成绩等关键字。但有些关键字不能唯一标识一个数据元素，而有的关键字可以唯一标识一个数据元素。如刚才的考生信息中，姓名
2、不能唯一标识一个数据元素(因有同名同姓的人)，而考号可以唯一标识一个数据元素(每个考生考号是唯一的，不能相同)。我们将能唯一标识一个数据元素的关键字称为主关键字，而其它关键字称为辅助关键字或从关键字。,有了主关键字及关键字后，我们可以给查找下一个完整的定义。所谓查找，就是根据给定的值，在一个表中查找出其关键字等于给定值的数据元素，若表中有这样的元素，则称查找是成功的，此时查找的信息为给定整个数据元素的输出或指出该元素在表中的位置；若表中不存在这样的记录，则称查找是不成功的，或称查找失败，并可给出相应的提示。,因为查找是对已存入计算机中的数据所进行的操作，所以采用何种查找方法，首先取决于使用哪种
3、数据结构来表示“表”，即表中结点是按何种方式组织的。为了提高查找速度，我们经常使用某些特殊的数据结构来组织表。因此在研究各种查找算法时，我们首先必须弄清这些算法所要求的数据结构，特别是存储结构。 查找有内查找和外查找之分。若整个查找过程全部在内存进行，则称这样的查找为内查找；反之，若在查找过程中还需要访问外存，则称之为外查找。我们仅介绍内查找。,要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL= ，其中i为查找第i个元素的概率，且 =1。一
4、般情形下我们认为查找每个元素的概率相等，i为查找第i个元素所用到的比较次数。 要衡量一种查找算法的优劣，主要是看要找的值与关键字的比较次数，但我们将找到给定值与关键字的比较次数的平均值来作为衡量一个查找算法好坏的标准，对于一个含有n个元素的表，查找成功时的平均查找长度可表示为ASL= ，其中i为查找第i个元素的概率，且=1。一般情形下我们认为查找每个元素的概率相等，i为查找第i个元素所用到的比较次数。,82 线性表的查找,8.2.1 顺序查找 1顺序查找的基本思想,顺序查找是一种最简单的查找方法，它的基本思想是：从表的一端开始，顺序扫描线性表，依次将扫描到的结点关键字和待找的值相比较，若相等，
5、则查找成功，若整个表扫描完毕，仍末找到关键字等于的元素，则查找失败。 顺序查找既适用于顺序表，也适用于链表。若用顺序表，查找可从前往后扫描，也可从后往前扫描，但若采用单链表，则只能从前往后扫描。另外，顺序查找的表中元素可以是无序的。,下面以顺序表的形式来描述算法。,2顺序查找算法实现,const int n=maxn /n为表的最大长度 struct node elemtype key; /key为关键字，类型设定为elemtype ; int seqsearch (node Rn+1,elemtype k) /在表中查找关键字值为的元素 R0.key=k; int i=n; /从表尾开始向前
6、扫描 while(Ri.key!=k) i-; return i;,在函数seqsearch中，若返回的值为表示查找不成功，否则查找成功。函数中查找的范围从n到，为监视哨，起两个作用，其一，是为了省去判定 while循环中下标越界的条件i1，从而节省比较时间，其二，保存要找值的副本，若查找时，遇到它，表示查找不成功。若算法中不设立监视哨R0，程序花费的时间将会增加，这时的算法可写为下面形式。,int seqsearch(node Rn+1，elemtype k) int i=n; while(Ri.key!=k) ,当然上面算法也可以改成从表头向后扫描，将监视哨设在右边，这种方法请读者自己完成
7、。,3.顺序查找性能分析,假设在每个位置查找的概率相等，即有pi=1/n，由于查找是从后往前扫描，则有每个位置的查找比较次数Cn=1，Cn-1=2，C1=n，于是，查找成功的平均查找ASL= = = = ,即它 的时间复杂度为O(n)。 这就是说，查找成功的平均比较次数约为表长的一半。若k值不在表中，则必须进行n+1次比较之后才能确定查找失败。另处，从ASL可知，当n较大时，ASL值较大，查找的效率较低。,顺序查找的优点是算法简单，对表结构无任何要求，无论是用向量还是用链表来存放结点，也无论结点之间是否按关键字有序或无序，它都同样适用。顺序查找的缺点是查找效率低，当n较大时，不宜采用顺序查找，
8、而必须寻求更好的查找方法。,8.2.2二分查找 1.二分查找的基本思想,二分查找，也称折半查找，它是一种高效率的查找方法。但二分查找有条件限制：要求表必须用向量作存贮结构，且表中元素必须按关键字有序(升序或降序均可)。我们不妨假设表中元素为升序排列。二分查找的基本思想是：首先将待查值K与有序表R1到Rn的中点mid上的关键字Rmid.key进行比较，若相等，则查找成功；否则，若Rmid.keyk ， 则在R1到Rmid-1中继续查找，若有Rmid.keyk ， 则在Rmid+1到Rn中继续查找。每通过一次关键字的比较，区间的长度就缩小一半，区间的个数就增加一倍，如此不断进行下去，直到找到关键字
9、为K的元素；若当前的查找区间为空(表示查找失败)。,从上述查找思想可知，每进行一次关键字比较，区间数目增加一倍，故称为二分（区间一分为二），而区间长度缩小一半，故也称为折半（查找的范围缩小一半）。,2二分查找算法实现,int binsearch (node Rn+1, elemtype k) int low=1, high=n; while (lowk) high=mid-1; /在左子区间中查找 else low=mid+1; /在右子区间中查找 return 0; /查找失败,例如，假设给定有序表中关键字为8,17,25,44,68,77,98,100,115,125，将查找K=17和K=
10、120的情况描述为图8-1及图8-2形式。,3.二分查找的性能分析,为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。例如，图8-1给定的关键字序列8,17,25,44,68,77,98,100,115,125，的判定树见图8-3。,从图8-3 可知，查找根结点68，需一次查找，查找17和100，各需二次查找，查找8、25、77、115各需三次查找，查找44、98、125各需四次查找。于是，可以得到结论：二叉树第K层结点的查找次数各为k次(
11、根结点为第1层)，而第k层结点数最多为2k-1个。假设该二叉树的深度为h， 则二分查找的成功的平均查找长度为（假设每个结点的查找概率相等）：,ASL= =1/n 1/n（1+22+322+h2h-1）， 因此，在最坏情形下，上面的不等号将会成立 ，并根据二叉树的性质，最大的结点数n=2h-1，h=log2(n+1) ，于是可以得到平均查找长度ASL=(n+1)/n log2(n+1)-1。该公式可以按如下方法推出：,设s= =20+2.21+3.22+(h-1).2h-2+h.2h-1 则2s=21+2.22+(h-2).2h-2+h-1).2h-1+h.2h s=2s-s =h .2h-(2
12、0+21+22+2h-2+2h-1) =h .2h-(2h-1) = log2(n+1).(n+1)-n,所以，ASL=s/n=(n+1)/n log2(n+1)-1。,当n很大时，ASL log2(n+1)-1 可以作为二分查找成功时的平均查找长度，它的时间复杂度为O(log2n)。,8.2.3 索引查找 1.索引查找的思想,索引查找，又称分级查找，它既是一种查找方法，又是一种存贮方法，称为索引存贮。它在我们的日常生活中有着广泛的应用。例如，在汉语字典中查找某个汉字时，若知道某个汉字读者，则可以先在音节表中查找到对应正文中的页码，然后再在正文中所对应的页中查出待查的汉字；若知道该汉字的字形，
13、但不知道读者，则可以先在部首表中根据字的部首查找到对应检字表中的页码，再在检字表中根据字的笔画找到该汉字所在的页码。在这里，整个字典就是索引查找的对象，字典的正文是字典的主要部分，被称之为主表，而检字表，部首表和音节表都有是为了方便查找主表而建立的索引，所以被称之为索引表。,在索引查找中，主表只有一个，其中包含的是待查找的内容，而索引表可以有多个，包含一级索引，二级索引，所需的级数可根据具体问题而定。如刚才的利用读音查找汉字为一级索引，而 利用字形查找汉字为二级索引（部首表检字表汉字）。在此，我们仅讨论一级索引。,索引查找是在线性表（主表）的索引存贮结构上进行的，而索引存贮的基本思想是：首先将
14、一个线性表（主表）按照一定的规则分成若干个逻辑上的子表，并为每个子表分别建立一个索引项，由所有这些索引项得到主表的一个索引表，然后，可采用顺序或链接的方法来存储索引表和各个子表。索引表中的每个索引项通常包含三个域：一是索引值域，用来存储标识对应子表的索引值，它相当于记录的关键字，在索引表中由此索引值来唯一标识一个索引项（子表）；二是子表的开始位置，用来存储对应子表的第一个元素的存储位置；三是子表的长度，用来存储对应子表的元素个数。,例如，设有一个学校部分教师档案表如表8-1所示，设编号为主关键字，则该表可以用一个线性表L=（a1,a2, a3,a4,a5,a6,a7,a8,a9,a10）来表示
15、，其中ai (1in)表示第i位教师的信息（包含有编号，姓名，部门，职称），而它的索引表可以按部门进行，也可以按职称进行，按部门的索引表中有4个子表，分别为： 计算机系J=（ a1,a2,a3,a4） 电工系 D=(a5,a6,a7) 管理系G=(a8,a9) 成教部C=(a10),该4个子表示成一个索引表如表8-2所示。,表8-1 教师档案表,表8-2 按部门的索引表,index start length,若按职称进行索引，则得到的索引表中也有4个子表，分别为： Jiaosou=(a1,a8) FuJiaosou=(a3,a7,a10) Jiangshi=(a2,a5,a9) Zhujiao=(a4,a6),这时的主表用顺序存贮不太方便，因相同职称的教师没有连在一起，故用链式存储得到主表较方便。具体的存贮如图8-4所示。在图8-4中，箭头上面的数字表示该元素在主表中的下标位置（指针），每个子表中最后个元素的指针为-1，表示为空指针。,于是，可以得到如表8-3所示的职称索引表。,表8-3 按职称的索引表 index start length,从刚才的两种索引表中，可以给出索引
