《xxxxxxxxxxx姓名-鲁东大学校园导游咨询系统》由会员分享，可在线阅读，更多相关《xxxxxxxxxxx姓名-鲁东大学校园导游咨询系统（13页珍藏版）》请在金锄头文库上搜索。
1、第 1 页 共 13 页鲁东大学数学与信息学院20092010学年第 1 学期数据结构专题设计课程论文课程号：2102791 任课教师陈军成绩论文题目：（可指定题目，也可说明题目范围。 ）从给出的参考选题中选（或自选）一个能体现数据结构课程特点的课题， 用 C 语言（TC/VC+）编程实现所述功能， 用论文形式描述整个工作。 详见数 据结构专题设计课程任务和要求文档。论文要求：（对论文题目、内容、行文、字数等作出判分规定。）按右边给定的模板要求写作，字数4000 字以上（不含附录）。评分采用五级制：优秀、良好、中等、及格、不及格。评分依据包括题目难易程度、程序运行情况、数据结构和算法设计合理与
2、否、算法注释的清晰程度；论文的规范程度、撰写质量（条理清晰，内容充实，文字通顺，图表恰当）；总结的深刻程度、 工作量和创新性； 交作业的及时程度、独立完成情况，以及其它参考因素。 不同同学可以选择同类题目，但在具体功能、程序代码、论文写作上都要 有所不同，若发现雷同，均判为不及格。教师评语：教师签字：2009 年 11 月 2 日鲁东大学校区导游咨询系统1、引言2009，是全运会举办之年； 烟台市是全运会举办城市之一。为了使来访外宾以及更方便地了解我校校区，我设计了校区无向平面图。它提供了以下服务：（1）为来访客人提供图中任意景点相关信息的查询。（2） 为来访客人提供任意景点的问路查询，即查询
3、任意两个景点之间的一条最短路径。2、需求分析该系统是无向平面图， 包含新校区 10 个景点，以图中顶点代表新校区内的每 个景点，存放景点的名称，代号，简介等信息；以边表示路径，存放长度有关的信 息。 它的功能是：(1) 输出图中新校区的所有景点； (2) 为用户提供任意景点的相关信息查询；(3)为用户提供任意景点的问路查询，即查询两个景点之间的一条短路径；(4)为用户找出两景点之间的最短距离，即最短路径。 单位 （米） 新校区面图无向平 所含景点： 0. 图书馆； 1. 管理楼； 2. 北区 8 号楼;3. 北区 7 号楼；4. 北区 5 号楼； 5. 北区 4 号楼； 6. 体育教学楼； 7
4、. 北区体育场； 8. 南区五号楼； 9. 北区 10 号楼； 10. 校医院学院_专业_班级_本 专学号_姓名_密封线学生须将文字写在此线以下第 2 页 共 13 页图书馆体育楼管理楼8号楼10 号楼体育场7号楼南五号楼校医院5号楼4号楼得出邻接矩阵 0 1 2 3 4 5 6 7 8 9 10 0 20 150 30 0 20 0 60 1 0 20 2 0 100 3 60 20 0 20 90 4 20 0 5 150 100 0 10 6 18 10 0 180 7 180 0 50 8 30 90 20 0 9 50 0 10 该程序主要分为是主函数和四个子函数 （1） void
5、Browser ()主要的功能是输出所有的景点； （2） void Search()主要功能是实现输出要查询的景点的信息； （3） void Shortpath()主要功能是为来访的客人提供任意景点的问路查询，即 查询两个景点之间的一条短路径；（4）Void Floyd()主要功能是输入要查的起点与终点（5） 主函数主要是调用这三个函数，实现上述三个功能；3、概要设计（或总体设计）如果要实现以上算法，就得需要声明一个结构体用来存放图的邻接矩阵 抽象数据类型： struct AlCell int verticesMAX; int vexnum,arcnum; int arcsMAXMAX; ;
6、定义数组用来存放景点名称 char name30= 用来存放景点信息 char introduction100 = 本程序主要包含的五个模块 （1） void Browser () （2）void Search() （3）Void ShortestPath_DIJ() （4）Void Floyd() （5）主函数模块Main（）第 3 页 共 13 页 初始化邻接矩阵并给其赋值； switch(i) case 1:system(“cls“);Browser(Menu();break;/调 用Browser 函数case 2:system(“cls“);ShortestPath_DIJ(Menu
7、();break;/ 调用 ShortestPath函case 3:system(“cls“);Floyd(Menu();break;/调 用Floyd 函数case 4:system(“cls“);Search(Menu();break;/调 用Search 函数case 5: exit(0); /正确退出default: coutvexnum;v+) for(w=0;wvexnum;w+) 该模块主要功能是输入要查的起点与终点（5）主函数模块Main（） switch(i) 狄克斯拉算法求最短路径以下内容为“网摘”狄克斯特拉具体做法是按照从源点到其余每一顶点的最短路径长度的升序 依次求出从
8、源点到各个顶点的最短路径及长度，每次求出从从源 i 点到一个终点 m 的最短路径及长度后都要以该m点作为新考虑的中间点，用Vi 到 Vm的最短路径和 最短路径长度对Vi 到其他尚未求出最短路径的那些终点的当前最短路径及长度作 必要的修改使之成为当前新的最短路径和最短的路径长度，当进行 n-2 次后结束算 法。 该算法程序中需要设置一个集合，用u 表示，其作用是保存已经求得最短路 径的终点序号， 它的初值只有一个元素， 即源点 i ，以后每求出一个源点i 到终点 m 的最短路径就将该点m并入 u 集合中，以便作为新考虑的中间点；还需设置一个具 有权值类型的一维数组distn，该数组中的第 j 个
9、元素 distj用来保存从源点 i 到终点 j 的目前最短的路径长度，他的初值为(i,j)或 边上的权值，若vi 到 vj 没有边则赋权值为lage ，以后每考虑一个新的中间点时distj可能变小；另外 再设置一个 smax 最短路径的终点判定集合为1 时则表示已经包含，否则不包含。 该算法的执行过程是：首先从u 集合以外的顶点 ( 即待求出最短路径的终点)第 4 页 共 13 页所对应得 dist数组元素中，查找出其值最小的元素，假定为distm，该元素值就 是从源点 i 到终点 m的最短路径长度，接着把已求得的最短路径的终点m并入集合 u 中然 后 以 Vm 作 为 新考虑 的中 间点 ，
10、对 u 集合 以外 的每 个顶点j ，比 较 distu+costuj与 distj的大小，若前者小于后者，表明加入了新的中间点 Vu之后，从 Vi 到 Vj 的路径长度比原来变短， 应用他替换 distj的原值使 distj 始终保持到目前为止的最短的路径长度。为了方便起见，可采用，一维数组 path来保存 已求得的最短路径的终点的集合，具体做法是：若顶点i 在集合在集合中，则令数组元素si为真，否则为假。这样当判断一个顶点i 是否在 path 以外时，只要判断对应的数组元素su 是否为假即可。4、详细设计及实现下面是校园导游咨询系统的详细设计的代码：#define INFINITY 100
11、000/设为无穷大值#define MAX_VERTEX_NUM 50 #define MAX 50 #include #include #include #include / 字符串所需的系统头文件typedef struct ArCell/构造结构体 int adj;/路径长度 ArCell,AdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM; typedef struct/图中顶点表示主要景点，存放景点的编号、名称、简介等信息， MGraph * CreatUDN(MGraph *G)/ 初始化一个图，可以接受用户输入 int i,j,k,w; char v120
12、,v220; printf(“输入图的顶点数 , 边数:“); scanf(“%d%d“,/ 输入用户所想查询的信息printf(“输入景点的代号 : 、名称、简介 :n“); for(i=0;ivexnum;i+) printf(“景点代号 :“);scanf(“%d“,/输入你要查询的景点代号printf(“景点名称 :“);/输出景点名称scanf(“%s“,G-vexsi.name); printf(“景点简介 :“);/输出景点简介scanf(“%s“,G-vexs-introduction);/输出用户查询信息MGraph InitGraph()/用来存储所有景点简介信息、代号MG
13、raph G;int i,j;G.vexnum=11;G.arcnum=14; for(i=0;iG-vexnum) printf(“景点代号输入错误 ! 请您重新输入景点代号 :“); / 如果所输数字大于景点数，则会显示景点代号输入错误! 请您重新输入景点代号scanf(“%d“, if(v0=0uvexnum;u+)/总路线长度的求解实现void Menu()/函数的主显示界面MGraph b; void cmd()/函数查询的主体，可以实现函数的调用以实现其功能 int i; b=InitGraph(); Menu(); scanf(“%d“, while(i!=5) switch(i
14、)/分支结构case 1:system(“cls“);Browser(Menu();break;/浏览大学校园全景case 2:system(“cls“);ShortestPath_DIJ(Menu();break;/查看全部游览路线case 3:system(“cls“);Floyd(Menu();break;/选择出发点和目的地case 4:system(“cls“);Search(Menu();break;/查看景点信息简介case 5:exit(1);break;/退出查询系统default:break; scanf(“%d“, void main()/设置主显示界面参数system(“color 8f“);/界面背景颜色system(“mode con: cols=110 lines=40“);/界面长度及宽度第 7 页 共 13 页5、调试分析在 C+ 环境中单击程序运行按钮；测试： （1）当输入 1 回车时：以上显示的是所有景点号及景点名称；（2）当输入 2 和 1 回车时：（3）当输入 3 回车， 1 回车， 3 回车时：（6） 当输入 4 回车， 1 回车时第 8 页 共 13
