软件技术基础新课件(查找与排序)讲述.ppt

第2篇 数据结构 南昌大学 机电工程学院 涂海宁 Cthn@163.com 第13章 查 找 和 排 序 1、线性查找 查找(Searching)，也称检索，亦即查表，就是在大量的信息集中寻找一个“特定的”信息元素。人们几乎每天都要做“查找”工作，如查寻电话号码、查字典、查图书目录卡片等。为确切定义查找，先引入几个概念。 查找表：由同一类型的数据元素(或记录)构成的集合。 关键字(key)：数据元素中可以惟一标识一个数据元素的数据项。如学生的学号，居民身份证号等。 查找就是根据给定的关键字值，在查找表中确定一个关键字等于给定值的记录或数据元素。若存在这样的数据元素，则称查找是成功的，否则称查找不成功。 决定查找操作的是关键字，因此这里讨论时，只关注记录中的关键字域，而一概忽略记录中其它诸域的信息。 查找是最耗费时间的部分，查找算法的优劣密切关系着查找操作的速度，因此对查找算法应认真研究。 关于查找，目前主要研究两方面的问题： (1) 查找的方法。 因为查找某个数据元素依赖于该数据元素在一组数据中所处的位置，即该组数据的组织方式，故应按照数据元素的组织方式决定采用的查找方法；反过来，为了提高查找方法的效率，要求数据元素采用某些特殊的组织方式。 (2) 查找算法的评价。 衡量算法的标准主要有两个：时间复杂度和空间复杂度。查找算法一般只需很少的辅助空间，因此更关心的是它的时间复杂度。 在查找算法中，基本运算是给定值与关键字的比较，所以算法的主要时间是花费在“比较”上。 下面用平均查找长度的概念，来评价查找算法的好坏。 对于含有n个数据元素的查找表，查找成功时的平均查找长度为 ASL = 其中，Pi为查找第i个数据元素的概率；Ci为查到第i个数据元素时，需与关键字进行比较的次数。 线性查找 线性查找也称顺序查找，是最简单、常用的查找技术。 基本思想是：从表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某个元素的关键字等于给定值K，则表明查找成功，返回该元素的下标；反之，若直到所有元素都比较完毕，仍找不到关键字为K的元素，则表明查找失败，返回特定的值。 顺序查找方法既适用于以顺序存储结构，也适用于以链式存储结构。在本章的有关查找和排序算法中，假设线性表均采用顺序存储结构，其类型说明为： #define MAXLEN n /* n为查找表中元素个数的最大可能值*/ struct element{ int key; /*设关键字的类型为整型*/ int otherterm; /*为说明起见，除关键字外只有一个整型数据项*/ }; typedef struct element DATATYPE; DATATYPE table[MAXLEN]; 算法 顺序查找算法。 int seqsearch1(DATATYPE A[], int k) { int i=0; while((A[i].key!=k)(iMAXLEN)) i++; if(A[i].key==k) return i; /*查找成功，返回被查元素在表中的相对位置*/ else return –1; /*查找失败，返回–1*/ } 若对此算法进行一些改进，在表尾增加一个关键字为指定值K的记录(即所谓的“前哨”)，可避免每“比较”一次，就要判别查找是否结束。当n很大时，大约可节省一半的时间。 算法 改进的（即增加“前哨” ）顺序查找算法。 #define MAXLEN n+1 int seqsearch2(DATATYPE A[],int k) { int i=0； A[MAXLEN?1].key=k; while (A[i].key!=k) i++; if(iMAXLEN?1) return i; /*查找成功，返回被查元素相对位置*/ else return –1; /*查找失败，返回?1*/ } 将A[MAXLEN?1]称作监视哨，这个增加的记录起到了边界标识的作用。 下面对改进后的算法进行一下性能分析，计算它的平均查找长度。 对