初赛基本算法知识初赛基本算法知识1 1线性表表示（一）线性表表示（一）线性表表示（一）线性表表示（一）l lN个数据元素的有限序列（一般用数组表示）l l存储结构：顺序存储结构、链式存储结构20123456782 2线性表表示（二）线性表表示（二）线性表表示（二）线性表表示（二）l l链式存储链式存储 2222 2020 Lhead3 3栈n n特殊的线性表n n操作特点：后进先出（Last In First Out）n n栈顶表尾n n栈底表头n n空栈（top=bottom)ABCD栈顶指针：栈顶指针：指想下一个元素指想下一个元素的存放位置的存放位置栈底指针栈底指针4 4栈 （考题分析）（19981998） 栈栈栈栈S S初始状态为空，现有初始状态为空，现有初始状态为空，现有初始状态为空，现有5 5个元素组成的个元素组成的个元素组成的个元素组成的序列序列序列序列11，2 2，3 3，4 4，55，对该序列在栈，对该序列在栈，对该序列在栈，对该序列在栈S S上一次上一次上一次上一次进行如下操作（从序列中的进行如下操作（从序列中的进行如下操作（从序列中的进行如下操作（从序列中的1 1开始，出栈后不再进开始，出栈后不再进开始，出栈后不再进开始，出栈后不再进栈）：进栈、进栈、进栈、出栈、进栈、出栈、栈）：进栈、进栈、进栈、出栈、进栈、出栈、栈）：进栈、进栈、进栈、出栈、进栈、出栈、栈）：进栈、进栈、进栈、出栈、进栈、出栈、进栈。问出栈的元素序列是进栈。问出栈的元素序列是进栈。问出栈的元素序列是进栈。问出栈的元素序列是_(A) 5,4,3,2,1 (B) 2,1 (C) 2,3 (D) 3,4(A) 5,4,3,2,1 (B) 2,1 (C) 2,3 (D) 3,45 5队列n n特点：先进先出先进先出n n允许插入的一端称为队尾(rear)，允许删除的一端称为队头(front)。a1 a2 a3 a4 an a1 a2 a3 a4 an 出队列入队列FRONTREAR6 6循环队列循环队列12345678REARFRONT现在栈中存放的元素个数：现在栈中存放的元素个数：(R-F+N) mod N7 7树树树树根、叶子、子树根、叶子、子树结点的度：结点拥有的子树数结点的度：结点拥有的子树数二叉树二叉树( (每个节点最多只有两个子节点的树每个节点最多只有两个子节点的树）ACFEBDG层次1238 8二叉树n n特点：每个结点至多只有二棵子树，并且二叉特点：每个结点至多只有二棵子树，并且二叉特点：每个结点至多只有二棵子树，并且二叉特点：每个结点至多只有二棵子树，并且二叉树的子树有左右之分。树的子树有左右之分。树的子树有左右之分。树的子树有左右之分。n n第第第第i i层至多有层至多有层至多有层至多有 2 2i-1i-1 个结点（个结点（个结点（个结点（i=1i=1）n n深度为深度为深度为深度为K K的二叉树最多有的二叉树最多有的二叉树最多有的二叉树最多有 2 2k k-1 -1 个结点个结点个结点个结点（K=1K=1）ACFEBDGACFEBD满二叉树满二叉树完全二叉树完全二叉树9 9二叉树的遍历二叉树的遍历二叉树的遍历二叉树的遍历l l先（根）序遍历先（根）序遍历l l中（根）序遍历中（根）序遍历l l后（根）序遍历后（根）序遍历先（根）序遍历先（根）序遍历ABDFGCEHABDFGCEH中（根）序遍历中（根）序遍历BFDGACHEBFDGACHE后（根）序遍历后（根）序遍历FGDBHECA FGDBHECA l l若左子树非空先访问左子树若左子树非空先访问左子树l l访问根节点访问根节点l l若左子树非空先访问左子树若左子树非空先访问左子树ACEDBHFG1010例题分析例题分析例题分析例题分析n n给出一棵二叉树的中序遍历：给出一棵二叉树的中序遍历：DBGEACHFI 与后序遍历：与后序遍历：DGEBHIFCA ，画出此二叉树。，画出此二叉树。ACEDBHFGI思考过程思考过程 先在后序中找到最后面的节点先在后序中找到最后面的节点AA，那我们，那我们，那我们，那我们知道这棵树的根目录是知道这棵树的根目录是知道这棵树的根目录是知道这棵树的根目录是AA，AA将中序的遍将中序的遍将中序的遍将中序的遍历分成两个部分前面部分历分成两个部分前面部分历分成两个部分前面部分历分成两个部分前面部分“DBGE”“DBGE”是左子是左子是左子是左子树的中序遍历，后面部分树的中序遍历，后面部分树的中序遍历，后面部分树的中序遍历，后面部分“CHFI”“CHFI”是右子是右子是右子是右子树的中序遍列，在后序遍历中找到这两个树的中序遍列，在后序遍历中找到这两个树的中序遍列，在后序遍历中找到这两个树的中序遍列，在后序遍历中找到这两个字符串中最先出现的字符，那就是左子树字符串中最先出现的字符，那就是左子树字符串中最先出现的字符，那就是左子树字符串中最先出现的字符，那就是左子树和右子树的根节点，再在中序遍历中划分和右子树的根节点，再在中序遍历中划分和右子树的根节点，再在中序遍历中划分和右子树的根节点，再在中序遍历中划分.1111图图ACEDB无向图无向图ACEDB有向图有向图1212图的存储结构图的存储结构图的存储结构图的存储结构邻接矩阵邻接矩阵邻接矩阵邻接矩阵l l邻接矩阵（二维数组二维数组）145231313 遍历遍历 是指从图的某个点出发，沿着与之相连的边访问图中的是指从图的某个点出发，沿着与之相连的边访问图中的每个一次且仅一次。基本方法有两种：每个一次且仅一次。基本方法有两种：深度优先遍历和广度优深度优先遍历和广度优深度优先遍历和广度优深度优先遍历和广度优先遍历。先遍历。先遍历。先遍历。 深度优先和广度优先遍历，与前面所说的树的深度与广度优先深度优先和广度优先遍历，与前面所说的树的深度与广度优先遍历是类似的：比下图中，如果从点遍历是类似的：比下图中，如果从点V1V1出发，那么：出发，那么： 深度优先遍历各点的顺序为：深度优先遍历各点的顺序为：v1v1，v2v2，v4v4，v7v7，v5v5，v3v3，v6v6，v8v8。 广度优先遍历各点的顺序为：广度优先遍历各点的顺序为：v1v1，v2v2，v3v3，v4v4，v5v5，v6v6，v7v7，v8v8。141415起泡排序n n方法方法先将序列中的第一个记录先将序列中的第一个记录R R0 0与第二个记录与第二个记录R R1 1比较，比较，若前者大于后者，则两个记录交换位置，否则不若前者大于后者，则两个记录交换位置，否则不交换交换然后对新的第二个记录然后对新的第二个记录R R1 1与第三个记录与第三个记录R R2 2作同样作同样的处理的处理依次类推，直到处理完第依次类推，直到处理完第n-1n-1个记录和第个记录和第n n个记录个记录n n从从(R(R0 0，R R1 1) )到到(R(Rn-2n-2，R Rn-1n-1) )的的n-1n-1次比较和交换过程次比较和交换过程称为称为一次起泡一次起泡n n经过这次起泡，经过这次起泡，n n个记录中最大者被安置在第个记录中最大者被安置在第n n个个位置上位置上151516此此后后，再再对对前前n-1n-1个个记记录录进进行行同同样样处处理理，使使n-1n-1个个记记录录的的最最大大者者被被安安置置在在整整个个序序列列的的第第n-1n-1个个位置上。位置上。然然后后再再对对前前n-2n-2个个记记录录重重复复上上述述过过程程，这这样最多做样最多做n-1n-1次起泡次起泡就能完成排序就能完成排序n n可可以以设设置置一一个个标标志志noswapnoswap表表示示本本次次起起泡泡是是否否有有记记录录交交换换，如如果果没没有有交交换换则则表表示示整整个个排排序序过过程完成程完成n n起泡排序是通过相邻记录之间的比较与交换，起泡排序是通过相邻记录之间的比较与交换，使值较大的记录逐步从前使值较大的记录逐步从前( (上上) )向后向后( (下下) )移，值移，值较小的记录逐步从后较小的记录逐步从后( (下下) )向前向前( (上上) )移，就像水移，就像水底的气泡一样向上冒，故称为底的气泡一样向上冒，故称为起泡排序起泡排序起泡排序方法1616冒泡排序算法如下：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 */ 171718初始序列为初始序列为49, 38, 65, 97, 76, 13, 27, 4949, 38, 65, 97, 76, 13, 27, 49，请用，请用起泡排序法排序起泡排序法排序第一趟起泡第一趟起泡 3838 49 4965657676131327274949 9797 第二趟起泡第二趟起泡 3838 49 4965 65 131327274949 76769797 第三趟起泡第三趟起泡 38 38 4949131327274949 65 7665 76 9797 例 题181819第四趟起泡第四趟起泡 38 13 38 13 27274949 4949656576769797 第五趟起泡第五趟起泡 13 13 27 273838 49494949656576769797 第六趟起泡第六趟起泡 13 13 27 27 383849494949656576769797 排序结果为排序结果为 13 13 27 27 38 38 49 494949656576769797例 题(续)1919n n若若文文件件初初状状为为正正序序，则则一一趟趟起起泡泡就就可可完完成成排排序序，排排序序码码的的比比较较次次数数为为n-1n-1，且且没没有有记记录录移移动动，时时间间复复杂杂度度是是O(n)O(n)n n若若文文件件初初态态为为逆逆序序，则则需需要要n-1n-1趟趟起起泡泡，每每趟趟进进行行n-in-i次次排排序序码码的的比比较较，且且每每次次比比较较都都移移动动三三次次，比比较较和和移移动次数均达到最大值动次数均达到最大值 起泡排序的算法评价2020起泡排序的算法评价(续)n n起泡排序最好时间复杂度是O(n)n n起泡排序最坏时间复杂度为O(n2)n n起泡排序平均时间复杂度为O(n2)n n起泡排序算法中增加一个辅助空间temp，辅助空间为S(n)=O(1)n n起泡排序是稳定的2121设置变量设置变量i i指向参加排序的序列中第一个位置指向参加排序的序列中第一个位置0 0，变量，变量j j指向参加排序的序列中最后位置指向参加排序的序列中最后位置n-1n-1首先保存记录首先保存记录R R0 0，R0R0为空出的位置，空位在前一区为空出的位置，空位在前一区令令j j向前扫描，寻找小于向前扫描，寻找小于R R0 0的记录，找到小于的记录，找到小于R R0 0的记录的记录RjRj ，将记录，将记录RjRj 移到当前空位中，这时空位在后一区移到当前空位中，这时空位在后一区这时令这时令i i自自i+1i+1起向后扫描，寻找大于起向后扫描，寻找大于R R0 0的记录，找到的记录，找到大于大于R R0 0的记录的记录RiRi ，将记录，将记录RiRi 移到当前空位中，空位移到当前空位中，空位又到了前一区，又到了前一区，然后再令然后再令j j自自j-1j-1起向前扫描，此交替改变扫描方向，起向前扫描，此交替改变扫描方向，从两端向中间靠拢，直到从两端向中间靠拢，直到i=ji=j，这时，这时i i所指的位置为所指的位置为R R0 0的的最终位置最终位置快速排序快速排序2222 初始序列为初始序列为49, 38, 65, 97, 76, 13, 27, 4949, 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 49ij2323第二次交换后第二次交换后27 38 27 38 97 76 13 97 76 13 65 65 4949 i i j jj j向左扫描，位置不变，第三次交换后向左扫描，位置不变，第三次交换后27 27 38 38 13 13 97 97 76 76 65 65 4949 i i j ji i向右扫描，位置不变，第四次交换后向右扫描，位置不变，第四次交换后27 27 38 38 13 13 76 76 97 97 65 65 4949 i j i jj j向左扫描向左扫描27 27 38 38 13 13 49 49 76 76 97 97 65 65 4949 ij ij2424 13 27 38 49 49 65 76 9713 27 38 4949 65 76 9713 27 38 4949 65 76 97 最后的排序结果13 27 38 4949 65 76 97例（续）:2525n n当待排序记录已经有序时，算法的执行时间最长，直当待排序记录已经有序时，算法的执行时间最长，直接蜕化为起泡排序接蜕化为起泡排序n n第一趟经过第一趟经过n-1n-1次比较，将第一个记录定位在原来的位次比较，将第一个记录定位在原来的位置上，并得到一个包括置上，并得到一个包括n-1n-1个记录的子文件个记录的子文件n n第二趟经过第二趟经过n-2n-2次比较，将第二个记录定位在原来的位次比较，将第二个记录定位在原来的位置上，并得到一个包括置上，并得到一个包括n-2n-2个记录的子文件；个记录的子文件； n n这样最坏情况总比较次数为这样最坏情况总比较次数为快速排序算法评价262627u最好情况下，每次划分使两个子区的长度大致相等uC(n) n+2C(n/2) n+2n/2+2C(n/22)=2n+4c(n/22)uukn+2kC(n/2k)= nlog2n+nC(1)= O(nlog2n)u快速排序的平均时间复杂度是T(n)=O(nlog2n)，空间上需要一个栈来进行递归u快速排序是不稳定的快速排序算法评价(续)2727插入排序n n基本思想：每步将一个待排序的记录，按其排序码大小插到前面已经排序的字序列的合适位置，直到全部插入排序完为止。x 顺次选取一个元素顺次选取一个元素插入到合适位置插入到合适位置2828插入排序的细分类n n如何插入到已排好序的序列中？vv直接插入（从后向前找位置后插入）直接插入（从后向前找位置后插入） O(nO(n2 2) )vv 二分法插入（按二分法找位置后插入）二分法插入（按二分法找位置后插入） O(nlogO(nlog2 2n)n)vv 表插入排序（按链表查找位置后插入）表插入排序（按链表查找位置后插入） O(nO(n2 2) )2929直接插入排序n n基本思想：n n假定前面m 个元素已经排序；n n取第(m+1) 个元素，插入到前面的适当位置；n n一直重复，到m=n 为止。n n（初始情况下，m = 1）3030 第一趟：第一趟： 23 23， 起始只有一个记录起始只有一个记录 r0 r0 监视哨监视哨 1111, 23 , 23 11 第二趟：第二趟： 11 11，2323， 11 11，2323，5555 55 第三趟：第三趟： 11 11，2323，5555， 11 11，2323，5555，9797 97 第四趟：第四趟： 11 11，2323，5555，9797， 11 11，1919，2323，5555，97 97 19 第五趟：第五趟： 11 11，1919，2323，5555，9797， 11 11，1919，2323，5555，8080，97 97 80示例示例：23，11，55，97，19，803131监视哨的作用n n算法中引进的附加记录算法中引进的附加记录R0R0称监视哨或哨兵称监视哨或哨兵(Sentinel)(Sentinel)，哨兵，哨兵有两个作用：有两个作用： 进人查找进人查找( (插入位置插入位置) )循环之前，它保存了循环之前，它保存了RiRi的副本，的副本，使不致于因记录后移而丢失使不致于因记录后移而丢失RiRi的内容；的内容； 它的主要作用是：在查找循环中它的主要作用是：在查找循环中 监视监视 下标变量下标变量j j是否是否越界。一旦越界越界。一旦越界( (即即j=0)j=0)，因为，因为R0.keyR0.key和自己比较，循环判定和自己比较，循环判定条件不成立使得查找循环结束，从而避免了在该循环内的每一条件不成立使得查找循环结束，从而避免了在该循环内的每一次均要检测次均要检测j j是否越界是否越界( (即省略了循环判定条件即省略了循环判定条件j=1)j=1)。注意：注意： 实际上，一切为简化边界条件而引入的附加结实际上，一切为简化边界条件而引入的附加结点点( (元素元素) )均可称为哨兵。均可称为哨兵。 【例】单链表中的头结点实际上是一个哨兵【例】单链表中的头结点实际上是一个哨兵 引入哨兵后使得测试查找循环条件的时间大约引入哨兵后使得测试查找循环条件的时间大约减少了一半，所以对于记录数较大的文件节约的时间就相当可减少了一半，所以对于记录数较大的文件节约的时间就相当可观。对于类似于排序这样使用频率非常高的算法，要尽可能地观。对于类似于排序这样使用频率非常高的算法，要尽可能地减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，减少其运行时间。所以不能把上述算法中的哨兵视为雕虫小技，而应该深刻理解并掌握这种技巧。而应该深刻理解并掌握这种技巧。 3232初始数据状态相关：n n文文件件初初态态不不同同时时，直直接接插插入入排排序序所所耗耗费费的的时时间间有很大差异。有很大差异。n n若文件初态为正序，则算法的时间复杂度为若文件初态为正序，则算法的时间复杂度为O(n)O(n)n n若初态为反序，则时间复杂度为若初态为反序，则时间复杂度为O(nO(n2 2) )3333小结n n直接插入排序算法的平均移动次数与平均比较次数同级，也是O(n2)n n直接插入排序的平均时间复杂度为T(n) = O(n2)n n算法中引入了一个附加的记录空间temp，因此辅助空间为S(n) = O(1)n n直接插入排序是稳定的3434折半插入排序n n原理 由于插入排序本身就是一个查找和插入的过程，那么这由于插入排序本身就是一个查找和插入的过程，那么这个查找过程可以运用折半查找来实现，这种方法就称为折半插个查找过程可以运用折半查找来实现，这种方法就称为折半插入排序。入排序。过程过程： 折半查找折半查找 - - 记录后移记录后移 - - 插入数据插入数据 折半查找虽然减少了关键字间的比较，但是记录的移动次折半查找虽然减少了关键字间的比较，但是记录的移动次数是没有改变，因此，算法时间复杂度依然是数是没有改变，因此，算法时间复杂度依然是O(nO(n2 2) )3535表插入排序n n表插入排序是在直接插入排序的基础上减少移动的次数。n n基本思想: 先在待插入记录之前的有序子链表中查找应插入位置，然后将待插入记录插入链表。由于链表的插入操作只修改指针域，不移动记录，所以表插入排序可提高排序效率。在算法的具体实现上，我们可以采用静态链表作为存储结构。3636归并排序（merge sort）n n归并排序的基本操作是将两个或两个以上的记录有序归并排序的基本操作是将两个或两个以上的记录有序序列归并为一个有序序列。序列归并为一个有序序列。n n最简单的情况是最简单的情况是: :只含一个记录的序列显然是个有序只含一个记录的序列显然是个有序序列，经过序列，经过 逐趟归并逐趟归并 使整个序列中的有序子序列的使整个序列中的有序子序列的长度逐趟增大，直至整个记录序列为有序序列止。长度逐趟增大，直至整个记录序列为有序序列止。37373838n n具有具有n n个记录的文件排序，必须做个记录的文件排序，必须做 loglog2 2n n 趟归并，趟归并，每趟归并所花费的时间是每趟归并所花费的时间是O(n)O(n)n n二路归并排序算法的时间复杂度为二路归并排序算法的时间复杂度为T(n)=T(n)=O(nlogO(nlog2 2n)n)n n算法中增加了一个数组算法中增加了一个数组recordrecord，算法的辅助空间，算法的辅助空间为为S(n)=O(n)S(n)=O(n)n n二路归并排序是二路归并排序是稳定的稳定的算法评价3939