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

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,习题讲解,(,第三、四、五、六章,),3-10,设稀疏矩阵,M,m,*,n,中有,t,个非零元素，用三元组表的方式存储,.,请设计一个算法，计算矩阵,M,的转置矩阵,N,，且算法的时间复杂性为,O(,n,+,t,).,注意，书中给出的算法的复杂性为,O(,n,*,t,).,A=,50 0 0 0,10 0 20 0,0 0 0 0,-30 0 -60 5,A,=,50 10 0 -30,0 0 0 0,0 20 0 -60,0 0 0 5,0,0,50,A,0,1,0,10,A,1,1,2,20,A2,3,0,-30,A3,3,2,-60,A4,3,3,5,A5,0,0,50,B0,0,1,10,B1,0,3,-30,B2,2,1,20,B3,2,3,-60,B4,3,3,5,B5,算法的关键是求出,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,中每列非零元素个数,FOR i=0 TO,n,-1 DO,num,i,0,.,FOR i=0 TO t-1 DO,（,j,col(A,i,).,num,j,num,j,+1.,）,/,数组,pos,存储,A,中每列第一个非零元素在,B,中的位置,pos0,0,.,FOR i=1 TO n-1 DO,(posi,pos,i-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,可以构成多少棵不同的树？可以构成多少棵不同的二叉树？,4-2,树有,2,种形态：,6+3=9,种,二叉树有,5,种形态：,6*5=30,种,4-3,判断以下命题是否为真？若真，请证明之；否则，举出反例。,一棵二叉树形的所有的叶结点，在先根次序、中根次序和后根次序下的排列都按相同的相对位置出现。,G,F,E,D,C,B,A,L,K,J,I,H,先根：,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,时，任意两个叶结点,l,1,l,2,：,l,1,，,l,2,都在根左（右）子树当中。,l,1,，,l,2,不在根的同一个子树当中。,4-5,编写一算法，判别给定二叉树是否为完全二叉树。,根据完全二叉树的定义可知，对完全二叉树层次遍历应满足：,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.QueueEmpty()&B)/,层次遍历,p=Q.Delete();,if(,p-left=NULL,),B=0;if (p-right!=NULL)return false;,else Q.Insert(p-left);,if (,p-right=NULL,)B=0;,else Q.Insert(p-right);,while(!Q.QueueEmpty(),p=Q.Delete();,if(,p-left!=NULL,),|(,p-right!=NULL,),return false;,;return true;,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,存储各子树的最大深度,WHILE(pNULL),(Depth(p.dp).,IF(dpMax)THEN Maxdp.,pGNB(p).).,d Max+1.RETURN.,),解题思路,2,基于所对应的二叉树：,dept(t)=max,（左子树的深度,+1,，右子树的深度）,A,C,B,G,D,F,E,A,C,B,G,D,F,E,算法,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.,关键在于如何判断本层遍历的结束。,解决方法：可将队列中的结点结构变为,(,结点，该结点的,层数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),.,),树的层次遍历,A,C,B,G,D,F,E,4-12,请构造权值为,5,13,21,7,18,30,41,的哈夫曼树。,4-12,首先，在森林中取权值最小的两个根结点,s,和,n,，合成一棵二叉树，新生成的结点,T1,，作为这两个结点的父结点，,T1,的权值是两个子结点的权值之和；,对新的森林重复上一步操作，直至森林中只有唯一的根结点时，终止操作。,5,，,13,，,21,，,7,，,18,，,30,，,41,25,80,55,135,12,41,39,30,5,13,7,18,21,5-7,用邻接矩阵存储一个包含,1000,个顶点和,1000,条边的图，则该图的邻接矩阵中有多少元素？有多少非零元素？该矩阵是否为稀疏矩阵？,）矩阵中元素个数：,1000000,）若图为有向图：,非零元素的个数：,1000,若图为无向图：,非零元素的个数：,2000,）该矩阵是稀疏矩阵,5-7,5-12,设计一个算法，检测采用邻接表方法存储、具有,n,个顶点的有向图中是否存在从顶点,v,到顶点,u,的路径，若存在路径，算法给出信息,TRUE,，否则，给出信息,FALSE.,算法,Pathornot,(,Head,v,visited.visited,),BFS1.,初始化,CREATQ(,Q,)./,创建队列,Q,FOR,i,=1 TO,n,DO,visited,i,0.,PRINT(,v,).,visited,v,1.,Q,v,.,BFS2.,广度优先遍历,WHILE,Q,非空,DO,(,v,Q,.,p,adjacent,(,Head,v,).,WHILE,p,DO,(,IF,visited,VerAdj,(,p,)=0 THEN,IF(,VerAdj,(,p,)=u)THEN RETURN TRUE,ELSE,(,Q,VerAdj,(,p,).,PRINT(,VerAdj,(,p,),.,visited,VerAdj,(,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(int i=0;in;i+),if(S.StackEmpty),/,检测图中是否有回路,cout There is a cycle in network!endl;return;,else,int,j=,S.pop();,coutjVerAdj;,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;in;i+),if(,top=-1,),/,检测图中是否有回路,cout There is a cycle in network!endl;return;,else,int,j=top;top=counttop,;,coutjVerAdj;,if(-countk=0),countk=top;top=k,;,p=p-link;,5-14,20,1,2,3,4,5,6,50,10,10,3,15,15,20,35,30,S,2,1,3,4,5,6,2,10,15,2 3,10,15,40,2 3 4,35,10,15,30,2 3 4 5,35,10,15,30,2 3 4 5 1,35,10,15,30,1 4 5 2 3 6,35,10,15,30,5-14,20,1,2,3,4,5,6,50,10,10,3,15,15,20,35,30,最短路径 最短路径长度,23 10,24 15,245 30,241 35,26,5-15,5-16 prim,算法,1,2,16,1,2,16,3,5,1,2,16,3,5,4,6,1,2,16,3,5,4,6,6,11,1,2,16,3,5,4,6,6,11,5,18,5-16 Kruskar,算法,3,5,1,2,4,6,5,5,1,2,3,4,6,5,6,5,1,2,3,4,6,5,6,11,5,1,2,3,4,6,5,6,11,16,5,1,2,3,4,6,5,6,11,16,18,1,若某线性表中最常用的操作是取第,i,个元素和删除最后一个元素，则采用（）存储方式最节省时间。,A.,顺序表,B.,单链表,C.,双链表,D.,单循环链表,A.,顺序表,A,D,2,中缀表达式,A-(B+C/D)*E,的后缀形式是,(),。,A.AB-C+D/E*,B.ABC+D/-E*,D.ABCD/+E*-,C.ABCD/E*+-,D.ABCD/+E*-,