《查找和排序》PPT课件

《《查找和排序》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第4章查找和排序4.1线性表查找4.1.1顺序查找4.1.2折半查找4.1.3分块查找4.2二叉排序树的查找4.3哈希查找4.3.1哈希表的建立4.3.2处理冲突的方法4.3.3哈希查找4.4排序4.4.1直接插入排序4.4.2简单选择排序4.4.3冒泡排序4.4.4快速排序4.4.5归并排序习题4.1线性表查找查找(Searching)，也称检索，亦即查表，就是在大量的信息集中寻找一个“特定的”信息元素。人们几乎每天都要做“查找”工作，如查寻电话号码、查字典、查图书目录卡片等。为确切定义查找，先引入几个概念。查找表：由同一类型的数据元素(或记录)构成

2、的集合。关键字(key)：数据元素中可以惟一标识一个数据元素的数据项。如学生的学号，居民身份证号等。查找就是根据给定的关键字值，在查找表中确定一个关键字等于给定值的记录或数据元素。若存在这样的数据元素，则称查找是成功的，否则称查找不成功。决定查找操作的是关键字，因此这里讨论时，只关注记录中的关键字域，而一概忽略记录中其它诸域的信息。查找是许多重要的计算机程序中最耗费时间的部分，查找算法的优劣密切关系着查找操作的速度，因此对查找算法应认真研究。关于查找，目前主要研究两方面的问题：(1)查找的方法。因为查找某个数据元素依赖于该数据元素在一组数据中所处的位置

3、，即该组数据的组织方式，故应按照数据元素的组织方式决定采用的查找方法；反过来，为了提高查找方法的效率，要求数据元素采用某些特殊的组织方式。(2)查找算法的评价。衡量一个算法的标准主要有两个：时间复杂度和空间复杂度。就查找算法而言，通常只需要很少的辅助空间，因此更关心的是它的时间复杂度。在查找算法中，基本运算是给定值与关键字的比较，所以算法的主要时间是花费在“比较”上。下面给出一个称为平均查找长度的概念，作为评价查找算法好坏的依据。对于含有n个数据元素的查找表，查找成功时的平均查找长度为ASL=其中，Pi为查找第i个数据元素的概率；Ci为查到第i个数据元

4、素时，需与关键字进行比较的次数。4.1.1顺序查找顺序查找是最简单、常用的查找技术。其基本思想是：从表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某个元素的关键字等于给定值K，则表明查找成功，返回该元素的下标；反之，若直到所有元素都比较完毕，仍找不到关键字为K的元素，则表明查找失败，返回特定的值(常用−1表示)。顺序查找方法既适用于以顺序存储结构组织的查找表的查找，也适用于以链式存储结构组织的查找表的查找。在本章的有关查找和排序算法中，假设线性表均采用顺序存储结构，其类型说明为：#defineMAXLENn/*n为查找表中元素个数的最大可能

5、值*/structelement{intkey;/*设关键字的类型为整型*/intotherterm;/*为说明起见，除关键字外只有一个整型数据项*/};typedefstructelementDATATYPE;DATATYPEtable[MAXLEN];算法4-1顺序查找算法。intseqsearch1(DATATYPEA[],intk){inti;i=0;while((A[i].key!=k)&&(i

6、找失败，返回–1*/}若对此算法进行一些改进，在表尾增加一个关键字为指定值K的记录，可避免每“比较”一次，就要判别查找是否结束。当n很大时，大约可节省一半的时间。算法4-2改进的顺序查找算法。#defineMAXLENn+1intseqsearch2(DATATYPEA[],intk){inti;i=0;A[MAXLEN−1].key=k;while(A[i].key!=k)i++;if(i

7、监视哨，这个增加的记录起到了边界标识的作用。下面对改进后的算法进行一下性能分析，计算它的平均查找长度。对含有n个记录的表，查找成功时的平均查找长度为ASL=从顺序查找的过程看，Ci取决于所查元素在表中的位置，对于第一个记录只要比较一次，对第n个记录，需要比较n次，查找记录A[i]时，比较i次。设每个记录的查找概率相等，则Pi=1/n。故此算法在等概率情况下查找成功的平均查找长度为ASL=4.1.2折半查找如果查找表中的记录按关键字有序，则可以采用一种高效率的查找方法——折半查找，也称二分查找。折半查找的基本思想是：对于有序表，查找时先取表中间位置的记录

8、关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进