南京大学数据结构期终复习.ppt

D.S.复习提纲 ;例1. 求n!;例2 computes the sum of the elements a[0] through a[n-1]  a[0], a[1], …, a[n-2], a[n-1] ;例3. 求数组中的最大值;例3. 求数组中的最大值;例4?. 求数组元素的平均值;例5. 统计叶子结点个数;例6. 交换左右子数;第2章 算法分析;第2章 算法分析; 第3章 表、栈和队列;第3章 表;第3章; 栈、队列; 对后缀表达式求值： 用了什么栈 例2. 队列---循环队列的补充题 已知队尾元素的位置与元素的个数， 求队头元素的位置。  先用实例来分析，然后归结到一般情况。;特殊矩阵的压缩存储 ;1D-Array;2D-Array;2D-Array;2D-Array;2D-Array;Matrix ;Matrix;Special Matrix;Special Matrix;Special Matrix;Special Matrix;Special Matrix;Sparse Matrices;Sparse Matrices;Sparse Matrices;Sparse Matrices; Sparse Matrices;;习题： 设有一个n*n的对称矩阵A，如下图(a)所示。为了节约存储，可以只存对角线及对角线以上的元素，或者只存对角线或对角线以下的元素。前者称为上三角矩阵，后者称为下三角矩阵。我们把它们按行存放于一个一维数组B中，如图(b)和图(c)所示。并称之为对称矩阵A的压缩存储方式。试问： 1）存放对称矩阵A上三角部分或下三角部分的一维数组B有多少元素？ 2）若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存上三角部分的情形下(图(b))应存于一维数组的什么下标位置？给出计算公式。 3）若在一维数组B中从0号位置开始存放，则如图(a)所示的对称矩阵中的任一元素aij在只存下三角部分的情况下*(图(c))应存于一维数组的什么下标位置？给出计算公式。 a11 a12 …a1n a11 a12 …a1n a11 a21 a22 …a2n a22 …a2n a21 a22 ……….. ………. ……… an1 an1 …ann ann an1 an2 … ann (a) (b) (c);答案： 1) 1+2+3+…+n = ?*(1+n)*n 2) loc(A[i,j] ) = loc(B[0]) + ( n+n-1+….+n-i+2 + j-i ) t = ?*(2*n-i+2)*(i-1) + j-i i=j t = ?*(2*n-j+2)*(j-1) + i-j ij 3) loc(A[i,j] = loc(B[0]) + (1+2+3+….+i-1+j-1) t = ?*i*(i-1) + j-1 i=j t = ?*j*(j-1) + i-1 ij ;第4章 树;例1. 第4章中用非递归实现中序,后序遍历 Inorder, Postorder non-recursive algorithm Inorder non-recursive algorithm ;templateclass T void InOrder(BinaryNodeT* t) { if(t){ InOrder(t?Left);