淮北师范大学数据结构图相关算法的课程设计.doc

淮北师范大学计算机学院数据结构设计报告淮北师范大学数据结构课程设计图的相关算法 -无向图相关算法学 院 计算机科学与技术 专 业 计算机科学与技术(师范) 学 号 20091201016 学 生 姓 名 * 指导教师姓名 * 2011年04月 13日8一、设计目的与内容： （1）实验目的l 进一步巩固和复习数据结构理论知识。l 培养学生结构化程序、模块化程序设计的方法和能力。l 提高学生调试程序的技巧和软件设计的能力。l 提高分析问题、解决问题以及综合利用各种数据结构的能力。l 了解软件的编制过程。（2）实验内容实现从文件中读入图的信息，能够根据信息建立有向图和无向图，并分别用邻接矩阵和邻接表存储。在此基础上，实现Prim、Kruskal、Dijkstra和拓扑排序算法。程序应具有以下基本功能： 图的建立和存储:根据文件中的信息，建立图并采用合适结构存储：无向图的邻接矩阵和邻接表、有向图的邻接矩阵和邻接表。 分别实现Prim、Kruskal、Dijkstra和拓扑排序算法。 使用菜单方式进行各功能选择。1、实现的任务：从文件中读入图的信息，建立图的邻接矩阵和邻接表，实现Prim、Kruskal、Dijkstra和拓扑排序算法。2、本系统涉及的知识点Prim、Kruskal、Dijkstra、拓扑排序、邻接矩阵和邻接表存储。3、功能要求1不同的功能使用不同的函数实现（模块化），对每个函数的功能和调用接口要注释清楚。对程序其它部分也进行必要的注释。2对系统进行功能模块分析、画出总流程图和各模块流程图。3用户接口要求使用方便、简洁明了、美观大方、格式统一。4通过命令行相应选项能直接进入某个相应菜单选项的功能模块。5所有程序需调试通过。二、功能设计：1、流程图（Prim算法找出最小生成树）开始辅助数组初始化输出生成树的边并计算其权值新顶点并入U集后重新选择最小边：遍历点，若g.edgeskj!=0 & g.edgeskjclosedgej.lowcost，则closedgej.adjvex=g.nk;closedgej.lowcost=g.arcskj;假真 g.n假当！时，有下面赋值：closedgej.adjvex=u;closedgej.lowcost=g.edgeskj;j+。closedgek.lowcost=0; / 初始,U=uk=LocateVex(u);k=minimum(closedge);输出生成树的边，并且遍历顶点数组g.n使closedgek.adjvex=g.na。通过s=s+g.edgesak计算最小生成树的长度。i+。closedgek.lowcost=0;结束2、程序无向图相关算法的基本功能本部分程序可以对图的相关信息：顶点、边以及顶点与边的指向关系建立无向图的邻接矩阵进行拓扑排序。3、程序代码设计1文件保存函数（void getin_1()）建立一个名为record_1.txt的文件保存数据，保存的数据包括顶点的个数、边的条数、顶点与边之间的关系。2文件载入函数（int getout_1()）根据文件中保存的数据，从指定文件中按格式输入数据，并根据输入图的相关信息建立对应的无向图邻接矩阵。3邻接矩阵输出函数（void outmatrix();）将根据相关信息建立的邻接矩阵打印出显示在屏幕上。4Prim算法函数（void MiniSpanTree_PRIM(char u)）根据输入图的相关信息建立邻接矩阵运用Prim算法得出最小生成树并将所得最小生成树的结果打印出显示在屏幕上。5迪杰斯特拉算法函数（void Dijkstra(int v)）根据输入图的相关信息建立邻接矩阵运用Dijkstra算法得出最短路径并将所得最短路径的结果打印出显示在屏幕上。4、数据结构typedef struct char vexsN;int edgesNN;int n,e; /顶点数和边数 MGraph;MGraph g;typedef structchar adjvex;int lowcost;minside;三、程序调试：1. 主程序界面：2. 子程序（无向图相关算法）界面：3. 建立无向图的邻接矩阵：4. 运用Prim算法计算最小生成树：5运用Dijkstra算法计算最短路径：四、结束语：1、本人在程序设计中感想：从学数据结构以来，有关数据结构的实验做得很少，现在做到图的相关算法，普里姆、克鲁斯卡尔、迪杰斯特拉、拓扑排序，平时感觉对这些算法都挺熟悉的，但要实现它们还真的不容易。2、 感谢语：这一周的收获与刘怀愚老师的辛勤付出是分不开的，刘老师总是很耐心的辅导我们，给我们讲程序一讲就是两节课，他不仅只是讲怎样写代码，还教我们怎样去分析，这让我学到不少，这种负责的态度让我们学得更有动力，衷心的感谢老师！五、相关程序源码：#include#include#define N 9999void main();typedef struct char vexsN;int edgesNN;int n,e;/顶点数和边数MGraph;MGraph g;typedef structchar adjvex;int lowcost;minside;/ 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。int LocateVex(char u)int i;for(i = 0; i g.n; +i)if( u=g.vexsi)return i;return -1;/ 求closedge.lowcost的最小正值int minimum(minside SZ)int i=0,j,k,min;while(SZi.lowcost=0)i+;min=SZi.lowcost; /第一个不为0的值k=i;for(j=i+1;j0)if(minSZj.lowcost)min=SZj.lowcost;k=j;return k;/用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边void MiniSpanTree_PRIM(char u)int i,j,k;minside closedge9999;k=LocateVex(u);for(j=0;jg.n;+j) /辅助数组初始化if(j!=k)closedgej.adjvex=u;closedgej.lowcost=g.edgeskj;closedgek.lowcost=0; /初始,U=uprintf(n最小代价生成树的各条边为:n);for(i=1;ig.n;+i) / 选择其余G.vexnum-1个顶点k=minimum(closedge); / 求出T的下一个结点：第K顶点 printf(%c-%c)n,closedgek.adjvex,g.vexsk); / 输出生成树的边 closedgek.lowcost=0; / 第K顶点并入U集 for(j=0;jg.n;+j)if(g.edgeskj!=0 & g.edgeskjclosedgej.lowcost) / 新顶点并入U集后重新选择最小边closedgej.adjvex=g.vexsk;closedgej.lowcost=g.edgeskj;void outmatrix()/输出邻接矩阵int i,m,z;printf(所建立表的邻接矩阵为:n);printf(t);for(i=0;ig.n;i+)printf(%ct,g.vexsi);for(m=0;mg.n;m+)printf(n%ct,g.vexsm);for(z=0;zg.n;z+) printf(%dt,g.edgesmz);void getin_1() int a,b,k,w,z;FILE *fp;if(fp=fopen(record_1.txt,w)=NULL)/*打开文件，并判断打开是否正常*/printf(不能打开文件n);/*没打开*/exit(0);printf(请输入顶点数:n);scanf(%d,&g.n); fprintf(fp,%dn,g.n);printf(请输入边数:n);scanf(%d,&g.e)fprintf(fp,%dn,g.e);/初始化矩阵各元素值/读入边printf(请输入顶点信息:n);/顶点的信息会出现在矩阵边界上。fflush(stdin);/清空缓冲for (z=0;zg.n;z+)scanf(%c,&g.vexsz);fprintf(fp,%cn,g.vexsz);for(a=0;ag.n;a+)for(b=0;bg.n;b+)g.edgesab=0;printf(n);printf(请输入应的弧头a和弧尾b及弧上的权值w(皆为整数，,从0开始，格式为:a,b,w):n);for(k=0;kg.e;k+)scanf(%d %d %d,&a,&b,&w);fprintf(fp,%d %d %dn,a,b,w);g.edgesab=w;g.edgesba=w;fclose(fp);void getout_1()int i,a,b,w;FILE *fp;if(fp=fopen(record_1.txt,ab+)=NULL)printf(不能打开文件n);exit(0);fscanf(fp,%dn,&g.n); fscanf(fp,%dn,&g.e);for(i=0;ig.n;i+)fscanf(fp,%cn,&g.vexsi);for (i=0;ig.n;i+)fscanf(fp,%d %d %dn,&a,&b,&w);g.edgesab=w;g.edgesba=w;/迪杰斯特拉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(int v)int distN,pathN; int sN; int mindis,i,j,u; for(i=0;ig.n;i+) for(j=0;jg.n;j+)if(g.edgesij=0)g.edgesij=9999; for(i=0;ig.n;i+) disti=g.edgesvi; si=0; if(g.edgesvi9999) pathi=v; else pathi=-1; sv=1;pathv=0; for(i=0;ig.n;i+) mindis=9999; 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.edgesuj9999&distu+g.edgesujdistj&distu!=0)distj=distu+g.edgesuj; pathj=u; Dispath(dist,path,s,g.n,v);int flag_1;void Undigraph() while(1)system(cls);if(flag_1=0) printf(ntt提示：若无文件请先输入数据建立无向图的邻接矩阵！n); system(pause);int a,i;printf(tt*无向图算法*n);printf(tt*nn);printf(ttt1:建立无向图的邻接矩阵nn);printf(ttt2:最小生成树（Prim）nn);printf(ttt3:最短路径（Dijkstra）nn);printf(ttt4:返回。nn);printf(tt*n);printf(tt*n);printf(ntt输入一个有效的数字,选择你要做的操作:n);scanf(%d,&a);switch(a)case 1:system(cls); printf(输入数据建立无向图的邻接矩阵);getin_1();printf(数据保存成功！n);system(pause);flag_1=1;Undigraph();case 2:getout_1();outmatrix();MiniSpanTree_PRIM(g