数据结构课程设计校园导游系统

1、1. 设计目的 设计一个学校的导游系统，方便游客游览我们学校。二. 设计内容为来访的客人提供各种信息查询服务。主要包括：查看学校的全景图各个景点的简介学校主要景点的分布查看某一景点到其它所有景点的最短路径查询任意两个景点之间的最短路径。三概要设计1功能模块图；maininigraphbrowsershortestpath_dijserchmapprimprintmenucmd2功能模块详细介绍；(1)main: 主函数(2) browser：(3) inigraph：初始化学校地图，给出景点的详细信息，以及景点之间的距离。(4) shortestpath_dij：迪杰斯特拉算法，用于求两个景点

2、之间的最短路径。(5) serch：供游客查询单个景点的详细信息(6) prim：普利姆算法，用于得出最佳布网方案。(7) map：无参函数，打印学校的全景图。(8) menu：游客的输入界面。(9) print：打印相应的游览路线。(10) cmd：输入相应的选择进行不同的游览方式。四详细设计search1功能函数的调用关系图primshortestpath_dijcmdmainprintbrowserinigraphmenumap2各功能函数的数据流程图无参函数，打印平面图map图存在且非空打印路线，文件存储输入起止点标号，非法则提示再次输入prim输入起点编号，非法提示，再次输入图存在且

3、非空dij依次输入，到各个景点最短距离，文件存储无参函数，菜单栏menu无向网初始化，得到景点距离，以及信息initgraph打印景点信息图存在且非空browserfor循环控制结点数目，并打印。图存在且非空print3重点设计及编码创建结构体，表示景点，成员为编号，名称，简介typedef struct /图中顶点表示主要景点，存放景点的编号、名称、简介等信息，char name30;int num;char introduction100;/简介infotype;prim算法：void prim(mgraph *g)file *fp;fp=fopen(d:sight.txt,at+);if

4、(fp=null)printf(fail to open!n);elseint 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+) p

5、vwi=pvui|puwi; while(flag) printf(请输入出发点和目的地的编号:); scanf(%d%d,&k,&j); if(kg-vexnum|jg-vexnum) printf(景点编号不存在!请重新输入出发点和目的地的编号:); scanf(%d%d,&k,&j); if(k=0&kvexnum&j=0&jvexnum) flag=0; fprintf(fp,%s,g-); for(u=0;uvexnum;u+) if(pkju&k!=u&j!=u) fprintf(fp,-%s,g-); fprintf(fp,-%s,g-ve

6、); fprintf(fp, 总路线长%dmn,dkj);fclose(fp);迪杰斯特拉算法：void shortestpath_dij(mgraph * g)file *fp;fp=fopen(d:approach.txt,at+);if(fp=null)printf(fail to open!n);elseint v,w,i,min,t=0,x,flag=1,v0; int final20, d20, p2020;while(flag)printf(请输入一个起始景点编号:);scanf(%d,&v0);if(v0g-vexnum)printf(景点编号不存在!请重新输入

7、景点编号:);scanf(%d,&v0);if(v0=0&v0vexnum)flag=0;/endwhilefor(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-arcsv

8、w.adjarcsvw.adj;for(x=0;xvexnum;x+) pwx=pvx;pww=1;for(v=0;vvexnum;v+)if(v0!=v)fprintf(fp,%s,g-);for(w=0;wvexnum;w+)if(pvw&w!=v0) fprintf(fp,-%s,g-); t+; if(tg-vexnum-1&v0!=v) fprintf(fp, 总路线长%dmnn,dv); /endfor/endif/shortestpath_dij end五测试数据及运行结果1 正常测试数据和运行结果2异常测试数据及运行结果六调试情况，设计

9、技巧及体会1改进方案对于我的设计，合理之处是对每一次查询都以文件的形式进行了存储，其次，校园的平面图比较好的展现了我们学校的风貌。不足之处是使用prim算法的时候，若终点输入不合法，程序会陷入，死循环。这是致命的错误，我的改进方法是若输入字符不合法，则跳出循环，再次输入，直到合法为止。利用迪杰斯特拉算法在计算到剩下的顶点的最短距离时第一个for循环时时间复杂度是o（n），每进行一次第二个for循环的时间复杂度都是o（n），第三个for循环也就是存储途经顶点时用的循环而不是书中算法所用的只是个地址的赋值，所以时间复杂度也是o（n），这样总的时间复杂度就是o(n3)。改进设想主要就是给用户一个浏览

10、路线的推荐本来在程序设计初期是计划要实现这个功能的，但是由于时间和能力问题没有去实现，因为它涉及到汉密尔顿路的实现，目前感觉还比较复杂所以暂时放弃了，日后如果有机会一定将这个功能完善。2体会调试过程中难免会遇见这样或者那样的问题，一个很低级的错误就是在字符串的赋值上居然还会出错，本来是不可以像int型数据那样直接用等于号赋值的，可是刚开始由于失误却犯了这样低级的错误结果导致出现102个错误，当时确实有点慌了，等冷静下来一想才把问题想明白，字符串的赋值必须用strcpy函数。看来基本功还是相当的重要的。此外，迪杰斯特拉算法其实放在这里多少有些不合适，因为不管在求任意两个景点之间的最短路径还是求某

11、一景点到其它景点的最短路径时都要完全的执行一遍算法时间复杂度是很高的，当时在实现时也确实考虑到了这个问题只是后来感觉要是实现时间复杂度的降低不是很简单也就暂时放弃了，也就选择了将这个算法直接搬了过来，这里是一点败笔，尚需要改进。七参考文献数据结构 严蔚敏 吴为民c语言程序设计（第三版） 谭浩强 八附录：源代码（电子版）#define infinity 10000 /*无穷大*/#define max_vertex_num 40#define max 40#include#include#include#includetypedef struct arcellint adj; /路径长度arce

12、ll,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;void cmd(void);mgraph initgraph(void);void menu(void);void browser(mgra

13、ph *g);void shortestpath_dij(mgraph * g);void prim(mgraph *g);void search(mgraph *g);int locatevex(mgraph *g,char* v);mgraph * creatudn(mgraph *g);void print(mgraph *g);void map();/*/void main(void) system(mode con: cols=100 lines=30); cmd();/*/void cmd(void) int i; b=initgraph(); menu(); scanf(%d,&

14、i); while(i!=6) switch(i) case 1:browser(&b);menu();break; case 2:map();menu();break; case 3:shortestpath_dij(&b);menu();break; case 4:floyd(&b);menu();break; case 5:search(&b);menu();break; case 6:exit(1);break; default:break; scanf(%d,&i); mgraph initgraph(void) mgraph g; int i,j; g.vexnum=10; g.a

15、rcnum=14; for(i=0;ig.vexnum;i+) g.vexsi.num=i; strcpy(g.,旭日苑); strcpy(g.roduction,难吃,洗过的筷子上面都是菜叶子); strcpy(g.,校医院); strcpy(g.roduction,校医院，名副其实的校(shou)医(yi)院(yuan); strcpy(g.,大学生活动中心); strcpy(g.roduction,又名大活,举办一些没什么卵用的晚会); strcpy(g.

16、,美食广场); strcpy(g.roduction,吃货的天堂,完爆旭日苑); strcpy(g.,图书馆); strcpy(g.roduction,warning!学霸出没!); strcpy(g.,足球场); strcpy(g.roduction,国足的未来.23333333); strcpy(g.,水煮鸽子); strcpy(g.roduction,然而他并不能吃); strcpy(g.,东区教学楼); strcpy(g.vexs7.i

17、ntroduction,又名尼伯龙根,进去就不要想出来); 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=100; g.arcs02.adj=200; g.arcs06.adj=400; g.arcs17.adj=30

18、0; g.arcs23.adj=120; g.arcs36.adj=220; g.arcs34.adj=100; g.arcs45.adj=300; g.arcs49.adj=250; g.arcs59.adj=350; g.arcs67.adj=60; g.arcs69.adj=200; g.arcs78.adj=50; g.arcs89.adj=20; for(i=0;ig.vexnum;i+) for(j=0;jg.vexnum;j+) g.arcsji.adj=g.arcsij.adj; return g;/initgraph endvoid menu() printf(n 西安邮(m

19、ei)电(dian)大学n); printf( n); printf( 1.校园景点介绍 n); printf( 2.校园平面图 n); printf( 3.查看所有游览路线(jiandan) n); printf( 4.选择出发点和目的地(zuiduan) n); printf( 5.查看景点信息 n); printf( 6.退出系统 n); printf( n); printf(option-:);void browser(mgraph *g) int v; printf(n); printf(编号景点名称 简介 n); for(v=0;vvexnum;v+) printf(%-4d%-1

20、6s%-56sn,g-vexsv.num,g-,g-roduction); printf(n);/ 迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径,v0为起点void shortestpath_dij(mgraph * g)file *fp;fp=fopen(d:approach.txt,at+);if(fp=null)printf(fail to open!n);elseint v,w,i,min,t=0,x,flag=1,v0; int final20, d20, p2020;while(flag)printf(请输入一个起始景点编号:);scan

21、f(%d,&v0);if(v0g-vexnum)printf(景点编号不存在!请重新输入景点编号:);scanf(%d,&v0);if(v0=0&v0vexnum)flag=0;/endwhilefor(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=

22、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)fprintf(fp,%s,g-);for(w=0;wvexnum;w+)if(pvw&w!=v0) fprintf(fp,-%s,g-); t+; if(tg-vexnum-1&v0!=v) fprintf(fp, 总路线长%dmnn,dv); /endfor/endifprintf(请稍候.n);printf

23、(文件已经成功地保存至d:/approach.txt!n);/shortestpath_dij endvoid search(mgraph *g) int k,flag=1; while(flag) printf(请输入要查询的景点编号:); scanf(%d,&k); if(kg-vexnum) printf(景点编号不存在!请重新输入景点编号:); scanf(%d,&k); if(k=0&kvexnum) flag=0; printf(n); printf(编号景点名称 简介 n); printf(%-4d%-16s%-56sn,g-vexsk.num,g-,g-ve

24、roduction); printf(n);/search endint locatevex(mgraph *g,char* v) int c=-1,i; for(i=0;ivexnum;i+) if(strcmp(v,g-)=0) c=i;break; return c;void print(mgraph *g)int v,w,t=0;for(v=0;vvexnum;v+) for(w=0;wvexnum;w+) if(g-arcsvw.adj=infinity) printf( ); else printf(%-7d,g-arcsvw.adj); t+;

25、if(t%g-vexnum=0) printf(n); void prim(mgraph *g)file *fp;fp=fopen(d:sight.txt,at+);if(fp=null)printf(fail to open!n);elseint 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) printf(请输入出发点和目的地的编号:); sca