数据结构 第9 章 查找

《数据结构 第9 章 查找》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、查找教学内容静态查找表及查找算法动态查找表及查找算法哈希表及查找算法基本概念查找表：由一些具有相同可辨认特性的数据元素（或记录）构成的集合。对查找表经常进行的操作：1、查询某个“特定的”数据元素是否在查找表中；2、查询某个“特定的”数据元素的各种属性；3、在查找表中插入一个数据元素；4、删除查找表中的某个数据元素。静态查找表：仅作“查询”（检索）操作的查找表。动态查找表：作“插入”和“删除”操作的查找表。关键字（key）：数据元素中某个数据项的值，用它可以标示（识别）一个数据元素。主关键字：可以惟一地标示一个数据元素的关键字。不同记录的主关键字不同。次关键字：可以标示若

2、干个数据元素的关键字。查找（检索）：根据给定的某个值，在查找表中确定一个关键字等于给定值的记录或数据元素。例：学号、身份证号例：性别查找成功：即找到满足条件的记录。此时作为结果可报告该记录在查找表中的位置，也可给出该记录的全部信息。查找不成功：即未找到满足条件的记录。作为结果可给出一个“空”记录或“空”指针。可以想像的到，如果能有目标地进行查找肯定比在一大堆事物中瞎摸要有效得多，因此为提高查找效率，一个办法就是在构造查找表时，在集合中的数据元素之间人为地加上某种确定的约束关系。本章正是讨论查找表的各种组织方法及其查找过程的实施。由于对查找表——“集合”中的数据元素之间的

3、关系未作限定，故在集合中查询或检索一个“特定的”数据元素时，无规律可循，只能对集合中的元素一一加以辨认直至找到为止。而这样的“查询”或“检索”是任何计算机应用系统中使用频度都很高的操作，因此设法提高查找表的查找效率，是本章讨论问题的出发点。9.1静态查找表静态查找表有多种不同的表示方法顺序表线性链表#defineLIST_INIT_SIZE100//线性表存储空间的初始分配量typedefstruct{ElemTypeelem[LIST_INIT_SIZE];intlength;//当前长度}SqList;typedefstruct{ElemType*elem;intl

4、ength;//表长度}SSTable;静态查找表的顺序存储结构……当静态查找表用不同的方法表示时，实现查找操作的方法也不同。9.1.1顺序表的查找（顺序查找）顺序表线性链表表示静态查找表顺序查找顺序查找：从表的一端开始，逐个进行记录的关键字和给定值的比较。查找过程：01234567891011找6453719211356649288807564算法描述：intSearch_Seq(SSTableST,KeyTypekey){for(i=ST.length;ST.elem[i].key!=key;--i)if(i<=0)break;if(i>0)returni;else

5、return0;}找60优点：算法简单，适应面广。缺点：平均查找长度大，不适用于表长大的查找表。顺序查找ST.elem[0].key=key;;01234567891011537192113566492888075当ST.length>=1000时，此改进能使进行一次查找所需的平均时间几乎减少一半。60监视哨查找方法评价：时间复杂度；空间复杂度；算法本身复杂程度。因为查找算法的基本操作为：将记录的关键字同给定值进行比较，所以，通常以关键字同给定值进行过比较的记录的个数的平均值作为衡量查找算法好坏的依据。平均查找长度ASL(AverageSearchLength)：为确定

6、记录在表中的位置，需要与给定值进行比较的关键字的个数的期望值叫做查找算法的平均查找长度。找到第i个记录需比较的次数。对含有n个记录的表，查找成功时：第i个记录被查找的概率。012345678910115371921135664928880751110987654321顺序查找的平均查找长度：ASL=nP1+(n-1)P2+…+2Pn-1+Pn假设每个记录的查找概率相等：Pi=1/n则：查找不成功时，关键字的比较次数总是n+1次。01234567891011537192113566492888075121110987654321假设：1、查找成功与不成功的概率相同。2、每

7、个记录被查找的概率相同。则：平均查找长度（成功与不成功的平均查找长度之和）为1、记录的查找概率不相等时如何提高查找效率？查找表存储记录原则：1)、查找概率越高比较次数越少；2)、查找概率越低，比较次数较多。讨论：2、记录的查找概率无法测定时如何提高查找效率？方法：1)、在每个记录中设一个访问频度域；2)、始终保持记录按非递增有序的次序排列；3)、每次查找后均将刚查到的记录直接移至表头。▲9.1.2有序表的查找（折半查找）有序表表示静态查找表折半查找：每次将待查记录所在区间缩小一半。查找过程：123456789101151319213756