数据结构课程设计――校园导游图

1、景德镇陶瓷学院信息工程学院班 级： 11计科（2）班学 号： 0姓 名： 张 斌指导老师： 李 娟、徐 星时 间： 2013年6月27号题 目： 13*：图（校园导游图） 7 ：建立二叉树，层序、先序遍历 14 ：拓扑排序题目一：图（校园导游图） 1.1、需求分析： 需求：（1）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离。为此图选择适当的数据结构。（2）把各种路径都显示给游客，由游客自己选择游览路线。（3）画出景点分布图于屏幕上。分析：完成对整个导游图系统的功能实现，需要对的每一项功能都有清楚的设想和认识，了解并明确每一项功能的实现需要解决的

2、问题，选择正确并且高效的算法把问题逐个解决，最终实现程序的正确调试运行。有以下设计思路：（1）.结合本校的实际情况，选出10个景点；（2）.人为手工为选出的10个景点赋上相关信息（名称、代号、简介信息、以及路权等等）；（3）.根据选出来的10个景点用邻接矩阵存储校园图。（4）.依照景点的相关信息创建校园图。（5）.把纸质上的内容，利用C+编程语言编写查找景点相关信息的程序。（6).根据人为赋值的路权，迪杰斯特拉算法计算任意两点之间的最短路径。（7）.综上所诉，用一个主函数把这些板块合成，生产一个菜单界面呈现在用户面前。1.2、设计与实现： 选出本校10个景点结合景德镇陶瓷学院实际情况，我选出以

3、下10个景点，从1到10编号：编号名称编号名称编号名称编号名称1校门口2A系列楼3B系列楼4翠湖5体育馆6主教楼7图书馆8田径场9二食堂10一食堂 图的初始化由于邻接矩阵特殊的存储方式，它非常便于快速的查找两个顶点之间的边上的权值。所以，图采用带权的邻接矩阵存储。A系列楼决定了图的存储方式后，以华南农业大学10个景点的游览地图作为蓝本，把校园地图抽象化成顶点与边构成的图形式，如图2.2所示，途中数字代表线的权值。 主教楼10 二食堂50101050B系列楼校门口4010203040 一食堂 田径场 图书管 体育馆 翠湖30108030204010302020 1.3、模块的划分 含有四个模块：

4、（1）陶院地图信息 （2）陶院景点信息 （3）查找两点间最短路径 （4）退出 模板功能 （1）将陶院的地图显示在程序运用上； （2）输入一个景点，运用程序上能够显示该景点的信息； （3）可以给游客提供两个景点的最短路径； （4）给游客提供方便。1.4、代码和实现界面 实现界面： 陶院目录图陶院地图显示陶院景点信息 查找两点最短路径 退出界面 代码：#define N 10#define MAX 25 #define MAXedg 30 #include #include #include #include void clrscr() system(cls);typedef int AdjMat

5、rixMAXMAX;typedef structint vexsMAX; AdjMatrix arcs;Matrix_Graph;typedef structchar name10; char information100; struct edgenode *link; vexnode; typedef struct edgenodeint adjvex; int length; char info10; char info2100; struct edgenode *next;edgenode, *Node ; typedef struct Edgeint lengh; int ivex,

6、jvex; struct Edge *next; EdgeType; typedef struct int num; char name10; vertex;typedef structvertex vexsMAX; int edgesMAXMAX; adjmax; void Name(int i)switch(i) case 1: printf(1:校门口nn);break;case 2: printf(2:A系列楼 nn);break; case 3: printf(3:B系列楼nn);break; case 4: printf(4:翠湖nn);break; case 5: printf(

7、5:体育馆nn);break; case 6:printf(6:主教楼nn);break; case 7: printf(7:图书馆nn);break; case 8: printf(8:田径场nn);break; case 9: printf(9:二食堂nn);break; case 10: printf(10:一食堂nn);break; default:printf(景点编号输入错误！请输入1-10的数字编号！nn); break; void Information(int i)/*景点介绍*/ switch(i) case 1: printf(校门口：学校的进门处，宏达雄伟。nn);br

8、eak;case 2: printf(A系列楼：包括行政楼，A1，A2，A3，还包括一些教室。nn);break; case 3: printf(B系列楼：包括B1，B2，B3，主要是信息工程学院的办公处。 nn);break; case 4: printf(翠湖：学校内最大的淡水湖，夏天清爽，是情侣约会的最佳场所。nn);break; case 5: printf(体育馆：学校最大的设备场所，是体育系学生主要的锻炼之地。nn);break; case 6:printf(主教楼：全校学生主要的上课楼系，也是校园最高的楼。nn);break; case 7: printf(图书馆：学生平时学习和

9、复习以及借阅资料的楼系。nn);break; case 8: printf(田径场：露天的场所，是学生，老师最重要的跑步以及锻炼的场所。nn);break; case 9: printf(二食堂：私人所办的食堂，里面食物极其好吃，但是价格方面比较贵，但也受广大学生喜好。nnn);break; case 10: printf(一食堂：学校所办的食堂，主要优点是价格方面很是优惠。nn);break; default:printf(景点编号输入错误！请输入1-10的数字编号！nn); break; void travgraph(vexnode g,int n,adjmax adj) /查找指定景点信

10、息int i = 1,flag = 1,len; char ch;printf(ttt请输入您要查询的景点序号:、nn);printf(ttt1.校门口 2.A系列楼 3.B系列楼 4.翠湖 5.体育馆n);printf(ttt6.主教楼 7.图书馆 8.田径场 9.二食堂 10.一食堂n);printf(你的选择是);scanf(%d,&len);getchar();printf(此景点的名称是:);Name(len);printf(此景点的介绍是:);Information(len);doprintf(tt是否继续? Y/N n);printf(tt你的选择是：);scanf(%c,&ch

11、);getchar();if(ch = Y | ch = y) clrscr();flag = 1;i = 1;printf(ttt请再次输入您要查询的景点序号:nn);printf(ttt1.校门口 2.A系列楼 3.B系列楼 4.翠湖 5.体育馆n); printf(ttt6.主教楼 7.图书馆 8.田径场 9.二食堂 10.一食堂n);printf(你的选择是);scanf(%d,&len);getchar();printf(此景点的名称是:);Name(len);printf(此景点的介绍是:);Information(len);continue ;elseflag = 0; prin

12、tf(tt请再次按回车键或者任意键加回车键返回至主菜单);break;while(1);void creat(Matrix_Graph *G)int i,j;for(i=1;ivexsi=i;for(i=1;i=N;i+)for(j=1;jarcsij=0;G-arcs12=50;G-arcs13=40; G-arcs14=30; G-arcs15=40; G-arcs21=50; G-arcs23=10;G-arcs26=10; G-arcs31=40; G-arcs32=10;G-arcs34=10; G-arcs36=10;G-arcs37=20; G-arcs41=30; G-arcs

13、43=10; G-arcs45=10; G-arcs47=10;G-arcs51=40; G-arcs54=10;G-arcs57=30; G-arcs58=20;G-arcs62=10;G-arcs63=10; G-arcs67=30;G-arcs69=50; G-arcs73=20; G-arcs74=10; G-arcs75=30;G-arcs76=30; G-arcs78=20; G-arcs79=40; G-arcs710=30;G-arcs85=20; G-arcs87=20; G-arcs810=20; G-arcs97=50;G-arcs98=40; G-arcs910=80;

14、G-arcs107=30;G-arcs108=20; G-arcs109=80; for(i=1;i=N;i+)for(j=1;jarcsij=0) G-arcsij=MAX;void path(Matrix_Graph *G,int s,int e)int i,j,u,c=1,t,v;int rN+1N+1;int TN,flagN,dN;for(i=0;i=N;i+)for(j=0;j=N;j+) rij=0;for(i=1;i=N;i+)Ti=-1;flagi=1;di=MAX;flags=0;while(c=N)t=MAX;for(i=1;iarcssiarcssi;v=i;rv1=v

15、;for(i=1;i=c;i+)for(j=1;jarcsTijarcsTij;v=j;if(rv0!=-1)u=1;while(rTiu!=0)rvu=rTiu;u+;rvu=v;rv0=-1;Tc=v;flagv=0;dc=t;c+;printf(n最短路径是以下这条:n(%d),s);j=1;while(rej!=0)printf(-(%d),rej);j+;printf(nn);int main()int i,j;Matrix_Graph G;creat(&G);int n = 0; vexnode gMAX; EdgeType eMAXedg; adjmax adj; char ch

16、oice = x;while(1)clrscr();printf(nnttt *校-园-导-游*);printf(ntt-nn);printf(ttt1. 陶院校园地图:nn);printf(ttt2. 陶院景点信息:nn);printf(ttt3. 查找两点间最短路径:nn);printf(ttt0. 退出nn);printf(ntt-nn);printf(tt景德镇陶瓷学院校训：崇德尚学 陶冶成器n);printf(ntt-nn);printf(tt请输入你的选择(0-3): );choice = getchar();switch(choice)case 1: clrscr();print

17、f(tt -陶-院-地-图-nn);printf( . n);printf( . . . n);printf( . . . n);printf( . . . . . n);printf( . . . . n);printf( . . . . . . n);printf( . . . . . . . n);printf( . . . . . . . n);printf( . . . . . . . n); printf( . . . . . . . . . . n);printf( . . . . . . n );printf( . . . . . . n );printf( . . . . .

18、 n );printf( . . . . . n );printf( . . . . . n );printf( . . . . . nn); printf(tt输入任意键返回菜单);getchar(); getchar();break;case 2:clrscr();travgraph(g,n,adj);getchar(); break;case 3:clrscr(); printf(tt -陶-院-地-图-nn);printf( . n);printf( . . . n);printf( . . . n);printf( . . . . . n);printf( . . . . n);pr

19、intf( . . . . . . n);printf( . . . . . . . n);printf( . . . . . . . n);printf( . . . . . . . n); printf( . . . . . . . . . . n);printf( . . . . . . n );printf( . . . . . . n );printf( . . . . . n );printf( . . . . . n );printf( . . . . . n );printf( . . . . . nn); printf(2你现在的位置是（请输入1-10）：n);printf(ttt1.校门口 2.A系列楼 3.B系列楼 4.翠湖 5.体育馆n); printf(ttt6.主教楼 7.图书馆 8.田径场 9.二食堂 10.一食堂n); printf(t你的输入是：);scanf(%d,&i);getchar();printf(2你想要去的地方是（请输入1-10）：n);printf(ttt1.校门口 2.A系列楼 3.B系列楼 4.翠