校园导航系统课程设计报告材料

1、题目石铁大校园导航系统学院信息科学与技术学院专业计算机科学与技术学号 20112840学生姓名铸辉指导教师娜日期： 2013-8-31题目与要求实习一校园导游程序 问题描述 用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号 、 名 称 、 简介等信息 ， 图中的边表示景点间的道路 ， 存放路径长度等信息 。 要求能够回 答有关景点介绍、游览路径等问题。 游客通过终端可询问：（ 1 ）从某一景点到另一景点的最短路径 。（ 2 ）游客从公园进入，选取一条最佳路线 。（ 3 ） 使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边） 。 基本 要求 （ 1 ）将导游图看

2、作一带权无向图，顶点表示公园的各个景点，边表示各景点之间的 道路，边上的权值表示距离为此图选择适当的数据结构 。（ 2 ）把各种路径都显示给游客，由游客自己选择浏览路线 。（ 3 ）画出景点分布图于屏幕上 。 实现提示 （ 1 ）构造一个无向图 G 并用邻接矩阵来存储。（ 2 ）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组 pi 来记录，最短路径长度就用一维数组di存放；i的围：020。（ 3 ）一维数组 have 是用来记录最短路径出现顶点的顺序。（ 4 ）根据起点和终点输出最短路径和路径长度。需求分析本校园导航系统由C语言编写，主要掌握最短路径的实现方法，以及构造无 向

3、图G并用邻接矩阵来存储，掌握迪杰斯特拉算法来算最短路径。1. 输入的形式和输出的围：2. 输出的形式：3. 程序所能到达的功能：A. 图中任意景点的相关信息查询B. 任意两个景点间的最短路径C. 任意两个景点间的所有路径D. 增加有关景点和道路的信息E删除更新有关景点和道路的信息F. 更新有关景点和道路的信息G. 显示全景H. 退出该系统(1) 本程序包含了 10个函数三.概要设计主函数main()显示操作菜单函数 menu()景点名称及其简介设置函数picture(void) 图中任意景点相关信息查询函数checksce ne(algraph g)图中任意两个景点间的最短路径Dijkstra

4、(algraph g)alldista nce(algraph g) addsce ne(algraph g) delsce ne(algraph g) cha nge(algraph g)(2) 各函数之间的关系menupictmai n()chang()任意两个景点间的全部路径 增加有关景点和道路的信息 删除有关景点和道路的信息 更新有关景点和道路的信息 显示全景chang()cene(algraph g)h g)lldista nce(algraph g) addsce ne(algraph g) raph g) cha nge(algraph g)四.详细设计实现概要设计中定义的所有的

5、数据类型，对每个操作给出伪代码，对主程序 和其他模块也都需要写出伪代码算法。(1)结点类型和指针类型typedef struct int adj;int *info;sce neinfo;typedef struct adjlistint num;char *sight;char *description;adjlist;typedef struct algraphadjlist verMAXNUM;sceneinfo arcsMAXNUMMAXNUM; int vexnum,arcnum; algraph; (2)图的基本操作 主菜单 / 主菜单 int menu(void) int i;p

6、rintf（"n 欢 迎 来 到 莱 震 德 瑞 hui 校 园 导 航 系统!n"）;printf（"1. 图中任意景点的相关信息查寻 n"）;printf（"2.任意两个景点间的最短路径n"）;printf（"3.任意两个景点间的所有路径n"）;printf（"4.增加有关景点和道路的信息n"）;printf（"5. 删除更新有关景点和道路的信息 n"）;printf（"6.更新有关景点和道路的信息n"）;printf（"7.显示全景 n &

7、quot;）;printf（"8.退出该系统 n "）;printf（" 让 辉 哥 带 大 家 在 铁 道 大 学 翱 翔吧!n"）;printf(" 请输入你要进行的操作： "); scanf("%d",&i);return(i); 景点名称及其简介void picture(void) int i,j;m.vexnum=11;m.arcnum=16;for(i=0;i<m.vexnum;i+)m.veri.num=i;m.ver0.sight="xiaomen"m.ver1.s

8、ight="学校大门，一教 "m.ver2.sight="图书馆 "m.ver3.sight="操场 "m.ver4.sight="体育馆 "m.ver5.sight="青春苑 "m.ver6.sight="办公楼 "m.ver7.sight="第一实验楼 "m.ver8.sight="第九实验楼 "m.ver9.sight="第九宿舍楼 "m.ver10.sight="家属院 "m.ver1.d

9、escription="m.ver2.description="m.ver3.description="m.ver4.description="进入学校大门就可以看见一教， 一教西面是二教和三教 " 自习和阅读的心灵家园，后身是第二实验楼 跑道和足球场 " 室篮球场和游泳场 "m.ver5.description="学生活动中心和综合餐厅 "m.ver6.description="m.ver7.description="m.ver8.description="办公中心，包括开

10、元楼和春晖楼挨着医院和综合教学楼，物理实验 计算机和电工实验，西邻机械学院m.ver9.description="m.ver10.description="生活区中心，西邻超市水房澡堂，东临一，二三食堂 教职工住处，在学校最北面for(i=0;i<m.vexnum;+i)for(j=0;j<m.vexnum;+j)m.arcsij.adj=INF;m.arcs12.adj=m.arcs21.adj=100;m.arcs13.adj=m.arcs31.adj=300;m.arcs26.adj=m.arcs62.adj=500;m.arcs35.adj=m.arcs

11、53.adj=600;m.arcs14.adj=m.arcs41.adj=220;m.arcs45.adj=m.arcs54.adj=600;m.arcs49.adj=m.arcs94.adj=450;m.arcs46.adj=m.arcs64.adj=650;m.arcs57.adj=m.arcs75.adj=300;m.arcs68.adj=m.arcs86.adj=600;m.arcs109.adj=m.arcs910.adj=100;m.arcs710.adj=m.arcs107.adj=250;m.arcs79.adj=m.arcs97.adj=280;m.arcs89.adj=m.

12、arcs98.adj=400;m.arcs84.adj=m.arcs48.adj=100; 图中任意景点相关信息查询 void checkscene(algraph g) int i,j;char ch; while(1) sceneplace(); printf(" 请输入你要查询的景点的编号 :");scanf("%d",&i);if(i>p | i<0) printf(" 输入错误！ n"); elsefor(j=0;j<=p;j+) if(i=j)n"); printf(" 你要查

13、询的景点的相关信息如下： printf("%dtt%sn",g.veri.num,g.veri.sight); printf("%sn",g.veri.description); printf(" 是否继续查询 ?(y|n):");scanf("%s",&ch); if(ch='N'|ch='n') break; 图中任意两个景点间的最短路径 void Dijkstra(algraph g) char ch;int path1MAXNUM;int distMAXNUM;int

14、 sMAXNUM;int mindis,i,j,u,n=p;int l,k;int v0,po;while(1)sceneplace();printf(" 请输入出发景点的序号： "); scanf("%d",&v0);printf(" 请输入目的景点的序号： "); scanf("%d",&po);for(i=0;i<n;i+) disti=g.arcsv0i.adj; si=0;if(g.arcsv0i.adj!=INF) path1i=v0;elsepath1i=-1;sv0=1;pat

15、h1v0=0; for(i=0;i<n;i+) mindis=INF;u=-1;for(j=0;j<n;j+)if(sj=0 && distj < INF) u=j;mindis=distj;su=1;for(j=0;j<n;j+) if(sj=0)INF&&if(g.arcsuj.adj < distu+g.arcsuj.adj<distj) distj=distu+g.arcsuj.adj; path1j=u; dispath(g,dist,path1,s,n,v0,po);printf("n 是否继续查询 ?(

16、y|n):"); scanf("%s",&ch);if(ch='N'|ch='n')break; 任意两个景点间的全部路径 void path(algraph g,int i,int j,int k) int s,ko;if(rk=j)a+;printf(”第 條:",a);for(s=0;s<=k-1;s+)printf("%s",g.verrs.sight);printf("->"); printf("%sn",g.verrs.sight)

17、; s=0; while(s<g.vexnum)if(s!=i) ko=rk;if(g.arcskos.adj != INF && visiteds=0) visiteds=1; rk+1=s;path(g,i,j,k+1); visiteds=0; s+; void alldistance(algraph g) int i,j,k,l;char sh; while(1) sceneplace();printf("n请选择出发景点的序号：");scanf("%d",&i);printf("n请选择目地景点的序号：&

18、quot;);scanf("%d",&j);for(k=0;k<g.vexnum;k+) if(i=g.verk.num) i=k;for( l=0;l<g.vexnum;l+)if(j=g.verl.num) j=l;prin tf(”从$到 s 的所有游览路径有：n",g.veri.sight,g.verj.sight);r0=i;for(k=0;k<1;k+) visitedi=0;a=0;path(g,i,j,0);printf(" 继续查询 ?(y|n)："); scanf("%s",&a

19、mp;sh);if(sh='N'|sh='n')break; 增加有关景点和道路的信息void addscene(algraph g)int j,i,b;char yi,mon10,moh100;while(1) sceneplace();g.verp.num=p;printf(" 请输入新景点的名称： ");scanf("%s",mon);m.verp.sight=(char*)malloc(10); strcpy(m.verp.sight,mon);printf("n 请输入新景点的相关简介： ")

20、; scanf("%s",moh);m.verp.description=(char*)malloc(100); strcpy(m.verp.description,moh);g.vexnum=g.vexnum+1;for(j=0;j<p;+j) m.arcspj.adj=INF;m.arcsjp.adj=INF;printf("n请问有几个景点与该景点直接相通： ");scanf("%d",&i);printf("n请输入与该景点相通的景点的序号及它们之间的距离：");for(j=0;j<i;

21、j+) printf("n请输入第d个景点的序号：",j+1);scanf("%d",&b);printf("n请输入该两个景点之间的距离： ");scanf("%d",&g.arcspb.adj);g.arcsbp.adj=g.arcspb.adj;m.arcsbp.adj=g.arcspb.adj; m.arcspb.adj=m.arcsbp.adj;printf(" 你输入的景点信息是： n");printf("%dt%st%snng.verp.num,m.ver

22、p.sight,m.verp.description);g.arcnum=g.arcnum+i;p=p+1;m.vexnum=p;sceneplace();printf(" 是否继续添加 ?(y|n)：");scanf("%s",&yi);if(yi='N'|yi='n')break; 删除有关景点和道路的信息void delscene(algraph g) int i,j,k,l;char sh;while(1)sceneplace();printf("n 请输入你将要删除的景点序号 :");

23、 scanf("%d",&i);for(k=0;k<g.vexnum;k+)if(i=g.verk.num) j=k; m.verj.sight=NULL;for(l=1;l<m.vexnum;+l) m.arcslj.adj=INF; m.arcsjl.adj=INF; m.vexnum=m.vexnum-1; sceneplace();printf(" 删除继续 ?(y|n):"); scanf("%s",&sh);if(sh='N'|sh='n')break; 更新有关

24、景点和道路的信息void change(algraph g) int i,b,j,th,fh,k;char sh,mon10,moh100;while(1) sceneplace();printf(" 请输入你将要修改信息的景点序号 :"); scanf("%d",&i);for(k=0;k<g.vexnum;k+)if(i=g.verk.num) j=k;printf("n");printf("1. 景点名称 t2. 景点简介 t3. 道路消息 n"); printf("n");

25、printf(" 请输入你要进行的操作的序号： "); scanf("%d",&th);switch(th) case 1:printf(" 请输入新景点名称： "); scanf("%s",mon);g.verj.sight=mon;m.verj.sight=g.verj.sight;break;case 2:printf(" 请输入新景点简介： ");scanf("%s",moh); m.verj.description=(char*)malloc(100);st

26、rcpy(m.verj.description,moh);break;case 3:printf(" 请输入要修改的与该景点相通的景点的距离的序号个数： "); scanf("%dn",&fh);for(k=0;k<fh;k+) printf(”请输入要修改的第d个景点的序号：",j+1);scanf("%dn",&b);printf(" 请重新输入该两个景点之间的距离： ");scanf("%d",&m.arcsjb.adj);m.arcsbj.adj=

27、m.arcsjb.adj;sceneplace();printf(" 继续修改 ?(y|n)：");scanf("%s",&sh);if(sh='N'|sh='n')break; 显示全景略 主函数int main()picture();printf("n 校 园 导 航 系 统n");sceneplace();for(;)switch(menu() case 1：checkscene(m);break;case 2：Dijkstra(m);break;case 3:alldistance(m)

28、;break;case 4:addscene(m);break;case 5:delscene(m);break;case 6:change(m);break;case 7:chang(m);break;case 8:printf("感你使用辉哥校园导航系统 ! 辉哥又一次带大家拯救了世界 ! 再见 !n");exit(0);default:printf(" 输入错误 ! 请重新输入你要进行的操作 !n");五调试分析在调试删除修改功能过程中，删除的总是不正确，删除的结果显示，没有将 要删除的景点删掉， 最后发现删除的结点不正确， 删除应该与输入的值和头

29、结点 next 比较，而不是头结点。还有就是删除结点不知道如何循环，最后又看看了 记得笔记和书，才知道如何继续删除而不出错误。六使用说明进入校园导航系统，首先看到的就是用户欢迎界面，然后根据提示：1. 图中任意景点的相关信息查寻； 2.任意两个景点间的最短路径； 3. 任意两个景点间的 所有路径； 4.增加有关景点和道路的信息； 5. 删除更新有关景点和道路的信息； 6.更新有关景点和道路的信息 7.显示全景； 8.退出该系统如 1，图中任意景点的相关信息查寻。 根据本系统提供的 10 个景点， 输入景 点编号，可以得到景点信息和景点介绍；如 2 ，任意两个景点间的最短路径。提示依次输入出发景

30、点序号和目的景点 序号，录入完毕后，按回车输出最短游览路径，以及路径长度，并提示是否继续 查询；如 3 ，任意两个景点间的所有路径。提示依次输入出发景点序号和目的景点序号，录入完毕后，按回车输出所有游览路径，并记数路径条数，最后提示是否 继续查询；如4，增加有关景点和道路的信息。提示依次输入 1.新景点的名称；2新景 点相关简介；3.有几个景点与该景点相通；4.依次输入相通景点的序号和两个景 点间的距离，添加成功后，提示是否继续添加。如5,删除有关景点和道路的信息，会提示要删除景点的编号；如6,更新有关景点和道路的信息，可以更新有关景点和道路的信息；如7,显示全景。显示铁道大学的平面图。如8,

31、退出该系统。退出校园导航系统。七.调试结果及部分截图1.进入主界面，校园导航系统。 # # # #4* Ml#H-* Is M- -NH-«4- -K欢世光临石嶺宦抵週天学* vvvt f *r*anrh b iJBSSW切知Ifl1户喝$=12.图中任意景点的相关信息查询44*MMJI-r=i!7sr.Ql*T4怎門四凹点天 4 «fl杠 IKEVI 剤点整?< *歩蠡-山婀哥带产辭片耳穿n说in丈豈斡73图中任意两个景点的最短路径丹.盯，=.!=社和-;-r.UH-r:*.* "还A? nI2j<6t7e-社is哥带灯陆石宝庄俅道大孝輝弭眄1卡十一,4任意两个景点间的所有路径檯陕ME 亍r-.:4誉 -铝r-Bi螫卿九忙一鱼一一->->-L->>->一 44 -卫nn* 弓 霍；->1樓K Mr朝 篇.二陀冗 雷一ZT 1严HT -I A > 二 V:. 1-LA 1补 V->M.1;<底匡贬T':rR4.變 烛帚经亠二罷R丄e .K->&g