《校园导游图数据结构课程设计最终版.doc》由会员分享，可在线阅读，更多相关《校园导游图数据结构课程设计最终版.doc（51页珍藏版）》请在三一文库上搜索。
1、数据结构课程设计-校园导游系统 080910315南京航空航天大学数据结构课程设计报告校 园 导 游 系 统 班 级：0809103班学 号：080910315 姓 名： 施国义指导老师： 胡彩平评定成绩：目录一、需求分析3二、程序的主要功能3三、程序运行平台4四、系统总框架图4五、数据结构.4六、测试用例.5七、存在的不足与对策及编程体会13八、程序源代码.14一、 需求分析校园导游程序 问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。基本要求（1）
2、 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 查询图中任意两个景点间的所有路径。（4） 增加、删除、更新有关景点和道路的信息。二、程序的主要功能该校园导游程序共有7个主要功能：功能一：查询景点的信息；功能二：查询任意两景点之间的最短路径及路径长度；功能三：查询任意两景点之间的所有路线；功能四：在已有的校园导游图中添加新的景点及该景点到其他景点的路径长度；功能五：在已有的校园导游图中删除已有的景点及以该景点为端点的路径；功能六：修改已有校园导游图中的任意一个景点的名称和景点信息或任意一条路径的长度；功能七：重新创建一个新的学校的导游图。三、程序运行平台virtual
3、C+ 6.0 四、系统总框架图校园导游图查询景点信息查询最短路查询所有路径添加景点和路径删除景点和路径修改景点和路径创建新导游图程序结束 五、 数据结构该程序运用数据结构中的图的邻接表的存储方式，用顶点来存储景点的名称和景点信息等，用边来存储路径的长度等信息。之后，以有向图的邻接矩阵的方式用Dijkstra算法来求图的最短路径问题，以及图的遍历来求两点间的所有路径问题。最后，用图的添加、删除、修改等基本操作完成对校园导游图的修改和重新创建。六、测试用例 运行程序： 输入“1”：输入“1”：输入编号“3”：按任意键返回上一菜单，再选择“2、按照景点名称查询”：输入“东区”：按任意键返回后，再输入
4、“e”，返回主菜单，选择“2.、查询两景点间最短路径”，再输入起点和终点景点的序号：按任意键返回主菜单，选择“3.、查询两景点间所有路线”，再输入出发和目的景点：按任意键返回主菜单，选择“4”添加新的景点和路径，输入新的景点名称、景点信息以及该景点到其他各景点的距离：选择“5”删除景点和路径，之后可以按照景点编号或景点名称查询景点，将其删除：按任意键返回后，6号景点四号楼已经被删除，其余景点依次重新排列：选择“6”修改已有景点和路径，会出现修改景点或修改道路的选择：我们输入“1”，然后出现输入选择要修改景点的编号，修改景点名称和修改景点描述的选择，我们输入“2”修改景点描述，再输入新的景点信息
5、：返回主菜单后，行政楼的景点描述已经修改：最后，我们选择“7”创建一个新的校园导游图，然后输入新的学校名称、景点数目、道路条数，再按提示输入景点名称、景点描述、和路径。返回主菜单后，新的马鞍山第二中学导游图就已经创建成功了。之后，新的导游图可以和原本的导游图作上述的同样的操作。七、存在的不足与对策及编程体会这次的课程设计一直做了将近一周，每天都想着如何去实现各个子函数，如何将各个子函数衔接好，如何解决程序中出现的问题。虽然程序仍旧存在一些不足，但是我从中编程序的过程中得了很多收获。这次的课程设计我应用数据结构中图的存储结构，对我来说算是一件很具有挑战性。因为图是我们新接触的存储方式，掌握的并不
6、是很熟练。在编程中，总是遇到各种各样的问题，于是不得不翻书去寻找解决的方案，再加上长时间没有用C编程，很多格式都已经遗忘，只好把更早的C语言程序设计找出来去看。但是，通过翻书去寻找答案，解决问题，使我对图的掌握、对C的掌握有很大的提高。这个导游图使用的是邻接矩阵和邻接表的存储方式，在定义二维数组的时候，因为没有使用动态存储，因此不得不为景点数目设定上限。在该程序中，景点数目的上限为20个，如果景点数超过20个，则会出现内存溢出的情况。但是我们可以通过增大二维数组的维数来提高景点数目的上限。虽然出现了各种各样的问题，但最终我还是用自己的方式解决了各种问题，并完成了这次的课程设计。通过这次课程设计
7、，我知道了想编好程必须拥有充足的理论知识，只有熟练地掌握数据结构和程序设计的所有重点内容，并将其融会贯通，才能够快速地编出很好的程序。除了需要足够的知识，编程更是需要细心和耐心的事，无论遇到什么问题，只要一点一点地去寻找问题的出处，耐心地去寻找问题的解决方法，就一定能够解决问题。八、程序源代码#include string.h #include stdio.h #include stdio.h#include malloc.h#include stdlib.h#define Max 20000typedef struct ArcCell int adj; /* 相邻接的景点之间的路程 */Ar
8、cCell; /* 定义边的类型 */typedef struct VertexType int number; /* 景点编号 */ char sight100; /* 景点名称 */ char description1000; /* 景点描述 */VertexType; /* 定义顶点的类型 */typedef struct VertexType vex20; /* 图中的顶点，即为景点 */ ArcCell arcs2020; /* 图中的边，即为景点间的距离 */ int vexnum,arcnum; /* 顶点数，边数 */MGraph; /* 定义图的类型 */MGraph G;
9、/* 把图定义为全局变量 */char nameofschool100;int NUM=9;int P2020; /* */int p20;/*全局数组，用来存放路径上的各顶点*/int visited20;/*全局数组，用来记录各顶点被访问的情况*/int a=0;/*全局变量，用来记录每对顶点之间的所有路径的条数*/long int D20; /* 辅助变量存储最短路径长度 */int x20=0; void CreateUDN(int v,int a); /* 造图函数 */void narrate(); /*说明函数*/void ShortestPath(int num); /*最短路
10、径函数*/void output(int sight1,int sight2); /*输出函数*/char Menu(); /* 主菜单 */void search(); /* 查询景点信息 */char SearchMenu(); /* 查询子菜单 */void HaMiTonian(int); /* 哈密尔顿图的遍历 */void Searchpath1(MGraph g);/*查询两个景点间的所有路径*/void disppath(MGraph g,int i,int j);void path(MGraph g,int i,int j,int k);/*确定路径上第k+1个顶点的序号*/
11、void NextValue(int); void display(); /* 显示遍历结果 */int Addnewsight(int n); /*添加新的景点和路径*/int Deletesight(int n); /*删除景点和路径*/void Changesight(); /*修改景点和路径*/char Changemenu(); /*修改路径或顶点的选择菜单*/char Sightmenu(); /*选择需该景点的菜单*/void NewCreateUDN(); /*创建新的导游图*/void main() /* 主函数 */ int v0,v1; char ck; system(c
12、olor 2); CreateUDN(NUM,11); do ck=Menu(); switch(ck) case 1: search(); break; case 2: system(cls); narrate(); printf(nnttt请选择起点景点（0%d）：,NUM-1); scanf(%d,&v0); printf(ttt请选择终点景点（0%d）：,NUM-1); scanf(%d,&v1); ShortestPath(v0); /* 计算两个景点之间的最短路径 */ output(v0,v1); /* 输出结果 */ printf(nntttt请按任意键继续.n); getch
13、ar(); getchar(); break; case 3: system(cls); narrate(); x0=1; Searchpath1(G); printf(nntttt请按任意键继续.n); getchar(); getchar(); break; case4: system(cls); narrate(); NUM=Addnewsight(NUM); system(cls); narrate(); break; case5: NUM=Deletesight(NUM); break; case6: Changesight(); break; case7: NewCreateUDN
14、(); break; ; while(ck!=e); char Menu() /* 主菜单 */ char c; int flag; do flag=1; system(cls); narrate(); printf(ntttn); printf(ttt n); printf(ttt 1、查询景点信息 n); printf(ttt 2、查询两景点间最短路径 n); printf(ttt 3、查询两景点间所有路线 n); printf(ttt 4、添加新的景点和路径 n); printf(ttt 5、删除已有景点和路径 n); printf(ttt 6、修改已有景点和路径 n); printf(
15、ttt 7、创建新的校园导游图 n); printf(ttt e、退出 n); printf(ttt n); printf(tttn); printf(tttt请输入您的选择：); scanf(%c,&c); if(c=1|c=2|c=3|c=4|c=5|c=6|c=7|c=e) flag=0; while(flag); return c;char SearchMenu() /* 查询子菜单 */ char c; int flag; do flag=1; system(cls); narrate(); printf(ntttn); printf(ttt n); printf(ttt 1、按照景
16、点编号查询 n); printf(ttt 2、按照景点名称查询 n); printf(ttt e、返回 n); printf(ttt n); printf(tttn); printf(tttt请输入您的选择：); 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; do system(cls); c=SearchMenu(); switch (c) case 1: system(cls); narra
17、te(); 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
18、(cls); narrate(); printf(nntt请输入您要查找的景点名称：); scanf(%s,name); for(i=0;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(); b
19、reak; while(c!=e);void CreateUDN(int v,int a) /* 造图函数 */ int i,j; strcpy(nameofschool,南京航空航天大学); G.vexnum=v; /* 初始化结构中的景点数和边数 */ G.arcnum=a; for(i=0;i20;+i) G.vexi.number=i; /* 初始化每一个景点的编号 */ /* 初始化每一个景点名及其景点描述 */ strcpy(G.vex0.sight,大西门); strcpy(G.vex0.description,学校正门，破旧的直升机。); strcpy(G.vex1.sight
20、,行政楼); strcpy( G.vex1.description,老师们的办公场所。); strcpy(G.vex2.sight,一号楼); strcpy(G.vex2.description,南航主楼，南航最高建筑。); strcpy(G.vex3.sight,理学院大楼); strcpy(G.vex3.description,理学院的院楼); strcpy(G.vex4.sight,二号楼); strcpy(G.vex4.description,教室); strcpy(G.vex5.sight,三号楼); strcpy(G.vex5.description,电子工程训练中心); strc
21、py(G.vex6.sight,四号楼); strcpy(G.vex6.description,考试专用教室); strcpy(G.vex7.sight,慧园); strcpy(G.vex7.description,南航最老最差的宿舍楼); strcpy(G.vex8.sight,东区); strcpy(G.vex8.description,南航最新最好的宿舍楼); /* 这里把所有的边假定为20000，含义是这两个景点之间是不可到达 */ for(i=0;i20;+i) for(j=0;j20;+j) G.arcsij.adj=Max; /* 下边是可直接到达的景点间的距离，由于两个景点间距
22、离是互相的， 所以要对图中对称的边同时赋值。 */ G.arcs01.adj=G.arcs10.adj=50; G.arcs13.adj=G.arcs31.adj=200; G.arcs06.adj=G.arcs30.adj=300; G.arcs14.adj=G.arcs41.adj=150; G.arcs24.adj=G.arcs42.adj=100; G.arcs35.adj=G.arcs53.adj=200; G.arcs52.adj=G.arcs25.adj=100; G.arcs46.adj=G.arcs64.adj=75; G.arcs47.adj=G.arcs74.adj=30
23、0; G.arcs27.adj=G.arcs72.adj=600; G.arcs78.adj=G.arcs87.adj=200;void narrate() /* 说明函数 */ int i,k=0; printf(nt*欢迎使用%s校园导游程序*n,nameofschool); printf(t_n); printf(tt景点名称tttt景点描述tttn); printf(t_|_n); for(i=0;iNUM;i+) printf(t%c (%2d)%-10stt|t%-25s%cn,3,i,G.vexi.sight,G.vexi.description,3); /* 输出景点列表 */
24、 k=k+1; printf(t_|_n);void ShortestPath(int num) /* 迪杰斯特拉算法最短路径函数 num为入口点的编号 */ int v,w,i,t; /* i、w和v为计数变量 */ int final20; /* */ int min; for(v=0;vNUM;v+) finalv=0; /* 假设从顶点num到顶点v没有最短路径 */ Dv=G.arcsnumv.adj;/* 将与之相关的权值放入D中存放 */ for(w=0;wNUM;w+) /* 设置为空路径 */ Pvw=0; if(Dv20000) /* 存在路径 */ Pvnum=1; /*
25、 存在标志置为一 */ Pvv=1; /* 自身到自身 */ Dnum=0; finalnum=1; /* 初始化num顶点属于S集合 */ /* 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 */ for(i=0;iNUM;+i) /* 其余G.vexnum-1个顶点 */ min=Max; /* 当前所知离顶点num的最近距离 */ for(w=0;wNUM;+w) if(!finalw) /* w顶点在v-s中 */ if(Dwmin) /* w顶点离num顶点更近 */ v=w; min=Dw; finalv=1; /* 离num顶点更近的v加入到s集合 */
26、for(w=0;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的最
27、短路径是,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.si
28、ght); /* 输出此节点的名称 */ q=q+1; /* 计数变量加一，满8控制输出时的换行 */ Pab=0; d=b; /* 将b作为出发点进行下一次循环输出，如此反复 */ if(q%8=0) printf(n); goto gate; void Searchpath1(MGraph g)/*查询两个景点间的所有路径*/int l=0;int k=0;int i,j; printf(选择出发景点：); scanf(%d,&i); printf(选择目地景点：); scanf(%d,&j); for(;kg.vexnum;k+)/*g.vexnumber表示网中的顶点个数*/ if(i
29、=g.vexk.number) i=k;/*在网中找到其编号与输入的出发景点的编号相同的顶点*/ for(;lg.vexnum;l+) if(j=g.vexl.number) j=l;/*在网中找到其编号与输入的目地景点的编号相同的顶点*/ printf(n从%s到%s的所有游览路径有:nn,g.vexi.sight,g.vexj.sight);/*输出出发景点和目地景点的名称*/ disppath(g,i,j);/*调用disppath函数,用来输出两个景点间的所有路径*/void disppath(MGraph g,int i,int j)int k;p0=i;for(k=0;kg.vex
30、num;k+)visitedi=0;/*初始化各顶点的访问标志位，即都为未访问过的*/a=0;/*初始化路径的条数*/path(g,i,j,0);/*通过调用path函数，找到从vi到vj的所有路径并输出*/void path(MGraph g,int i,int j,int k)/*确定路径上第k+1个顶点的序号*/int s;if(pk=j)/*找到一条路径*/a+;/*路径的条数值加1*/printf(第%d条:t,a);for(s=0;s);/coutg.vexps.sight;printf(%sn,g.vexps.sight); s=0;while(sg.vexnum)if(s!=i
31、)/*保证找到的是简单路径*/if(g.arcspks.adj!=Max&visiteds=0)/*当vk与vs之间有边存在且vs未被访问过*/visiteds=1;/*置访问标志位为1,即已访问的*/pk+1=s;/*将顶点s加入到p数组中*/ path(g,i,j,k+1);/*递归调用之*/ visiteds=0;/*重置访问标志位为0，即未访问的，以便该顶点能被重新使用*/s+;int Addnewsight(int n)int i;char sight100,description1000;int length;printf(请输入新景点的名称：n);scanf(%s,&sight)
32、;printf(请输入新景点的相关信息：n);scanf(%s,&description);strcpy(G.vexn.sight,sight); strcpy(G.vexn.description,description);G.vexn.number=n;for(i=0;in;i+) system(cls); narrate();printf(请输入此景点到第%d个景点的距离（单位：m）（同一景点或不可到达用20000表示）：n,i);scanf(%d,&length);if(length!=20000)G.arcnum+;G.arcsni.adj=G.arcsin.adj=length;n
33、+;G.vexnum+;return n;int Deletesight(int n)int i;int j;char c;int num;char name20;system(cls); c=SearchMenu(); switch (c) case 1: system(cls); narrate(); printf(nntt请输入您要删除景点的编号：); scanf(%d,&num); for(i=0;iNUM;i+) if(num=G.vexi.number) for(j=0;jNUM;j+) if(G.arcsij.adj!=20000) G.arcnum-; G.arcsij.adj
34、=G.arcsji.adj=20000; for(;numNUM;num+)strcpy(G.vexnum.sight,G.vexnum+1.sight);strcpy(G.vexnum.description,G.vexnum+1.description); n-; printf(nttt按任意键返回.); getchar(); getchar(); break; if(i=NUM) printf(nnttt没有找到！); printf(nnttt按任意键返回.); getchar(); getchar(); break; case 2: system(cls); narrate(); pr
35、intf(nntt请输入您要删除景点的名称：); scanf(%s,name); for(i=0;iNUM;i+) if(!strcmp(name,G.vexi.sight) num=i; for(j=0;jNUM;j+) if(G.arcsij.adj!=20000) G.arcnum-;G.arcsij.adj=G.arcsji.adj=20000; for(;numNUM;num+) strcpy(G.vexnum.sight,G.vexnum+1.sight); strcpy(G.vexnum.description,G.vexnum+1.description); n-; printf(nttt按任意键返回.); getchar(); getchar(); break;