C语言及程序设计

1、数据结构（C语言版）课程设计 学 院： 班 级：姓 名： 指导老师： 二一五年一月二十二日一、课程设计的题目校园网架设的方案与设计问题【问题描述】若要在扬州大学的七个校区（江阳路南校区、江阳路北校区、瘦西湖校区、农学院校区、工学院校区、水利学院校区、医学院校区）之间架设校园网，如何以最低的经济代价架设这个校园网。并求出江阳路南校区到其他各校区之间的最短距离。【基本要求】（1）利用二种方法（Prim算法和克鲁斯卡尔（Kruskual）算法生成校园网的架设方案。（2）利用迪杰斯特拉算法求出江阳路校区到其他各校区之间的最短距离。（3）写出课程设计报告。【测试数据】对每种方法设定一组模拟测试数据进行测

2、试，验证程序的正确性。二、课程设计的目的课程设计的目的是培养学生综合程序设计的能力，训练学生灵活应用所学数据结构知识，独立完成问题分析、总体设计、详细设计和编程实现等软件开发全过程的综合实践能力。巩固、深化学生的理论知识，提高编程水平，并在此过程中培养他们严谨的科学态度和良好的学习作风。为今后学习其他计算机课程打下基础。课程设计为学生提供了一个既动手又动脑，独立实践的机会，将书本上的理论知识和工作、生产实际有机地结合起来，从而锻炼学生分析问题、解决实际问题的能力，提高学生的编程序能力和创新意识。三、分析系统的主要功能及用途在扬州大学的七个校区（江阳路南校区、江阳路北校区、瘦西湖校区、农学院校区

3、、工学院校区、水利学院校区、医学院校区）之间架设校园网，所架设的校园网经济代价最低。并能计算出江阳路南校区到其他各校区之间的最短距离。四、分析和描述的基本要求1、基本要求（1）利用二种方法（Prim算法和克鲁斯卡尔（Kruskual）算法生成校园网的架设方案。（2）利用迪杰斯特拉算法求出江阳路校区到其他各校区之间的最短距离。（3）写出课程设计报告。2、程序包含模块1） 主程序模块，其中主函数为main() 初始化图形界面； 读入用户选择信息； 根据用户选择执行相应模块； 关闭文件及图形界面； ；2） 创建模块实现将七个校区设计成无向图G的创建；3） 普里姆模块实现图G的经济代价最低的校园网的架

4、设方案；4） 克鲁斯卡尔模块实现图G的经济代价最低的校园网的架设方案；5） 迪杰斯特拉算法求最短距离模块实现图G从江阳路南校区（v0）到其它各校区的最短距离。3、模块功能框图主程序模块创建模块普里姆模块克鲁斯卡尔模块迪杰斯特拉算法求最短距离模块五、问题实现的主要算法与分析1、顶点、边、图和最小生成树的边类型#define MAX 20 /最大顶点数设为20#define INF 10000 /无穷设为32767typedef struct node int adjvex; /邻接点struct node * next; /指向下一个邻接点的指针域EdgeNode;typedef struct

5、vnode int vertex; /顶点 int indegree; /入度 EdgeNode * firstedge; /边表头指针VertexNode;typedef VertexNode AdjListMAX; /adj_list是邻接表类型typedef struct AdjList adjlist; /邻接表 int vexnum,arcnum; /图中顶点数和边数ALGraph;typedef struct int vexsMAX; /定点表 int AdjMatrixMAXMAX; /邻接矩阵 int vexnum,arcnum; /顶点数和边数MGragh;typedef s

6、truct int begin,end; /边顶点序号 int cost; /边上的权值TreeEdge;2、图的基本操作void Create (void)/将七个校区设计成一个无向图G，创建无向图G的邻接矩阵存储void prim(void)/用Prim算法建立经济代价最低的校园网架设方案void Sort(void)/在G中选择经济代价最低的校园网void Kruskal(int n)/用克鲁斯卡尔算法求图G的经济代价最低的校园网架设方案void ShortPath(int path,int i,int v0)/将源点设为v0（江阳路南校区）void Distance(int v0)/迪

7、杰斯特拉算法求无向网G的从江阳路南校区（v0）到其它各校区的最短距离3、函数调用关系mainCreate()()primsortKruskalShortPathDistance六、源程序 #include<stdio.h>#include<malloc.h>#define MAX 20#define INF 10000typedef struct nodeint adjvex;/邻接点struct node * next;/指向下一个邻接点的指针域EdgeNode;typedef struct vnodeint vertex;/顶点int indegree;/入度Edg

8、eNode * firstedge;/边表头指针VertexNode;typedef VertexNode AdjListMAX;/adj_list是邻接表类型typedef structAdjList adjlist;/邻接表int vexnum,arcnum;/图中顶点数和边数ALGraph;typedef struct int vexsMAX;/定点表 int AdjMatrixMAXMAX;/邻接矩阵 int vexnum,arcnum;/顶点数和边数MGragh;typedef struct int begin,end;/边顶点序号 int cost;/边上的权值TreeEdge;M

9、Gragh G;void Create(void)/创建无向图G的邻接矩阵存储FILE *f1;int i,j,k,x;f1=fopen("d:c.txt","r");fscanf(f1,"%d%d",&G.vexnum,&G.arcnum);for (i=0;i<G.vexnum;i+)for(j=0;j<G.vexnum;j+)G.AdjMatrixij=INF;for(k=0;k<G.arcnum;k+)fscanf(f1,"%d%d%d",&i,&j,&am

10、p;x);G.AdjMatrixij=x;G.AdjMatrixji=G.AdjMatrixij;fclose(f1);void prim(void) int n=G.vexnum;int lowerCostMAX,mincost=0,closeVertexMAX;TreeEdge closeMAX;int i,j,k,sum=0;for(i=1;i<n;i+) lowerCosti=G.AdjMatrix0i; closeVertexi=0; lowerCost0=0; closeVertex0=0;for(i=1;i<n;i+)mincost=INF; j=1;k=1;whil

11、e(j<n)if(lowerCostj!=0&&lowerCostj<mincost)mincost=lowerCostj;k=j;j+;closei-1.begin=closeVertexk;closei-1.end=k;closei-1.cost=mincost;sum=sum+mincost;lowerCostk=0;for(j=1;j<n;j+)if(G.AdjMatrixkj<lowerCostj)lowerCostj=G.AdjMatrixkj;closeVertexj=k; printf("校园网构架方案如下所示：n")

12、; printf("n"); printf("始点终点两校距离n"); for(i=0;i<n-1;i+) printf("n");printf("%4d%4d%8dn",closei.begin,closei.end,closei.cost); printf("n"); printf("校园网最低的经济代价总长为:%dn",sum);TreeEdge edgeMAX*MAX,treeMAX;void Sort(void)/在G中选择经济代价最低的校园网int i,j,

13、k=0,p;TreeEdge temp; for(i=0;i<G.vexnum;i+) for(j=0;j<=i;j+) if(G.AdjMatrixij<INF) edgek.begin=i; edgek.end=j; edgek.cost=G.AdjMatrixij; k+; for(i=0;i<k-1;i+) p=i; for(j=i;j<k;j+) if(edgej.cost<edgep.cost) p=j; if(p!=i) temp=edgei; edgei=edgep; edgep=temp; void Kruskal(int n)int v=

14、0,j,k,sum=0; int cnvxMAX; for(j=0;j<n;j+) cnvxj=j; for(k=0;k<n-1;k+) while(cnvxedgev.begin=cnvxedgev.end) v+; treek=edgev; sum=sum+edgev.cost;for(j=0;j<n;j+)if(cnvxj=cnvxedgev.begin)cnvxj=cnvxedgev.end; v+;printf("校园网构架方案如下所示：n"); printf("n"); printf("始点终点两校距离n"

15、;);for(j=0;j<n-1;j+)printf("n");printf("%4d%4d%8dn",treej.end,treej.begin,treej.cost);printf("n");printf("校园网最低的经济代价总长为:%dn",sum);void ShortPath(int path,int i,int v0)/将源点设为v0即为路南校区int k;k=pathi; if(k!=v0) ShortPath(path,k,v0); printf("%d ",k);voi

16、d DIJ(int v0) int v,w,i,min,pathMAX,finalMAX,disMAX; int pMAXMAX; for(v=0;v<G.vexnum;+v) pathv=0; for(w=0;w<G.vexnum;+w) pvw=0; for(v=0;v<G.vexnum;+v)finalv=0;disv=G.AdjMatrixv0v; disv0=0; finalv0=1; pathv0=-1; for(i=1;i<G.vexnum;+i) min=INF; for(w=0;w<G.vexnum;+w) if(!finalw) if(disw

17、<min) v=w; min=disw; finalv=1; for(w=0;w<G.vexnum;+w) if(!finalw&&(min+G.AdjMatrixvw<disw) disw=min+G.AdjMatrixvw;pathw=v; printf("最短路径:n"); for(i=1;i<G.vexnum;+i) if(finali=1 && i!=v0) printf("从校区%d到校区%d的最短距离为:%dt路径为:",v0,i,disi); ShortPath(path,i,v0)

18、; printf("%dn",i); else printf("从%d到%d不存在!n",v0,i); main() int c;Create();printf("n 校园网架设的方案与设计nn");printf(" 1.prim算法的实现n");printf(" 2.克鲁斯卡尔（Kruskual）算法的实现n");printf(" 3.路南校区到各个区的最短距离n");printf(" 4.退出系统nn");printf(" 请输入您所要做的序号：");scanf("%d",&c);if(c<1|c>4) printf(" 无此菜单号，请重新输入!n");printf(" 请输入您所要做的序号：");scanf(&