数据结构课件查找.ppt

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

1、第九章查找由于查找运算的使用效率很高，几乎在任意一个计算机系统软件和应用软件中都会涉及到，所以当问题所涉及的数据量相当大时，查找方法的效率就显得格外重要。在一些实事查询系统中尤其如此。因此，本章将系统地讨论各种查找方法，并通过对它们的效率分析来比较各种查找方法的优劣。10/7/20211第九章查找9.1静态查找表9.2动态查找表9.3哈希表10/7/20212查找的基本概念查找又称为查询或检索，是在一批记录中依照某个域的指定域值，找出相应的记录的操作。在计算机中，被查找的数据对象是由同一类型的记录构成的集合，

2、可称之为查找表（searchtable）。在实际应用问题中，每个记录一般包含有多个数据域，查找是根据其中某一个指定的域进行的，这个作为查找依据的域称为关键字（key）。10/7/20213对于给定的关键字的值，如果在表中经过查找能找到相应的记录，则称查找成功，一般可输出该记录的有关信息或指示该记录在查找表中的位置。若表中不存在相应的记录，则称查找不成功，此时应该给出不成功的信息。查找算法中的基本运算是记录的关键字与给定值所进行的比较，其执行时间通常取决于比较的次数。因此，通常以关键字与给定值进行比较的记录个数

3、的平均值，作为衡量查找算法好坏的依据。10/7/20214查找表操作及分类操作：(1)查询某个“特定的”数据元素是否在查找表中；(2)某个“特定的”数据元素的各种属性；(3)在查找表中插入一个数据元素；(4)从查找表中删去某个数据元素。分类：若对查找表只作(1)和(2)两种操作，则称此类查找表为静态查找表。若在查找过程中同时插入查找表中不存在的数据元素，或者从查找表中删除已存在的某个数据元素，则称此类查找表为动态查找表。10/7/202159.1静态查找表抽象数据类型静态查找表的定义：ADTStaticSea

4、rchTable{数据对象D:D是具有相同属性的数据元素的集合。数据关系R:数据元素同属一个集合。基本操作P:Create(&ST,n);Destroy(&ST);Search(ST,key);Traverse(ST,Visit());}ADTStaticSearchTable10/7/20216一、顺序查找顺序查找的基本思想是：从线性表的一端开始，依次将扫描到得结点关键字和给定值K相比较。若当前扫描到得结点关键字与K相等，则查找成功；若扫描结束后，仍未找到关键字等于K的结点，则查找失败。顺序查找的存储结构要

5、求：顺序查找方法既适用于线性表的顺序存储结构，也适用于线性表的链式存储结构（使用单链表作为存储结构时，扫描必须从第一个结点开始），顺序查找对数据在表中存放的先后次序没有任何要求。在表的组织方式中，线性表是最简单的一种。顺序查找是一种最简单的查找方式。10/7/20217顺序查找的线性表定义如下：typedefstruct{ElemType*elem;intlength;};每个结点包含两部分内容：Key和info其他信息10/7/20218（2）算法的实现：技巧：把待查关键字key存入表头或表尾（俗称“哨兵”

6、），这样可以加快执行速度。例：若将待查找的特定值key存入顺序表的首部（如0号单元），则顺序查找的实现方案为：从后向前逐个比较！intSearch_Seq(SSTableST,KeyTypekey){//在顺序表ST中，查找关键字与key相同的元素；若成功，返回其位置信息，否则返回0ST.elem[0].key=key;//设立哨兵，可免去查找过程中每一步都要检测是否查找完毕，0单元被当作监视哨，用来判断表是否查找完毕（技巧）。当n>1000时，查找时间将减少一半。for(i=ST.length;ST.ele

7、m[i].key!=key;--i);//不要用for(i=n;i>0;--i)或for(i=1;i<=n;i++)returni;//若到达0号单元才结束循环，说明不成功，返回0值(i=0)。成功时则返回找到的那个元素的位置i。}//Search_Seq监视哨的作用:无需判断是否越界.选择0当作监视哨，因为在数组里面0单元处理比较麻烦，不小心就出错10/7/2021901234567（a）初态40803060102025(b)K=80(returni=4)804080306010202501234567(c

8、)K=90(returni=0)012345679040803060102025顺序查找的算法：intSearch_seq(SSTableST[],intn,intkey){inti=n;ST[0].key=key;for(i=ST.length;ST.elem[i].key!=key;--i);/*从表尾往前查*/returni;}监视哨for(i=n;i>0;--i){if(ST.elem[i]