数据结构课程设计—校园导航报告

1、下载可编辑课程设计报告学院、系：大学学院计算机科学与技术系专业：软件工程班级：2008级9班课程设计科目数据结构学生：04080904 喆指导教师：娄雅芳完成时间：2010 年 10 月-12 月.专业 .整理 .下载可编辑校园导航系统设计报告一、设计任务与目标设计要求：设计你的学校的平面图，至少包括10 个以上的场所，每两个场所间可以有不同的路，且路长也可能不同，找出从任意场所到达另一场所的最佳路径（最短路径）。本系统是一个涉及大学学院相关景点和场所查询系统, 是为了方便人们能够更快更准地获得学校各个景点和场所的详细信息。本系统为用户提供以下功能:( 一) 、查询了解学校概况，为导游参观者提

2、供关于学校的相关信息。( 二) 、查询校园各个场所和景点信息;( 三) 、为导游者或外来人员参观人员提供校园交通信息，方便用户走访学校。校园导航查询系统的开发方法总结如下：(1) 调查，了解学校各个场所与 场所或者是各个景点与景点之间的信息，路径和距离，从外来人员或者参观者和走访者的角度出发，该如何设计才能满足用户需求。(2) 分析，对调查得到的数据进行分析，根据其要求实现的功能分析系统结构和界面将实现的基本功能。(3) 设计与开发，设计系统界面并编辑实现其各个功能的代码。(4) 调试，在设计完成后，调试系统运行的状况，修改完善系统 , 然后进行测试。二、方案设计与论证校园旅游模型是由各个景点

3、和景点以及场所和场所之间的路径组成的，所以这完全可以用数据结构中的图来模拟。用图的结点代表景点或场所，用图的.专业 .整理 .下载可编辑边代表景点或场所之间的路径。所以首先应创建图的存储结构。结点值代表景点信息，边的权值代表景点间的距离。结点值及边的权值采用图存储。本系统需要查询景点信息和求一个景点到另一个景点的最短路径长度及路线，为方便操作，所以给每个景点一个代码，用结构体类型实现。计算路径长度，最短路线和最佳路径时可分别用迪杰斯特拉（Dijkastra）算法和哈密而顿回路算法实现。最后用 switch 选择语句选择执行浏览景点信息或查询最短路径和距离。搭建程序框架图，其图如下所示：1、打开

4、导航在屏幕显示输出学校各个景点场所选查择询相学应校数简介字，导航参观路线和各2、主菜单个景点与场所之间的距离回车返回主菜选择屏幕所设菜单单进入子菜单选择景点与场所，查询了解景点与选择相应数字3、子菜单场所信息，及景点与场所之间的最短路径退出系统4、退出导航三、算法说明（一）设计功能的实现接下来根据以上搭建的程序框架完成各个模块的算法1、首先是抽象数据类型的定义：.专业 .整理 .下载可编辑图的抽象数据类型的定义：ADTMgragh数据对象 V:V是具有相同特征的数据元素的集合，称为定点集数据关系 R=VRVR= | V, W V, 表示从 V 到 W的边2、 基本操作：CreateUDN(&G

5、,V,VR); /创建图初始条件： V是图的顶点集， VR是图中边的集合。操作结果：按 V 和 VR的定义构造图 G。（二）主要算法设计及相关算法补充先创建图存储学校各个景点或场所，以图的顶点表示景点或场所，以边表示路径，再利用迪杰斯特拉（DijkStra）算法求出校园各个地方的最短路径，然后根据需要进行补充相关算法。四、全部源程序清单#include stdio.h#include iostream.h#include malloc.h#include conio.h#include stdlib.h#defineNum11/最多顶点个数#defineuplimit100000/定义一个无穷

6、大的值struct inttint value;inttEdgeNumNum;/Edge为带权邻接矩阵inttdistNum;/dist为最短路程inttpathNum;/path为最短路径上.专业 .整理 .下载可编辑该顶点的前一顶点的顶点号inttSNum;/S为已求得的在最短路径上的顶点号intt DNum;/* 生成地图，输入地图的基本信息*/voidBuildMap()inti,j;/*初始化平面图矩阵*/for(i=0;i11;i+)for(j=0;j11;j+)Edge00.value=0,Edge01.value=25,Edge02.value=25 ;Edge03.value

7、=90,Edge04.value=uplimit,Edge05.value=uplimit ;Edge06.value=10,Edge07.value=uplimit,Edge08.value=uplimit;Edge09.value=uplimit,Edge010.value=uplimit;Edge10.value=25,Edge11.value=0,Edge12.value=10 ;Edge13.value=32,Edge14.value=uplimit,Edge15.value=uplimit ;Edge16.value=10,Edge17.value=uplimit,Edge18.v

8、alue=21;Edge19.value=16,Edge110.value=uplimit;Edge20.value=25,Edge21.value=10,Edge22.value=0 ;Edge23.value=uplimit,Edge24.value=uplimit,Edge25.value=uplimit ;Edge26.value=uplimit,Edge27.value=uplimit,Edge28.value=uplimit;Edge29.value=uplimit,Edge210.value=uplimit;Edge30.value=90,Edge31.value=32,Edge

9、32.value=uplimit ;Edge33.value=0,Edge34.value=uplimit,Edge35.value=uplimit ;.专业 .整理 .下载可编辑Edge36.value=uplimit,Edge37.value=uplimit,Edge38.value=26;Edge39.value=uplimit,Edge310.value=uplimit;Edge40.value=uplimit,Edge41.value=uplimit,Edge42.value=uplimit ;Edge43.value=uplimit,Edge44.value=0,Edge45.va

10、lue=9 ;Edge46.value=uplimit,Edge47.value=uplimit,Edge48.value=uplimit;Edge49.value=uplimit,Edge410.value=60;Edge50.value=uplimit,Edge51.value=uplimit,Edge52.value=uplimit ;Edge53.value=uplimit,Edge54.value=9,Edge55.value=0 ;Edge56.value=uplimit,Edge57.value=15,Edge58.value=50;Edge59.value=14,Edge510

11、.value=uplimit;Edge60.value=10,Edge61.value=10,Edge62.value=uplimit;Edge63.value=uplimit,Edge64.value=uplimit,Edge65.value=uplimit ;Edge66.value=0,Edge67.value=35,Edge68.value=uplimit;Edge69.value=30,Edge610.value=uplimit;Edge70.value=uplimit,Edge71.value=uplimit,Edge72.value=uplimit ;Edge73.value=u

12、plimit,Edge74.value=uplimit,Edge75.value=15 ;Edge76.value=35,Edge77.value=0,Edge78.value=uplimit;Edge79.value=13,Edge710.value=uplimit;Edge80.value=uplimit,Edge81.value=21,Edge82.value=uplimit ;Edge83.value=26,Edge84.value=uplimit;Edge85.value=50 ;Edge86.value=uplimit,Edge87.value=uplimit,Edge88.val

13、ue=0;Edge89.value=22,Edge810.value=10;.专业 .整理 .下载可编辑Edge90.value=uplimit,Edge91.value=16,Edge92.value=uplimit ;Edge93.value=uplimit,Edge94.value=uplimit,Edge95.value=14 ;Edge96.value=30,Edge97.value=13,Edge98.value=22;Edge99.value=0,Edge910.value=uplimit;Edge100.value=uplimit,Edge101.value=uplimit,E

14、dge102.value=uplimit;Edge103.value=uplimit,Edge104.value=60;Edge105.value=uplimit ;Edge106.value=uplimit,Edge107.value=uplimit,Edge108.value=10;Edge109.value=uplimit,Edge1010.value=0;/*找出场所间的最短距离 - 迪杰斯特拉算法*/void ShortestDist(int s)for ( int i=0;i11;i+)/dist和 path 数组初始化disti.value=Edgesi.value;/邻接矩阵第

15、 s 行元素赋值到 dist中Si.value=0;/已求出最短路径的顶点集合初始化if(i!=s & disti.valueuplimit)pathi.value=s;else pathi.value=-1;/路径存放数组初始化Ss.value=1;/ 顶点 s 加入顶点集合dists.value=0;/*循环计算该场所与邻接场所之间的最短距离*/for (i=0;i11-1;i+)/从顶点 s 确定 n-1 条路径float min=uplimit;int u=s;for (int j=0;j11;j+)/选择当前不在集合S 中具有最短路径的顶点u/*如果有路径比目前的最小值还小，则替换这

16、个最小值*/if (!Sj.value & distj.valuemin).专业 .整理 .下载可编辑u=j;min=distj.value;Su.value=1;/将顶点 u 加入集合S，表示它已在最短路径上for (int w=0;w11;w+)/修改if(!Sw.value&Edgeuw.valueuplimit&distu.value+Edgeuw.valuedistw.value)distw.value=distu.value+Edgeuw.value;pathw.value=u;void bh()/显示场所名称coutt0.女生公寓1.图书馆2.体育馆 endl;coutt3.校东

17、门4.一教学楼5.教师公寓 endl;coutt6.食堂7.体育场8.校南门 endl;coutt9.大学生活动中心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 体育

18、场 ;break;case 8: cout 校南门 ;break;case 9: cout 大学生活动中心 ;break;case 10:cout实验楼 ;break;.专业 .整理 .下载可编辑/* 输出两个场所之间的最短距离，和最短路径 */ void getdata(int s,int e)D0.value=e;int k;for (k=0;Dk.value!=s;k+)Dk+1.value=pathDk.value.value;if(Se.value)coutnt场所s,e之间的最短距离是：diste.valueendl;coutnt场所 s,e 之间的最短路径是 :;for(; k!

19、=-1;k-)Outpath(Dk.value);if (k!=0)cout ;elsecoutnt场所 s 到场所 e 之间没有路径 !endl;void Begin()int flag=1;int s,e;while ( flag )bh();coutse;coutendl;if(s=0 & e=0)flag=0;elsecoutn场所号非法，请重新输入！;ShortestDist(s);getdata(s,e);.专业 .整理 .下载可编辑/* 显示场所的具体信息 */void info(int c)/c为场所对应的数字号switch(c)case 0:coutt 女生公寓，具体指桂园七

20、栋，住宿条件较好。endl;break;case 1:coutt 图书馆，部藏有丰富的书籍，供同学们学习参考，也可以自习。 endl;break;case 2:coutt 体育馆，供同学们进行体育活动以及上体育课。endl;break;case 3:coutt 校东门，大学学院的正门。 endl; break;case 4:coutt 一教学楼，供同学们上课和自习使用。 endl; break;case 5:coutt 教师公寓，提供给单身的老师们居住。 endl; break;case 6:coutt 食堂，有两层楼 , 是同学们用餐的地方。 endl; break;case 7:coutt

21、 体育场，是同学们开运动会和进行体育赛事的地方。 endl;break;case 8:coutt 校南门，这是同学，老师比较集中的地方。晚上的时候这里最热闹。； endl;coutt另一边是小店的集中地，相当于一个小型商业街。.专业 .整理 .下载可编辑endl;break;case 9:coutt 大学生活动中心，这栋楼是办公楼也是活动中心，主要供各系的同学办活动使用； endl;coutt这栋楼的后面就是高尔夫球场，主要供旅游系的同学上课使用。 endl;break;case 10:coutt 实验楼，是同学们计算机上机，各系做实验的地方。 endl;break;case 11:syste

22、m(cls);break;default:coutt输入不合法，请重新输入!endl;break;void num()couttt*endl;couttt*校园导航系统*endl;couttt*endl;couttt 0.女生公寓 endl;couttt 1.图书馆 endl;couttt 2.体育馆 endl;couttt 3.校东门 endl;couttt 4.一教学楼 endl;couttt 5.教师公寓 endl;couttt 6.食堂 endl;couttt 7.体育场 endl;couttt 8.校南门 endl;couttt 9.大学生活动中心 endl;couttt 10.实验

23、楼 endl;void main().专业 .整理 .下载可编辑int c;char option=0;coutt-endl;coutt* * * * endl;coutt* * * * * * * * * * * * endl; coutt * * * * * * * * * * * * * * endl; coutt * * * * * * * * * * * * endl;coutt* * * * * * endl;coutt-endl;coutendl;coutendl;coutt*endl;coutttt欢迎光临大学学院 endl;coutt*endl;coutendltendl;c

24、outttt1.显示场所的编号 endl;coutttt2.查看场所的具体信息 endl;coutttt3.找出最短路径及计算路径长度endl;coutttt4.退出 endl;coutt endl;coutendloption;while (option!=0)switch(option)case 1:num();coutendltt*endl;coutttt1.显示场所的编号 endl;coutttt2.查看场所的具体信息 endl;coutttt3.找出最短路径及计算路径长度endl;coutttt4.退出 endl;.专业 .整理 .下载可编辑couttt*endl;coutoption;system(cls);/清屏break;case 2:/具体信息coutendl;coutendl;coutt请从 0 10 中选择任意字母，查看所对应场所的具体信息：endl;coutt选择 11 则退出该命令 c;info(c);if(c=11)coutendltt*endl;coutttt1.显示场所的编号 endl;coutttt2.查看场所的具体信息 endl;coutttt3.找出最短路径及计算路径长度endl;coutttt4.退出 endl;couttt*endl;coutoption;break;cas