第五六章作业讲解.ppt

1、数据结构习题讲解,TRANSPOSE(A.B) TP1初始化 nRows(B)Cols(A). Cols (B)Rows(A). tCount(B) Count(A). FOR I=0 TO n-1 DO SI0. FOR I=0 TO t-1 DO （ J col(AI). FOR K=J+1 TO n-1 DO SKSK+1. ）,P95 5-2 求转置矩阵（方法一）,TP2处理三元组表 FOR I=0 TO t-1 DO ( Jcol(AI). KSJ. col( BK) row(AI). row(BK) J. val(BK) val(AI). SJ SJ+1 ).,求转置矩阵（方法一）

2、,TRANSPOSE(A.B) TP1初始化 nRows(B)Cols(A). Cols (B)Rows(A). tCount(B) Count(A). FOR I=0 TO n-1 DO ( SI0. RI 0）. FOR I=0 TO t-1 DO （ J col(AI). SJ SJ +1.） FOR I=1 TO n-1 DO （ RIRI-1+SI-1. ）,求转置矩阵（方法二）,TP2处理三元组表 FOR I=0 TO t-1 DO ( Jcol(AI). KRJ. col( BK) row(AI). row(BK) J. val(BK) val(AI). RJ RJ+1 ).,求

3、转置矩阵（方法二）,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的最小祖

4、先节点x，使得vi，vj分别在x的左、右子树中。 由先、中、后根遍历定义可知，对于这三种遍历，vi总先于vj被访问。 因此，对先、中、后根遍历，叶节点被访问的先后次序都为v1,v2,vk.,6-13 后根遍历树非递归算法,template void Tree : NorecPostOrder（） Stack * s ; TreeNode *p = current ; do while（!IsEmpty（） s.Push（current）; FirstChild（）; while（IsEmpty（） ,6-13 后根遍历树递归算法,template void Tree : PostOrder（）

5、 if（! IsEmpty（） TreeNode *p = current ; / 保存当前结点 int k = FirstChild（）; while（k）/ 后根遍历当前结点的诸子树 PostOrder（）; k = NextBrother（）; current = p ; / 恢复当前指针 visit（）; / 访问当前结点 ,构造权值为5,13,21,7,18,30,41的哈夫曼树。,6-16 构造哈夫曼树,6-10 插入最右子结点,成员函数InsertChild(T value)执行的操作是：插入一个数据值为value的结点，作为当前结点的最右边的子结点。,6-10 插入最右子结点,

6、template int Tree : InsertChild（T value） if（current = = NULL） return 0; if（currentfirstChild = NULL） currentfirstChild=new TreeNode(value,NULL,NULL);return 1 ; else TreeNode *temp= currentfirstChild; while(tempnextBrother!=NULL) temp= tempnextBrother; tempnextBrother=new TreeNode(value,NULL,NULL);return 1 ; ,6-11 删除子结点,成员函数DeleteChild(int i)执行的操作是：删除当前结点的第i个子结点及其所有子树。,6-11 删除子结点,template int Tree : DeleteChild（int i） if（i *temp= currentfirstChild,*pred; if(i= =1) pred=current; currentfi