7.2 静态表的查找

《7.2 静态表的查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第7章查找7.1基本概念查找表是由同一类型的数据元素(或记录)构成的集合。对查找表经常进行的操作:1）查询某个“特定的”数据元素是否在查找表中；2）检索某个“特定的”数据元素的各种属性；3）在查找表中插入一个数据元素；4）从查找表中删去某个数据元素。静态查找表仅作上述1）和2）操作的查找表动态查找表有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入查找表；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素.查找---根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）.找到：

2、查找成功找不到：查找失败主关键字---能唯一确定结点的一个或多个域。平均查找长度（ASL）---查找一个结点所作的平均比较次数（ASL是衡量一个查找算法优劣的主要标准）。如何进行查找？取决于查找表的结构，即：记录在查找表中所处的位置。然而，查找表本身是一种很松散的结构，因此，为了提高查找的效率，用另外一种结构来表示查找表。本章讨论的重点：查找表的各种表示方法及其相应的查找算法7.2静态查找7.2.1顺序查找一、算法思想：从表的一端开始，用给定值k与表中各个结点的关键字逐个比较。查找成功---找出相等的值；查找失败---已到达

3、表的另一端，即表中所有结点的关键字值都不等于k。提示：可在此设置一个监视哨，作为下标越界的条件。二、示例r[0]：为监视哨。视哨的作用：作为越界（即已查完）的检测条省去在循环中每次均要判定是否越界，从而节省比较的时间。三、存储结构keyinfotypedefstruct{keytpyekey;………….}sstable;k1k2k3…………kn0123n四、顺序查找算法：intsearch(sstabler[],intn,keytypek){//在n个结点的顺序表r[1]..r[n]中查找关键字kinti=n;//从表尾开始

4、向前查找r[0].key=k;//设置监视哨while(r[i].key!=k)i--;return(i);}五、算法分析（1）查找成功的平均查找长度（在等概率的前提下）ASL=（1+2+……+n)/n=（n+1）/2。（2）查找失败的平均查找长度n+1。六、顺序查找的特点：（1）算法简单，对线性表的逻辑次序无要求;（2）存储结构可采用顺序或链式存储结构均可，但其平均查找长度较大,均为：（n+1)/2。思考题：（1）表有序时，查找成功和失败的平均查找长度与表无序时是否相同？算法怎么改进？（2）次关键的查找（表中有多个关键字值

5、相同时的查找如何进行）？（3）多关键字的查找？（4）用单链表为存储结构，实现时有何考虑？（5）顺序查找的适用范围？7.2.2二分(折半）查找一、二分查找的先决条件表中结点必须按关键字有序且采用顺序存储。二、二分法思想：取中，比较（1）用给定的k与有序表的中间位置mid上的结点的关键字比较，若相等，查完；否则：（2）若r[mid].key>k,则在左子表中继续进行二分查找；若(r[mid].key

6、34567891011i=1,j=11,ijm1221303538404855566064二分法查找示例（1）k=351234567891011i=1,j=11,m=(i+j)/2=6。r[m]>k:在左半部分继续查找。ij1221303538404855566064二分法查找示例（1）k=351234567891011i=1,j=11,m=(i+j)/2=6。r[m]>k:在左半部分继续查找。i=1,j=m-1=5,ij1221303538404855566064二分法查找示例（1）k=351234567891011i=1

7、,j=11,m=(i+j)/2=6。r[m]>k:在左半部分继续查找。i=1,j=m-1=5,m=(i+j)/2=3。r[m]k:在左半部分继续查找。i=1,j=m-1=5,m=(i+j)/2=3。r[m]

8、91011i=1,j=11,m=(i+j)/2=6。r[m]>k:在左半部分继续查找。i=1,j=m-1=5,m=(i+j)/2=3。r[m]