【数据结构电子课件】查找1

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

1、第九章查找查找的概念静态查找表动态查找表哈希表查找表是由同一类型的数据元素(或记录)构成的集合,由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的数据结构。对查找表的操作:查询某个“特定的”数据元素是否在查找表中；检索某个“特定的”数据元素的各种属性；在查找表中插入一个数据元素；从查找表中删去某个数据元素查找的概念静态查找表仅作查询和检索操作的查找表。动态查找表在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素,此类表为动态查找表。查找表的分类：关键字是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）

2、。若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。若此关键字能识别若干记录，则称之谓“次关键字”。根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。若查找表中存在这样一个记录，则称“查找成功”，查找结果：给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：给出“空记录”或“空指针”。查找如何进行查找？查找的方法取决于查找表的结构。由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。查找方法评价查找速度

3、占用存储空间多少算法本身复杂程度平均查找长度ASL(AverageSearchLength)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的~抽象数据类型静态查找表的定义:ADTStaticSearchTable{D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。数据关系R：数据元素同属一个集合。静态查找表数据对象D:Create(&ST,n);//构造一个含n个数据元素的静态查找表ST。Destroy(&ST);//销毁表ST。Search(ST,key);//查找ST中其关键字等于kval的数据元素。Trave

4、rse(ST,Visit());//按某种次序对ST的每个元素调用函数Visit()一次且仅一次，}ADTStaticSearchTable基本操作P：顺序表的查找typedefstruct{ElemType*elem;//数据元素存储空间基址，建表时按实际长度分配，0号单元留空intlength;//表的长度}SSTable;以顺序表表示静态查找表，则Search函数可用顺序查找来实现。其顺序存储结构如下：i01234567891011513192137566475808892找6464监视哨iiii比较次数=5比较次数：查找第n个元素：1查找第n-1个元素：2……….查找第1个

5、元素：n查找第i个元素：n+1-i查找失败：n+1查找过程：从表的一端开始逐个进行记录的关键字和给定值的比较。例如：intSearch_Seq(SSTableST,KeyTypekval){//在顺序表ST中顺序查找其关键字等于//key的数据元素。若找到，则函数值为//该元素在表中的位置，否则为0。ST.elem[0].key=kval;//设置“哨兵”for(i=ST.length;ST.elem[i].key!=kval;--i);//从后往前找returni;//找不到时，i为0}//Search_Seq算法描述：顺序查找性能分析查找算法的平均查找长度(AverageSea

6、rchLength)：为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值。其中:n为表长Pi为查找表中第i个记录的概率Ci为找到该记录时，曾和给定值比较过的关键字的个数顺序表查找的平均查找长度为：对顺序表而言，Ci=n-i+1ASL=nP1+(n-1)P2++2Pn-1+Pn在等概率查找的情况下，在不等概率查找的情况下，ASLss在Pn≥Pn-1≥···≥P2≥P1时取极小值。表中记录按查找概率由小到达重新排列,以提高查找效率。若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。顺序表的查找算法简单，但平均查找

7、长度较大，不适用于表长较大的查找表。若以有序表表示静态查找表，则查找过程可以基于“折半”进行。有序表的查找折半查找查找过程：每次将待查记录所在区间缩小一半。适用条件：采用顺序存储结构的有序表。1.设表长为n，low、high和mid分别指向待查元素所在区间的上界、下界和中点,k为给定值。2.初始时，令low=1,high=n,mid=(low+high)/2让k与mid指向的记录比较若k==r[mid].key，查找成功若k