数据结构第7章答案_第1页
数据结构第7章答案_第2页
数据结构第7章答案_第3页
数据结构第7章答案_第4页
数据结构第7章答案_第5页
已阅读5页,还剩10页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

答:11、设图G=(V,E),V={1,2,3,4,5,6},E={〈1,2〉,〈1,3〉,〈2,5〉,〈3,6〉,〈6,5〉,〈5,4〉,〈6,4〉}。画出图G,并写出图G中顶点的所有拓扑序列。1,2,3,6,5,41,3,2,6,5,41,3,6,2,5,4五、代码填空题01、图的存储结构定义如下:typedefstructArcCell{VRTypeadj;/*图中有1/0表示是否有边,网中表示边上的权值*//*InfoType*info;与边相关的信息*/}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefstruct{VertexTypevexs[MAX_VERTEX_NUM];/*顶点向量*/AdjMatrixarcs;/*邻接矩阵*/intvexnum,arcnum;/*图中当前顶点数和边数*/}MGraph;请写出下面函数实现的功能:顶点在顶点向量中的定位。intLocateVex(MGraphG,VertexTypev){inti;for(i=0;i〈G.vexnum;i++)if(strcmp(v,G.vexs[i])==0)break;returni;}下面函数的功能是在图中查找第1个邻接点,请填空。intFirstAdjVex(MGraphG,intv){intj,p=-1;for(j=0;j〈G.vexnum;j++)if(G.arcs[v][j].adj==1){p=j;break;}returnp;下面函数的功能是在图中查找下一个邻接点,请填空。intNextAdjVex(MGraphG,intv,intw){intj,p=-1;for(j二w+1;j〈G.vexnum;j++)if(G.arcs[v][j].adj==l){p=j;break;}returnp;}02、已知图的邻接表表示的形式说明如下:#defineMaxNum80typedefstructnode{intadjvex;//邻接点域structnode*next;//链指针域}EdgeNode;//边表结点结构描述typedefstruct{charvertex;//顶点域EdgeNode*firstedge;//边表头指针}VertexNode;//顶点表结点结构描述typedefstruct{VertexNodeadjlist[MaxNum];//邻接表intn,e;}AlGraph;//邻接表结构描述下列算法输出图G的深度优先生成树(或森林)的边,阅读算法,并在空缺处填入合适的内容,使其成为个完整的算法。typedefenum{FALSE,TRUE}Boolean;Booleanvisited[MaxNum];voidDFSForest(AlGraph*G){for(i=0;i〈G-〉n;i++)visited[i]二FALSE;for(i=0;i〈G-〉n;i++)if(!visited[i])DFSTree(G,i);}voidDFSTree(AlGraph*G,inti){visited[i]=TRUE;p=G-〉adjlist[i].firstedge;while(p!=NULL){if(!visited[p-〉adjves]){printf(G-〉adjlist[i].vertex,G-〉adjlist[p-〉adjvex].vertex);DSFTree(G,p-〉adjvex);}p=p-〉next;}}六、算法设计题01、编写编历算法,完成对图的深度优先搜索和广度优先搜索。答:深度优先搜索:课本P169算法7.4和算法7.5广度优先搜索:课本P170算法7.602、编写算法,由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。答:StatusBuild_AdjList(ALGraph&G)//输入有向图的顶点数,边数,顶点信息和边的信息建立邻接表{InitALGraph(G);scanf("%d",&v);if(v〈0)returnERROR;//顶点数不能为负G.vexnum=v;scanf("%d",&a);

if(a<0)returnERROR;//边数不能为负G.arcnum=a;for(m=0;m<v;m++)G.vertices[m].data=getchar();//输入各顶点的符号for(m=1;m<=a;m++){t=getchar();h=getchar();//t为弧尾,h为弧头if((i=LocateVex(G,t))<0)returnERROR;if((j=LocateVex(G,h))<0)returnERROR;//顶点未找到p=(ArcNode*)malloc(sizeof(ArcNode));if(!G.vertices.[i].firstarc)G.vertices[i].firstarc=p;else{for(q=G.vertices[i].firstarc;q->nextarc;q=q->nextarc);q->nextarc=p;}p->adjvex=j;p->nextarc=NULL;}//whilereturnOK;}//Build_AdjList03、试在邻接矩阵存储结构上实现图的基本操作:DeleteArc(G,v,w),即删除一条边的操作。提示:要删除所有从第i个顶点出发的边,即将邻接矩阵的第i行全部置0。答://本题中的图G均为有向无权图。StatusDelete_Arc(MGraph&G,charv,charw)//在邻接矩阵表示的图G上删除边(v,w){if((i=LocateVex(G,v))<0)returnERROR;if((j=LocateVex(G,w))<0)returnERROR;if(G.arcs[i][j].adj){G.arcs[i][j].adj=0;G.arcnum--;}returnOK;}//Delete_Arc04、有n个顶点的有向图的邻接表定义如下04、有n个顶点的有向图的邻接表定义如下:#defineMaxNum80typedefstructArcNode{intadjvex;structArcNode*nextarc;}ArcNode;typedefstructVNode{VertexTypedata;ArcNode*firstedge;}VNode,AdjList[MaxNum];typedefstruct{AdjListvertices;intvexnum,arcnum;}AlGraph;设计算法分别实现以下要求求出图G中每个顶点的出度;求出图G中出度最大的一个顶点,计算图G中出度为0的顶点数;//邻接点域//链指针域//边表结点结构描述//顶点域//边表头指针//顶点向量结点结构描述//邻接表//邻接表结构描述输出该顶点号及其信息判断图G中是否存在弧〈i,j〉。答:本题答案见实验部分05、试基于图的深度优先搜索策略写一算法,判别以邻接表方式存储的有向图中是否存在由顶点v到顶点v的ij路径(i^j)。注意:算法中涉及的图的基本操作必须在此存储结构上实现。答:intvisited[MAXSIZE];//指示顶点是否在当前路径上intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{visited[i]=1;for(p=G.vertices[i].firstarc;p;p=p-〉nextarc){k=p-〉adjvex;辻(!visited[k]&&exist_path(k,j))returnl;//i下游的顶点到j有路径}//for}//else}//exist_path_DFS解2:(以上算法似乎有问题:如果不存在路径,则原程序不能返回0。我的解决方式是在原程序的中引入一变量level来控制递归进行的层数。具体的方法我在程序中用红色标记出来了。)intvisited[MAXSIZE];//指示顶点是否在当前路径上intlevel=l;//递归进行的层数intexist_path_DFS(ALGraphG,inti,intj)//深度优先判断有向图G中顶点i到顶点j是否有路径,是则返回1,否则返回0{if(i==j)return1;//i就是jelse{vis

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论