数据结构课程设计-校园导游咨询

PAGEPAGE9学号武汉科技大学城市学院课程设计报告课程名称数据结构课程设计题目校园导游咨询学部专业班级姓名指导教师2016年6月12日数据结构课程设计任务书课程设计名称：校园导游咨询课程设计开发平台与工具：MicrosoftVisualC++6.01.课程设计任务设计学校的校园平面图，所含景点不少于10个。以图中顶点表示学校各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。为来访客人提供图中任意景点相关信息的查询。2.课程设计功能说明（1）输入数据：景点个数，景点信息结构（包含名称、代号、简介等信息）（2）输入约束：景点个数为整形；校园景点平面图用图的形式存储;（3）实现以下功能：a)查询校园地图；b)查询单个景点的相关信息如名称或简介等；c)查询从某个景点到其他所有景点最短路径长度即最短距离和途中要经历的景点；d)查询学校里任意两个景点之间的最短距离和途经点。3.设计内容及步骤（1）分析问题，给出数学模型，设计相应的数据结构。a)分析问题的特点，用数学表达式或其它形式描述其数学模型。b)选择能够体现问题本身特点的逻辑结构。c)在逻辑结构确定的情况下，为算法的设计选择相应的存储结构，顺序存储结构和链式存储结构的不同存储方式，其对应的算法也不同。（2）在已经选择好数据结构的前提下，为解决的问题设计算法。a)确定所需要的模块b)对于稍复杂的问题，要充分利用模块化程序设计方法，自顶向下，逐步细化，在整体思路确定的情况下，考虑所需模块数，各模块完成功能以及模块之间的数据联系和调用关系。c)各子模块功能描述：给出主要模块的算法描述，用流程图或伪代码表示。d)模块之间的调用关系：给出算法各模块之间的关系图示。（3）编写程序为了提高工作效率，要求学生充分利用上机调试程序的时间。（4）用测试数据去验证算法及程序的正确性（5）算法分析：分析算法的时间复杂度和空间复杂度。目录一需求分析 2二概要设计 4三详细设计 5四测试分析 6五小结 6参考文献 7课设计评分表 8

1需求分析1.1需求分析来访我校的游客可能刚到学校不了解学校里的景点，为了给游客提供一条最短的游览路径，结合对校园平面图的分析，将其转化为数据并保存在系统中，使顾客可以找到游玩景点最省市，最高效的路径。1.2功能需求描述<1>设计学校的校园平面图，所含景点10个。<2>为来访的客人提供图中任意景点相关信息的查询。<3>为来访客人提供任意景点的问路查询。即查询任意两个景点之间的一个最短的简单路径，并提示出个经典之间的防卫关系，行走方向。2概要设计2.1抽象数据类型定义#include<stdio.h>#include<process.h>/*定义符号常量*/#defineINT_MAX10000#definen10/*定义全局变量*/intcost[n][n];/*边的值*/intshortest[n][n];/*两点间的最短距离*/intpath[n][n];/*经过的景点*/开始2.2模块结构开始显示查询信息显示查询信息加入文字文件读取加入文字文件读取显示最短路径显示最短路径退出退出图2.2模块图2.3函数的详细调用处理流程当游客选择了要查找景点的信息的介绍这一项功能的时候，程序就会调用DisIntroduction(G);函数进入到查找景点的介绍的界面，当游客输入了需要查找的景点的名称的时候，程序利用for();循环语句来查找是否有这个景点for(int

i=0;i<G.vexnum;i++)

{

int

m

=

strcmp(G.vexs[i].name,n1);

if(m==0)

{

v1=i;

count1=count1+1;

}}找到将它的编号返回，并输出它的介绍，没有找到这输出错误提示，提醒游客进行相关的操作进入正确的操作过程当中。当游客选择了要查找两个景点之间的最短距离这一项功能的时候，程序就会调用DisPath(G)；函数进入到查找两个景点之间的最短距离的操作界面当中，当游客输入了两个景点的名称过后，程序会调用strcmp();函数查看是否有这两个景点，如果有则返回他们各自的编号，并调用ShortPath_DIJ(G,v1,v2);函数进入到查找最短路径问题的程序当中。

for(v=0;v<G.vexnum;v++)//各对节点之间初始已知路径及距离

{

final[v]=FALSE;//从V出发的最短路径的空集合

D[v]=G.arcs[v0][v];//从V出发到图上其余各个定点v0可能到达的最短路径的初始值

for(w=0;w<G.vexnum;w++)

{

P[v][w]=FALSE;//设空路径

}

if(D[v]<MAXNUM)

{

P[v][v0]=TRUE;

P[v][v]=TRUE;

}

}

D[v0]=0;

final[v0]=TRUE;

int

a[20];

for(i=0;i<G.vexnum;i++)//对Path[i][j]进行初始化，使其值全部为1000，便于后期的判断

{

for(j=0;j<G.vexnum;j++)

{

Path[i][j]=1000;

}

}

for(i=0;i<G.vexnum;i++)//对数组进行初始化，以便对Path[i][j]进行描述

{

a[i]=1;}

for(v=0;v<G.vexnum;v++)//各条路线的初始节点为v0

{

Path[v][0]=v0;

}

//开始主循环，每次求解得到v0到某个v顶点的最短路径，并加入到S集合中

for(i=1;i<G.vexnum;i++)//其余G.vexnum

-

1个顶点

{

m=MAXNUM;//当前所知的离v0最近的距离

for(w=0;w<G.vexnum;w++)

{

if(!final[w])//w顶点在V-S中

{

if(D[w]<m)//w顶点离v0顶点更近

{

v=w;

m=D[w];

}

}

}

Path[v][a[v]]=v;//离v0顶点最近的v加入s集合

final[v]=TRUE;

for(w=0;w<G.vexnum;w++)//更新当前最短路径及距离

{

if((!final[w])&&(m+G.arcs[v][w]<D[w]))

{

D[w]=m+G.arcs[v][w];//修改当前的最短路径的值

int

k0=1;

a[w]=1;

while(Path[v][k0]!=1000)

//如果上述条件成立，Path[w]路径需要改变，因为从v0到w的路径显然经过了v0和v之间的所有的点（包括v）

{

Path[w][k0]=Path[v][k0];

k0++;

a[w]++;

}

}

}

}

cout<<"两个景点之间的最短路径为:"<<'\t';

int

k=0;

while(Path[v2][k]!=1000){

int

m=Path[v2][k];

cout<<G.vexs[m].name<<'\t';

k++;

}

cout<<endl;

cout<<"两个景点之间的最短距离为:

"<<D[v2]<<"M"<<endl;

cout<<"请选择要进行的操作(I:查询景点信息，P:查询两个景点之间的最短路径，Q:退出)"<<endl;

(1)假设用带权的邻接矩阵arcs来表示带权的有向图，arcs[i][j]表示弧（vi,vj）上的权值。若(vi,vj)不存在，则置arcs[i][j]为无穷大。S为已找到从v出发的最短路径的终点集合，它的初始状态为空集。那么，从v出发到图上其余各个定点vi可能到达的最短路径长度的初始值为：D[i]

=

arcs[v][i];

(2)选择vj,使得D[j]

=

Min{D[i]

|

vi

∈

V

–

S}vj就是当前求得的一条从v出发的最短路径的终点。令S

=

S

∪

{j};

(3)修改从v出发到集合V

–

S

上任意顶点vk可到达的最短路径的长度。如果D[j]

+

arcs[j][k]

<

D[k]则修改D[k]为D[k]

=

D[j]+arcs[j][k];

(4)重复操作(2)、(3)共n

–

1

次，由此求得从v到图上其余各个顶点的最短路径是依路径长度递增的序列。从而求得了从一个景点到另一个景点的最短路径的问题。

3详细设计3.1数据结构存储定义1.

邻接矩阵typedef

int

AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

定义一个邻接矩阵，用邻接矩阵来定义和储存边的相关信息。

2.

顶点的结构体

typedef

struct

Vertex//定义图中顶点的数据类型

{

int

num;//景点编号

char

name[14];//景点名称

char

introduction[100];//景点介绍

}Vertex;

定义一个顶点的结构体，用来储存景点的编号、景点得名称和景点的介绍等关于景点的信息。

3.无向图的结构体

typedef

struct

//定义图的数据类型

{

Vertex

vexs[MAX_VERTEX_NUM];//顶点的结构体

AdjMatrix

arcs;//边的邻接矩阵

int

vexnum,arcnum;//顶点的个数，边的个数

}MGraph;

定义一个图的结构体，用来储存顶点的信息、边的信息、顶点的个数和边的个数等相关的信息便于我们以后在用的时候能够方便快捷的调用。

定义好这些结构体后，当我们以后需要调用的时候，我们就能够方便快捷的调用这些结构体，从而使得我们在运行程序的时候能够更加的快速能够提高我们的程序的运行效率，大大的节省了我们的时间还使得程序变得更加的简单3.2算法设计voidfloyed(){/*用floyed算法求两个景点的最短路径*/inti,j,k;for(i=1;i<=n;i++)for(j=1;j<=n;j++){shortest[i][j]=cost[i][j];path[i][j]=0;}for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)if(shortest[i][j]>(shortest[i][k]+shortest[k][j])){/*用path[][]记录从i到j的最短路径上点j的前驱景点的序号*/shortest[i][j]=shortest[i][k]+shortest[k][j];path[i][j]=k;path[j][i]=k;}}3.3界面设计3.3.1主界面图3.1主界面3.3.2查询图3.2查询界面3.3.3查找最短路径图3.3查找最短路径界面3.3.4退出图3.4退出4测试分析调试过程中难免会遇到这样或者那样的问题，一个很低级的错误就是在字符串的赋值上居然还会出错，本来是不可以像int型数据那样直接用等号赋值的，可是刚开始由于食物却犯了这样低级的错误结果导致出现一百多个错误，当时还莫名其妙，仔细看了几遍后才把问题想明白，字符串赋值必须用strcpy函数。看来基本功还是相当重要的。5小结在本次的实验过程当中，虽然有各种各样的问题在困扰着我，但是好在我的身边总会有人在这个时候出现为我解决这些问题，而他们就我的老师和同学们，一个人做事的时候总是会遇到问题的，有问题并不可怕只要我们相信我们不是一个人在战斗而是有很多的同学和老师与我们站在一起的样我们就能够战胜各种困难，感谢我的老师和我的同学们。是他们在我遇到问题的时候给我指明了解决的方法，从而克服了一个又一个的问题最终解决了所有的问题实现了程序所需要的功能，感谢我的同学们，不论是上课还是下课，只要是遇到了困难找到他们的时候只要是能够解决的他们会义不容辞的献出自己的力量。感谢老师们的谆谆教诲，他们不辞辛劳为了我们能够顺利的解决问题无时刻不在我们的身边，当我们一遇到问题的时候他就会出现，从没有半点怨言。最后还要感谢学校感谢给我们提供了良好的实验环境，使我们能够安心轻松的在好的额环境当中完成我们的实验。

参考文献[1]严蔚敏,吴伟民.数据结构（C语言版）.清华大学出版社,2011.[2]刘振安,刘燕君.C程序设计课程设计[M].北京:机械工业出版社,2004.[3]谭浩强.C程序设计（第三版）.清华大学出版社,2010.[4]吴文虎.程序设计基础.清华大学出版社,2010.[5]严蔚敏,陈文博.数据结构及应用算法教程.清华大学出版社,2004.

课设计评分表评分标准：学生是否严格遵守课程设计纪律，按照规定时间完成设计任务(占30%)程序设计的质量与规范：(占40%)(1)选题难度：ACM题目（A级或B级）、传统题目(2)是否采用了良好的设计方法，独立完成程序设计(3)程序界面设计是否合理、美观(4)程序是否运行正常，未见运行错误课程设计报告书的质量与规范(占30%)教师评分：1.学生出勤得分：A，B，C，D2.程序设计得分：A，B，C，D3.设计报告得分：A，B，C，D教师评语：根据该生在课程设计期间，是否严格遵守课程设计纪律，按照规定时间完成设计任务，完成的程序设计的质量与规范，提交的课程设计报告书的质量与规范等多方面的评分，该生本次课程设计的评分为：________教师签名：杨艳霞日期：2016年6月15日基于C8051F单片机直流电动机反馈控制系统的设计与研究基于单片机的嵌入式Web服务器的研究MOTOROLA单片机MC68HC（8）05PV8/A内嵌EEPROM的工艺和制程方法及对良率的影响研究基于模糊控制的电阻钎焊单片机温度控制系统的研制基于MCS-51系列单片机的通用控制模块的研究基于单片机实现的供暖系统最佳启停自校正（STR）调节器单片机控制的二级倒立摆系统的研究基于增强型51系列单片机的TCP/IP协议栈的实现基于单片机的蓄电池自动监测系统基于32位嵌入式单片机系统的图像采集与处理技术的研究基于单片机的作物营养诊断专家系统的研究基于单片机的交流伺服电机运动控制系统研究与开发基于单片机的泵管内壁硬度测试仪的研制基于单片机的自动找平控制系统研究基于C8051F040单片机的嵌入式系统开发基于单片机的液压动力系统状态监测仪开发模糊Smith智能控制方法的研究及其单片机实现一种基于单片机的轴快流CO〈,2〉激光器的手持控制面板的研制基于双单片机冲床数控系统的研究基于CYGNAL单片机的在线间歇式浊度仪的研制基于单片机的喷油泵试验台控制器的研制基于单片机的软起动器的研究和设计基于单片机控制的高速快走丝电火花线切割机床短循环走丝方式研究基于单片机的机电产品控制系统开发基于PIC单片机的智能手机充电器基于单片机的实时内核设计及其应用研究基于单片机的远程抄表系统的设计与研究基于单片机的烟气二氧化硫浓度检测仪的研制基于微型光谱仪的单片机系统单片机系统软件构件开发的技术研究基于单片机的液体点滴速度自动检测仪的研制基于单片机系统的多功能温度测量仪的研制基于PIC单片机的电能采集终端的设计和应用基于单片机的光纤光栅解调仪的研制气压式线性摩擦焊机单片机控制系统的研制基于单片机的数字磁通门传感器基于单片机的旋转变压器-数字转换器的研究基于单片机的光纤Bragg光栅解调系统的研究单片机控制的便携式多功能乳腺治疗仪的研制基于C8051F020单片机的多生理信号检测仪基于单片机的电机运动控制系统设计Pico专用单片机核的可测性设计研究基于MCS-51单片机的热量计基于双单片机的智能遥测微型气象站MCS-51单片机构建机器人的实践研究基于单片机的轮轨力检测基于单片机的GPS定位仪的研究与实现基于单片机的电液伺服控制系统用于单片机系统的MMC卡文件系统研制基于单片机的时控和计数系统性能优化的研究基于单片机和CPLD的粗光栅位移测量系统研究单片机控制的后备式方波UPS提升高职学生单片机应用能力的探究基于单片机控制的自动低频减载装置研究基于单片机控制的水下焊接电源的研究基于单片机的多通道数据采集系统基于uPSD3234单片机的氚表面污染测量仪的研制基于单片机的红外测油仪的研究96系列单片机仿真器研究与设计基于单片机的单晶金刚石刀具刃磨设备的数控改造基于单片机的温度智能控制系统的设计与实现基于MSP430单片机的电梯门机控制器的研制基于单片机的气体测漏仪的研究基于三菱M16C/6N系列单片机的CAN/USB协议转换器基于单片机和DSP的变压器油色谱在线监测技术研究基于单片机的膛壁温度报警系统设计基于AVR单片机的低压无功补偿控制器的设计基于单片机船舶电力推进电机监测系统基于单片机网络的振动信号的采集系统基于单片机的大容量数据存储技术的应用研究基于单片机的叠图机研究与教学方法实践基于单片机嵌入式Web服务器技术的研究及实现基于AT89S52单片机的通用数据采集系统基于单片机的多道脉冲幅度分析仪研究机器人旋转电弧传感角焊缝跟踪单片机控制系统基于单片机的控制系统在PLC虚拟教学实验中的应用研究基于单片机系统的网络通信研究与应用基于PIC16F877单片机的莫尔斯码自动译码系统设计与研究基于单片机的模糊控制器在工业电阻炉上的应用研究基于双单片机冲床数控系统的研究与开发基于Cygnal单片机的μC/OS-Ⅱ的研究基于单片机的一体化智能差示扫描量热仪系统研究基于TCP/IP协议的单片机与Internet互联的研究与实现变频调速液压电梯单片机控制器的研究基于单片机γ-免疫计数器自动换样功能的研究与实现基于单片机的倒立摆控制系统设计与实现单片机嵌入式以太网防盗报警系统基于51单片机的嵌入式Internet系统的设计与实现单片机监测系统在挤压机上的应用MSP430单片机在智能水表系统上的研究与应用基于单片机的嵌入式系统中TCP/IP协议栈的实现与应用单片机在高楼恒压供水系统中的应用基于ATmega16单片机的流量控制器的开发基于MSP430单片机的远程抄表系统及智能网络水表的设计基于MSP430单片机具有数据存储与回放功能的嵌入式电子血压计的设计基于单片机