作业解(第三、四、五、六章).ppt

1、习题讲解(第三、四、五、六章),3-10设稀疏矩阵Mm*n中有t个非零元素，用三元组表的方式存储. 请设计一个算法，计算矩阵M的转置矩阵N ，且算法的时间复杂性为O(n+t). 注意，书中给出的算法的复杂性为O(n*t).,算法的关键是求出A中元素在B中的位置,3-10,算法TRANSPOSE(A. B) TP1初始化/*声明A的转置矩阵B，使得B的行数等于A的列数，B的列数等于A的行数，B中非0元素的个数等于A中非0元素的个数*/nRows(B)Cols(A). Cols (B)Rows(A).tCount(B) Count(A).,TP2计算存储位置 /定义数组num存储A中每列非零元素个

2、数 FOR i=0 TO n-1 DO numi0. FOR i=0 TO t-1 DO （ j col(Ai). numjnumj+1. ） /数组pos存储A中每列第一个非零元素在B中的位置 pos0 0 . FOR i=1 TO n-1 DO (posi posi-1+numi-1 . ),TP3处理三元组表 FOR i=0 TO t-1 DO ( pcol(Ai). kposp. col( Bk) row(Ai). row(Bk) col(Ai). val(Bk) val(Ai). posp posp+1.) ,4-2,由三个结点A，B和C可以构成多少棵不同的树？可以构成多少棵不同的二

3、叉树？,4-2,树有2种形态：6+3=9种 二叉树有5种形态：6*5=30种,4-3,判断以下命题是否为真？若真，请证明之；否则，举出反例。一棵二叉树形的所有的叶结点，在先根次序、中根次序和后根次序下的排列都按相同的相对位置出现。,先根： A B C E I F J D G H K L中根： E I C F J B G D K H L A后根： I E J F C G K L H D B A,数学归纳法,令n等于二叉树的高度； n=1时； 假设n=k时命题成立，n=k+1时，任意两个叶结点l1,l2： l1，l2都在根左（右）子树当中。 l1，l2不在根的同一个子树当中。,4-5,编写一算法，

4、判别给定二叉树是否为完全二叉树。,根据完全二叉树的定义可知，对完全二叉树层次遍历应满足： 1）若某结点没有左孩子，则一定无右孩子； 2）若某结点有左孩子，但无右孩子，则其层次序列所有后继结点一定是叶结点。 3）叶结点的层次序列的所有后继结点一定是叶结点。 为此，在层次遍历二叉树时，增加一个标志B，B=1表示所有已扫描过的结点均有左、右孩子，B=0，表示遇到无左或右孩子的结点，此后的所有结点均应为叶结点。,bool completetree(BintreeNode * t) Queue Q; Bool B=1, CM=1; if (t!=NULL) Q.Insert(t); while (!Q.

5、QueueEmpty() ,4-10,对以左儿子右兄弟链接表示的树，编写计算树的深度的算法。,4-10,解题思路1 树的深度dept(t)=max(t的各子树的深度)+1 解题思路2 基于所对应的二叉树求树的深度 解题思路3 对树做层次遍历，求树的深度,解题思路1 树的深度dept(t)=max(t的各子树的深度)+1 算法 Depth(t. d) D1递归出口 IF t=NULL THEN ( d -1 . RETURN ) IF (GFC(t)=NULL) THEN ( d 0 . RETURN ) D2递归调用 p=GFC(t). Max -1. / Max存储各子树的最大深度 WHIL

6、E (pNULL) ( Depth(p. dp). IF (dpMax) THEN Maxdp. pGNB(p). ). d Max+1 . RETURN. ) ,解题思路2 基于所对应的二叉树： dept(t)=max（左子树的深度+1，右子树的深度）,算法 Depth(t. d) D1递归出口 IF t=NULL THEN ( d -1 . RETURN ) D2递归调用 Depth(GFC(t). d1) Depth(GNB(t). d2) Max(d1+1, d2). RETURN. ) ,解题思路3 对树做层次遍历，每遍历一层树的深度+1. 关键在于如何判断本层遍历的结束。 解决方法

7、：可将队列中的结点结构变为(结点，该结点的层数i) 。,算法Depth(t. d) /t指向与树自然对应的二叉树的根 D1 判断t是否为NULL IF t=NULL THEN ( d -1 . RETURN ) D2 创建辅助队列, 根结点入队 CREATE(Q). Q ( t, 0) . d0. D3 利用队列Q遍历第d层结点 WHILE NOT (IsEmpty(Q) DO ( (p, d) Q . WHILE pNULL DO ( IF FirstChild(p)NULL THEN Q(FirstChild(p),d+1) pNextBrother(p) .) ) ,树的层次遍历,4-1

8、2,请构造权值为 5,13,21, 7,18,30,41的哈夫曼树。,4-12,首先，在森林中取权值最小的两个根结点s和n，合成一棵二叉树，新生成的结点T1，作为这两个结点的父结点，T1的权值是两个子结点的权值之和； 对新的森林重复上一步操作，直至森林中只有唯一的根结点时，终止操作。, 5，13，21，7，18，30，41 ,5-7,用邻接矩阵存储一个包含1000个顶点和1000条边的图，则该图的邻接矩阵中有多少元素？有多少非零元素？该矩阵是否为稀疏矩阵？,）矩阵中元素个数：1000000 ）若图为有向图： 非零元素的个数：1000 若图为无向图： 非零元素的个数：2000 ）该矩阵是稀疏矩阵

9、,5-7,5-12,设计一个算法，检测采用邻接表方法存储、具有n个顶点的有向图中是否存在从顶点v到顶点u的路径，若存在路径，算法给出信息TRUE，否则，给出信息FALSE .,算法Pathornot (Head, v, visited. visited) BFS1. 初始化 CREATQ(Q). / 创建队列 Q FOR i = 1 TO n DO visitedi 0. PRINT(v) . visitedv 1. Q v. BFS2. 广度优先遍历 WHILE Q 非空 DO ( v Q. padjacent(Headv) . WHILE p DO ( IF visitedVerAdj(p

10、) = 0 THEN IF (VerAdj(p)=u) THEN RETURN TRUE ELSE ( QVerAdj(p). PRINT(VerAdj(p) . visitedVerAdj(p)1.). p link(p). ) ) RETURN FALSE.,5-13,设G（V,E）是有向图，请给出算法，判 断G中是否有回路，并要求算法的复杂性为 O（n+e）。 书中P146，拓扑排序算法： void Graph : TopoOrder( ) Stack S; for ( int i=0 ; in ; i + + ) if ( counti = = 0 ) S.push(i) ; ,for

11、 ( int i=0 ; iVerAdj ; if ( -countk= = 0 ) S.push(i); p=p-link ;,5-13,设G（V,E）是有向图，请给出算法，判 断G中是否有回路，并要求算法的复杂性为 O（n+e）。 书中P146，拓扑排序算法： void Graph : TopoOrder( ) int top = - 1 ; for ( int i=0 ; in ; i + + ) if ( counti = = 0 ) counti = top ; top = i ; ,for ( int i=0 ; iVerAdj ; if ( -countk= = 0 ) countk=top ; top=k ; p=p-link ;,5-14,20,5-14,20,最短路径 最短路径长度 23 10 24 15