校园导航系统课程设计报告.doc

题 目 石铁大校园导航系统 学 院 信息科学与技术学院 专 业 计算机科学与技术 学 号 20112840 学 生 姓 名 刘铸辉 指导教师姓名 陈娜 日期： 2013-8-31 一题目与要求实习一校园导游程序 问题描述 用无向网表示学校的校园景点平面图，图中顶点表示主要景点，存放景点的编号 、 名称 、 简介等信息 ， 图中的边表示景点间的道路 ， 存放路径长度等信息 。 要求能够回答有关景点介绍、游览路径等问题。 游客通过终端可询问：（ 1 ）从某一景点到另一景点的最短路径 。（ 2 ）游客从公园进入，选取一条最佳路线 。（ 3 ） 使游客可以不重复地浏览各景点，最后回到出口（出口就在入口旁边） 。 基本 要求 （ 1 ）将导游图看作一张带权无向图，顶点表示公园的各个景点，边表示各景点之间的道路，边上的权值表示距离为此图选择适当的数据结构 。（ 2 ）把各种路径都显示给游客，由游客自己选择浏览路线 。（ 3 ）画出景点分布图于屏幕上 。 实现提示 （ 1 ）构造一个无向图 G 并用邻接矩阵来存储。（ 2 ）利用迪杰斯特拉算法来计算出起点到各个顶点之间的最短路径用二维数组 pi来记录，最短路径长度就用一维数组 di 存放； i 的范围： 0 20 。（ 3 ）一维数组 have 是用来记录最短路径出现顶点的顺序。（ 4 ）根据起点和终点输出最短路径和路径长度。二需求分析本校园导航系统由C语言编写，主要掌握最短路径的实现方法，以及构造无向图G并用邻接矩阵来存储，掌握迪杰斯特拉算法来算最短路径。1. 输入的形式和输出的范围：2. 输出的形式：3. 程序所能到达的功能：A. 图中任意景点的相关信息查询B. 任意两个景点间的最短路径C. 任意两个景点间的所有路径D. 增加有关景点和道路的信息E. 删除更新有关景点和道路的信息F. 更新有关景点和道路的信息G. 显示全景H. 退出该系统三概要设计（1） 本程序包含了10个函数1 主函数main()2 显示操作菜单函数 menu()3 景点名称及其简介设置函数 picture(void)4 图中任意景点相关信息查询函数 checkscene(algraph g)5 图中任意两个景点间的最短路径 Dijkstra(algraph g)6 任意两个景点间的全部路径 alldistance(algraph g)7 增加有关景点和道路的信息 addscene(algraph g)8 删除有关景点和道路的信息 delscene(algraph g)9 更新有关景点和道路的信息 change(algraph g)10 显示全景 chang()（2） 各函数之间的关系 menu() picture(void) checkscene(algraph g) Dijkstra(algraph g) main() alldistance(algraph g) addscene(algraph g) delscene(algraph g) change(algraph g) chang()四详细设计实现概要设计中定义的所有的数据类型，对每个操作给出伪代码，对主程序和其他模块也都需要写出伪代码算法。（1） 结点类型和指针类型typedef struct int adj; int *info; sceneinfo;typedef struct adjlistint num; char *sight; char *description;adjlist;typedef struct algraph adjlist verMAXNUM; sceneinfo arcsMAXNUMMAXNUM;int vexnum,arcnum; algraph;（2） 图的基本操作1 主菜单/主菜单int menu(void) int i; printf(n-欢迎来到 莱震德瑞hui 校园导航系统!-n); printf(1.图中任意景点的相关信息查寻n); printf(2.任意两个景点间的最短路径n); printf(3.任意两个景点间的所有路径n); printf(4.增加有关景点和道路的信息n); printf(5.删除更新有关景点和道路的信息n); printf(6.更新有关景点和道路的信息n); printf(7.显示全景n ); printf(8.退出该系统n ); printf(-让辉哥带大家在石家庄铁道大学翱翔吧!-n); printf(请输入你要进行的操作：); scanf(%d,&i); return(i);2 景点名称及其简介void picture(void) int i,j; m.vexnum=11;m.arcnum=16; for(i=0;im.vexnum;i+) m.veri.num=i; m.ver0.sight=xiaomen; m.ver1.sight=学校大门，一教; 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.description=进入学校大门就可以看见一教，一教西面是二教和三教;m.ver2.description=自习和阅读的心灵家园，后身是第二实验楼;m.ver3.description=跑道和足球场;m.ver4.description=室内篮球场和游泳场;m.ver5.description=学生活动中心和综合餐厅;m.ver6.description=办公中心，包括开元楼和春晖楼;m.ver7.description=挨着医院和综合教学楼，物理实验;m.ver8.description=计算机和电工实验，西邻机械学院;m.ver9.description=生活区中心，西邻超市水房澡堂，东临一，二三食堂;m.ver10.description=教职工住处，在学校最北面; for(i=0;im.vexnum;+i) for(j=0;jp | i0) printf(输入错误！n);elsefor(j=0;j=p;j+) if(i=j)printf(你要查询的景点的相关信息如下：n);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; 4 图中任意两个景点间的最短路径void Dijkstra(algraph g) char ch; int path1MAXNUM; int distMAXNUM; int 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;in;i+)disti=g.arcsv0i.adj; si=0; if(g.arcsv0i.adj!=INF) path1i=v0;else path1i=-1; sv0=1;path1v0=0; for(i=0;in;i+)mindis=INF;u=-1;for(j=0;jn;j+) if(sj=0 & distj INF)u=j;mindis=distj;su=1; for(j=0;jn;j+) if(sj=0)if(g.arcsuj.adj INF& distu+g.arcsuj.adjdistj) distj=distu+g.arcsuj.adj;path1j=u; dispath(g,dist,path1,s,n,v0,po); printf(n是否继续查询?(y|n):); scanf(%s,&ch); if(ch=N|ch=n) break; 5 任意两个景点间的全部路径void path(algraph g,int i,int j,int k) int s,ko; if(rk=j) a+; printf(第%d条:,a);for(s=0;s);printf(%sn,g.verrs.sight); s=0; while(sg.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请选择目地景点的序号：);scanf(%d,&j);for(k=0;kg.vexnum;k+) if(i=g.verk.num) i=k;for( l=0;lg.vexnum;l+)if(j=g.verl.num) j=l; printf(从%s到%s的所有游览路径有:n,g.veri.sight,g.verj.sight); r0=i;for(k=0;k1;k+) visitedi=0; a=0; path(g,i,j,0); printf(继续查询?(y|n):); scanf(%s,&sh); if(sh=N|sh=n) break; 6 增加有关景点和道路的信息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请输入新景点的相关简介：); scanf(%s,moh); m.verp.description=(char*)malloc(100); strcpy(m.verp.description,moh); g.vexnum=g.vexnum+1; for(j=0;jp;+j) m.arcspj.adj=INF; m.arcsjp.adj=INF; printf(n请问有几个景点与该景点直接相通：); scanf(%d,&i); printf(n请输入与该景点相通的景点的序号及它们之间的距离：); for(j=0;ji;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(%d t%s t %snn , g.verp.num,m.verp.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; 7 删除有关景点和道路的信息void delscene(algraph g) int i,j,k,l; char sh; while(1) sceneplace(); printf(n请输入你将要删除的景点序号:); scanf(%d,&i); for(k=0;kg.vexnum;k+) if(i=g.verk.num) j=k; m.verj.sight=NULL; for(l=1;lm.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; 8 更新有关景点和道路的信息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;kg.vexnum;k+) if(i=g.verk.num) j=k; printf(-n); printf(1.景点名称t2.景点简介t3.道路消息n); printf(-n); 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); strcpy(m.verj.description,moh); break; case 3:printf(请输入要修改的与该景点相通的景点的距离的序号个数：); scanf(%dn,&fh); for(k=0;kfh;k+) printf(请输入要修改的第%d个景点的序号:,j+1);scanf(%dn,&b);printf(请重新输入该两个景点之间的距离：); scanf(%d,&m.arcsjb.adj);m.arcsbj.adj=m.arcsjb.adj; sceneplace(); printf(继续修改?(y|n):); scanf(%s,&sh); if(sh=N|sh=n) break; 9 显示全景略10 主函数int main() picture(); printf(n-校园导航系统-n); sceneplace();for(;) switch(menu() case 1:checkscene(m);break; case 2:Dijkstra(m);break; case 3:alldistance(m);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); 5 调试分析在调试删除修改功能过程中，删除的总是不正确，删除的结果显示，没有将要删除的景点删掉，最后发现删除的结点不正确，删除应该与输入的值和头结点next比较，而不是头结点。还有就是删除结点不知道如何循环，最后又看看了记得笔记和书，才知道如何继续删除而不出错误。6 使用说明进入校园导航系统，首先看到的就是用户欢迎界面，然后根据提示：1.图中任意景点的相关信息查寻；2.任意两个景点间的最短路径；3.任意两个景点间的所有路径；4.增加有关景点和道路的信息；5.删除更新有关景点和道路的信息；6.更新有关景点和道路的信息7.显示全景；8.退出该系统如1，图中任意景点的相关信息查寻。根据本系统提供的10个景点，输入景点编号，可以得到景点信息和景点介绍；如2，任意两个景点间的最短路径。提示依次输入出发景点序号和目的景点序号，录入完毕后，按回车输出最短游览路径，以及路径长度，并提示是否继续查询；如3，任意两个景点间的所有路径。提示依次输入出发景点序号和目的景点序号，录入完毕后，按回车输出所有游览路径，并记数路径条数，最后提示是否继续查询；如4，增加有关景点和道路的信息。提示依次输入1.新景点的名称；2新景点相关简介；3.有几个景点与该景点相通；4.依次输入相通景点的序号和两个景点间