第五六章作业讲解.pptVIP

P95 5-2 求转置矩阵（方法一） TRANSPOSE(A.B) TP1[初始化] n←Rows(B)←Cols(A). Cols (B)←Rows(A). t←Count(B)← Count(A). FOR I=0 TO n-1 DO S[I]←0. FOR I=0 TO t-1 DO （ J ←col(A[I]). FOR K=J+1 TO n-1 DO S[K]←S[K]+1. ） 求转置矩阵（方法一） TP2[处理三元组表] FOR I=0 TO t-1 DO ( J←col(A[I]). K←S[J]. col( B[K]) ← row(A[I]). row(B[K]) ←J. val(B[K]) ← val(A[I]). S[J]← S[J]+1 ). 求转置矩阵（方法二） TRANSPOSE(A.B) TP1[初始化] n←Rows(B)←Cols(A). Cols (B)←Rows(A). t←Count(B)← Count(A). FOR I=0 TO n-1 DO ( S[I]←0. R[I] ←0）. FOR I=0 TO t-1 DO （ J ←col(A[I]). S[J] ← S[J] +1.） FOR I=1 TO n-1 DO （ R[I]←R[I-1]+S[I-1]. ） 求转置矩阵（方法二） TP2[处理三元组表] FOR I=0 TO t-1 DO ( J←col(A[I]). K←R[J]. col( B[K]) ← row(A[I]). row(B[K]) ←J. val(B[K]) ← val(A[I]). R[J]← R[J]+1 ). 6-7 判断以下命题是否为真？若真，请证明之；否则，举出反例。一棵二叉树形的所有的叶结点，在先根次序、中根次序和后根次序下的排列都按相同的相对位置出现。 先根： ABCEIFJDGHKL 中根： EICFJBGDKHLA 后根： IEJFCGKLHDBA 6-7 数学归纳法 令n等于二叉树的高度； n=0时，命题成立； 假设n=k时命题成立，n=k+1时，任意两个叶结点l1,l2： l1，l2都在根左（右）子树当中。 l1，l2不在根的同一个子树当中。 证明: 设v1,v2,…,vk,表示所有叶节点的序列，且满足如下条件： 对任意的vi,vj,如果ij,则存在vi，vj的最小祖先节点x，使得vi，vj分别在x的左、右子树中。 由先、中、后根遍历定义可知，对于这三种遍历，vi总先于vj被访问。 因此，对先、中、后根遍历，叶节点被访问的先后次序都为v1,v2,…,vk. 6-13 后根遍历树——非递归算法 templateclass T void TreeT :: NorecPostOrder（） { Stack TreeNodeT * s ; TreeNodeT *p = current ; do { while（!IsEmpty（）） { s.Push（current）; FirstChild（）; } while（IsEmpty（） ! s.StackEmpty（）） { current = s.Pop（）; visit（）; NextBrother（）; } } while（! s. StackEmpty（）） current = p ; } 6-13 后根遍历树——递归算法 templateclass T void TreeT :: PostOrder（） { if（! IsEmpty（）） { TreeNodeT *p = current ; // 保存当前结点 int k = FirstChild（）; while（k）// 后根遍历当前结点的诸子树 { PostOrder（）; k = NextBrother（）;