南昌大学第第2 2篇篇 数据结构数据结构南昌大学 机电工程学院 涂海宁 13970855564 Cthn163.com1南昌大学第13章 查 找 和 排 序2南昌大学1、线性查找查找(Searching)，也称检索，亦即查表，就是在大量的信息集中寻找一个“特定的”信息元素。人们几乎每天都要做“查找”工作，如查寻电话号码、查字典、查图书目录卡片等。为确切定义查找，先引入几个概念。查找表：由同一类型的数据元素(或记录)构成的集合。3南昌大学关键字(key)：数据元素中可以惟一标识一个数据元素的数据项。如学生的学号，居民身份证号等。查找就是根据给定的关键字值，在查找表中确定一个关键字等于给定值的记录或数据元素。若存在这样的数据元素，则称查找是成功的，否则称查找不成功。决定查找操作的是关键字，因此这里讨论时，只关注记录中的关键字域，而一概忽略记录中其它诸域的信息。4南昌大学查找是最耗费时间的部分，查找算法的优劣密切关系着查找操作的速度，因此对查找算法应认真研究。关于查找，目前主要研究两方面的问题：(1) 查找的方法。因为查找某个数据元素依赖于该数据元素在一组数据中所处的位置，即该组数据的组织方式，故应按照数据元素的组织方式决定采用的查找方法；反过来，为了提高查找方法的效率，要求数据元素采用某些特殊的组织方式。5南昌大学(2) 查找算法的评价。衡量算法的标准主要有两个：时间复杂度和空间复杂度。查找算法一般只需很少的辅助空间，因此更关心的是它的时间复杂度。在查找算法中，基本运算是给定值与关键字的比较，所以算法的主要时间是花费在“比较”上。下面用平均查找长度的概念，来评价查找算法的好坏。 6南昌大学对于含有n个数据元素的查找表，查找成功时的平均查找长度为ASL = 其中，Pi为查找第i个数据元素的概率；Ci为查到第i个数据元素时，需与关键字进行比较的次数。7南昌大学线性查找线性查找也称顺序查找，是最简单、常用的查找技术。基本思想是：从表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某个元素的关键字等于给定值K，则表明查找成功，返回该元素的下标；反之，若直到所有元 素都比较完毕，仍找不到关键字为K的元素，则表明查找失败，返回特定的值。8南昌大学顺序查找方法既适用于以顺序存储结构，也适用于以链式存储结构。在本章的有关查找和排序算法中，假设线性表均采用顺序存储结构，其类型说明为：9南昌大学#define MAXLEN n/* n为查找表中元素个数的最大可能值*/struct elementint key; /*设关键字的类型为整型*/int otherterm;/*为说明起见，除关键字外只有一个整型数据项*/;typedef struct element DATATYPE;DATATYPE tableMAXLEN;10南昌大学算法 顺序查找算法。int seqsearch1(DATATYPE A, int k) int i=0;while(Ai.key!=k)elsehigh=mid1;return 1;/*查找失败，返回1*/16南昌大学折半查找成功的平均查找长度为ASLbslog2 (n+1) 1(求解过程从略)折半查找的优点是比较次数少，查找速度快，但只能对有序表进行查找。它适用于一经建立就很少变动而又经常需进行查找的有序表。17南昌大学例 一有序表的关键字序列为(5，12，18，20，35，50，64，72，80，88，95)，表长为11，采用折半查找求其在等概率情况下查找成功时的平均查找长度。解：按照折半查找算法，对序列中11个元素的查找过程如下：(1) mid =(1+11)DIV 2查到第6个元素50，比较1次；(2) mid =(1+5)DIV 2查到第3个元素18，比较2次；或mid =(7+11)DIV 2查到第9个元素80，比较2次；(3) 依次类推，查到第1、4、7和第10个元素需比较3次；查到第2、5、8和第11个元素需比较4次。18南昌大学这个查找过程可用一棵二叉树表示。这种描述查找过程的二叉树为判定树，若树中每个结点表示一个记录， 结点中的值为该记录在表中的位置。结点在树中所处的层数，即为采用折半查找此结点的步数（比较的次数）。步数最多不超过树的深度19南昌大学3、分块查找分块查找又称索引顺序查找，这是顺序查找的另一种改进方法。顺序查找速度慢；而折半查找虽速度快，但要将线性表按关键字排序，而且必须采取顺序存储。在顺序结构里执行插入、删除操作都很困难。如果要处理的线性表既希望较快的检索又需要存储结构灵活，可以采用分块查找。分块查找是顺序查找和折半查找的折衷方案，特别适用于索引存储结构。20南昌大学分块查找基本思想：按照表内记录的某种属性（关键字）把表分成n(n1)个块(子表)，每一块中记录的存放是任意的，但是块与块之间是有序的，即所谓“分块有序”。假如按关键字递增顺序进行分块排列，就是指第j块的所有记录的关键字均大于第j1块的所有记录的关键字(j=2,3,n)，并建立一个索引表。把每块中的最大关键字值及每块的第一个记录在表中的位置存放在索引项中。整个查找过程分两步进行：(1) 确定待查记录所在的块。(2) 在块内按顺序查找。21南昌大学例 设给定值K=32，在图4-2所示的索引顺序表中查找关键字等于K的记录。22南昌大学解：在图4-2的表中有18个记录，分成了三个子表(R1，R2，R6)，(R7，R8，R12)，(R13，R14，R18)。先将K依次和索引表中各最大关键字进行比较，因为25Rj+1.key) temp=Rj; /*交换元素，设结构体变量可以整体赋值*/Rj=Rj+1;Rj+1=temp;排 序69南昌大学按照冒泡排序算法，对具有n个记录的待排序序列要执行n1趟冒泡排序。但从上例中我们可以发现，在进行第三趟冒泡排序过程时，已没有记录进行过交换，表明此时记录序列已经“正序”(有序)，后面的3趟没有发生交换。因此应该对算法加以改进：使之能“记住”每趟冒泡排序过程中是否发生了“交换”，若某一趟冒泡未发生“交换”，表示此时记录序列已经有序，应结束排序过程。排 序70南昌大学算法 改进后的冒泡排序算法。void bubblesort_m(RECORD R,int n) int i,j,flag;RECORD temp;i=1;do flag=0; /*在进行每一趟冒泡之前置flag为0，表示无交换*/for(j=1;jRj+1.key) temp=Rj; Rj=Rj+1; Rj+1=temp; flag=1; i+;while(iR，完成快速排序的第一趟排序。然后分别对子序列1和子序列2重复上述划分，直到每个子序列中只有一个记录时为止。那么如何实现这个划分呢？需设两个指针i、j，初始时分别指向第一个和最后一个记录，即令i=1，j=n，并将第一个记录的关键字暂存于k(先用第一个记录的关键字k进行划分，称这个记录为控制记录或支点)。排 序74南昌大学当ij时，重复以下操作：(1) 若kRj.key，则j=j1，即再比较j的前一个记录关键字；否则Rj与Ri交换。(2) 比较k与i指向的记录的关键字，若kRi.key，则与i的后一个记录关键字比较(i=i+1)；否则将Ri与Rj交换。(3) 重复上述过程，直至i=j时，划分结束，i所指示的位置就是控制记录应有的位置。下面看一个快速排序的例子。排 序75南昌大学例 一组待排序的记录关键字序列为(46，55，13， 42，94，05，17，70)，试给出第一趟快速排序过程中记录的交换示意图。解：一趟快速排序过程如图4-14所示。上例给出了一趟快速排序的过程，整个快速排序的过程可递归进行。若待排序列中只有一个记录，显然已有序，否则进行一趟快速排序后再分别对分割所得的两个子序列进行快速排 序。结合上述例题，给出快速排序的全过程，如图4-15所示。排 序76南昌大学排 序77南昌大学排 序78南昌大学5、归并排序归并(merging)就是将两个(或两个以上)的有序表合并成一个新的有序表的操作。若是对2个有序表进行的归并则称为2路归并。对于一个无序表来说，归并排序把它看成是由n个只包含一个记录的有序表组成的表，然后进行两两归并，最后形成包 含n个记录的有序文件。排 序79南昌大学2路归并排序的思想：设初始文件含有n个记录，则可看成n个有序的子文件，每个子文件长度为1，然后两两归并，得到n/2个长度为2或1的子文件，再两两归并，如此重复，直到得到一个长度为n的有序子文件为止。例如：关键字序列为(49，38，65，97，76，13，27)。归并排序时，先将这7个记录看成长度为1的7个有序子序列，然后逐步两两归并，排序过程如图所示。排 序80南昌大学排 序2路归并排序示例81