数据结构课程设计—校园导航问题报告.doc

数学与计算机学院课程设计说明书课 程 名 称: 数据结构-课程设计 课 程 代 码: 8404181 题 目: 校园导航问题 年级/专业/班: 学 生 姓 名: 学 号: 开 始 时 间: 年 月 日完 成 时 间: 年 月 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书撰写质量（45）总 分（100）指导教师签名： 年 月 日校园导航问题数 据 结 构 课 程 设 计 任 务 书学院名称： 数学与计算机学院 课程代码： 8404181 专 业： 年 级： 一、设计题目校园导航问题二、主要内容设计西华大学的平面图，至少包括10个以上的场所，找出从任意场所到达另一场所的最短路径。三、具体要求及应提交的材料1每个同学以自己的学号和姓名建一个文件夹，如：“312009080611101张三”。里面应包括：学生按照课程设计的具体要求所开发的所有源程序（应该放到一个文件夹中）、任务书和课程设计说明书的电子文档。2打印的课程设计说明书（注意：在封面后夹入打印的“任务书”以后再装订）。四、主要技术路线提示涉及无向图的操作。该设计共分三部分，一是建立西华大学平面图的存储结构，二是解决单源点最短路径问题，最后再实现任意一对场所之间的最短路径问题。五、进度安排共计两周时间，建议进度安排如下：选题，应该在上机实验之前完成需求分析、概要设计可分配4学时完成详细设计可分配4学时调试和分析可分配10学时。2学时的机动，可用于答辩及按教师要求修改课程设计说明书。注：只用课内上机时间一般不能完成设计任务，所以需要学生自行安排时间做补充。六、推荐参考资料(不少于3篇)1苏仕华等编著，数据结构课程设计，机械工业出版社，20072严蔚敏等编著，数据结构（C语言版），清华大学出版社，20033严蔚敏等编著，数据结构题集（C语言版），清华大学出版社，2003指导教师 签名日期 年 月 日系 主 任 审核日期 年 月 日校园导航问题摘要：程序设计目的是用哈斯图方式计算两个旅游点的最短距离以及路线。编程所实现的功能除了可以查询两个旅游点的最短距离以及最短的路线，还可以看到旅游点的介绍，以及逛遍所有旅游点所能组成的所有路线可能，实现全面查询。 关键字：景点；路线；距离；校园导航1 课程设计题目 设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。2 分析21设计基础：要掌握最短路径的实现方式。22分析设计课题的要求，要求编程实现以下功能：（1）查询景点路径（2）查询景点信息（3）查看参观路线（4）查询各景点之间的距离23主控菜单设计为实现通信录管理的操作功能，首先设计一个含有多个菜单项的主控菜单程序，然后再为这些菜单项配上相应的功能。程序运行后，给出菜单项的内容和输入提示，如下： 1学校简介 2查询景点路径3. 查询景点信息4. 查看参观路线5. 查询各景点之间的距离6. 退出24设计课题已明确要求，有关的定义如下：typedefstructArcCellintadj; / 相邻接的景点之间的路程char *info;ArcCell; / 定义边的类型typedefstructVertexTypeint number; / 景点编号char *sight; / 景点名称char *description; / 景点描述VertexType; / 定义顶点的类型typedefstructVertexType vexNUM; / 图中的顶点，即为景点ArcCell arcsNUMNUM; / 图中的边，即为景点间的距离intvexnum,arcnum; / 顶点数，边数MGraph; / 定义图的类型3 共0条评论.3步骤3.1函数调用图函数调用关系3.2主代码#include #include #include #include #define Max 32767#define NUM 11typedef struct ArcCellint adj; / 相邻接的景点之间的路程 char *info;ArcCell; / 定义边的类型 typedef struct VertexTypeint number; / 景点编号 char *sight; / 景点名称 char *description; / 景点描述 VertexType; / 定义顶点的类型 typedef structVertexType vexNUM; / 图中的顶点，即为景点 ArcCell arcsNUMNUM; / 图中的边，即为景点间的距离 int vexnum,arcnum; / 顶点数，边数 MGraph; / 定义图的类型 MGraph G; / 把图定义为全局变量 int PNUMNUM; / /long int DNUM; / 辅助变量存储最短路径长度 int x13=0; void CreateUDN(int v,int a); / 创建图的函数 void pingmu(); /屏幕输出函数void introduce();void ShortestPath(int num); /最短路径函数void output(int sight1,int sight2); /输出函数void PrintMGraph();char Menu(); / 主菜单 void search(); ;/ 查询景点信息 char SearchMenu(); / 查询子菜单 void HaMiTonian(int); / 哈密尔顿图的遍历 void NextValue(int); void display(); / 显示遍历结果 void main() / 主函数 int v0,v1;char ck;system(color 0);CreateUDN(NUM,11);do ck=Menu();switch(ck)case1:introduce();printf(nnttt%-25snn,G.vex0.description);getchar();getchar();break;case 2:system(cls);pingmu();printf(nnttt请选择起点景点（110）：);scanf(%d,&v0);printf(ttt请选择终点景点（110）：);scanf(%d,&v1);ShortestPath(v0); / 计算两个景点之间的最短路径 output(v0,v1); / 输出结果 printf(nntttt请按回车键继续.n);getchar();getchar();break;case 3:search();break;case 4:system(cls);pingmu();x0=1; HaMiTonian(1); printf(nntttt请按回车键继续.n);getchar();getchar();break;case5:PrintMGraph();printf(nntttt请按回车键继续.n);getchar();getchar();break;while(ck!=e);char Menu() / 主菜单 /char c;int flag;doflag=1;system(cls);pingmu();introduce();printf(nttn);printf(tt n);printf(tt 1.学校简介 n);printf(tt 2.查询景点路径 n);printf(tt 3.查询景点信息 n);printf(tt 4.查看参观路线 n);printf(tt 5.查询各景点之间的距离 n);printf(tt e.退出 n);printf(tt n);printf(ttn);printf(tttt请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=3|c=4|c=5|c=e)flag=0;while(flag);return c;char SearchMenu() / 查询子菜单 char c;int flag;doflag=1;system(cls);pingmu();introduce();printf(nttn);printf(tt n);printf(tt 1、按照景点编号查询 n);printf(tt 2、按照景点名称查询 n);printf(tt e、返回 n);printf(tt n);printf(tt n);printf(ttt请输入您的选择：);scanf(%c,&c);if(c=1|c=2|c=e)flag=0;while(flag);return c;void search() / 查询景点信息 int num;int i;char c;char name20;dosystem(cls);c=SearchMenu();switch (c)case 1: system(cls);introduce();pingmu();printf(nntt请输入您要查找的景点编号：);scanf(%d,&num);for(i=0;iNUM;i+)if(num=G.vexi.number)printf(nnttt您要查找景点信息如下:);printf(nnttt%-25snn,G.vexi.description);printf(nttt按任回车返回.);getchar();getchar();break;if(i=NUM)printf(nnttt没有找到！);printf(nnttt按回车键返回.);getchar();getchar();break;case 2:system(cls);pingmu();introduce();printf(nntt请输入您要查找的景点名称：);scanf(%s,name);for(i=1;iNUM;i+)if(!strcmp(name,G.vexi.sight)printf(nnttt您要查找景点信息如下:);printf(nnttt%-25snn,G.vexi.description);printf(nttt按回车键返回.);getchar();getchar();break;if(i=NUM)printf(nnttt没有找到！);printf(nnttt按回车键返回.);getchar();getchar();break;while(c!=e);void CreateUDN(int v,int a) / 创建图的函数 int i,j;G.vexnum=v; / 初始化结构中的景点数和边数 G.arcnum=a;for(i=1;iG.vexnum;+i) G.vexi.number=i; / 初始化每一个景点的编号 / 初始化没一个景点名及其景点描述 G.vex0.sight=学校简介;G.vex1.sight=东大门;G.vex2.sight=培训楼;G.vex3.sight=气象楼;G.vex4.sight=文德楼;G.vex5.sight=明德楼;G.vex6.sight=尚贤楼;G.vex7.sight=电影院;G.vex8.sight=北辰楼;G.vex9.sight=图书馆;G.vex10.sight=实验楼;/ 这里把所有的边假定为32767，含义是这两个景点之间是不可到达 for(i=1;iG.vexnum;+i)for(j=1;jG.vexnum;+j) G.arcsij.adj=Max;G.=NULL;/下边是可直接到达的景点间的距离，由于两个景点间距离是互相的，/ 所以要对图中对称的边同时赋值。G.arcs14.adj=G.arcs41.adj=200;G.arcs13.adj=G.arcs31.adj=150;G.arcs35.adj=G.arcs53.adj=100;G.arcs310.adj=G.arcs103.adj=400;G.arcs46.adj=G.arcs64.adj=200;G.arcs25.adj=G.arcs52.adj=200;G.arcs24.adj=G.arcs42.adj=100;G.arcs57.adj=G.arcs75.adj=150;G.arcs46.adj=G.arcs64.adj=150;G.arcs47.adj=G.arcs74.adj=150;G.arcs68.adj=G.arcs86.adj=150;G.arcs78.adj=G.arcs87.adj=100;G.arcs69.adj=G.arcs96.adj=200;/ 打印出邻接矩阵void PrintMGraph()int i,j;coutn =nn ;for(i=1;iG.vexnum;+i)coutG.vexi.sight ;coutendl;for(i=1;iG.vexnum;+i)coutnnG.vexi.sight ;for(j=1;jG.vexnum;+j)if(G.arcsij.adj=Max)cout no ;elsecout G.arcsij.adj;coutnnnn=nnn;void introduce() / 介绍函数 int i;for(i=1;i=NUM;i+) G.vex0.description=南京信息工程大学是江苏省人民政府和中国气象局共建的全国重点高校，是江苏省十一五重点建设的15所大学之一。;G.vex1.description=东大门，有五根大柱子 ;G.vex2.description=留学生学习的地方;G.vex3.description=气象楼，特色楼 ;G.vex4.description=全校最大的教学楼 ;G.vex5.description=又一个教学楼;G.vex6.description=实验楼，历史悠久;G.vex7.description=经常放恐怖片 ;G.vex8.description=听说有灵异事件发生过 ;G.vex9.description=很不错;G.vex10.description=刚建好的，蛮新的，不错;void pingmu() / 屏幕输出函数 int i;printf(nntt*欢迎来到南京信息工程大学*nn);printf(ttn);printf(tttt学校简介ttn,1,1);printf(ttn);printf(tttt学校概况ttn,6,6);printf(ttn);for(i=1;iNUM;i+)printf(tt%ctt(%2d)%-20s%cttt,1,i,G.vexi.sight,1); / 输出景点列表 printf(ttnn);void ShortestPath(int num) / 迪杰斯特拉算法最短路径函数 num为入口点的编号 int v,w,i,t; / i、w和v为计数变量 int finalNUM; int min;for(v=1;vNUM;v+)finalv=0; / 假设从顶点num到顶点v没有最短路径 Dv=G.arcsnumv.adj;/ 将与之相关的权值放入D中存放 for(w=1;wNUM;w+) / 设置为空路径 Pvw=0;if(Dv32767) / 存在路径 Pvnum=1; / 存在标志置为一 Pvv=1; / 自身到自身 Dnum=0;finalnum=1; / 初始化num顶点属于S集合 / 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 for(i=1;iNUM;+i) / 其余G.vexnum-1个顶点 min=Max; / 当前所知离顶点num的最近距离 for(w=1;wNUM;+w)if(!finalw) / w顶点在v-s中 if(Dwmin) / w顶点离num顶点更近 v=w;min=Dw; finalv=1; / 离num顶点更近的v加入到s集合 for(w=1;wNUM;+w) / 更新当前最短路径极其距离 if(!finalw&(min+G.arcsvw.adj)Dw)/ 不在s集合，并且比以前所找到的路径都短就更新当前路径 /Dw=min+G.arcsvw.adj;for(t=0;tNUM;t+)Pwt=Pvt;Pww=1;void output(int sight1,int sight2) / 输出函数 int a,b,c,d,q=0;a=sight2; / 将景点二赋值给a if(a!=sight1) / 如果景点二不和景点一输入重合，则进行. printf(nt从%s到%s的最短路径是,G.vexsight1.sight,G.vexsight2.sight);/ 输出提示信息 printf(t(最短距离为 %dm.)nnt,Da); / 输出sight1到sight2的最短路径长度，存放在D数组中 printf(t%s,G.vexsight1.sight); / 输出景点一的名称 d=sight1; / 将景点一的编号赋值给d for(c=0;cNUM;+c)gate:; / 标号，可以作为goto语句跳转的位置 Pasight1=0;for(b=0;bNUM;b+)if(G.arcsdb.adj%s,G.vexb.sight); / 输出此节点的名称 q=q+1; / 计数变量加一，满8控制输出时的换行 Pab=0;d=b; / 将b作为出发点进行下一次循环输出，如此反复 if(q%8=0) printf(n);goto gate;void HaMiTonian(int m) / 哈密尔顿图的遍历 if(m8) return; L: NextValue(m); if(xm=0) return; if(m=7&G.arcs1x8-1.adj!=32767) display(); else HaMiTonian(m+1); goto L; void NextValue(int k) int j; l:xk=(xk+1)%10; if(xk=0) return; if(G.arcsxk-1-1xk-1.ad