数据结构题集答案第章图.docx

《数据结构题集答案第章图.docx》由会员分享，可在线阅读，更多相关《数据结构题集答案第章图.docx（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第七章 图 7.14 Status Build_AdjList(ALGraph &G)/输入有向图的顶点数,边数,顶点信息与边的信息建立邻接表InitALGraph(G);scanf(%d,&v);if(v0) return ERROR; /顶点数不能为负G.vexnum=v;scanf(%d,&a);if(a0) return ERROR; /边数不能为负G.arcnum=a;for(m=0;mv;m+)G.verticesm.data=getchar(); /输入各顶点的符号for(m=1;m=a;m+)t=getchar();h=getchar(); /t为弧尾,h为弧头if(i=Loc

2、ateVex(G,t)0) return ERROR;if(j=LocateVex(G,h)nextarc;q=q-nextarc);q-nextarc=p;p-adjvex=j;p-nextarc=NULL;/whilereturn OK;/Build_AdjList 7.15 /本题中的图G均为有向无权图,其余状况简洁由此写出Status Insert_Vex(MGraph &G, char v)/在邻接矩阵表示的图G上插入顶点vif(G.vexnum+1)MAX_VERTEX_NUM return INFEASIBLE;G.vexs+G.vexnum=v;return OK;/Inser

3、t_Vex Status Insert_Arc(MGraph &G,char v,char w)/在邻接矩阵表示的图G上插入边(v,w)if(i=LocateVex(G,v)0) return ERROR;if(j=LocateVex(G,w)0) return ERROR;if(i=j) return ERROR;if(!G.arcsij.adj)G.arcsij.adj=1;G.arcnum+;return OK;/Insert_Arc Status Delete_Vex(MGraph &G,char v)/在邻接矩阵表示的图G上删除顶点vn=G.vexnum;if(m=LocateVex

4、(G,v)0) return ERROR;G.vexsmG.vexsn; /将待删除顶点交换到最终一个顶点for(i=0;in;i+)G.arcsim=G.arcsin;G.arcsmi=G.arcsni; /将边的关系随之交换G.arcsmm.adj=0;G.vexnum-;return OK;/Delete_Vex分析:假如不把待删除顶点交换到最终一个顶点的话,算法将会比较困难,而伴随着大量元素的移动,时间困难度也会大大增加. Status Delete_Arc(MGraph &G,char v,char w)/在邻接矩阵表示的图G上删除边(v,w)if(i=LocateVex(G,v)0

5、) return ERROR;if(j=LocateVex(G,w)0) return ERROR;if(G.arcsij.adj)G.arcsij.adj=0;G.arcnum-;return OK;/Delete_Arc 7.16 /为节约篇幅,本题只给出Insert_Arc算法.其余算法请自行写出. Status Insert_Arc(ALGraph &G,char v,char w)/在邻接表表示的图G上插入边(v,w)if(i=LocateVex(G,v)0) return ERROR;if(j=LocateVex(G,w)adjvex=j;p-nextarc=NULL;if(!G.

6、verticesi.firstarc) G.verticesi.firstarc=p;elsefor(q=G.verticesi.firstarc;q-q-nextarc;q=q-nextarc)if(q-adjvex=j) return ERROR; /边已经存在q-nextarc=p;G.arcnum+;return OK;/Insert_Arc 7.17 /为节约篇幅,本题只给出较为困难的Delete_Vex算法.其余算法请自行写出. Status Delete_Vex(OLGraph &G,char v)/在十字链表表示的图G上删除顶点vif(m=LocateVex(G,v)0) re

7、turn ERROR;n=G.vexnum;for(i=0;itailvex=m) /假如待删除的边是头链上的第一个结点q=G.xlisti.firstin;G.xlisti.firstin=q-hlink;free(q);G.arcnum-;else /否则for(p=G.xlisti.firstin;p&p-hlink-tailvex!=m;p=p-hlink);if(p)q=p-hlink;p-hlink=q-hlink;free(q);G.arcnum-;/else/forfor(i=0;iheadvex=m) /假如待删除的边是尾链上的第一个结点q=G.xlisti.firstout

8、;G.xlisti.firstout=q-tlink;free(q);G.arcnum-;else /否则for(p=G.xlisti.firstout;p&p-tlink-headvex!=m;p=p-tlink);if(p)q=p-tlink;p-tlink=q-tlink;free(q);G.arcnum-;/else/forfor(i=m;ihlink)p-headvex-;for(p=G.xlisti.firstout;p;p=p-tlink)p-tailvex-; /修改各链中的顶点序号G.vexnum-;return OK;/Delete_Vex 7.18 /为节约篇幅,本题只给

9、出Delete_Arc算法.其余算法请自行写出. Status Delete_Arc(AMLGraph &G,char v,char w)/在邻接多重表表示的图G上删除边(v,w)if(i=LocateVex(G,v)0) return ERROR;if(j=LocateVex(G,w)jvex=j)G.adjmulisti.firstedge=G.adjmulisti.firstedge-ilink;elsefor(p=G.adjmulisti.firstedge;p&p-ilink-jvex!=j;p=p-ilink);if (!p) return ERROR; /未找到p-ilink=p

10、-ilink-ilink; /在i链表中删除该边if(G.adjmulistj.firstedge-ivex=i)G.adjmulistj.firstedge=G.adjmulistj.firstedge-jlink;elsefor(p=G.adjmulistj.firstedge;p&p-jlink-ivex!=i;p=p-jlink);if (!p) return ERROR; /未找到q=p-jlink;p-jlink=q-jlink;free(q); /在i链表中删除该边G.arcnum-;return OK;/Delete_Arc 7.19 Status Build_AdjMulis

11、t(AMLGraph &G)/输入有向图的顶点数,边数,顶点信息与边的信息建立邻接多重表InitAMLGraph(G);scanf(%d,&v);if(v0) return ERROR; /顶点数不能为负G.vexnum=v;scanf(%d,&a);if(a0) return ERROR; /边数不能为负G.arcnum=a;for(m=0;mv;m+)G.adjmulistm.data=getchar(); /输入各顶点的符号for(m=1;m=a;m+)t=getchar();h=getchar(); /t为弧尾,h为弧头if(i=LocateVex(G,t)0) return ERRO

12、R;if(j=LocateVex(G,h)ivex=i;p-jvex=j;p-ilink=NULL;p-jlink=NULL; /边结点赋初值if(!G.adjmulisti.firstedge) G.adjmulisti.firstedge=p;elseq=G.adjmulisti.firstedge;while(q)r=q;if(q-ivex=i) q=q-ilink;else q=q-jlink;if(r-ivex=i) r-ilink=p;/留意i值既可能出现在边结点的ivex域中,else r-jlink=p; /又可能出现在边结点的jvex域中/else /插入i链表尾部if(!G

13、.adjmulistj.firstedge) G.adjmulistj.firstedge=p;elseq=G.adjmulisti.firstedge;while(q)r=q;if(q-jvex=j) q=q-jlink;else q=q-ilnk;if(r-jvex=j) r-jlink=p;else r-ilink=p;/else /插入j链表尾部/forreturn OK;/Build_AdjList 7.20 int Pass_MGraph(MGraph G)/推断一个邻接矩阵存储的有向图是不是可传递的,是则返回1,否则返回0for(x=0;xG.vexnum;x+)for(y=0;

14、yG.vexnum;y+)if(G.arcsxy)for(z=0;zG.vexnum;z+)if(z!=x&G.arcsyz&!G.arcsxz) return 0;/图不行传递的条件/ifreturn 1;/Pass_MGraph分析:本算法的时间困难度也许是O(n2*d). 7.21 int Pass_ALGraph(ALGraph G)/推断一个邻接表存储的有向图是不是可传递的,是则返回1,否则返回0for(x=0;xnextarc)y=p-adjvex;for(q=G.verticesy.firstarc;q;q=q-nextarc)z=q-adjvex;if(z!=x&!is_adj

15、(G,x,z) return 0;/for/for/Pass_ALGraph int is_adj(ALGraph G,int m,int n)/推断有向图G中是否存在边(m,n),是则返回1,否则返回0for(p=G.verticesm.firstarc;p;p=p-nextarc)if(p-adjvex=n) return 1;return 0;/is_adj 7.22 int visitedMAXSIZE; /指示顶点是否在当前路径上 int exist_path_DFS(ALGraph G,int i,int j)/深度优先推断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0

16、if(i=j) return 1; /i就是jelsevisitedi=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(!visitedk&exist_path(k,j) return 1;/i下游的顶点到j有路径/for/else/exist_path_DFS 7.23 int exist_path_BFS(ALGraph G,int i,int j)/广度优先推断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0int visitedMAXSIZE;InitQueue(Q);EnQueue(Q,i);while(!Q

17、ueueEmpty(Q)DeQueue(Q,u);visitedu=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)k=p-adjvex;if(k=j) return 1;if(!visitedk) EnQueue(Q,k);/for/whilereturn 0;/exist_path_BFS 7.24 void STraverse_Nonrecursive(Graph G)/非递归遍历强连通图Gint visitedMAXSIZE;InitStack(S);Push(S,GetVex(S,1); /将第一个顶点入栈visit(1);visited=1;w

18、hile(!StackEmpty(S)while(Gettop(S,i)&i)j=FirstAdjVex(G,i);if(j&!visitedj)visit(j);visitedj=1;Push(S,j); /向左走到终点/whileif(!StackEmpty(S)Pop(S,j);Gettop(S,i);k=NextAdjVex(G,i,j); /向右走一步if(k&!visitedk)visit(k);visitedk=1;Push(S,k);/if/while/Straverse_Nonrecursive分析:本算法的基本思想与二叉树的先序遍历非递归算法相同,请参考6.37.由于是强连

19、通图,所以从第一个结点动身肯定能够访问到全部结点. 7.25 见书后解答. 7.26 Status TopoNo(ALGraph G)/依据题目要求依次重排有向图中的顶点int newMAXSIZE,indegreeMAXSIZE; /储存结点的新序号n=G.vexnum;FindInDegree(G,indegree);InitStack(S);for(i=1;inextarc)k=p-adjvex;if(!(-indegreek) Push(S,k);/for/whileif(countG.vexnum) return ERROR; /图中存在环for(i=1;i0)visitedi=1;

20、for(p=G.verticesi.firstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl)if(exist_path_len(G,l,j,k-1) return 1; /剩余路径长度减一/forvisitedi=0; /本题允许曾经被访问过的结点出现在另一条路径中/elsereturn 0; /没找到/exist_path_len 7.28 int pathMAXSIZE,visitedMAXSIZE; /暂存遍历过程中的路径 int Find_All_Path(ALGraph G,int u,int v,int k)/求有向图G中顶点u到v之间的全部简

21、洁路径,k表示当前路径长度pathk=u; /加入当前路径中visitedu=1;if(u=v) /找到了一条简洁路径printf(Found one path!n);for(i=0;pathi;i+) printf(%d,pathi); /打印输出elsefor(p=G.verticesu.firstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl) Find_All_Path(G,l,v,k+1); /接着找寻visitedu=0;pathk=0; /回溯/Find_All_Path main().Find_All_Path(G,u,v,0); /在主函数

22、中初次调用,k值应为0./main 7.29 int GetPathNum_Len(ALGraph G,int i,int j,int len)/求邻接表方式存储的有向图G的顶点i到j之间长度为len的简洁路径条数if(i=j&len=0) return 1; /找到了一条路径,且长度符合要求else if(len0)sum=0; /sum表示通过本结点的路径数visitedi=1;for(p=G.verticesi.firstarc;p;p=p-nextarc)l=p-adjvex;if(!visitedl)sum+=GetPathNum_Len(G,l,j,len-1)/剩余路径长度减一/

23、forvisitedi=0; /本题允许曾经被访问过的结点出现在另一条路径中/elsereturn sum;/GetPathNum_Len 7.30 int visitedMAXSIZE;int pathMAXSIZE; /暂存当前路径int cyclesMAXSIZEMAXSIZE; /储存发觉的回路所包含的结点int thiscycleMAXSIZE; /储存当前发觉的一个回路int cycount=0; /已发觉的回路个数 void GetAllCycle(ALGraph G)/求有向图中全部的简洁回路for(v=0;vG.vexnum;v+) visitedv=0;for(v=0;vn

24、extarc)w=p-adjvex;if(!visitedw) DFS(G,w,k+1);else /发觉了一条回路for(i=0;pathi!=w;i+); /找到回路的起点for(j=0;pathi+j;i+) thiscyclej=pathi+j;/把回路复制下来if(!exist_cycle() cyclescycount+=thiscycle;/假如该回路尚未被记录过,就添加到记录中for(i=0;iG.vexnum;i+) thiscyclei=0; /清空目前回路数组/else/forpathk=0;visitedk=0; /留意只有当前路径上的结点visited为真.因此一旦遍

25、历中发觉当前结点visited为真,即表示发觉了一条回路/DFS int exist_cycle()/推断thiscycle数组中记录的回路在cycles的记录中是否已经存在int tempMAXSIZE;for(i=0;icycount;i+) /推断已有的回路与thiscycle是否相同 /也就是,全部结点与它们的依次都相同j=0;c=thiscycle� /例如,142857与857142是相同的回路for(k=0;cyclesik!=c&cyclesik!=0;k+);/在cycles的一个行向量中找寻等于thiscycle第一个结点的元素if(cyclesik) /有与之相同的

26、一个元素for(m=0;cyclesik+m;m+)tempm=cyclesik+m;for(n=0;nk;n+,m+)tempm=cyclesin; /调整cycles中的当前记录的循环相位并放入temp数组中if(!StrCompare(temp,thiscycle) /与thiscycle比较return 1; /完全相等for(m=0;mG.vexnum;m+) tempm=0; /清空这个数组/forreturn 0; /全部现存回路都不与thiscycle完全相等/exist_cycle分析:这个算法的思想是,在遍历中暂存当前路径,当遇到一个结点已经在路径之中时就表明存在一条回路;

27、扫描路径向量path可以获得这条回路上的全部结点.把结点序列(例如,142857)存入thiscycle中;由于这种算法中,一条回路会被发觉好几次,所以必需先推断该回路是否已经在cycles中被记录过,假如没有才能存入cycles的一个行向量中.把cycles的每一个行向量取出来与之比较.由于一条回路可能有多种存储依次,比如142857等同于285714与571428,所以还要调整行向量的次序,并存入temp数组,例如,thiscycle为142857第一个结点为1,cycles的当前向量为857142,则找到后者中的1,把1后部分提到1前部分前面,最终在temp中得到142857,与this

28、cycle比较,发觉相同,因此142857与857142是同一条回路,不予存储.这个算法太困难,很难保证细微环节的精确性,大家理解思路便可.盼望有人给出更加简捷的算法. 7.31 int visitedMAXSIZE;int finishedMAXSIZE;int count; /count在第一次深度优先遍历中用于指示finished数组的填充位置 void Get_SGraph(OLGraph G)/求十字链表结构储存的有向图G的强连通重量count=0;for(v=0;vG.vexnum;v+) visitedv=0;for(v=0;vG.vexnum;v+) /第一次深度优先遍历建立f

29、inished数组if(!visitedv) DFS1(G,v);for(v=0;v=0;i-) /第二次逆向的深度优先遍历v=finished(i);if(!visitedv)printf(n); /不同的强连通重量在不同的行输出DFS2(G,v);/for/Get_SGraph void DFS1(OLGraph G,int v)/第一次深度优先遍历的算法visitedv=1;for(p=G.xlistv.firstout;p;p=p-tlink)w=p-headvex;if(!visitedw) DFS1(G,w);/forfinished+count=v; /在第一次遍历中建立fini

30、shed数组/DFS1 void DFS2(OLGraph G,int v)/第二次逆向的深度优先遍历的算法visitedv=1;printf(%d,v); /在第二次遍历中输出结点序号for(p=G.xlistv.firstin;p;p=p-hlink)w=p-tailvex;if(!visitedw) DFS2(G,w);/for/DFS2分析:求有向图的强连通重量的算法的时间困难度与深度优先遍历相同,也为O(n+e). 7.32 void Forest_Prim(ALGraph G,int k,CSTree &T)/从顶点k动身,构造邻接表结构的有向图G的最小生成森林T,用孩子兄弟链表存

31、储for(j=0;jnextarc)if(p-adjvex=k) closedgej.lowcost=p-cost;/ifclosedgek.lowcost=0;for(i=1;iG.vexnum;i+)k=minimum(closedge);if(closedgek.lowcostnextarc)if(p-costadjvex.lowcost)closedgep-adjvex=k,p-cost;/ifelse Forest_Prim(G,k); /对另外一个连通重量执行算法/for/Forest_Prim void Addto_Forest(CSTree &T,int i,int j)/把边

32、(i,j)添加到孩子兄弟链表表示的树T中p=Locate(T,i); /找到结点i对应的指针p,过程略q=(CSTNode*)malloc(sizeof(CSTNode);q-data=j;if(!p) /起始顶点不属于森林中已有的任何一棵树p=(CSTNode*)malloc(sizeof(CSTNode);p-data=i;for(r=T;r-nextsib;r=r-nextsib);r-nextsib=p;p-firstchild=q; /作为新树插入到最右侧else if(!p-firstchild) /双亲还没有孩子p-firstchild=q; /作为双亲的第一个孩子else /双亲已经有了孩子for(r=p-firstchild;r-nextsib;r=r-nextsib);r-nextsib=q; /作为双亲最终一个孩子的兄弟/Addto_Forest main().T=(CSTNode*)malloc(sizeof(CSTNode); /建立树根T-data=1;Forest_Prim(G,1,T);./main分析:这个算法是在Prim算法的基础上添加了非连通图支持与孩子兄弟链表构建模块而得到的,其时间困难度为O(n2). 7.33 typedef struct int vex; /结点序号 int ecn