信息学联赛初赛基本算法介绍

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,初赛基本算法知识,1,线性表表示（一）,N,个数据元素的有限序列,（一般用数组表示）,存储结构：顺序存储结构、链式存储结构,20,12345678,2,线性表表示（二）,链式存储,22,20,L,head,3,栈,特殊的线性表,操作特点：,后进先出,（Last In First Out）,栈顶表尾,栈底表头,空栈（top=bottom),A,B,C,D,栈顶指针：,指想下一个元素的存放位置,栈底指针,4,栈 （考题分析）,（1998）,栈S初始状态为空，现有5个元素组成的序列1，2，3，4，5，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是_,(A) 5,4,3,2,1 (B) 2,1 (C) 2,3 (D) 3,4,5,队列,特点：,先进先出,允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。,a1 a2 a3 a4 an,出队列,入队列,FRONT,REAR,6,循环队列,1,2,3,4,5,6,7,8,REAR,FRONT,现在栈中存放的元素个数：(R-F+N) mod N,7,树,根、叶子、子树,结点的度：结点拥有的子树数,二叉树,(,每个节点最多只有两个子节点的树,）,A,C,F,E,B,D,G,层次,1,2,3,8,二叉树,特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。,第i层至多有,2,i-1,个结点（i=1）,深度为K的二叉树最多有,2,k,-1,个结点（K=1）,A,C,F,E,B,D,G,A,C,F,E,B,D,满二叉树,完全二叉树,9,二叉树的遍历,先（根）序遍历,中（根）序遍历,后（根）序遍历,先（根）序遍历,ABDFGCEH,中（根）序遍历,BFDGACHE,后（根）序遍历,FGDBHECA,若左子树非空先访问左子树,访问根节点,若左子树非空先访问左子树,A,C,E,D,B,H,F,G,10,例题分析,给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA ，画出此二叉树。,A,C,E,D,B,H,F,G,I,思考过程,先在后序中找到最后面的节点,A，那我们,知道这棵树的根目录是A，A将中序的遍,历分成两个部分前面部分“DBGE”是左子,树的中序遍历，后面部分“CHFI”是右子,树的中序遍列，在后序遍历中找到这两个,字符串中最先出现的字符，那就是左子树,和右子树的根节点，再在中序遍历中划分,.,11,图,A,C,E,D,B,无向图,A,C,E,D,B,有向图,12,图的存储结构邻接矩阵,邻接矩阵（,二维数组,）,1,4,5,2,3,13,遍历是指从图的某个点出发，沿着与之相连的边访问图中的每个一次且仅一次。基本方法有两种：,深度优先遍历和广度优先遍历。,深度优先和广度优先遍历，与前面所说的树的深度与广度优先遍历是类似的：比下图中，如果从点V1出发，那么：,深度优先遍历各点的顺序为：v1，v2，v4，v7，v5，v3，v6，v8。,广度优先遍历各点的顺序为：v1，v2，v3，v4，v5，v6，v7，v8。,图的遍历,14,15,起泡排序,方法,先将序列中的第一个记录,R,0,与第二个记录,R,1,比较，若前者大于后者，则两个记录交换位置，否则不交换,然后对新的第二个记录,R,1,与第三个记录,R,2,作同样的处理,依次类推，直到处理完第,n-1,个记录和第,n,个记录,从,(R,0,，,R,1,),到,(R,n-2,，,R,n-1,),的,n-1,次比较和交换过程称为,一次起泡,经过这次起泡，,n,个记录中最大者被安置在第,n,个位置上,15,16,此后，再对,前,n-1,个记录,进行同样处理，使,n-1,个记录的最大者被安置在整个序列的第,n-1,个位置上。,然后再对前,n-2,个记录重复上述过程,，这样最多做,n-1,次起泡,就能完成排序,可以设置一个标志,noswap,表示本次起泡是否有记录交换，如果没有交换则表示整个排序过程完成,起泡排序是通过相邻记录之间的比较与交换，使值较大的记录逐步从前,(,上,),向后,(,下,),移，值较小的记录逐步从后,(,下,),向前,(,上,),移，就像水底的气泡一样向上冒，故称为,起泡排序,起泡排序方法,16,冒泡排序算法如下：,void BubbleSort(RecordType r, int length ),/*对记录数组r做冒泡排序， length为数组的长度*/,n=length; change=TRUE； ,for ( i=1 ; i= n-1 +i ) , change=FALSE； ,for ( j=1 ; j rj+1.key ) ,x= rj;,rj= rj+1;,rj+1= z;,change=TRUE； , , /* BubbleSort */,17,18,初始序列为49, 38, 65, 97, 76, 13, 27, 49，请用起泡排序法排序,第一趟起泡,38 496576132749,97,第二趟起泡,38 4965 132749,7697,第三趟起泡,38 49132749,65 7697,例 题,18,19,第四趟起泡,38 132749,49657697,第五趟起泡,13 2738,4949657697,第六趟起泡,13 27,384949657697,排序结果为,13 27 38 4949657697,例 题(续),19,若文件初状为,正序,，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是,O(n),若文件初态为,逆序,，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次数均达到最大值,起泡排序的算法评价,20,起泡排序的算法评价(续),起泡排序,最好,时间复杂度是,O(n),起泡排序,最坏,时间复杂度为,O(n,2,),起泡排序,平均,时间复杂度为,O(n,2,),起泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1),起泡排序是,稳定的,21,设置变量,i,指向参加排序的序列中第一个位置,0,，变量,j,指向参加排序的序列中最后位置,n-1,首先保存记录,R,0,，,R0,为空出的位置，空位在前一区,令,j,向前扫描，寻找小于,R,0,的记录，找到小于,R,0,的记录,Rj,，将记录,Rj,移到当前空位中，这时空位在后一区,这时令,i,自,i+1,起向后扫描，寻找大于,R,0,的记录，找到大于,R,0,的记录,Ri,，将记录,Ri,移到当前空位中，空位又到了前一区，,然后再令,j,自,j-1,起向前扫描，此交替改变扫描方向，从两端向中间靠拢，直到,i=j,，这时,i,所指的位置为,R,0,的最终位置,快速排序,22,初始序列为49, 38, 65, 97, 76, 13, 27, 49，,例:,(1)一次分区过程如下,j向左扫描,49,38 65 97 76 1327 49,ij,第一次交换后,27 38 65 97 76 13,49,ij,i向右扫描,27 3865977613,49,ij,23,第二次交换后,27 38,97 76 13 65 49,i j,j向左扫描，位置不变，第三次交换后,27 38 13 97 76,65 49,i j,i向右扫描，位置不变，第四次交换后,27 38 13,76 97 65 49,i j,j向左扫描,27 38 13,49,76 97 65 49,ij,24,13 27 38 49 49 65 76 97,1327 38 4949 65 76 97,1327 38 4949 65 76 97,最后的排序结果,1327 38 4949 65 76 97,例（续）:,25,当待排序记录已经有序时，算法的执行时间最长，直接蜕化为起泡排序,第一趟经过n-1次比较，将第一个记录定位在原来的位置上，并得到一个包括n-1个记录的子文件,第二趟经过n-2次比较，将第二个记录定位在原来的位置上，并得到一个包括n-2个记录的子文件；,这样最坏情况总比较次数为,快速排序算法评价,26,27,最好情况下，每次划分使两个子区的长度大致相等,C(n,) n+2C(n/2) n+2n/2+2C(n/2,2,)=2n+4c(n/2,2,),kn+2,k,C(n/2,k,)= nlog,2,n+nC(1)= O(nlog,2,n),快速排序的平均时间复杂度是,T(n,)=O(nlog,2,n),，空间上需要一个栈来进行递归,快速排序是不稳定的,快速排序算法评价(续),27,插入排序,基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。,x,顺次选取一个元素,插入到合适位置,28,插入排序的细分类,如何插入到已排好序的序列中？,直接插入（从后向前找位置后插入）,O(n,2,),二分法插入（按二分法找位置后插入）,O(nlog,2,n),表插入排序（按链表查找位置后插入）,O(n,2,),29,直接插入排序,基本思想：,假定前面m 个元素已经排序；,取第(m+1) 个元素，插入到前面的适当位置；,一直重复，到m=n 为止。,（初始情况下，m = 1）,30,第一趟： 23，,起始只有一个记录,r0 监视哨,11, 23,11,第二趟： 11，23，,11，23，,55,55,第三趟： 11，23，55，,11，23，55，,97,97,第四趟： 11，23，55，97，,11，,19,，23，55，97,19,第五趟： 11，19，23，55，97，,11，19，23，55，,80,，97,80,示例,：,23，11，55，97，19，80,31,监视哨的作用,算法中引进的附加记录R0称监视哨或哨兵(Sentinel)，哨兵有两个作用： 进人查找(插入位置)循环之前，它保存了Ri的副本，使不致于因记录后移而丢失Ri的内容； 它的主要作用是：在查找循环中监视下标变量j是否越界。一旦越界(即j=0)，因为R0.key和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件j=1)。注意： 实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。 【例】单链表中的头结点实际上是一个哨兵 引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。,32,初始数据状态相关：,文件初态不同时，直接插入排序所耗费的时间有很大差异。,若文件初态为正序，则算法的时间复杂度为O(n),若初态为反序，则时间复杂度为O(n,2,),33,小结,直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2),直接插入排序的平均时间复杂度为T(n) = O(n2),算法中引入了一个附加的记录空间temp，因此辅助空间为S(n) = O(1),直接插入排序是稳定的,34,折半插入排序,原理,由于插入排序本身就是一个查找和插入的过程，那么这个查找过程可以运用折半查找来实现，这种方法就称为折半插入排序。,过程,：,折半查找 - 记录后移 - 插入数据,折半查找虽然减少了关键字间的比较，但是记录的移动次数是没有改变，因此，算法时间复杂度依然是O(n,2,),35,表插入排序,表插入排序是在直接插入排序的基础上减少移动的次数。,基本思想:,先在待插入记录之前的有序子链表中查找应插入位置，然后将待插入记录插入链表。由于链表的插入操作只修改指针域，不移动记录，所以表插入排序可提高排序效率。在算法的具体实现上，我们可以采用静态链表作为存储结构。,36,归并排序（merge sort）,归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。,最简单的情况是:只含一个记录的序列显然是个有序序列，经过逐趟归并使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止。,37,38,具有n个记录的文件排序，必须做,log,2,n,趟归并，每趟归并所花费的时间是O(n),二路归并排序算法的时间复杂度为T(n)=,O(nlog,2,n),算法中增加了一个数组record，算法的辅助空间为S(n)=O(n),二路归并排序是,稳定的,算法评价,39,