校园导游系统.doc

安徽理工大学数据结构课程设计说明书题目: 校园导游系统 院 系： 计算机科学与工程学院 专业班级： 计算机07-4班 学 号： 200614398 学生姓名： 张嵩 指导教师： 张金伟 2009年 07 月 02 日安徽理工大学课程设计（论文）任务书 计算机科学与工程 学院 计算机网络教研室学 号200614398学生姓名张嵩专业（班级）计07-4设计题目 校园导游系统设计技术参数系统平台：Windows XP开发工具：Microsoft visual studio c+设计要求(1)设计校园的校园平面设计图，所含景点不少于10个。以图中的顶点表示学校的各个景点，存放景点名称，代号，简介等信息；以边表示路径，存放路径的长度等相关信息。(2)为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的最短路径。(3)为来访客人提供图中任意景点的相关信息的查询。工作量课程设计报告要求不少于3000字。源程序要求不少于300行工作计划6月25日-6月29日 查找设计设计校园导游系统所需的有关资料7月29日-6月30日 上网搜索一些所需函数代码，设计图形界面7月1日 修改并完善自己的代码7月2日 撰写实验报告参考资料1秦锋.数据结构(c语言版).合肥：中国科学技术大学出版社，20072温秀梅,丁学钧.VisualC+面向对象程序设计.北京:清华大学出版社,20053徐孝凯.C+语言基础教程.北京:清华大学出版社,2006指导教师签字教研室主任签字 2009年 07月 03 日 学生姓名： 张嵩 学号： 200614398 专业班级： 计07-4 课程设计题目： 校园导游系统 指导教师评语： 成绩： 指导教师： 年 月 日安徽理工大学课程设计（论文）成绩评定表免责声明：文档在线网中所有的文档资料均由文档在线网会员提供,该文档资料的版权属于提供者所有。文档在线网会对会员提供的文档资料进行筛选和编辑，但是并不声明或保证其内容的合法性和正确性。目录1、需求分析32、总体设计32.1 抽象数据类型图的定义32.2 程序中包含的模块32.3模块间的调用关系33、详细设计33.1 代码设计33.1.1 定义结构体和全局变量33.1.2 平面图的初始化33.1.3 最短路径查询33.1.4 景点信息查询33.1.5景点信息更新33.2 界面分析33.2.1 主程序界面33.2.2 景点信息的查询33.2.3 最短路径查询33.2.4 管理校园查询系统34、总结报告3参考文献3 I1、需求分析设计一个校园导游系统程序，为来访的客人提供各种服务的信息查询。(1).设计安徽理工大学校园平面图，所含的景点不少于10个。以图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。(2).为来访客人提供图中任意景点相关信息的查询。(3).为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。2、总体设计2.1 抽象数据类型图的定义ADT Mgraph数据对象V:V是具有相同特性的数据元素的集合，即顶点集。数据关系：Mgraph=(V,R)。其中，R=|v,wV且P(v,w),表示从v到w的一条弧。基本操作：/ADT Mgraph2.2 程序中包含的模块（1）主程序模块void main()/*主函数*/定义平面图：Mgraph G初始化图：void InitGraph( )打印平面图：void Printer( )while(1)接受命令；处理命令；键入0退出；/main( )函数实现人机界面和交互命令（2）查询模块void Reception( )/*前台查询*/初始化图：void InitGraph( )while(1)信息查询：void Sinfor( )；路经查询：void ShortestPath( )；键入0退出；（3）管理模块void Backstage( )/*后台管理*/while(1)修改信息：void ChangP( );删除信息：void DeleteP( );添加信息：void Add( );键入0退出；2.3模块间的调用关系主程序模块添加信息void Add( )删除信息void DeleteP( )修改信息void ChangP( )路经查询void ShortestPath( )查询模块管理模块信息查询void Sinfor( )3、详细设计3.1 代码设计3.1.1 定义结构体和全局变量#define INT_MAX 10000 /*无穷大*/#define MAX 50typedef struct ArCell int len; /路径长度 ArCell,AdjMatrixMAXMAX;typedef struct char name10;/ char infor100; int c;Infor;/顶点名称和信息typedef struct Infor vexs 20 ;/顶点表，用一维向量即可 AdjMatrix cost;/邻接矩阵 int vexnum, arcnum; /顶点总数，弧（边）总数 Mgraph;3.1.2 平面图的初始化void InitGraph(Mgraph &G)/初始化函数 int i,j;G.vexnum=10;G.arcnum=15;for(i=0;iG.vexnum;i+) G.vexsi.c=i; strcpy(G.,图书馆); strcpy(G.r,藏书丰富，藏书量之最);strcpy(G.,实验楼); strcpy(G.r,有着先进、完善的试验设备); strcpy(G.,信息中心); strcpy(G.r,全校的学生上课的地方); strcpy(G.,活动中心); for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.costij.len=INT_MAX; G.cost01.len=90; G.cost02.len=100; G.cost03.len=360; G.cost12.len=300; G.cost14.len=120; for(i=0;iG.vexnum;i+) for(j=0;jG.vexnum;j+) G.costji.len=G.costij.len;3.1.3 最短路径查询使用Floyd的算法求最短路径void ShortestPath (Mgraph G)/Floyd方法查询最短路径 char a10,d10; int b=1,i,j,v,v0,w; int Dist100,S100,Path100; int n=G.vexnum; while(b) for(i=0;iG.vexnum;i+) coutG.endl; for(i=0;i100;i+) Disti=9999; Si=0; Pathi=-1; cout请输入要查询路径的两个景点a; cind; v0=LocateVex(G,a); j=LocateVex(G,d); for(v=0;vn;v+) Sv=0; Distv=G.costv0v.len; if(Distv9999) Pathv=v0;/v1是v的前趋 else Pathv=-1;/v无前趋 / Distv0=0; Sv0=1; for(i=1;in;i+) int min=9999; for(w=0;wn;w+) if(!Sw&Distwmin) v=w; min=Distw; /w顶点离v1顶点更近 Sv=1; for(w=0;wn;w+)/更新当前最短路径及距离 if(!Sw&(Distv+G.costvw.lenDistw) Distw=Distv+G.costvw.len; Pathw=v; cout最短距离为：endl; coutDistjendl; cout所走路径为:=0;v-) coutG.; coutG.endl; cout返回后台系统按0,继续删除按1b; 3.1.4 景点信息查询void Sinfor(Mgraph &G) /查询景点信息char a20; int b=1; while(b) for(int i=0;iG.vexnum;i+) coutG.endl; cout请输入要查找的景点信息a; for(i=0;iG.vexnum;i+) if(strcmp(G.,a)=0) coutG.rendl; b=0; if(b!=0) cout输入错误请重新输入！endl; cout返回前台系统按0,继续查找按1b; 3.1.5景点信息更新void ChangeP(Mgraph &G)/修改已存在景点的相关信息 char a10; int b=1,i; while(b) for(i=0;iG.vexnum;i+) coutG.endl; cout请输入要修改的景点的信息a; for(i=0;iG.vexnum;i+) if(strcmp(a,G.)=0) coutG.rendl; cout请输入该景点的修改后的信息G.r; cout修改成功!endl; b=0; if(b!=0) couterror!输入有误!endl; cout保存请按1，不保存请按2c; if(c=1) WriteTXT(G); cout返回后台系统按0,继续修改按1b; 3.2 界面分析3.2.1 主程序界面根据图中提示选择要执行的操作 图1 主界面3.2.2 景点信息的查询输入你要查询的景点名称：通过调用函数Sinfor()l来查询景点信息。如果输入的景点不存在，系统会提示你输入错误，请重新输入。 图2 信息查询界面3.2.3 最短路径查询输入你所在的景点和要到达的景点，将输出这两点的最短距离：调用函数ShortestPath()来求最短路径。 图3 路径查询界面3.2.4 管理校园查询系统你可以在此修改、删除、添加某个景点的路径和信息：删除调用函数DeleteP()，修改调用函数ChangP()，添加调用函数Add()。 图4 管理界面3.2.5 退出系统根据提示按“0”退出该系统，程序结束。4、总结报告通过本次课程设计实验，使我更能熟练地掌握c语言、c+以及数据结构等知识的综合运用。当然在课程设计期间，也遇到了大大小小的一些问题，是我看到了自己的不足之处，使我认识到在以后的学习中要善于发现自己的不足，找出自己的薄弱环节，以便能够更好的去巩固所学的。本次设计中要求求最短路径，就必须了解最短路径的算法：Dijkstra算法和Floyd算法。在拿到题目时，通过查找相关的资料才回忆起这两种方法的具体算法。比较这两种算法的复杂度，尽量选用复杂度小。当然任何程序都不可能完美，往往会牺牲程序的空间来换取时间，或者牺牲时间来换取足够大的空间，这就需要根据程序的具体要求来设计算法。在选用存储方法是，