《校园导游咨询系统---数据结构课程设计》由会员分享，可在线阅读，更多相关《校园导游咨询系统---数据结构课程设计（35页珍藏版）》请在金锄头文库上搜索。
1、石家庄经济学院 本科生课程设计报告书 题 目 校园导游咨询系统 姓名 颜建学 学号 410109070321 学 院 信息工程学院 专业 计算机方向 指导教师 XXXXXX 完成日期： 2012-07-5校园导游咨询系统1 需求分析本程序的主要目的是为了提供本学校的景点的路径咨询和来访客人以及刚来报到的新生提供一个快捷方便的路径咨询，快速有效的提高了用户的熟悉度。满足用户查询的需要：1、从石家庄经济学院的平面地图中选取出10个有代表性的景点。2、为来访的客人提供图中任意景点相关信息的查询。当用户输入正确时，为用户输出景点的相关信息；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。3、
2、为来访的客人提供图中任意景点的路径查询，即查询任意两个景点之间的最短简单路径。当用户输入正确时，为用户输出任意两景点的最短路径；当用户输入不合法时，提示用户输入有误并返回让用户重新输入。4、为来访客人推荐参观路线。2 概要设计1、抽象数据类型图的定义如下：ADT Graph数据对象V：V是具有相同特性的数据元素的集合，称为顶点集。数据关系R：R=VRVR=(v,w)|v,wV,(v,w)表示v和w之间存在路径基本操作P：CreatGraph70321(&G,V,VR)初始条件：V是图的顶点集，VR是图中边的集合。操作结果：按V和VR的定义构造图G。DestroyGraph70321(&G)初始
3、条件：图G存在。操作结果：销毁图G。LocateVex70321(G,u)初始条件：图G存在，u和G中顶点有相同特征。操作结果：若G中存在顶点u，则返回该顶点在图中位置；否则返回其他信息。GetVex70321(G,v)初始条件：图G存在，v是G中某个顶点。操作结果：返回v的信息。FirstEdge70321(G,v)初始条件：图G存在，v是G中某个顶点。操作结果：返回依附于v的第一条边。若该顶点在G中没有邻接点，则返回“空”。 NextEdge70321(G,v,w)初始条件：图G存在，v是G中某个顶点，w是v的邻接顶点。操作结果：返回依附于v的（相对于w的）下一条边。若不存在，则返回“空”
4、。 InsertVex70321(&G,v)初始条件：图G存在，v和图中顶点有相同特征。操作结果：在图中增添新顶点v。DeleteVex70321(&G,v)初始条件：图G存在，v是G中某个顶点。操作结果：删除G中顶点v及其相关的边。InsertEdge70321(&G,v,w)初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中增添边(v,w).DeleteEdge70321(&G,v,w)初始条件：图G存在，v和w是G中两个顶点。操作结果：在G中删除边(v,w)。GetShortestPath70321(G,st,nd,&Path)初始条件：图G存在，st和nd是G中两个顶点。操作结
5、果：若st和nd之间存在路径，则以Path返回两点之间一条最短路径，否则返回其他信息。ADT Graph主程序void main()初始化； do 接受命令（输入景点信息或输出最短路径）； 处理命令； while（“命令”！=“退出”）；2、调用的函数有如下：void CreateUDN70321(int v,int a); /* 造图函数 */void narrate70321(); /*说明函数*/void ShortestPath70321(int num); /*最短路径函数*/void output70321(int sight1,int sight2); /*输出函数*/char
6、Menu70321(); /* 主菜单 */void search70321(); /* 查询景点信息 */char SearchMenu70321(); /* 查询子菜单 */void HaMiTonian70321(int); /* 哈密尔顿图的遍历 */void NextValue70321(int); void display70321(); /* 显示遍历结果 */3、运行主界面：*欢 迎 使 用 校 园 导 游 程 序*石*家*庄*经*济*学*院*制作者：信息工程学院 410109070321 颜建学 ！欢迎您的使用！ 景点名称 （0）教学主楼 （1）足球场 （2）灯光篮球场 （3
7、）惠馨园 （4）实验楼 （5）计算机实验室 （6）地球科学博物馆 （7）学术报告厅 （8）图书馆 （9）喷泉 1、查询景点路径 2、查询景点信息 3、推荐参观路线 e、退出 子界面如下： 1、按照景点编号查询 2、按照景点名称查询 e、返回 3、模块图表示如下：主程序模块处理功能模块无向图存储模块为用户输出景点信息为用户输出两景点最佳路径推荐参观路径3 详细设计从石家庄经济学院的平面地图中选取出10个有代表性的景点，将其抽象成无向带权网并用邻接矩阵来表示。以图中的顶点代表景点，存放景点名称、代号、简介等信息，权值代表两地之间的距离。1、 图的存储结构如下：#define Max 20000#d
8、efine NUM 9typedef struct ArcCell int adj; /* 相邻接的景点之间的路程 */ArcCell; /* 定义边的类型 */typedef struct VertexType70321 int number; /* 景点编号 */ char *sight; /* 景点名称 */ char *description; /* 景点描述 */VertexType; /* 定义顶点的类型 */typedef struct VertexType vexNUM; /* 图中的顶点，即为景点 */ ArcCell arcsNUMNUM; /* 图中的边，即为景点间的距离
9、 */ int vexnum,arcnum; /* 顶点数，边数 */MGraph; /* 定义图的类型2、该程序的算法如下：1)void CreateUDN70321(MGraph&G) /* 造图函数 */ /采用邻接矩阵表示法，构造无向网Gscanf(&G.vexnum,&G.arcnum,&IncInfo);/ IncInfo为0则各弧不含其它信息for(i=0;i G.vexnum;+i)scanf(&G.vexsi);/构造顶点向量for(i=0;i G.vexnum;+i)/初始化邻接矩阵for(j=0;j G.vexnum;+j)G.arcsij=INFINITY,NULLfo
10、r(k=0;k G.arcnum;+k)/构造邻接矩阵scanf(&v1,&v2,&w);/输入一条边依附的顶点及权值i=LocateVex(G,v1);j= LocateVex(G,v2);/确定V1和V2在G中的位置G.arcsij.adj=w;/弧的权值If(IncInfo)Input(*G.arcsij.info);/若弧含有相关信息，则输入G.arcsji= G.arcsij;/置的对称弧 Return OK; 2)void narrate70321() /* 说明函数 */k=0;printf(ntt*欢 迎 使 用 校 园 导 游 程 序*n);printf(ntt*石*家*庄*
11、经*济*学*院*n);printf(ntt制作者： 信息工程学院 410109070321 颜建学 ！欢迎您使用！n);printf(ntt_n);printf(ttttt 景点名称ttn);printf(tt_n);for(i=0;iNUM;i+)printf(tt (%2d)%-15stt,i,G.vexi.sight);if(i%2=(NUM-1)%2)printf(n);/奇数编号景点在右边，偶数编号景点在左边k=k+1;printf(tt_n);3) void ShortestPath70321(int num) /用迪杰斯特拉算法求G的v0顶点到其余顶点的最短路径Pv及其带权长度 Dv/若Pvw为TRUE,则 w是从v0到v当前求得最短路径上的顶点 /finalv为TRUE当且仅当v属于S，即已经 求得从 v0到v的最短路径 for(v=0;vG.vexnum;+v) Finalv=FALSE;Dv= G.arcsv0v; For(w=0;w G.vexnum;+w)Pv
