校园导游程序

1、洛 阳 理 工 学 院课 程 设 计 报 告 课程名称 数据结构课程设计 题 目 校园导游程序 课 程 设 计 任 务 书1、设计题目： 校园导游程序 2、设计内容与要求：问题描述用无向网表示你所在学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号、名称、简介等信息，图中的边表示景点间的道路，存放路径长度等信息。要求能够回答有关景点介绍、游览路径等问题。基本要求 （1） 查询各景点的相关信息；（2） 查询图中任意两个景点间的最短路径。（3） 查询图中任意两个景点间的所有路径。（4） 增加、删除、更新有关景点和道路的信息。课 程 设 计 评 语 成绩： 指导教师：_ 年 月 日洛 阳 理

2、 工 学 院 课 程 设 计 报 告3、 流程图校园导游图删除景点和路径添加景点和路径查询所有路径查询最短路径查询景点信息修改景点和路径结 束 4、模块划分（1）主函数：void main( )（2）void CreateUDN(int v,int a); /* 造图函数 */（3）void narrate(); /*说明函数*/（4）void ShortestPath(int num); /*最短路径函数*/（5）void output(int sight1,int sight2); /*输出函数*/（6）char Menu(); /* 主菜单 */（7）void search(); /*

3、查询景点信息 */（8）char SearchMenu(); /* 查询子菜单 */（9）void HaMiTonian(int); /*图的遍历 */（10）void Searchpath1(MGraph g);/*查询两个景点间的所有路径*/（11）void disppath(MGraph g,int i,int j);（12）void path(MGraph g,int i,int j,int k);/*确定路径上第k+1个顶点的序号*/（13）void NextValue(int); （14）void display(); /* 显示遍历结果 */（15）int Addnewsight

4、(int n); /*添加新的景点和路径*/（16）int Deletesight(int n); /*删除景点和路径*/5、数据结构类型定义typedef struct ArcCell int adj; /* 相邻接的景点之间的路程 */ArcCell; /* 定义边的类型 */ typedef struct VertexType int number; /* 景点编号 */ char sight100; /* 景点名称 */ char description1000; /* 景点描述 */VertexType; /* 定义顶点的类型 */typedef struct VertexType

5、vex20; /* 图中的顶点，即为景点 */ ArcCell arcs2020; /* 图中的边，即为景点间的距离 */ int vexnum,arcnum; /* 顶点数，边数 */MGraph; /* 定义图的类型 */6、测试结果1、查询景点信息2、 查询两景点间最短路径 3、查询两景点间所有路径4、添加新的景点和路径5、删除已有的景点和路径6、修改删除已有的景点和路径7、 实验心得经过几天的课程设计，总的来说收获还是很大的！首先代码能力明显提高，有了想法基本都能顺利表达出来；再者就是数据结构的选择使用能力也有了很大的提高！虽说平时的实验课我们也有用各种数据做题，但那些都是很明确的知道

6、该做什么操作，存什么，我们的发挥空间不大一般照做就行，然而这次实习我们却在自主的选择判断，这本身就是一个很大的提高！还有就是算法方面的学习有了初步进阶，如最短路径，这样比较简单的图论算法能比较熟练的写出来。但是还是有很多的只是不了解！收获真的很多，但是最大的收获可能就是对编程的兴趣吧，在一次次的改错，一次次的完成想要的效果后，越写越有感觉！当然还收获了无知，更确切的说是自知，原来我们现在什么也不算，还有很多有用的只是等着我们去学习！课程设计是把我们所学的理论知识进行系统的总结并应用于实践的良好机会，有利于加强我们用知识理论来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论

7、知识，深化了对知识的认识，并为走向社会打下一个良好的基础。8、 源程序#include <string.h> #include <stdio.h> #include <stdio.h>#include <malloc.h>#include <stdlib.h>#define Max 20000typedef struct ArcCellint adj; /* 相邻接的景点之间的路程 */ArcCell; /* 定义边的类型 */typedef struct VertexTypeint number; /* 景点编号 */ char s

8、ight100; /* 景点名称 */ char description1000; /* 景点描述 */VertexType; /* 定义顶点的类型 */typedef structVertexType vex20; /* 图中的顶点，即为景点 */ ArcCell arcs2020; /* 图中的边，即为景点间的距离 */ int vexnum,arcnum; /* 顶点数，边数 */MGraph; /* 定义图的类型 */MGraph G; /* 把图定义为全局变量 */char nameofschool100;int NUM=9;int P2020; /* */int p20;/*全局数

9、组，用来存放路径上的各顶点*/int visited20;/*全局数组，用来记录各顶点被访问的情况*/int a=0;/*全局变量，用来记录每对顶点之间的所有路径的条数*/long int D20; /* 辅助变量存储最短路径长度 */int x20=0; void CreateUDN(int v,int a); /* 造图函数 */void narrate(); /*说明函数*/void ShortestPath(int num); /*最短路径函数*/void output(int sight1,int sight2); /*输出函数*/char Menu(); /* 主菜单 */void

10、 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个顶点的序号*/void NextValue(int); void display(); /* 显示遍历结果 */int Addnewsight(int n); /*添加新的

11、景点和路径*/int Deletesight(int n); /*删除景点和路径*/void Changesight(); /*修改景点和路径*/char Changemenu(); /*修改路径或顶点的选择菜单*/char Sightmenu(); /*选择需该景点的菜单*/void main() /* 主函数 */ int v0,v1; char ck; system("color 0"); CreateUDN(NUM,11); do ck=Menu(); switch(ck)case '1': search(); break; case '2&

12、#39;: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"); getchar

13、(); getchar();break; case '3':system("cls"); narrate(); x0=1; Searchpath1(G); printf("nntttt请按任意键继续.n"); getchar(); getchar(); break;case'4': system("cls"); narrate(); NUM=Addnewsight(NUM); system("cls"); narrate(); break;case'5': NUM=D

14、eletesight(NUM); break;case'6':Changesight(); 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");

15、 printf("ttt 3、查询两景点间所有路线 n"); printf("ttt 4、添加新的景点和路径 n"); printf("ttt 5、删除已有景点和路径 n"); printf("ttt 6、修改已有景点和路径 n"); printf("ttt e、退出 n"); printf("ttt n"); printf("tttn"); printf("tttt请输入您的选择："); scanf("%c",&a

16、mp;c); if(c='1'|c='2'|c='3'|c='4'|c='5'|c='6'|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("

17、;ttt 1、按照景点编号查询 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

18、() /* 查询景点信息 */ int num; int i; char c; char name20; do system("cls"); c=SearchMenu(); switch (c) case '1': system("cls"); narrate(); printf("nntt请输入您要查找的景点编号："); scanf("%d",&num); for(i=0;i<NUM;i+) if(num=G.vexi.number) printf("nnttt您要查找景点

19、信息如下:"); 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"); narrate(); printf("

20、;nntt请输入您要查找的景点名称："); scanf("%s",name); for(i=0;i<NUM;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没有找到！");

21、 printf("nnttt按任意键返回."); getchar(); getchar(); break; while(c!='e');void CreateUDN(int v,int a) /* 造图函数 */ int i,j; strcpy(nameofschool,"洛阳理工学院"); G.vexnum=v; /* 初始化结构中的景点数和边数 */ G.arcnum=a;for(i=0;i<20;+i) G.vexi.number=i; /* 初始化每一个景点的编号 */ /* 初始化每一个景点名及其景点描述 */ strcp

22、y(G.vex0.sight,"东门"); strcpy(G.vex0.description,"学校正门，图书馆。"); strcpy(G.vex1.sight,"图书馆"); strcpy( G.vex1.description,"藏书100万册，环境优雅"); strcpy(G.vex2.sight,"教学楼"); strcpy(G.vex2.description,"学生上课的地方"); strcpy(G.vex3.sight,"子衿餐厅"); s

23、trcpy(G.vex3.description,"一餐厅，新装修过的豪华餐厅"); strcpy(G.vex4.sight,"实验A楼"); strcpy(G.vex4.description,"办公室"); strcpy(G.vex5.sight,"B楼"); strcpy(G.vex5.description,"机房"); strcpy(G.vex6.sight,"C楼"); strcpy(G.vex6.description,"电气实验教室");

24、strcpy(G.vex7.sight,"璞院餐厅"); strcpy(G.vex7.description,"二餐厅"); strcpy(G.vex8.sight,"璞院"); strcpy(G.vex8.description,"男生的宿舍楼"); /* 这里把所有的边假定为20000，含义是这两个景点之间是不可到达 */ for(i=0;i<20;+i) for(j=0;j<20;+j) G.arcsij.adj=Max; /* 下边是可直接到达的景点间的距离，由于两个景点间距离是互相的， 所以要

25、对图中对称的边同时赋值。 */ G.arcs01.adj=G.arcs10.adj=50; G.arcs13.adj=G.arcs31.adj=70; G.arcs06.adj=G.arcs30.adj=250; G.arcs14.adj=G.arcs41.adj=80; G.arcs24.adj=G.arcs42.adj=100; G.arcs35.adj=G.arcs53.adj=90; G.arcs52.adj=G.arcs25.adj=100; G.arcs46.adj=G.arcs64.adj=75; G.arcs47.adj=G.arcs74.adj=300; G.arcs27.a

26、dj=G.arcs72.adj=400; G.arcs78.adj=G.arcs87.adj=40;void narrate() /* 说明函数 */ int i,k=0; printf("nt*欢迎使用%s校园导游程序*n",nameofschool); printf("t_n"); printf("tt景点名称tttt景点描述tttn"); printf("t_|_n"); for(i=0;i<NUM;i+) printf("t%c (%2d)%-10stt|t%-25s%cn",3,

27、i,G.vexi.sight,G.vexi.description,3); /* 输出景点列表 */ 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;v<NUM;v+) finalv=0; /* 假设从顶点num到顶点v没有最短路径 */ Dv=G.arcsnumv.adj;/* 将与之相关的权值放入D中存放 */ for(w

28、=0;w<NUM;w+) /* 设置为空路径 */ Pvw=0; if(Dv<20000) /* 存在路径 */ Pvnum=1; /* 存在标志置为一 */ Pvv=1; /* 自身到自身 */ Dnum=0; finalnum=1; /* 初始化num顶点属于S集合 */ /* 开始主循环，每一次求得num到某个顶点的最短路径，并将其加入到S集合 */ for(i=0;i<NUM;+i) /* 其余G.vexnum-1个顶点 */ min=Max; /* 当前所知离顶点num的最近距离 */ for(w=0;w<NUM;+w) if(!finalw) /* w顶点在

29、v-s中 */ if(Dw<min) /* w顶点离num顶点更近 */ v=w; min=Dw; finalv=1; /* 离num顶点更近的v加入到s集合 */ for(w=0;w<NUM;+w) /* 更新当前最短路径极其距离 */ if(!finalw&&(min+G.arcsvw.adj)<Dw)/* 不在s集合，并且比以前所找到的路径都短就更新当前路径 */ Dw=min+G.arcsvw.adj; for(t=0;t<NUM;t+) Pwt=Pvt; Pww=1; void output(int sight1,int sight2) /*

30、输出函数 */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); /* 输出景点

31、一的名称 */ d=sight1; /* 将景点一的编号赋值给d */ for(c=0;c<NUM;+c) gate:; /* 标号，可以作为goto语句跳转的位置 */ Pasight1=0; for(b=0;b<NUM;b+) if(G.arcsdb.adj<20000&&Pab) /* 如果景点一和它的一个临界点之间存在路径且最短路径 */ printf("->%s",G.vexb.sight); /* 输出此节点的名称 */ q=q+1; /* 计数变量加一，满8控制输出时的换行 */ Pab=0; d=b; /* 将b作为出

32、发点进行下一次循环输出，如此反复 */ 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(;k<g.vexnum;k+)/*g.vexnumber表示网中的顶点个数*/ if(i

33、=g.vexk.number) i=k;/*在网中找到其编号与输入的出发景点的编号相同的顶点*/ for(;l<g.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=

34、i;for(k=0;k<g.vexnum;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<=k-1;s+)/*输出一条路径*/printf("%s"

35、,g.vexps.sight);printf("->");/cout<<g.vexps.sight;printf("%sn",g.vexps.sight); s=0;while(s<g.vexnum)if(s!=i)/*保证找到的是简单路径*/if(g.arcspks.adj!=Max&&visiteds=0)/*当vk与vs之间有边存在且vs未被访问过*/visiteds=1;/*置访问标志位为1,即已访问的*/pk+1=s;/*将顶点s加入到p数组中*/ path(g,i,j,k+1);/*递归调用之*/ vi

36、siteds=0;/*重置访问标志位为0，即未访问的，以便该顶点能被重新使用*/s+;int Addnewsight(int n)int i;char sight100,description1000;int length;printf("请输入新景点的名称：n");scanf("%s",&sight);printf("请输入新景点的相关信息：n");scanf("%s",&description);strcpy(G.vexn.sight,sight); strcpy(G.vexn.descript

37、ion,description);G.vexn.number=n;for(i=0;i<n;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+;G.vexnum+;return n;int Deletesight(int n)int i;int

38、 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;i<NUM;i+) if(num=G.vexi.number) for(j=0;j<NUM;j+) if(G.arcsij.adj!=20000) G.arc

39、num-; G.arcsij.adj=G.arcsji.adj=20000; for(;num<NUM;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按任意键返回."); getch

40、ar(); getchar(); break; case '2': system("cls"); narrate(); printf("nntt请输入您要删除景点的名称："); scanf("%s",name); for(i=0;i<NUM;i+) if(!strcmp(name,G.vexi.sight) num=i; for(j=0;j<NUM;j+) if(G.arcsij.adj!=20000) G.arcnum-;G.arcsij.adj=G.arcsji.adj=20000; for(;num&

41、lt;NUM;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; return n;char Changeme

42、nu()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 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;char Sightmenu()char c;int flag;doflag=1;system("cls"); narrate(); printf("ntttn"); printf("ttt n"); printf("ttt 1、修改景点名称 n"); printf