数据结构课程设计---校园导航问题.docx

目 录1需求分析12概要设计13详细设计24调试分析45使用说明46心得体会6附录：源程序清单72校园导航问题摘要：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径关键字： 校园景点 最短路径一、 需求分析 本次实验设计的任务是实现一个南京信息工程大学的校园导航平面图。设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。本课题实现校园多个场所（至少10个）的最短路径求解。（1）输入的形式和输入值的范围：本系统主要数据类型为字符型char及整形int,char型主要包括单位编号，单位名称，单位简介，功能编号；输入功能编号与单位编号进行操作。 （2） 输出的形式：输出则通过已有的信息数据，通过相关的操作输出相应信息。 （3） 程序所能达到的功能：本程序可供任何人使用，主要功能1.浏览各单位及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看某一单位信息。（4）测试数据：包括正确的输入及其输出结果和含有错误的输入及其输出结果。二、 概要设计本系统包含一个文件。设计分有菜单，显示信息，弗洛伊德算法，迪杰斯特拉算法，查找景点信息等程序段。主程序为整系统的入口处，菜单主要实现显示系统功能，显示信息主要实现显示景点信息，弗洛伊德算法主要实现求两景点之间最短路径，迪杰斯特拉算法实现求两景点之间最短路径，查找景点信息主要实现显示某一景点信息。 系统首先通过主程序调用void main( );进入系统主菜单函数，根据用户的选择可分别进入：1.浏览各景点及简介；2.查看所有游览路线；3.选择出发点和目的地求出最佳路径；4.查看景点信息；5.退出系统。选择“浏览各景点及简介”项，显示十个景点的有关信息，包括景点编号，景点名称，景点简介。选择“查看所有游览路线”项，会进入输入起始景点编号的界面，输入正确编号后会显示起始景点到其余九个景点的最短路线的方案。选择“选择出发点和目的地”项，会进入输入起始景点与目的景点的界面，输入起始景点与目的景点，并有空格隔开就得到两景点之间的最佳路径。选择“查看景点信息”项，会进入输入要查看的景点的界面，如入后会显示该景点的有关信息。选择“退出系统”项，就会退出程序。三、 详细设计 1 30 6 10 7 20 8 10 9 20 20 30 20 0 5 10 20 30 2 10 3 10 4 10 100 11 20 120：大活 1：宾馆 2：明德楼3：校史馆4：老图书馆5：沁园6：食堂7：鸳鸯楼8：新食堂9：田径场 10：新图书馆11：北辰楼12：电子楼 2、主程序流程图： （3）弗洛伊德的算法：void floyd(mgraph *g) int v,u,i,w,k,j,flag=1,p101010,d1010;/定义参数for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) dvw=g-arcsvw.adj; for(u=0;uvexnum;u+) pvwu=0; if(dvwinfinity) pvwv=1;pvww=1; for(u=0;uvexnum;u+) for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(dvu+duwdvw) dvw=dvu+duw; for(i=0;ivexnum;i+) pvwi=pvui|puwi; while(flag) coutkj; if(kg-vexnum|jg-vexnum) /判断输入的景点编号正确与否 coutkj; if(k=0&kvexnum&j=0&jvexnum) flag=0; ; /输出景点名称 for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) /输出路线 ;;cout 总路线长dkjendl; /输出总路线长度四、 调试分析 在程序设计中遇到了输出景点信息的表不整齐，用setw（）解决了；默认的界面太小，不能完整的看到输出信息，用了system(mode con: cols=100 lines=40)命令语句设置了行数和列数。刚开始做系统缺乏全局观念，分工也不是很合理，做得很零碎，所以在组合的时候也出现了很多问题。五、 使用说明与测试结果打开系统，首先会进入系统的主菜单：1. 浏览各景点及简介 2. 查看所有游览路线 3. 选择出发点和目的地4. 查看景点信息5. 退出系统用户可以进行如下操作： 1、如果你想浏览各景点及简介的话，请输入“1”，并回车。此时界面上将显示出各景点的编号、名称及其简介。2、如果你想查看某一景点的所有游览路线，可选择2操作。输入“2”，并回车。此时，系统会提示你输入某景点的编号。输入编号后，回车，便可以看到该景点的所有游览路线。若输入的景点编号错误就会有提示重新输入。3、如果你想查看两个景点之间的最短路线的，可选择3操作。输入“3”，并回车。此时，系统会提示你要输入起始景点与终点的编号。输入编号后，回车，此时，便可以见到这两个景点之间的最短路径。4、如果你想查看具体某些景点的简介及信息，可以选择4操作。输入“4”，并回车。此时，系统会提示全部景点的对应的编号，选择你要查看的景点信息，输入其编号，回车，此时，屏幕上将会显示出该景点的各种信息。若输入的景点编号错误就会有提示重新输入。5、在主菜单键入“5” ，退出程序。测试结果1、 菜单界面2、 进入“浏览各景点及简介”后，输出景点信息的界面。3、 进入“查看所有游览路线”，显示输出景点编号为0的景点到其余九个景点的最佳路线。4、 进入“选择出发点和目的地”，输入出发点2和目的点9后输出的的最佳路线的界面。5、 进入“查看景点信息”，输入要查看的景点编号，输出景点信息的界面。6、 输入要查询的景点编号错误，提示重新输入。 7、 退出程序界面。六、 心得体会经过两个星期的课程设计实习，我从中学会了许多东西。首先，我明白了理论与实际应用相结合的重要性，并提高了自己组织数据集，编写大型程序的能力。程序的编写需要有耐心，有些事情看起来很复杂，但问题需要一点一点去解决，分析问题，把问题一个一个划分，划分成小块以后就逐个去解决。再总体解决大的问题。这样做起来不仅有条理，也使问题可以得到轻松的解决。，其次，通过这段时间的课程设计，我认识到数据结构是一门比较难的课程。需要多花时间上机练习。这次的程序训练培养了我实际分析问题、编程和动手能力，使我掌握了程序设计的基本技能，提高了我适应实际，实践编程的能力。最后，这次的课程设计使我对专业课的学习有了更加深刻的认识，曾以为现在学的知识用不上，就加以怠慢，等到想用的时候却发现自己的学习原来是那么的不扎实。我决定以后要加倍努力学好专业课，让自己的基础知识更扎实，同时不断提高自己的实践操作能力，为以后的工作学习打下坚实的基础。总的来说，这次课程设计让我获益匪浅，对数据结构也有了进一步的认识和理解。 参考文献：1数据结构（c语言版）作者：严蔚敏、吴伟民 清华大学出版社2c程序设计（第二版）作者：谭浩强 清华大学出版社3数据结构题集（c语言版）作者：严蔚敏、吴伟民、米宁 清华大学出版社附录：源程序清单#define infinity 10000 /*无穷大*/#define max_vertex_num 40#define max 40#include#include#include using namespace std;#include typedef struct arcellint adj; /路径长度arcell,adjmatrixmax_vertex_nummax_vertex_num;typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction100;/简介infotype;typedef structinfotype vexsmax_vertex_num;adjmatrix arcs;int vexnum,arcnum;mgraph;mgraph b;mgraph initgraph(void);void menu(void);void browser(mgraph *g);void shortestpath_dij(mgraph * g);void floyd(mgraph *g);void search(mgraph *g);/*主函数*/void main(void) system(color 1f); system(mode con: cols=100 lines=40); int i; b=initgraph(); menu(); cini; while(i!=5) switch(i) case 1:system(cls);browser(&b);menu();break; case 2:system(cls);shortestpath_dij(&b);menu();break; case 3:system(cls);floyd(&b);menu();break; case 4:system(cls);search(&b);menu();break; case 5:exit(1);break; default:break; cini; /*/*定义景点编号，名称及简介*/mgraph initgraph(void) mgraph g; int i,j; g.vexnum=13; /十个景点 g.arcnum=14; /邻接矩阵 for(i=0;ig.vexnum;i+) g.vexsi.num=i; /各景点的代码，名称及简介 strcpy(g.,大活 ); strcpy(g.roduction, 大学生活动中心，举办各种活动的主要场所 ); strcpy(g.,宾馆); strcpy(g.roduction, 可给开学时的家长提供便利，且价格优惠 ); strcpy(g.,明德楼 ); strcpy(g.roduction,学校的特色教学楼，共六层，可容纳多人 ); strcpy(g.,校史馆 ); strcpy(g.roduction,学校历史资料的展览室 ); strcpy(g.,老图书馆 ); strcpy(g.roduction, 拥有全校机房，环境舒适 ); strcpy(g.,沁园 ); strcpy(g.roduction, 男生公寓 ); strcpy(g.,食堂 ); strcpy(g.roduction, 标准食堂，两层，清洁卫生 ); strcpy(g.,鸳鸯楼 ); strcpy(g.roduction, 男女混合公寓 ); strcpy(g.,新食堂); strcpy(g.roduction, 标准食堂，两层，清洁卫生 ); strcpy(g.,田径场); strcpy(g.roduction, 全新塑胶跑道，中间为人工草皮足球场，排球场和篮球场 ); strcpy(g.,新图书馆); strcpy(g.roduction, 藏书几十万册，设施良好，每层楼均有阅览室 ); strcpy(g.,北辰楼); strcpy(g.roduction, 计软院大一新生晚自习教室楼 ); strcpy(g.,电子楼 ); strcpy(g.roduction,计软院的院办与学办 ); for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.arcsij.adj=infinity;/各景点之间的距离，没有的均为无穷大g.arcs01.adj=20; g.arcs02.adj=20; g.arcs15.adj=20; g.arcs16.adj=30; g.arcs23.adj=10; g.arcs25.adj=30; g.arcs34.adj=10; g.arcs411.adj=10; g.arcs56.adj=30; g.arcs67.adj=10; g.arcs78.adj=20; g.arcs89.adj=10; g.arcs910.adj=20; g.arcs1012.adj=100; g.arcs1112.adj=20; for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.arcsji.adj=g.arcsij.adj; return g;/*/*主菜单（显示输入提示）*/void menu() cout 南京信息工程大学导游图 endl;cout endl;cout 1.浏览各景点及简介 endl;cout 2.查看所有游览路线 endl;cout 3.选择出发点和目的地 endl;cout 4.查看景点信息 endl;cout 5.退出系统 endl;cout endl;coutoption-:;/*显示景点编号、名称、简介*/void browser(mgraph *g) int v;coutendl;cout编号景点名称 简介 endl; for(v=0;vvexnum;v+)coutvexsv.numsetw(5)setw(10)roductionsetw(3)endl;coutendl;/*迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点*/void shortestpath_dij(mgraph * g) int v,w,i,min,t=0,x,flag=1,v0; int final20, d20, p2020;coutendl;cout编号景点名称 简介 endl; for(v=0;vvexnum;v+)coutvexsv.numsetw(5)setw(10)roductionsetw(3)endl;coutendl; while(flag) coutv0; if(v0g-vexnum) coutv0; if(v0=0&v0vexnum) flag=0; for(v=0;vvexnum;v+) finalv=0; dv=g-arcsv0v.adj; for(w=0;wvexnum;w+) pvw=0; if(dvinfinity) pvv0=1;pvv=1; dv0=0;finalv0=1; for(i=1;ivexnum;i+) min=infinity; for(w=0;wvexnum;w+) if(!finalw) if(dwmin)v=w;min=dw; finalv=1; for(w=0;wvexnum;w+) if(!finalw&(min+g-arcsvw.adjarcsvw.adj; for(x=0;xvexnum;x+) pwx=pvx; pww=1; for(v=0;vvexnum;v+) if(v0!=v) ; for(w=0;wvexnum;w+) if(pvw&w!=v0) ; t+; if(tg-vexnum-1&v0!=v) cout 总路线长dvendl; /*floyd函数*/void floyd(mgraph *g) int v,u,i,w,k,j,flag=1,p101010,d1010;coutendl;cout编号景点名称 简介 endl; for(v=0;vvexnum;v+)coutvexsv.numsetw(5)setw(10)roductionsetw(3)endl;coutendl; for(v=0;