课程设计报告院、系：专业：软件工程班级：课程设计科目数据结构学生姓名：指导教师：完成时间：校园导航系统设计报告一、设计任务与目标设计要求：设计你的学校的平面图，至少包括10个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。
本系统是一个涉及吉林大学珠海学院相关景点和场所查询系统,是为了方便人们能够更快更准地获得学校各个景点和场所的详细信息。
本系统为用户提供以下功能:(一)、查询了解学校概况，为导游参观者提供关于学校的相关信息。
(二)、查询校园各个场所和景点信息;(三)、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学校。
校园导航查询系统的开发方法总结如下：(1) 调查，了解学校各个场所与场所或者是各个景点与景点之间的信息，路径和距离，从外来人员或者参观者和走访者的角度出发，该如何设计才能满足用户需求。
(2) 分析，对调查得到的数据进行分析，根据其要求实现的功能分析系统结构和界面将实现的基本功能。
(3) 设计与开发，设计系统界面并编辑实现其各个功能的代码。
(4) 调试，在设计完成后，调试系统运行的状况，修改完善系统,然后进行测试。
二、方案设计与论证校园旅游模型是由各个景点和景点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。
用图的结点代表景点或场所，用图的边代表景点或场所之间的路径。
所以首先应创建图的存储结构。
结点值代表景点信息，边的权值代表景点间的距离。
结点值及边的权值采用图存储。
本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。
计算路径长度，最短路线和最佳路径时可分别用迪杰斯特拉（Dijkastra）算法和哈密而顿回路算法实现。
最后用switch选择语句选择执行浏览景点信息或查询最短路径和距离。
搭建程序框架图，其图如下所示：三、算法说明（一）设计功能的实现接下来根据以上搭建的程序框架完成各个模块的算法1、首先是抽象数据类型的定义：图的抽象数据类型的定义：ADT Mgragh{数据对象V: V是具有相同特征的数据元素的集合，称为定点集数据关系R={VR}VR={ <V,W> | V, W∈V, <V , W>表示从V到W的边}2、基本操作：CreateUDN(&G,V,VR); // 创建图初始条件：V是图的顶点集，VR是图中边的集合。
操作结果：按V和VR的定义构造图 G。
（二）主要算法设计及相关算法补充先创建图存储学校各个景点或场所，以图的顶点表示景点或场所，以边表示路径，再利用迪杰斯特拉（DijkStra）算法求出校园各个地方的最短路径，然后根据需要进行补充相关算法。
四、全部源程序清单#include "stdio.h"#include "iostream.h"#include "malloc.h"#include "conio.h"#include "stdlib.h"#define Num 11 //最多顶点个数#define uplimit 100000 //定义一个无穷大的值struct intt{int value;};intt Edge[Num][Num]; //Edge为带权邻接矩阵 intt dist[Num]; //dist为最短路程intt path[Num]; //path为最短路径上该顶点的前一顶点的顶点号intt S[Num]; //S为已求得的在最短路径上的顶点号intt D[Num];/*** 生成地图，输入地图的基本信息***/void BuildMap(){int i,j;/* 初始化平面图矩阵 */for ( i=0;i<11;i++){for ( j=0;j<11;j++){Edge[0][0].value=0 , Edge[0][1].value=25 , Edge[0][2].value=25 ;Edge[0][3].value=90, Edge[0][4].value=uplimit, Edge[0][5].value=uplimit ;Edge[0][6].value=10 , Edge[0][7].value=uplimit ,Edge[0][8].value=uplimit;Edge[0][9].value=uplimit, Edge[0][10].value=uplimit;Edge[1][0].value=25 , Edge[1][1].value=0 , Edge[1][2].value=10 ;Edge[1][3].value=32, Edge[1][4].value=uplimit, Edge[1][5].value=uplimit ;Edge[1][6].value=10 , Edge[1][7].value=uplimit ,Edge[1][8].value=21;Edge[1][9].value=16, Edge[1][10].value=uplimit;Edge[2][0].value=25 , Edge[2][1].value=10 , Edge[2][2].value=0 ;Edge[2][3].value=uplimit, Edge[2][4].value=uplimit, Edge[2][5].value=uplimit ;Edge[2][6].value=uplimit, Edge[2][7].value=uplimit ,Edge[2][8].value=uplimit;Edge[2][9].value=uplimit, Edge[2][10].value=uplimit;Edge[3][0].value=90 , Edge[3][1].value=32 , Edge[3][2].value=uplimit ;Edge[3][3].value=0 , Edge[3][4].value=uplimit, Edge[3][5].value=uplimit ;Edge[3][6].value=uplimit, Edge[3][7].value=uplimit ,Edge[3][8].value=26;Edge[3][9].value=uplimit, Edge[3][10].value=uplimit;Edge[4][0].value=uplimit, Edge[4][1].value=uplimit ,Edge[4][2].value=uplimit ;Edge[4][3].value=uplimit, Edge[4][4].value=0, Edge[4][5].value=9 ;Edge[4][6].value=uplimit, Edge[4][7].value=uplimit ,Edge[4][8].value=uplimit;Edge[4][9].value=uplimit, Edge[4][10].value=60;Edge[5][0].value=uplimit , Edge[5][1].value=uplimit ,Edge[5][2].value=uplimit ;Edge[5][3].value=uplimit, Edge[5][4].value=9, Edge[5][5].value=0 ;Edge[5][6].value=uplimit , Edge[5][7].value=15 , Edge[5][8].value=50;Edge[5][9].value=14, Edge[5][10].value=uplimit;Edge[6][0].value=10 , Edge[6][1].value=10 , Edge[6][2].value=uplimit;Edge[6][3].value=uplimit, Edge[6][4].value=uplimit,Edge[6][5].value=uplimit ;Edge[6][6].value=0 , Edge[6][7].value=35 , Edge[6][8].value=uplimit;Edge[6][9].value=30, Edge[6][10].value=uplimit;Edge[7][0].value=uplimit , Edge[7][1].value=uplimit ,Edge[7][2].value=uplimit ;Edge[7][3].value=uplimit, Edge[7][4].value=uplimit,Edge[7][5].value=15 ;Edge[7][6].value=35 , Edge[7][7].value=0 , Edge[7][8].value=uplimit;Edge[7][9].value=13, Edge[7][10].value=uplimit;Edge[8][0].value=uplimit , Edge[8][1].value=21 , Edge[8][2].value=uplimit ;Edge[8][3].value=26, Edge[8][4].value=uplimit;Edge[8][5].value=50 ;Edge[8][6].value=uplimit , Edge[8][7].value=uplimit ,Edge[8][8].value=0;Edge[8][9].value=22, Edge[8][10].value=10;Edge[9][0].value=uplimit , Edge[9][1].value=16 , Edge[9][2].value=uplimit ;Edge[9][3].value=uplimit, Edge[9][4].value=uplimit, Edge[9][5].value=14 ;Edge[9][6].value=30 , Edge[9][7].value=13 , Edge[9][8].value=22;Edge[9][9].value=0, Edge[9][10].value=uplimit;Edge[10][0].value=uplimit , Edge[10][1].value=uplimit ,Edge[10][2].value=uplimit;Edge[10][3].value=uplimit, Edge[10][4].value=60; Edge[10][5].value=uplimit ;Edge[10][6].value=uplimit , Edge[10][7].value=uplimit ,Edge[10][8].value=10;Edge[10][9].value=uplimit, Edge[10][10].value=0;}}}/* 找出场所间的最短距离--迪杰斯特拉算法 */void ShortestDist(int s){for ( int i=0;i<11;i++){ //dist和path数组初始化dist[i].value=Edge[s][i].value; //邻接矩阵第s行元素赋值到dist中S[i].value=0; //已求出最短路径的顶点集合初始化if(i!=s && dist[i].value<uplimit){path[i].value=s;}else path[i].value=-1; //路径存放数组初始化}S[s].value=1;//顶点s加入顶点集合dist[s].value=0;/* 循环计算该场所与邻接场所之间的最短距离 */for (i=0;i<11-1;i++){ //从顶点s确定n-1条路径float min=uplimit;int u=s;for (int j=0;j<11;j++){ //选择当前不在集合S中具有最短路径的顶点u/* 如果有路径比目前的最小值还小，则替换这个最小值 */if (!S[j].value && dist[j].value<min){u=j;min=dist[j].value;}}S[u].value=1; //将顶点u加入集合S，表示它已在最短路径上for (int w=0;w<11;w++){ //修改if (!S[w].value && Edge[u][w].value<uplimit && dist[u].value+Edge[u][w].value<dist[w].value){dist[w].value=dist[u].value+Edge[u][w].value;path[w].value=u;}}}}void bh() //显示场所名称{cout<<"\t0.女生公寓 1.图书馆 2.体育馆"<<endl;cout<<"\t3.校东门 4.一教学楼 5.教师公寓"<<endl;cout<<"\t6.食堂 7.体育场 8.校南门"<<endl;cout<<"\t9.大学生活动中心 10.实验楼"<<endl;}/*将顶点序列号转换成场所名称*/void Outpath(int c){ switch(c){case 0: cout<<"女生公寓";break;case 1: cout<< "图书馆";break;case 2: cout<< "体育馆";break;case 3: cout<< "校东门";break;case 4: cout<< "一教学楼";break;case 5: cout<< "教师公寓";break;case 6: cout<< "食堂";break;case 7: cout<< "体育场";break;case 8: cout<< "校南门";break;case 9: cout<< "大学生活动中心";break;case 10:cout<<"实验楼";break;}/* 输出两个场所之间的最短距离，和最短路径 */void getdata(int s,int e){D[0].value=e;int k;for (k=0;D[k].value!=s;k++){D[k+1].value=path[D[k].value].value;}if(S[e].value){cout<<"\n\t场所"<<s<<","<<e<<"之间的最短距离是："<<dist[e].value<<endl;cout<<"\n\t场所"<<s<<","<<e<<"之间的最短路径是:";for(; k!=-1;k--){Outpath(D[k].value);if (k!=0){cout<<" --> ";}}}elsecout<<"\n\t场所"<<s<<"到场所"<<e<<"之间没有路径!"<<endl;}void Begin(){int flag=1;int s,e;while ( flag ){bh();cout<<"\n\t请输入起始场所号与目的场所号：";cin>>s>>e;cout<<endl;if(s<11 && s>=0 && e<11 && e>=0){flag=0;}elsecout<<"\n场所号非法，请重新输入！";}ShortestDist(s);getdata(s,e);/*显示场所的具体信息*/void info(int c) //c为场所对应的数字号{switch(c){case 0:cout<<"\t▲女生公寓，具体指桂园七栋，住宿条件较好。