【精品数据结构】查找1

《【精品数据结构】查找1》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章查找9.1.基本概念9.2顺序表9.2.1顺序查找9.2.2二分法查找9.2.3分块查找9.3散列表9.3.1概述9.3.2散列函数的构造方法9.3.3处理冲突的方法9.3.4散列表的性能分析9.4.树表9.4.1二叉排序树9.4.2平衡的二叉排序树9.4.3B－树小结◆查找表：由同一类型的数据元素（记录）组成的集合，可以由任意的数据结构实现。9.1基本概念◆查找表的操作：（1）查询某个“特定的”数据元素是否在查找表中；（2）查找某个“特定的”数据元素的属性；（3）在查找表中插入一个数据元素；（4）从查

2、找表中删除某个数据元素。◆静态查找表:若对查找表只作前两种操作，此类查找表称静态查找表。◆动态查找表:若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已经存在的某个数据元素，此类查找表为动态查找表。◆关键字：数据元素中某个数据项的值，用它可以标示查找表中的一个数据元素。主关键字可以唯一地标识一个记录，次关键字用以识别若干记录。◆查找：就是根据给定的关键字值，在特定的查找表中确定一个其关键字与给定值相同的数据元素，并返回该数据元素在查找表中的位置。如果找到数据元素，则称查找成功，否则查找失败。

3、◆平均查找长度：为了确定数据元素在查找表中的位置需要和给定值进行比较的关键字个数期望值，称为查找算法在查找成功时的平均查找长度。•对于长度为n的查找表，查找成功的平均查找长度为：•其中Pi为查找表中第i个数据元素的概率，Ci为找到查找表中第i个元素时，已经进行的比较次数。由于查找算法的基本元素是关键字之间的比较操作，所以可以平均查找长度来衡量查找算法的性能。9.2顺序表顺序表中相邻的两个记录Ri和Ri+1在存储器中的物理位置也是相邻的，因此存储结构采用的是顺序结构。顺序结构有关C++语言描述的数据类型定义：（

4、为了简单起见，我们假设记录的排序码为整型，在本章以后讨论的顺序表中均采用这样的向量存储结构）•顺序表的查找方法分为顺序查找法、二分法（折半）查找法以及分块（索引）查找法。#definemaxn30//文件中最大记录数typedefstruct{intkey;//假设记录排序码为整数char*other;//记录中其它信息域，暂不用}record;typedefrecordrecordfile[maxn];9.2.1顺序查找顺序查找（sequentialsearch)用待查的关键字值与线性表里各结点的关键字值逐

5、个比较，•查找第n个元素：比较次数1查找第n-1个元素：比较次数2……….查找第1个元素：比较次数n查找第i个元素：比较次数n+1-i查找失败：比较次数n+1443211237669875676012345678监视哨查找76↑i↑i↑i↑i↑i查找次数＝5intseqserch(recordfiler,intk,intn)//k为给定值,n为表长;//返回0表明查找不成功,否则返回关键字等于k的记录在表r中的序号.{inti=n;r[0].key=k;while(r[i].key!=k)i--;return

6、i;}顺序查找的算法:查找前对结点之间并没有排序要求.用C++语言描述的顺序查找算法如下：在此算法中，查找之前，先对r[0]的关键字赋值为k，目的在于免去查找过程中每一步都要检测整个表是否查找完毕。在此r[0]起了监视哨的作用这种改进能使顺序查找在n≥1000时进行一次查找所需要的平均时间几乎减少一半，从而提高查找效率。•顺序查找方法的ASL：••有n个记录的表，查找成功时的平均查找长度为••假设每个记录的平均查找概率相等即：Pi=1/n。。在顺序查找时，ci取决于所查记录在表中的位置。如查找记录r[n]时，

7、仅需比较一次，而查找记录r[1]时，则需比较n次。一般地，ci=n-i+1。故顺序查找的平均查找长度为：ASL=np1+(n-1)p2+…+2pn-1+pn。顺序查找法和后面将要讨论的其它查找法相比，其缺点是平均查找长度较大，特别是当n很大时，查找效率低。然而，它有很大的优点：算法简单且适用面广。它对表的结构无任何要求，无论记录是否按关键字有序均可应用，而且上述所有讨论对线性链表也同样适用。算法的评价9.2.2二分法查找查找过程：每次将待查记录所在区间缩小一半，适用条件：采用顺序存储结构的有序表•算法实现:设

8、表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值初始时，令low=1,up=n,mid=(low+up)/2让k与mid指向的记录比较若k==r[mid].key，查找成功若kr[mid].key，则low=mid+1重复上述操作，直至low>up时，查找失败9589807563563421191551234