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

1、初赛基本算法知识1线性表表示（一）N个数据元素的有限序列（一般用数组表示）存储结构：顺序存储结构、链式存储结构20123456782线性表表示（二）链式存储 22 20 Lhead3栈特殊的线性表操作特点：后进先出（Last In First Out）栈顶表尾栈底表头空栈（top=bottom)ABCD栈顶指针：指想下一个元素的存放位置栈底指针4栈 （考题分析）（1998） 栈S初始状态为空，现有5个元素组成的序列1，2，3，4，5，对该序列在栈S上一次进行如下操作（从序列中的1开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是_(A) 5,4,3,2,1 (

2、B) 2,1 (C) 2,3 (D) 3,45队列特点：先进先出允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。a1 a2 a3 a4 an 出队列入队列FRONTREAR6循环队列12345678REARFRONT现在栈中存放的元素个数：(R-F+N) mod N7树根、叶子、子树结点的度：结点拥有的子树数二叉树(每个节点最多只有两个子节点的树）ACFEBDG层次1238二叉树特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。第i层至多有 2i-1 个结点（i=1）深度为K的二叉树最多有 2k-1 个结点（K=1）ACFEBDGACFEBD满二叉树完全二叉

3、树9二叉树的遍历先（根）序遍历中（根）序遍历后（根）序遍历先（根）序遍历ABDFGCEH中（根）序遍历BFDGACHE后（根）序遍历FGDBHECA 若左子树非空先访问左子树访问根节点若左子树非空先访问左子树ACEDBHFG10例题分析给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：DGEBHIFCA ，画出此二叉树。ACEDBHFGI思考过程 先在后序中找到最后面的节点A，那我们知道这棵树的根目录是A，A将中序的遍历分成两个部分前面部分“DBGE”是左子树的中序遍历，后面部分“CHFI”是右子树的中序遍列，在后序遍历中找到这两个字符串中最先出现的字符，那就是左子树和右子树的根节点，

4、再在中序遍历中划分.11图ACEDB无向图ACEDB有向图12图的存储结构邻接矩阵邻接矩阵（二维数组）1452313 遍历是指从图的某个点出发，沿着与之相连的边访问图中的每个一次且仅一次。基本方法有两种：深度优先遍历和广度优先遍历。 深度优先和广度优先遍历，与前面所说的树的深度与广度优先遍历是类似的：比下图中，如果从点V1出发，那么： 深度优先遍历各点的顺序为：v1，v2，v4，v7，v5，v3，v6，v8。 广度优先遍历各点的顺序为：v1，v2，v3，v4，v5，v6，v7，v8。图的遍历1415起泡排序方法先将序列中的第一个记录R0与第二个记录R1比较，若前者大于后者，则两个记录交换位置，

5、否则不交换然后对新的第二个记录R1与第三个记录R2作同样的处理依次类推，直到处理完第n-1个记录和第n个记录从(R0，R1)到(Rn-2，Rn-1)的n-1次比较和交换过程称为一次起泡经过这次起泡，n个记录中最大者被安置在第n个位置上1516此后，再对前n-1个记录进行同样处理，使n-1个记录的最大者被安置在整个序列的第n-1个位置上。然后再对前n-2个记录重复上述过程，这样最多做n-1次起泡就能完成排序可以设置一个标志noswap表示本次起泡是否有记录交换，如果没有交换则表示整个排序过程完成起泡排序是通过相邻记录之间的比较与交换，使值较大的记录逐步从前(上)向后(下)移，值较小的记录逐步从后

6、(下)向前(上)移，就像水底的气泡一样向上冒，故称为起泡排序起泡排序方法16冒泡排序算法如下：void BubbleSort(RecordType r, int length )/*对记录数组r做冒泡排序， length为数组的长度*/ n=length; change=TRUE； for ( i=1 ; i= n-1 & change ;+i ) change=FALSE； for ( j=1 ; j rj+1.key ) x= rj; rj= rj+1; rj+1= z; change=TRUE； /* BubbleSort */ 1718初始序列为49, 38, 65, 97, 76,

7、13, 27, 49，请用起泡排序法排序第一趟起泡38 49657613274997第二趟起泡38 4965 1327497697第三趟起泡38 4913274965 7697例 题1819第四趟起泡 38 13274949657697第五趟起泡 13 27384949657697第六趟起泡 13 27384949657697排序结果为 13 27 38 4949657697例 题(续)19若文件初状为正序，则一趟起泡就可完成排序，排序码的比较次数为n-1，且没有记录移动，时间复杂度是O(n)若文件初态为逆序，则需要n-1趟起泡，每趟进行n-i次排序码的比较，且每次比较都移动三次，比较和移动次

8、数均达到最大值起泡排序的算法评价20起泡排序的算法评价(续)起泡排序最好时间复杂度是O(n)起泡排序最坏时间复杂度为O(n2)起泡排序平均时间复杂度为O(n2)起泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)起泡排序是稳定的21设置变量i指向参加排序的序列中第一个位置0，变量j指向参加排序的序列中最后位置n-1首先保存记录R0，R0为空出的位置，空位在前一区令j向前扫描，寻找小于R0的记录，找到小于R0的记录Rj，将记录Rj移到当前空位中，这时空位在后一区这时令i自i+1起向后扫描，寻找大于R0的记录，找到大于R0的记录Ri，将记录Ri移到当前空位中，空位又到了前一区，然后

9、再令j自j-1起向前扫描，此交替改变扫描方向，从两端向中间靠拢，直到i=j，这时i所指的位置为R0的最终位置快速排序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 iji向右扫描27 3865977613 49ij23第二次交换后27 38 97 76 13 65 49 i jj向左扫描，位置不变，第三次交换后27 38 13 97 76 65 49 i ji向右扫描，位置不变，第四次交换后27 38 13 76 97 65

10、49 i jj向左扫描27 38 13 49 76 97 65 49 ij24 13 27 38 49 49 65 76 971327 38 4949 65 76 971327 38 4949 65 76 97 最后的排序结果1327 38 4949 65 76 97例（续）:25当待排序记录已经有序时，算法的执行时间最长，直接蜕化为起泡排序第一趟经过n-1次比较，将第一个记录定位在原来的位置上，并得到一个包括n-1个记录的子文件第二趟经过n-2次比较，将第二个记录定位在原来的位置上，并得到一个包括n-2个记录的子文件；这样最坏情况总比较次数为快速排序算法评价2627最好情况下，每次划分使两个

11、子区的长度大致相等C(n) n+2C(n/2) n+2n/2+2C(n/22)=2n+4c(n/22)kn+2kC(n/2k)= nlog2n+nC(1)= O(nlog2n)快速排序的平均时间复杂度是T(n)=O(nlog2n)，空间上需要一个栈来进行递归快速排序是不稳定的快速排序算法评价(续)27插入排序基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。x 顺次选取一个元素插入到合适位置28插入排序的细分类如何插入到已排好序的序列中？直接插入（从后向前找位置后插入） O(n2) 二分法插入（按二分法找位置后插入） O(nlog2n)

12、 表插入排序（按链表查找位置后插入） O(n2)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，8031监视哨的作用算法中

13、引进的附加记录R0称监视哨或哨兵(Sentinel)，哨兵有两个作用： 进人查找(插入位置)循环之前，它保存了Ri的副本，使不致于因记录后移而丢失Ri的内容； 它的主要作用是：在查找循环中监视下标变量j是否越界。一旦越界(即j=0)，因为R0.key和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测j是否越界(即省略了循环判定条件j=1)。注意： 实际上，一切为简化边界条件而引入的附加结点(元素)均可称为哨兵。 【例】单链表中的头结点实际上是一个哨兵 引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排

14、序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。 32初始数据状态相关：文件初态不同时，直接插入排序所耗费的时间有很大差异。若文件初态为正序，则算法的时间复杂度为O(n)若初态为反序，则时间复杂度为O(n2)33小结直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2)直接插入排序的平均时间复杂度为T(n) = O(n2)算法中引入了一个附加的记录空间temp，因此辅助空间为S(n) = O(1)直接插入排序是稳定的34折半插入排序原理 由于插入排序本身就是一个查找和插入的过程，那么这个查找过程可以运用折半查找来实现，这种方法就称为折半插入排序。过程： 折半查找 - 记录后移 - 插入数据 折半查找虽然减少了关键字间的比较，但是记录的移动次数是没有改变，因此，算法时间复杂度依然是O(n2)35表插入排序表插入排序是在直接插入排序的基础上减少移动的次数。基本思想: 先在待插入记录之前的有序子链表中查找应插入位置，然后将待插入记录插入链表。由于链表的插入操作只修改指针域，不移动记录，所以表插入排序可提高排序效率。在算法的具体实现上，我们可以采用静态链表作为存储结构。36归并排序（mer