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

目录摘要…………………………………………………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)//采用邻接矩阵表示法，构造图G.StatusCreateGraph(MGraph&G)//采用邻接表表示法，构造图GStatusMinSpanTree_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;iG.vexnum;++i)scanf(&G.vexs[i]);//构造顶点向量for(i=0;iG.vexnum;++i)//初始化邻接矩阵for(j=0;jG.vexnum;++j)G.arcs[i][j]={INFINITY,NULL};//{adj,info}for(k=0;kG.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){//建立无向图的邻接表表示inti，j，k；EdgeNode*s；scanf(％d％d，&G-n，&G-e)；//读入顶点数和边数for(i=0；iG-n；i++){//建立顶点表G-adjlist[i].vertex=getchar()；//读入顶点信息G-adjlist[i].firstedge=NULL；//边表置为空表}for(k=0；kG-e；k++){//建立边表scanf(％d％d，&i,&j)；读入边(vi，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;in;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(e0&&kn-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(v1||vn)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;in;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(newdistdist[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;iG-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;ik;i++)printf(%d,path[i]);printf(\n);}k--;v[path[k]]=0;}5、程序设计#includestdio.h#includestdlib.h#defineMAXV50#defineINF32767typedefintInfoType;//邻接矩阵存储方法typedefstruct{intno;InfoTypeinfo;}VertexType;typedefstruct{intedges[MAXV][MAXV];intn,e;VertexTypevexs[MAXV];}MGraph;//狄克斯特拉算法voidPpath(intpath[],inti,intv){intk;k=path[i];if(k==v)return;Ppa