数据结构与算法大作业

课 程 设 计 说 明 书课程名称： 数据结构与算法 设计题目： 校园导游程序 院 系： 计算机科学与信息工程学院 学生姓名： 丁守亮 学 号： 7 专业班级： 10级软件工程一班 指导教师： 闫怀平 2012年 6 月 15日1 课 程 设 计 任 务 书设计题目校园导游程序学生姓名丁守亮所在院系计算机科学与信息工程学院专业、年级、班10级软件工程一班设计要求：应用无向网表示学校的校园景点平面图（1） 建图以图中顶点表示主要景点，并存放景点的编号、名称、简介等信息；图中的边表示景点间的道路，存放路径长度等信息。（2） 查询该系统可以查询景点的信息； 查询图中任意两个景点间的最短路径； 查询图中任意两个景点间的所有路径。（3） 更新 可以进行景点的更新，如去除、增添景点和路径，可以随时对景点间路径长度的更新。学生应完成的工作：根据设计要求，我们需完成如下工作： 程序编写方面：（1）建立无向图，保存景点信息和路径信息；（2）景点相关信息查询函数；（3）查询图中任意两个景点间最短路径函数；（4）查询图中任意两个景点间的所有路径函数；（5）更新景点信息函数，需要完成对以下函数的调用1）增加景点的信息函数；2）增加道路的信息函数；3）删除景点的信息函数；4）删除道路的信息函数；5）更新道路权值的信息函数。 （6）建立校园景点平面图； （7）对（2）、（3）、（4）、（5）、（6）功能函数调用函数。 其他方面：（1） 对编写完成的程序进行上机调试；（2） 运行程序；（3） 对运行结果进行分析；（4） 撰写课程设计说明书（5） 完成设计答辩。参考文献阅读：1 严蔚敏、吴伟民.据结构（c语言版）.北京：清华大学出版社.2009 2 谭浩强.C程序设计（第四版）.北京：清华大学出版社.2010 3 严蔚敏、吴伟民.据结构题集.北京：清华大学出版社.2009工作计划：本次课程设计时间为20112012学年度第二学期的第17、18周1、第一周的第一天：小组布置设计题目；说明进度安排。2、第一周的第二天：小组审题，查阅资料，进行设计前的必要资料准备。3、第一周的第三天、第四天、第五天：程序编写、上机调试4、第二周的第一天至第三天： 上机调试程序、结果分析。5、第二周的第四天： 撰写设计报告。6、第二周的第五天： 设计答辩及成绩评定。任务下达日期： 2012年 6月 4 日 任务完成日期： 2012年 6月 15 日指导教师（签名）： 学生（签名）： 校园导游程序摘 要：随着现代旅游业的快速发展,图文声像导游方式和实地口语导游方式都已经不能满足现阶段旅游者的需求,信息化的飞速发展造就了地理信息系统(GIS)和全球定位系统(GPS),促使消费者更多的选择自助游和自驾游等方式出行。而近年来高等院校的发展使得高校也成为了一个景点。如何让游客以最短的时间到达旅游目的地就是本文所寻求解决的问题。文章通过最短路径算法,并结合实际情况以高等院校为例采集所需要的数据,理论上使得游客可以轻松的寻找到最适合自己的旅游线路,并以此为依据合理安排自己的行程。 关键词：数据结构 图 结点 边 权 景点 路径 距离 目 录 1.设计背景1 1.1课程设计目的1 1.2题目要求12.设计方案2 2.1功能构思2 2.2方法实现33. 方案实施4 3.1基本操作4 3.2各步操作函数模块4 4.结果和结论17 4.1运行结果17 4.2结论255. 收获和致谢266. 参考文献277. 附件28 1. 设计背景1.1 课程设计目的 数据结构是计算机程序设计的重要理论技术基础，它不仅是计算机科学的核心课程，而且已成为其他理工专业的热门选修课。从课程性质上讲，数据结构是一门专业技术基础课。它的教学要求是：学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当地逻辑结构，存储结构和其相应的算法，并初步掌握算法的时间分析和空间分析的技术。另一方面，本课程的学习也是复杂程序的设计的训练过程，要求学生编写的程序结构清楚和正确易读，符合软件工程的规范。如果说高级语言程序设计的训练过程，要进行结构化的程序设计的初步训练的话，那么数据结构就要培养我们的数据抽象能力。本次课程设计的目的就是培养学生运用数据结构中基本算法进行处理现实中的问题的能力。通过本次课程设计，可以让学生更好地掌握数据结构中的各类基本算法，并运用C语言完成简单的编程，为以后更好的学习高级编程语言打下基础。1.2题目要求 本次设计要求两人合作共同完成： 1.景点信息和路径信息保存在文本文件，景点个数不少于20个 2.查询各景点的相关信息； 3.查询图中任意两个景点间的最短路径。 4.查询图中任意两个景点间的所有路径。 5.增加、删除、更新有关景点和道路的信息。2.设计方案2.1 功能构思2.1.1问题的分析和结构的设计思路 1） 在安阳工学院校内选取具有代表性的景点，把这些景点看作无向带权图的各个结点，景点间的路径看作无向图的边，两景点之间的距离以各对应边上的权值表示。2）校园咨询程序要为用户提供最佳路径查询，根据用户提供的起始景点和终端景点输出最佳的路径，此时，可以运用弗洛伊德算法函数完成最短路径的输出。3）校园咨询程序可以用迪杰斯特拉算法完成在游客只提供起始景点的情况下，告知游客到校园内其余景点的最短路径。4）景点信息的更新则可以在无向图中以添加、删除结点，添加、删除边以及改变各边权值表示。2.1.2校园导游咨询程序的算法思想及设计1）由校园各景点建立起的无向带权图，采用邻接矩阵的形式进行存储，其中点信息的存储形式如“strcpy( ,南门); strcpy(roduction , 安阳工学院正门)”所示，各边以及路径长度的则以c.arcs ij.adj =Infinity表示（其中i,j表示景点的编号）。2）校园任意两景点间的最短路径问题则可以用弗洛伊德算法实现，3）显示校园其中一个景点到其余各景点的最短路径的过程用迪杰斯特拉算法求一个结点到其余各结点的最短路径像似，因此我们可以采用迪杰斯特拉算法实现。4）校园景点的更新，我们则可以在无向图中做出相应的表示。2.1.3校园导游咨询程序的设计流程图: 校园导游程序查询两景点间的所有路径查找两景点间最短路径 创建校园平面图 初始化无向图查询一个景点到其余各景点最短路径图形更新更新边的权值插入和删除边插入和删除结点2.2方法实现2.2.1基本操作函数实现 1.建立无向图的初始化 mgraph initgraph()2. 查找景点在图中的序号 int locatevex(mgraph c,int v) 3.求序号为m,n景点间的长度不超过8个景点的路径 void path(mgraph c, int m,int n,int k) 4.打印两景点间的景点个数不超过8的所有路径。调用2 int allpath(mgraph c) 5.用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径，并打印 void shortestpath_dij(mgraph c) 6.构造图的邻接矩阵 int creatgragh(mgraph &c) 7.建图、更新信息、删除、增加结点和边 int newgraph(mgraph &c) /新建图 int enarc(mgraph&c) /增加边 int envex(mgraph&c) /增加结点 int delvex(mgraph&c) /删除结点 int delarc(mgraph&c) /删除边 8.使用FLOYD算法查询两景点间的最短路径 void shortestpath_floyd(mgraph c) 3. 方案实施3.1基本操作 3.1.1完成图的各个模块以及各模块之间的调用 Main（）Allpath（）Printmatrix（）Printfmap（）Changegraph（）shortestpath_dij（）browsecompus（）Seeabout（）shortestpath_floyd（）delvexCreatgraghnewgraphenarcenvexdelarc3.2各步操作函数模块 3.2.1定义边、点、图结构体以及整形变量 typedef struct arcell /边结构体 int adj; arcell,adjmatrixMaxVertexNumMaxVertexNum; typedef struct vexsinfo /点信息结构体 int position; char name32; char introduction256; vexsinfo; typedef struct mgraph /图结构体 vexsinfo vexsMaxVertexNum; adjmatrix arcs; int vexnum,arcnum; mgraph; 3.2.2无向图的邻接矩阵存储 mgraph initgraph()/对图初始化 int i=0,j=0; mgraph c; c.vexnum =21; c.arcnum =36; for(i=0;ic.vexnum ;i+) c.vexsi.position =i;strcpy( ,南门);/依次输入顶点信息strcpy(roduction , 安阳工学院正门);strcpy( ,报告厅);strcpy(roduction ,学生聆听名人演讲的地方); strcpy( ,行政楼);strcpy(roduction ,教务后勤办公处); strcpy( ,主教楼);strcpy(roduction ,考研学生的自习室); strcpy( ,明德湖);strcpy(roduction ,学生早读之处);strcpy(,求索广场);strcpy(roduction ,因有八卦图故名求索); strcpy( ,网球场);strcpy(roduction ,网球运动绝佳圣地); strcpy(,足球场);strcpy(roduction ,每年大学生春季运动会在这里举办);strcpy( ,宿舍楼);strcpy(roduction ,校内女生宿舍，离餐厅很近);strcpy(, 餐厅);strcpy(roduction , 校内学生在这里就餐); strcpy( ,羽毛球场);strcpy(roduction ,学生运动好去处);strcpy( ,工行取款机);strcpy(roduction ,方便学生取钱的地方);strcpy( ,医务室);strcpy(roduction ,小病，可以轻松治愈);strcpy( ,外语学院);strcpy(roduction ,在这里你可以进行英语交流);strcpy( ,艺术楼);strcpy(roduction ,每年都有书画展览);strcpy( ,卫东超市);strcpy(roduction ,生活和学习用品销售);strcpy( ,至善湖);strcpy(roduction ,充满灵性和流动);strcpy( ,乒乓球场);strcpy(roduction ,休闲生活，运动至上);strcpy( ,计科学院);strcpy(roduction ,软工、网工、计科学习之处);strcpy( ,篮球场);strcpy(roduction ,男生的天堂);strcpy( ,图书馆);strcpy(roduction ,图书馆大楼，高5层); for(i=0;ic.vexnum ;i+)/依次输入边上的权值信息for(j=0;jc.vexnum ;j+)c.arcs ij.adj =Infinity; /先初始化图的邻接矩阵c.arcs01.adj=100;c.arcs02.adj=300;c.arcs03.adj=500; c.arcs04.adj=80; c.arcs17.adj=150; c.arcs23.adj=200;c.arcs24.adj=200;c.arcs25.adj=200; c.arcs210.adj=200; c.arcs34.adj=200;c.arcs35.adj=300; c.arcs310.adj=200;c.arcs45.adj=150; c.arcs49.adj=100; c.arcs510.adj=150; c.arcs511.adj=100; c.arcs67.adj=50; c.arcs68.adj=90; c.arcs78.adj=50; c.arcs89.adj=100; c.arcs817.adj=150; c.arcs910.adj=150; c.arcs915.adj=50; c.arcs1011.adj=200; c.arcs1112.adj=50; c.arcs1213.adj=250; c.arcs1314.adj=150; c.arcs1320.adj=500;c.arcs1416.adj=90; c.arcs1420.adj=500; c.arcs1516.adj=150;c.arcs1618.adj=40; c.arcs1620.adj=300;c.arcs1718.adj=100; c.arcs1819.adj=100;c.arcs1920.adj=300; for(i=0;ic.vexnum ;i+) /邻接矩阵是对称矩阵，对称赋值for(j=0;jc.vexnum ;j+)c.arcsji.adj =c.arcsij.adj ;return c;/initgraph3.2.3迪杰斯特拉算法求一个景点到其余各景点的最短路径/ 用迪杰斯特拉算法，求出一个景点到其他景点间的最短路径，并打印void shortestpath_dij(mgraph c)int v,w,i,min,t=0,x,flag=1,v0; /vo为起始景点的编号int final35,d35,p3535;printf(请输入一个起始景点的编号:);scanf(%d,&v0);while(v0c.vexnum) printf(你所输入的景点编号不存在.n); printf(请重新输入：); scanf(%d,&v0);for(v=0;vc.vexnum ;v+)finalv=0; /初始化各顶点访问标志dv=c.arcsv0v.adj; /v0 到各顶点 v 的权值赋值给dvfor(w=0;wc.vexnum ;w+)pvw=0;if(dvInfinity) /v0 到v 有边相连，修改pvv0的值为1pvv0=1;pvv=1; /各顶点自己到自己要连通dv0=0; /自己到自己的权值设为0finalv0=1; /v0的访问标志设为1，v 属于 s 集for(i=1;ic.vexnum ;i+)/对其余c.vexnum-1个顶点w，依次求 v 到 w 的最短路径min=Infinity;for(w=0;wc.vexnum ;w+) /在未被访问的顶点中，查找与 v0 最近的顶点vif(!finalw)if(dwmin) /v0 到 w (有边)的权值minv=w;min=dw;finalv=1; /v 的访问标志设置为1，v 属于s集for(w=0;wc.vexnum ;w+) /修改v0 到其余各顶点w 的最短路径权值dwif(!finalw&(min+c.arcsvw.adj dw) /若w 不属于s，且v 到w 有边相连dw=min+c.arcsvw.adj; /修改v0 到w 的权值dwfor(x=0;xc.vexnum ;x+) /所有v0 到v 的最短路径上的顶点x，都是v0 到w 的最短路径上的顶点pwx=pvx;pww=1;for(v=0;vc.vexnum ;v+) /输出v0 到其它顶点v 的最短路径if(v!=v0) printf(%s,); /输出景点v0 的景点名for(w=0;w%s,);printf(-%s,); printf(n总路线长为%d米n,dv);3.2.4实现景点的更新/(6) 构造图的邻接矩阵 int creatgragh(mgraph &c) /建图。以图的邻接矩阵存储图 int i,j,m,n;int v0,v1;int distance;printf(请输入图的顶点数和边数: );scanf(%d %d,&c.vexnum ,&c.arcnum );while(c.arcnum (c.vexnum *(c.vexnum -1)/2)/无向网的边数最多为n*(n-1)/2, printf(输入边数有误,请重新输入所建新图的边数：);/输入边数过多时报错 scanf(%d,&c.arcnum );printf(n*下面请输入景点的信息：*n);for(i=0;ic.vexnum ;i+) /构造顶点向量(数组)printf(n请输入景点的名称：); scanf(%s, );printf(n请输入景点的简介：); scanf(%s,roduction );for(i=0;ic.arcnum ;i+) /初始化邻接矩阵for(j=0;jc.arcnum ;j+)c.arcsij.adj =Infinity;printf(n*下面请输入图的边的信息：*n);for(i=1;i=0 & n=0)c.arcsmn.adj =distance;c.arcsnm.adj =c.arcsmn.adj ;return 1; / (7) 更新图的部分信息。返回值: 1int newgraph(mgraph &c)int changenum; /计数。用于记录要修改的对象的个数int i,m,n,t,distance,v0,v1;printf(n下面请输入你要修改的景点的个数：n);scanf(%d,&changenum);while(changenumc.vexnum )printf(n输入错误！请重新输入);scanf(%d,&changenum);for(i=0;ichangenum;i+)printf(n请输入景点的编号：);scanf(%d,&m);t=locatevex(c,m);printf(n请输入景点的名称：); scanf(%s, );printf(n请输入景点的简介：); scanf(%s,roduction );printf(n下面请输入你要更新的边数); scanf(%d,&changenum);while(changenumc.arcnum )printf(n输入错误！请重新输入);scanf(%d,&changenum);printf(n下面请输入更新边的信息：n);for(i=1;i=0&n=0)c.arcsmn.adj =distance;c.arcsnm.adj =c.arcsmn.adj ;return 1;/ (8) 增加一条边。返回值：1int enarc(mgraph&c)int m,n,distance;printf(n请输入边的起点和终点编号,权值：); scanf(%d %d %d,&m,&n,&distance);while(mc.vexnum |nc.vexnum )printf(输入错误，请重新输入：);scanf(%d %d,&m,&n);if(locatevex(c,m)0)printf(此结点%d已删除,m);return 1;if(locatevex(c,n)0)printf(此结点%d已被删除：,n);return 1;c.arcsmn.adj =distance; c.arcsnm.adj =c.arcsmn.adj; /对称赋值return 1;/ (9) 增加一个结点。返回值：1int envex(mgraph&c)int i;printf(请输入你要增加结点的信息：);printf(n编号：);scanf(%d,&c.vexsc.vexnum .position );printf(名称：);scanf(%s,c.vexsc.vexnum .name );printf(简介：);scanf(%s,c.vexsc.vexnum .introduction) ;c.vexnum +;for(i=0;ic.vexnum;i+) /对原邻接矩阵新增加的一行及一列进行初始化c.arcs c.vexnum -1i.adj=Infinity; /最后一行(新增的一行)c.arcs ic.vexnum -1.adj=Infinity; /最后一列(新增的一列)return 1; / (10) 删除图的一个顶点。返回值：1int delvex(mgraph&c)int i=0,j;int m;int v;if(c.vexnum =0)printf(图中已无顶点);return 1;printf(n下面请输入你要删除的景点编号：);scanf(%d,&v);while(vc.vexnum )printf(n输入错误！请重新输入);scanf(%d,&v);m=locatevex(c,v);if(m0)printf(此顶点 %d 已删除,v);return 1;for(i=m;ic.vexnum-1 ;i+)/对顶点信息所在顺序表进行删除m 点的操作strcpy( ,c.vexs i+1.name );strcpy(roduction ,c.vexs i+1.introduction );/对原邻接矩阵，删除该顶点到其余顶点的邻接关系。分别删除相应的行和列for(i=m;ic.vexnum-1 ;i+) for(j=0;jc.vexnum ;j+) c.arcs ij=c.arcs i+1j; for(i=m;ic.vexnum-1 ;i+)for(j=0;jc.vexnum ;j+) c.arcs ji=c.arcs ji+1; c.vexnum -;return 1; /(11) 删除图的一条边。返回值：1 int delarc(mgraph&c)int m,n;int v0,v1;if(c.arcnum =0)printf(图中已无边，无法删除。);return 1;printf(n下面请输入你要删除的边的起点和终点编号：);scanf(%d %d,&v0,&v1); m=locatevex(c,v0);if(m0)printf(此 %d 顶点已删除,v0);return 1;n=locatevex(c,v1);if(n0)printf(此 %d 顶点已删除,v1);return 1;c.arcs mn.adj =Infinity; /修改邻接矩阵对应的权值 c.arcs nm.adj =Infinity;c.arcnum -;return 1;3.2.4 打印图的邻接矩阵void printmatrix(mgraph c)int i,j,k=0; for(i=0;ic.vexnum ;i+)for(j=0;jc.vexnum ;j+)if(c.arcsij.adj =Infinity)printf(*);elseprintf(%4d,c.arcsij.adj);k+;if(k%c.vexnum =0)printf(n);3.2.5使用弗洛伊德算法求任意两景点间的最短路径void shortestpath_floyd(mgraph c)int i,j,k,d3535,p353535;int v,u,w; for(v=0;vc.vexnum ;v+) /初始化各对顶点 v，w 之间的起始距离 dvw 及 路径 pvw 数组for(w=0;wc.vexnum ;w+)dvw=c.arcsvw.adj; /dvw 中存放 v 至 w 间初始权值for(u=0;uc.vexnum ;u+) /初始化最短路径 pvw 数组，第 3 个分量全部清0pvwu=0;if(dvwInfinity) /如果 v 至 w 间有边相连pvwv=1; / v 是 v 至 w 最短路径上的顶点pvww=1; / w 是 v 至 w 最短路径上的顶点for(u=0;uc.vexnum ;u+) for(v=0;vc.vexnum ;v+)for(w=0;wc.vexnum ;w+) if(dvu+duwdvw) /从 v 经 u 到 w 的一条路径更短 dvw=dvu+duw; /修改 v 至 w 的最短路径长度 for(i=0;ic.vexnum ;i+) /修改 v 至 w 的最短路径数组。 若i是v至u的最短路径上的顶点,pvwi=pvui|puwi; /或i是u至w的最短路径上的顶点, 则i是v至w的最短路径上的顶点 printf(n请输入出发点和目的地编号：);scanf(%d%d,&k,&j);printf(nn);while(kc.vexnum|jc.vexnum)printf(n你所输入的景点编号不存在！);printf(n请重新输入出发点和目的地编号：n);scanf(%d%d,&k,&j);printf(nn);printf(%s, ); /输出出发景点名称for(u=0;u%s, );printf(-%s, ); /输出目的地景点名称printf(nnn总长为%d米nnn,dkj);3.2.6查询景点信息void seeabout(mgraph c)int k;printf(n请输入要查询的景点编号：);scanf(%d,&k);while(kc.vexnum)printf(n你所输入的景点编号不存在！);printf(n请重新输入：);scanf(%d,&k);printf(nn编号：%-4dn,c.vexsk.position );printf(nn景点名称：%-10sn, );printf(nn介绍：%-80snn,roduction );3.2.7查询所有景点信息void browsecompus(mgraph c)int i;printf( n编号 景点名称 简介n);printf(_n);for(i=0;ic.vexnum ;i+) printf(%-10d%-25s%-80sn,c.vexsi.position,,roduction);printf(_nn);3.2.8主函数，调用各部函数void mainwork()int yourchoice;campus=initgraph();printf(n-欢迎使用校园导游程序-n);printf(n 欢迎来到安阳