《校园导游咨询.docx》由会员分享，可在线阅读，更多相关《校园导游咨询.docx（18页珍藏版）》请在三一办公上搜索。
1、 HUBEI NORMAL UNIVERSITY课程设计论文Courses Thesis 课程名称数据结构 专 业 通信工程 班 级 0803班 学 生 蔡兵 学 号 2008115020301 设计题目校园导游咨询指导教师 孙玉霞老师 时间 2011年3月22日 年度 2011年 第二 学期目录一、 课程目的二、 基本要求三、 实验内容及步骤1、概要设计2、详细设计 （1）建立模型（逻辑结构） （2）建立模块之间的关系（存储结构）（3）算法四、源程序清单五、测试结果六、课程设计总结及心得体会实验题目：校园导游咨询一、课程目的 为用户提供路径咨询和景点查询，根据用户指定的始点和终点输出相应路径
2、或者根据用户指定的景点输出景点的信息。二、基本要求（1）设计校园平面图，在校园景点选10个左右景点。以图中顶点表示校园内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等有关信息。（2）为来访客人提供图中任意景点相关信息的查询。（3）为来访客人提供任意景点的问路查询，即查询任意两个景点之间的一条最短路径。附加要求：a、界面友好，函数功能要划分好 b、总体设计应画一流程图 c、程序要加必要的注释 d、要提供程序测试方案三、实验内容及步骤1、概要设计： 在设计这个校园导游系统前考虑到整个信息的结点和操作，可以通过邻接矩阵借助图的相关知识来完成。按照要求分为三个模块，图的信息的初始
3、化，图各个景点信息的查询和景点间的最短路径查询功能void introduce() /用来查询各景点的相关信息int shortestdistance() /用来查询任意两个景点之间的最短路径和经过的景点void floyed() /用来计算任意两个景点之间的最短路径void display(int i,int j) /用来显示任意景点之间的最短路径和经过的景点/*包含头文件*/#include /*定义符号常量*/#define INT_MAX 10000#define n 10/*定义全局变量*/int costnn;/* 边的值*/int shortestnn;/* 两点间的最短距离*/
4、int pathnn;/* 经过的景点*/2、详细设计：（1）建立模型（逻辑结构：图）17823459610732151111112222湖北师范学院简要校园景点指示图（2）建立模块之间的关系（存储结构：邻接矩阵）（3）算法这个程序的关键代码就利用Floyd算法求最短路径并将路径存放起来。Floyd算法的算法思想：设矩阵cost用来存放带权无向图G的权值，即矩阵元素costij中存放着序号为i的结点到序号为j的结点之间的权值，可以通过递推构造一个矩阵序列A0，A1，A2，AN来求每对结点之间的最短路径。其中，Akij表示从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度。初始时
5、有A0ij=costij。当已经求出Ak，要递推求解Ak+1时，可分为两种情况来考虑：一种清楚是该结点序号为k+1的结点，此时该路径长度与从结点Vi到结点Vj的路径上所经过的结点序号不大于k的最短路径长度相同；另一种情况是该路径经过结点序号k+1的结点，此时该路径可分为两段，一段是从结点Vi到结点Vk+1的最短路径，另一段是从结点Vk+1到结点Vj的最短路径，此时的最短路径长度等于这两段最短路径长度之和。这两种情况的路径长度较小者，就是要求的从结点Vi到结点Vj的路径上所经过的结点序号不大于k+1的最短路径长度。Floyd具体算法设计void floyed() int i,j,k; for(i
6、=1;i=n;i+) for(j=1;j=n;j+) shortestij=costij; pathij=0; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j(shortestik+shortestkj) shortestij=shortestik+shortestkj; pathij=k; pathji=k; 四、源程序清单#include #define INT_MAX 10000#define n 10int costnn;int shortestnn;int pathnn;void introduce();int shortestdistance()
7、;void floyed(); void display(int i,int j);void main() int i,j,q; char k; printf(t-欢迎来到湖北师范学院-nn); printf(t-按1进入校园导游指示系统，否则请再次输入-n); PR:printf(t -请输入你的选择-nt);scanf(%d,&q); if(q!=1) printf(t-输入错误，请再次输入-n); goto PR; else for(i=0;i=n;i+) for(j=0;j10的数字编号！nn); break; int shortestdistance() int i,j; print
8、f(请输入要查询的两个景点的编号(1-10的数字编号并用,间隔):); scanf(%d,%d,&i,&j); if(in|in|j10的数字编号并用,间隔):n); scanf(%d,%d,&i,&j); else floyed(); display(i,j); return 1;void floyed() int i,j,k; for(i=1;i=n;i+) for(j=1;j=n;j+) shortestij=costij; pathij=0; for(k=1;k=n;k+) for(i=1;i=n;i+) for(j=1;j(shortestik+shortestkj) shortes
9、tij=shortestik+shortestkj; pathij=k; pathji=k; void display(int i,int j) int a,b; a=i; b=j; printf(您要查询的两景点间最短路径是:nn); if(shortestij!=INT_MAX) if(ij) printf(%d,b); while(pathij!=0) printf(-%d,pathij); if(ij) j=pathij; else i=pathji; printf(%d)最短距离是:%d米nn,a,b,shortestab); else printf(%d,a); while(pat
10、hij!=0) printf(-%d,pathij); if(i%d,b); printf(nn); printf(%d-%d)最短距离是:%5d米nn,a,b,shortestab); else printf(输入错误！不存在此路！nn); printf(n);五、测试结果 校园导游的主页面输入1时进入校园导游系统查询景点5的相关信息查询景点1和6之间的最短路径和经过的景点六、课程设计总结及心得体会这次的课程设计题目是校园导游，总的来说还是比较简单的，只运用了Floyd算法和操作。程序设计也比较简单，运行结果正确，能够实现为来访客人提供校园任意景点的相关信息。通过这次课程设计试验，我更加体会到了程序设计的三要素（即逻辑结构、存储结构和算法）的重要性，也让我加深了对三要素的理解。校园导游咨询这个程序设计充分体现了程序设计的三要素。 不过也通过这次课程设计，让我明白现实生活跟程序之间联系，同时也让我明白了数据结构这门课程的重要性，我以后会继续努力学习这门课程。
