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

目录摘要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.概要设计ADT Graph 数据对象V:V是具有相同特性的数据元素的集合，称为顶点集； 数据关系R： R=VR VR=|v,wV且P(v,w),表示从v到w的弧，谓词P(v,w)定义了弧的意义或信息基本操作：CreateGraph(&G,V,VR);Status CreateGraph(MGraph &G)/采用邻接矩阵表示法，构造图G.Status CreateGraph(MGraph &G)/采用邻接表表示法，构造图GStatus MinSpanTree_Prim(MGraph G,VertexType u)/用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边Status MinSpanTree_ Kruskal(MGraph G,VertexType u)/用克鲁斯卡尔算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边Status ShortestPath_DIJ(MGraph G,int v0,PathMatrix &p,ShortPathTable &D)/用 Dijkstra算法求有向网G的 v0顶点到其余顶点v的最短路径Pv及带权长度DvStatus TopSort(ALGraph G)/若G中无回路，则输出G的顶点的一个拓扑排序并返回OK,否则返回ERROR存储结构typedef struct/邻接矩阵存储结构 int no; int info;VertexType;typedef struct int edgesMAXVMAXV; int n,e; VertexType vexsMAXV;MGraph;typedef struct ANode /邻接表存储结构 int adjvex; struct ANode *nextarc; int info;ArcNode;typedef struct Vnode int data; int count; ArcNode *firstarc;VNode;typedef VNode AdjListMAXV;typedef struct AdjList adjlist; int n,e;ALGraph;typedef struct node int data; struct node *next;List;4、详细设计图的邻接矩阵存储结构算法：Status CreateUDN(MGraph &G)/采用邻接矩阵表示法，构造无向网GScanf(&G.vexnum,&G.arcnum,&IncInfo); /IncInfo为0则各弧不含其他信息for(i=0;iG.vexnum;+i) scanf(&G.vexsi); /构造顶点向量for(i=0;iG.vexnum;+i) /初始化邻接矩阵for(j=0;jG.vexnum;+j) G.arcsij=INFINITY,NULL; /adj,infofor(k=0;kG.arcnum;+k) /构造邻接矩阵scanf(&v1,&v2,&w); /输入一条边依附的顶点及权值i=LocateVex(G,v1); j=LocateVex(G,v2); /确定v1和v2在G中位置G.arcsij.adj=w; /弧的对称弧Return Ok;/CreateUDN图的邻接表存储结构算法：void CreateALGraPh(ALGraph *G) /建立无向图的邻接表表示 int i，j，k； EdgeNode *s； scanf( dd ，&G- n，&G- e)； /读入顶点数和边数 for(i=0；i n；i+)/建立顶点表 G- adjlisti.vertex=getchar()； /读入顶点信息 G- adjlisti.firstedge=NULL；/边表置为空表 for(k=0；k e；k+) /建立边表 scanf( dd ，&i,&j)；读入边(vi，vj)的顶点对序号 s=(EdgeNode *)malloc(sizeof(EdgeNode)； /生成边表结点 s- adjvex=j; /邻接点序号为j s- next=G- adjlisti.firstedge； G- adjlisti.firstedge=s； /将新结点*s插入顶点vi的边表头部 s=(EdgeNode *)malloc(sizeof(EdgeNode)； s- adjvex=i; /邻接点序号为i s- next=G- adjlistj.firstedge； G- adjlistkj.firstedge=s； /将新结点*s插入顶点vj的边表头部 /end for CreateALGraphPrim算法实现：Public static void prim(int n,float) /prim算法floatlowcost=new floatn+1;Intclosest=new intn+1;Booleans=new booleann+1;S1=true;for(int i=2;i=n;i+)Lowesti=c1i;Closesti=1;Si=false;for(int i=1;in;i+)float min=Float.MAX_VALUE;int j=1;for(int k=2;k=n;k+)if(lowcostkmin)&(!sk)min=lowcostk;j=k;System.out.println(j+“, ”+closestj);Sj=true;for(int k=2;k=n;k+)if(cjk0&kn-1)EdgeNode x=(EdgeNode)H.removeMin();e-;int a=U.find(x.u);int b=U.find(x.v);if(a!=b)tk+=x;U.union(a,b);Return(k=n-1);Dijkstra算法实现:Public static void Dijkstra(int v,floata,floatdist,intprev)/单源最短路径问题的Dijkstra算法Int n=dist.length-1;If(vn)return;Booleans=new Booleann+1;/初始化for(int i=1;i=n;i+)disti=avi;si=false;if(disti=Float.MAX_VALUE)previ=0;else previ=v;Distv=0;sv=true;for(int i=1;in;i+)float temp=Float.MAX_VALUE;int u=v;for(int j=1;j=n;j+)if(!si)&(distitemp)u=j;temp=distj;su=true;for(int j=1;j=n;j+)if(! s j)&(aujFloat.MAX_VALUE)float newdist=distu+auj;if(newdistn) for(i=0;in;i+) if(G-adjlisti.count=0&vi=0) pathk=i; k+; vi=1; p=G-adjlisti.firstarc; while(p!=NULL) j=p-adjvex; G-adjlistj.count-; p=p-nextarc; TopSort(G); p=G-adjlisti.firstarc; while(p!=NULL) j=p-adjvex; G-adjlistj.count+; p=p-nextarc; else for(i=0;ik;i+)printf(%d ,pathi); printf(n); k-; vpathk=0;5、程序设计#include #include #define MAXV 50#define INF 32767typedef int InfoType;/邻接矩阵存储方法 typedef struct int no; InfoType info; VertexType;typedef struct int edgesMAXVMAXV; int n,e; VertexType vexsMAXV; MGraph; /狄克斯特拉算法void Ppath(int path,int i,int v) int k; k=pathi; if(k=v) return; Ppath(path,k,v); printf(%d,k); void Dispath(int dist,int path,int s,int n,int v) int i; for(i=0;in;i+) if(i=v) continue; if(si=1) printf(从%d到%d的最短路径长度为：%dt路径为：,v,i,disti); printf(%d,v); Ppath(path,i,v); printf(%dn,i); else printf(从%d到%d不存在路径n,v,i); void Dijkstra(MGraph g,int v) int distMAXV,pathMAXV; int sMAXV; int mindis,i,j,u; for(i=0;ig.n;i+) disti=g.edgesvi; si=0; if(g.edgesviINF) pathi=v; else pathi=-1; sv=1;pathv=0; for(i=0;ig.n;i+) mindis=INF; for(j=0;jg.n;j+) if(sj=0&distjmindis) u=j; mindis=distj; su=1; for(j=0;jg.n;j+) if(sj=0) if(g.edgesujINF&distu+g.edgesujdistj) distj=distu+g.edgesuj; pathj=u; Dispath(dist,path,s,g.n,v); /弗洛伊德算法void Ppath1(int pathMAXV,int i,int j) int k; k=pathij; if(k=-1) return; Ppath1(path,i,k); printf(%d,k); Ppath1(path,k,j); void Dispath1(int AMAXV,int pathMAXV,int n) int i,j; for(i=0;in;i+) for(j=0;jn;j+) if(i=j) continue; if(Aij=INF) if(i!=j) printf(从%d到%d不存在路径n,i,j); else printf(从%d到%d的最短路径长度为：%dt路径为：,i,j,Aij); printf(%d,i); Ppath1(path,i,j); printf(%dn,j); void Floyd(MGraph g) int AMAXVMAXV,pathMAXVMAXV; int i,j,k; for(i=0;ig.n;i+) for(j=0;jg.n;j+) Aij=g.edgesij; pathij=-1; for(k=0;kg.n;k+) for(i=0;ig.n;i+) for(j=0;jAik+Akj) Aij=Aik+Akj; pathij=k; Dispath1(A,path,g.n); /主函数int main() int i,j,n; MGraph g; pri