数据结构与算法课程设计报告

目录TOC\o"1-5"\h\z摘要 11、 引言 12、需求分析 13、概要设计 24、详细设计 45、程序设计 106、运行结果 187、总结体会 19摘要（题目）：图的算法实现实验内容图的算法实现问题描述：（1）将图的信息建立文件；（2）从文件读入图的信息，建立邻接矩阵和邻接表；（3）实现Prim、Kruskal、Dijkstra和拓扑排序算法。关键字：邻接矩阵、Dijkstra和拓扑排序算法1.引言本次数据结构课程设计共完成图的存储结构的建立、Prim、Kruskal、Dijkstra和拓扑排序算法等问题。通过本次课程设计，可以巩固和加深对数据结构的理解，通过上机和程序调试，加深对课本知识的理解和熟练实践操作。(1)通过本课程的学习，能够熟练掌握数据结构中图的几种基本操作；(2)能针对给定题目，选择相应的数据结构，分析并设计算法，进而给出问题的正确求解过程并编写代码实现。使用语言：CPrim算法思想：从连通网N={V,E}中的某一顶点v0出发，选择与它关联的具有最小权值的边(v0,v)，将其顶点加入到生成树的顶点集合V中。以后每一步从一个顶点在V中，而另一个顶点不在V中的各条边中选择权值最小的边(u,v),把它的顶点加入到集合V中。如此继续下去，直到网中的所有顶点都加入到生成树顶点集合V中为止。拓扑排序算法思想：1、从有向图中选取一个没有前驱的顶点，并输出之；2、从有向图中删去此顶点以及所有以它为尾的弧；重复上述两步，直至图空，或者图不空但找不到无前驱的顶点为止。没有前驱--入度为零，删除顶点及以它为尾的弧--弧头顶点的入度减1。2.需求分析1、通过键盘输入建立一个新的有向带权图，建立相应的文件；2、对建立的有向带权图进行处理，要求具有如下功能：(1)用邻接矩阵和邻接表的存储结构输出该有向带权图，并生成相应的输出结果；(2)用Prim、Kruskal算法实现对图的最小生成树的求解，并输出相应的输出结果；(3)用Dijkstra算法实现对图中从某个源点到其余各顶点的最短路径的求解，并输出相应的输出结果；(4)实现该图的拓扑排序算法。3.概要设计ADTGraph{数据对象V:V是具有相同特性的数据元素的集合，称为顶点集；数据关系R：R={VR}VR={<v,w>|v,w£V且P(v,w),<v,w>表示从v到w的弧，谓词P(v,w)定义了弧<v,w>的意义或信息}基本操作：CreateGraph(&G,V,VR);StatusCreateGraph(MGraph&G)〃采用邻接矩阵表示法，构造图伍StatusCreateGraph(MGraph&G)〃采用邻接表表示法，构造图6StatusMinSpanTree_Prim(MGraphG,VertexTypeu)〃用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边StatusMinSpanTree_Kruskal(MGraphG,VertexTypeu)〃用克鲁斯卡尔算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边StatusShortestPath_DIJ(MGraphG,intv0,PathMatrix&p,ShortPathTable&D)〃用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度D[v]StatusTopSort(ALGraphG)〃若G中无回路，则输出G的顶点的一个拓扑排序并返回OK,否则返回ERROR存储结构typedefstruct〃邻接矩阵存储结构(intno;intinfo;}VertexType;typedefstruct(intedges[MAXV][MAXV];intn,e;VertexTypevexs[MAXV];}MGraph;typedefstructANode 〃邻接表存储结构{ intadjvex;structANode*nextarc;intinfo;}ArcNode;typedefstructVnode(intdata;intcount;ArcNode*firstarc;}VNode;typedefVNodeAdjList[MAXV];typedefstruct(AdjListadjlist;intn,e;}ALGraph;typedefstructnode(intdata;structnode*next;}List;4、详细设计图的邻接矩阵存储结构算法：StatusCreateUDN(MGraph&G){〃采用邻接矩阵表示法，构造无向网GScanf(&G.vexnum,&G.arcnum,&IncInfo);//IncInfo为0则各弧不含其他信息for(i=0;i<G.vexnum;++i)scanf(&G.vexs[i]); //构造顶点向量for(i=0;i<G.vexnum;++i) //初始化邻接矩阵for(j=0;j<G.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};//{adj,info)for(k=0;k<G.arcnum;++k){ 〃构造邻接矩阵scanf(&v1,&v2,&w); 〃输入一条边依附的顶点及权值i=LocateVex(G,v1);j=LocateVex(G,v2);〃确定v1和v2在G中位置G.arcs[i][j].adj=w; 〃弧<v1,v2>的对称弧<v2,v1>)ReturnOk;}//CreateUDN图的邻接表存储结构算法：voidCreateALGraPh(ALGraph*G)( 〃建立无向图的邻接表表示int i，j，k；EdgeNode*s；scanf(〃％d%d〃，&G->n,&G->e)； 〃读入顶点数和边数for(i=0；i<G->n；i++){//建立顶点表G->adjlist[i].vertex=getchar()； //读入顶点信息G->adjlist[i].firstedge=NULL；〃边表置为空表)for(k=0；k<G->e；k++){〃建立边表scanf("%d%d”,&1,&))；读入边«1，vj)的顶点对序号s=(EdgeNode*)malloc(sizeof(EdgeNode))；〃生成边表结点s->adjvex=j; 〃邻接点序号为js->next=G->adjlist[i].firstedge；G->adjlist[i].firstedge=s； 〃将新结点*s插入顶点vi的边表头部s=(EdgeNode*)malloc(sizeof(EdgeNode))；s->adjvex=i; 〃邻接点序号为is->next=G->adjlist[j].firstedge；G->adjlistk[j].firstedge=s； 〃将新结点*s插入顶点vj的边表头部}//endfor}CreateALGraphPrim算法实现：Publicstaticvoidprim(intn,float口□)//prim算法{float[]lowcost=newfloat[n+1];Int[]closest=newint[n+1];Boolean[]s=newboolean[n+1];S[1]=true;for(inti=2;i<=n;i++){Lowest[i]=c[1][i];Closest[i]=1;S[i]=false;)for(inti=1;i<n;i++){floatmin=Float.MAX_VALUE;intj=1;for(intk=2;k<=n;k++)if((lowcost[k]<min)&&(!s[k])){min=lowcost[k];j=k;)System.out.println(j+“，”+closest[j]);S[j]=true;for(intk=2;k<=n;k++)if((c[j][k]<lowcost[k])&&(!s[k])){lowcost[k]=c[j][k];closest[k]=j;)Kruskal算法实现：PublicstaticBooleanKruskal(intn,inte,EdgeNode口E,EdgeNode口t)(MinHeapH=newMinHeap(1);H.initialize(E,e);FastUnionFindU=newFastUnionFind(n);Intk=0;While(e>0&&k<n-1){EdgeNodex=(EdgeNode)H.removeMin();e--;inta=U.find(x.u);intb=U.find(x.v);if(a!=b){t[k++]=x;U.union(a,b);}Return(k==n-1);)Dijkstra算法实现：PublicstaticvoidDijkstra(intv,float[][]a,float[]dist,int[]prev){〃单源最短路径问题的Dijkstra算法Intn=dist.length-1;If(v<1||v>n)return;Boolean[]s=newBoolean[n+1];〃初始化for(inti=1;i<=n;i++){dist[i]=a[v][i];s[i]=false;if(dist[i]==Float.MAX_VALUE)prev[i]=0;elseprev[i]=v;)Dist[v]=0;s[v]=true;for(inti=1;i<n;i++){floattemp=Float.MAX_VALUE;intu=v;for(intj=1;j<=n;j++)if((!s[i])&&(dist[i]<temp)){u=j;temp=dist[j];)s[u]=true;for(intj=1;j<=n;j++)if((!s[j])&&(a[u][j]<Float.MAX_VALUE)){floatnewdist=dist[u]+a[u][j];if(newdist<dist[j]){〃dist[j]减少dist[j]=newdist;prev[j]=u;))图的拓扑排序算法：voidTopSort(ALGraph*G){〃若G中无回路，则返回G的一个拓扑排序，且函数值为OK,否则为ERRORinti,j;ArcNode*p;if(k!=G->n){for(i=0;i<G->n;i++){if(G->adjlist[i].count==0&&v[i]==0){path[k]=i;k++;v[i]=1;p=G->adjlist[i].firstarc;while(p!=NULL){j=p->adjvex;G->adjlist[j].count--;p=p->nextarc;)TopSort(G);p=G->adjlist[i].firstarc;while(p!=NULL){j=p->adjvex;G->adjlist[j].count++;p=p->nextarc;))))else{for(i=0;i<k;i++)printf("%d”,path[i]);printf(〃\n〃)；k--;v[path[k]]=0;)5、程序设计#include<stdio.h>#include<stdlib.h>#defineMAXV50#defineINF32767typedefintInfoType;〃邻接矩阵存储方法typedefstruct(intno;InfoTypeinfo;}VertexType;typedefstructintedges[MAXV][MAXV];intn,e;VertexTypevexs[MAXV];}MGraph;〃狄克斯特拉算法voidPpath(intpath口，inti,intv)(intk;k=path[i];if(k==v)return;Ppath(path，k，v);printf("%d,",k);)voidDispath(intdist口，intpath口，ints口，intn,intv)(inti;for(i=0;i<n;i++)(if(i==v)continue;if(s[i]==1)(printf(〃从%d到％d的最短路径长度为：％d\t路径为：〃,v,i,dist[i]);printf("%d,”,v);Ppath(path,i,v);printf("%d\n”,i);)elseprintf(〃从％d到％d不存在路径\n”,v,i);))voidDijkstra(MGraphg,intv)(intdist[MAXV],path[MAXV];ints[MAXV];for(i=0;i<g.n;i++)(dist[i]=g.edges[v][i];s[i]=0;if(g.edges[v][i]<INF)path[i]=v;elsepath[i]=-1;)s[v]=1;path[v]=0;for(i=0;i<g.n;i++)(mindis=INF;for(j=0;j<g,n;j++)(if(s[j]==0&&dist[j]<mindis)(u=j;mindis=dist[j];s[u]=1;for(j=0;j<g,n;j++)(if(s[j]==0)(if(g.edges[u][j]<INF&&dist[u]+g.edges[u][j]<dist[j])(dist[j]=dist[u]+g.edges[u][j];path[j]=u;))))Dispath(dist,path,s,g.n,v);〃弗洛伊德算法voidPpath1(intpath[][MAXV],inti,intj)(intk;k=path[i][j];if(k==-1)return;Ppath1(path,i,k);printf("%d,”,k);Ppath1(path,k,j);)voidDispath1(intA[][MAXV],intpath[][MAXV],intn)(inti,j;for(i=0;i<n;i++)(for(j=0;j<n;j++)if(i==j)continue;if(A[i][j]==INF)(if(i!=j)printf(〃从%d到％d不存在路径\n”,i,j);)else(printf(〃从%d到％d的最短路径长度为：％d\t路径为：〃，i,j,A[i][j]);printf("%d,”,i);Ppath1(path,i,j);printf(〃%d\n〃，j);))))voidFloyd(MGraphg)intA[MAXV][MAXV],path[MAXV][MAXV];inti,j,k;for(i=0;i<g.n;i++)(for(j=0;j<g,n;j++)(A[i][j]=g.edges[i][j];path[i][j]=-1;))for(k=0;k<g.n;k++)(for(i=0;i<g.n;i++)(for(j=0;j<g,n;j++)if(A[i][j]>A[i][k]+A[k][j])(A[i][j]=A[i][k]+A[k][j];path[i][j]=k;))))Dispath1(A,path,g.n);) 〃主函数intmain(){inti,j,n;MGraphg;printf(〃请输入带权有向图的顶点个数：〃)；〃6while(scanf("%d",&n)!=EOF)(printf(〃请输入带权有向图的邻接矩阵：\n〃)；/*05327677327673276732767043276732767327678327670327673276793276732767503276763276732767327675032767332767327673276710*/for(i=0;i<n;i++)(for(j=0;j<n;j++)(scanf("%d”,&g.edges[i][j]);))g.n=n;printf（〃采用狄克斯特拉算法得到的最短路径为：\n〃）;

for(i=0;i<n;i++)Dijkstra(g,i);printf(〃\n〃)；printf（〃采用弗洛伊德算法得到的最短路径为：\n〃）；Floyd（g）;printf（〃\n请输入带权无向图的顶点个数：〃）；）return0;6、程序运行结果:，l.\-Jseh".AcFFiinstrataf*,pDCjnnenf3；'liC-Free\Tetr.贯