数据结构与算法课程设计报告_图的算法实现.doc

《数据结构与算法课程设计报告_图的算法实现.doc》由会员分享，可在线阅读，更多相关《数据结构与算法课程设计报告_图的算法实现.doc（68页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数据结构与算法课程设计报告 课程设计题目： 图的算法实现 专业班级： 信息与计算科学1001班 姓 名： 学 号： 设计室号： 理学院机房 设计时间： 2011-12-26 批阅时间： 指导教师： 成 绩： 课题：图的算法实现 任务要求：（1）将图的信息建立文件；（2）从文件读入图的信息，建立邻接矩阵和邻接表；（3）实现Prim、Kruskal、Dijkstra序算法功能、算法、体会描述：系统主要功能是实现图的算法，主界面选着建立保存图的信息，可以用普利姆，克鲁斯卡尔和狄克斯特拉三种算法分别实现。1建立图的邻接矩阵基本思想：输入顶点和边数，输入顶点信息，算出邻接矩阵程序模块：typedef

2、struct char vexsN; int edgesNN; int n,e; /顶点数和边数MGraph;MGraph g;typedef struct char 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;else return -1;int minimum(minside SZ) int i=0,j,k,min; while(SZi.lowcost=0) i+;min=SZ

3、i.lowcost; /第一个不为0的值k=i;for(j=i+1;j0)if(minSZj.lowcost)min=SZj.lowcost;k=j;return k;用outmatrix()函数输出邻接矩阵，getin_1()函数保存文件和对文件进行载入。程序模块：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+) prin

4、tf(%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);/顶点的信息会出

5、现在矩阵边界上。 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);

6、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;2分别用普利姆，克鲁斯卡尔和狄克斯特拉算法实现程序模块：void MiniSpa

7、nTree_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用prim算法生成的最小生成树为：n);k=minimum(closedge); / 求出T的下一个结点：第K顶点 printf(%c-%c)n,closedgek.adjvex,g.vexsk); / 输出生成树的边 closed

8、gek.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 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

9、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=

10、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.edgesuj0)t=frontt;return t;void Kruskal(edgetype edges,int n)int front

11、100;int i,vf1,vf2;printf(用Kruskal算法生成的最小生成树为：n);for(i=0;in;i+)fronti=0;for(i=0;in-1;i+)vf1=Search(front,edgesi.w1);vf2=Search(front,edgesi.w2);if(vf1!=vf2)frontvf2=vf1;printf(%c-%c)n,edgesi.w1,edgesi.w2);3主函数void main() int a,i;printf(tt*图的实现算法*n);printf(tt*nn);printf(ttt1:建立图的邻接矩阵nn);printf(ttt2:用p

12、rim算法生成的最小生成树为：nn);printf(ttt3:用Dijkstra生成的最短路径nn);printf(ttt4:用Kruskal算法生成的最小生成树为：nn);printf(ttt5:返回nn);printf(tt*n);printf(tt*n);printf(ntt输入一个有效的数字,选择你要做的操作:n); system(color A);/*改变界面颜色的，对程序没什么影响*/ scanf(%d,&a);switch(a)case 1:system(cls); printf(输入数据建立无向图的邻接矩阵);getin_1();printf(数据保存成功！n);/*flag_

13、1=1;Undigraph();*/main();break; case 2:getout_1();outmatrix();MiniSpanTree_PRIM(g.vexs0);/用prim算法求最小生成树main();break;case 3:getout_1();outmatrix();printf(n采用Dijkstra算法得到的最短路径为：n); for(i=0;ig.n;i+)Dijkstra(i);printf(n);main();break; case 5:main();case 4:getout_1();outmatrix();printf(n); edgetype edgex

14、1000; int p,q,c=0;for(p=0;pg.n;p+)for(q=p+1;q=g.n;q+)edgexc+.Cost=g.edgespq;edgex-c.w1=g.vexsp;edgexc+.w2=g.vexsq;Kruskal(edgex,g.e);main();break;功能调试主界面建立图的信息用普利姆算法生成最小生成树用狄克斯特拉算法生成最短路径用克鲁斯卡尔算法生成最小生成树返回程序源代码#include#include#define N 9999typedef int elemtype;typedef structelemtype w1;elemtype w2;int

15、 Cost;edgetype;typedef struct char vexsN; int edgesNN; int n,e; /顶点数和边数MGraph;MGraph g;typedef struct char 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;else return -1;int minimum(minside SZ) int i=0,j,k,min; while(S

16、Zi.lowcost=0) i+;min=SZi.lowcost; /第一个不为0的值k=i;for(j=i+1;j0)if(minSZj.lowcost)min=SZj.lowcost;k=j;return k;/用prim算法从第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.edgesk

17、j;closedgek.lowcost=0; /初始,U=uprintf(n用prim算法生成的最小生成树为：n);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.lowcos

18、t=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) /*打开文件，并判断打开是否正常*/print

19、f(不能打开文件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

20、.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

21、.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

22、 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

23、;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.edgesuj0)t=frontt;return t;void Kruskal(edgetype edges,int n)int front100;in

24、t i,vf1,vf2;printf(用Kruskal算法生成的最小生成树为：n);for(i=0;in;i+)fronti=0;for(i=0;in-1;i+)vf1=Search(front,edgesi.w1);vf2=Search(front,edgesi.w2);if(vf1!=vf2)frontvf2=vf1;printf(%c-%c)n,edgesi.w1,edgesi.w2);void main() int a,i;printf(tt*图的实现算法*n);printf(tt*nn);printf(ttt1:建立图的邻接矩阵nn);printf(ttt2:用prim算法生成的最小

25、生成树为：nn);printf(ttt3:用Dijkstra生成的最短路径nn);printf(ttt4:用Kruskal算法生成的最小生成树为：nn);printf(ttt5:返回nn);printf(tt*n);printf(tt*n);printf(ntt输入一个有效的数字,选择你要做的操作:n); system(color A);/*改变界面颜色的，对程序没什么影响*/ scanf(%d,&a);switch(a)case 1:system(cls); printf(输入数据建立无向图的邻接矩阵);getin_1();printf(数据保存成功！n);/*flag_1=1;Undigr

26、aph();*/main();break; case 2:getout_1();outmatrix();MiniSpanTree_PRIM(g.vexs0);/用prim算法求最小生成树main();break;case 3:getout_1();outmatrix();printf(n采用Dijkstra算法得到的最短路径为：n); for(i=0;ig.n;i+)Dijkstra(i);printf(n);main();break; case 5:main();case 4:getout_1();outmatrix();printf(n); edgetype edgex1000; int

27、p,q,c=0;for(p=0;pg.n;p+)for(q=p+1;q=g.n;q+)edgexc+.Cost=g.edgespq;edgex-c.w1=g.vexsp;edgexc+.w2=g.vexsq;Kruskal(edgex,g.e);main();break;原文已完。下文为附加文档，如不需要，下载后可以编辑删除，谢谢！施工组织设计本施工组织设计是本着“一流的质量、一流的工期、科学管理”来进行编制的。编制时，我公司技术发展部、质检科以及项目部经过精心研究、合理组织、充分利用先进工艺，特制定本施工组织设计。一、 工程概况：西夏建材城生活区27#、30#住宅楼位于银川市新市区，橡胶厂对

28、面。本工程由宁夏燕宝房地产开发开发，银川市规划建筑设计院设计。本工程耐火等级二级，屋面防水等级三级，地震防烈度为8度，设计使用年限50年。本工程建筑面积:27#m2;30# m2。室内地坪 m为准，总长27#m；30# m。总宽27#m；30# m。设计室外地坪至檐口高度18.6 00m，呈长方形布置，东西向，三个单元。本工程设计屋面为坡屋面防水采用防水涂料。外墙水泥砂浆抹面，外刷浅灰色墙漆。内墙面除卫生间200300瓷砖，高到顶外，其余均水泥砂桨罩面，刮二遍腻子；楼梯间内墙采用50厚胶粉聚苯颗粒保温。地面除卫生间200200防滑地砖，楼梯间50厚细石砼1：1水泥砂浆压光外，其余均采用50厚豆

29、石砼毛地面。楼梯间单元门采用楼宇对讲门，卧室门、卫生间门采用木门，进户门采用保温防盗门。本工程窗均采用塑钢单框双玻窗，开启窗均加纱扇。本工程设计为节能型住宅，外墙均贴保温板。本工程设计为砖混结构，共六层。基础采用C30钢筋砼条形基础，上砌MU30毛石基础，砂浆采用M10水泥砂浆。一、二、三、四层墙体采用M10混合砂浆砌筑MU15多孔砖；五层以上采用M混合砂浆砌筑MU15多孔砖。本工程结构中使用主要材料：钢材：I级钢，II级钢；砼：基础垫层C10，基础底板、地圈梁、基础构造柱均采用C30，其余均C20。本工程设计给水管采用PPR塑料管，热熔连接；排水管采用UPVC硬聚氯乙烯管，粘接；给水管道安装

30、除立管及安装IC卡水表的管段明设计外，其余均暗设。本工程设计采暖为钢制高频焊翅片管散热器。本工程设计照明电源采用BV铜芯线，插座电源等采用BV4铜芯线；除客厅为吸顶灯外，其余均采用座灯。二、 施工部署及进度计划1、工期安排本工程合同计划开工日期：2004年8月21日，竣工日期：2005年7月10日，合同工期315天。计划2004年9月15日前完成基础工程，2004年12月30日完成主体结构工程，2005年6月20日完成装修工种，安装工程穿插进行，于2005年7月1日前完成。具体进度计划详见附图1（施工进度计划）。2、施工顺序基础工程工程定位线（验线）挖坑钎探（验坑）砂砾垫层的施工基础砼垫层刷环保沥青 基础放线（预检）砼条形基础刷环保沥青 毛石基础的砌筑构造柱砼地圈梁地沟回填工。结构工程结构定位放线（预检）构造柱钢筋绑扎、定位（隐检）砖墙砌筑（