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

学 号

武 汉 科 技 大 学 城 市 学 院

课 程 设 计 报 告

课程名称 数据结构课程设计
题 目
校园导游咨询
学 部

专 业

班 级

姓 名

指导教师

2016
年
6
月
12
日

11

数据结构课程设计任务书

课程设计名称：校园导游咨询
课程设计开发平台与工具：Microsoft Visual C++ 6.0
1.课程设计任务
设计学校的校园平面图，所含景点不少于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>

/*定义符号常量*/
#define INT_MAX 10000
#define n 10

/*定义全局变量*/
int cost[n][n];/* 边的值*/
int shortest[n][n];/* 两点间的最短距离*/
int path[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算法设计
void floyed()
{/*用floyed算法求两个景点的最短路径*/
int i,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.

课设计评分表

评分标准：
1. 学生是否严格遵守课程设计纪律，按照规定时间完成设计任务(占30%)
2. 程序设计的质量与规范：(占40%)
(1)选题难度：ACM题目（A级或B级）、传统题目
(2)是否采用了良好的设计方法，独立完成程序设计
(3)程序界面设计是否合理、美观
(4)程序是否运行正常，未见运行错误
3. 课程设计报告书的质量与规范 (占30%)

教师评分：
1.学生出勤得分： A， B， C， D
2.程序设计得分： A， B， C， D
3.设计报告得分： A， B， C， D

教师评语：

根据该生在课程设计期间，是否严格遵守课程设计纪律，按照规定时间完成设计任务，完成的程序设计的质量与规范，提交的课程设计报告书的质量与规范等多方面的评分，该生本次课程设计的评分为：________

教师签名：杨艳霞

日期： 2016 年 6 月 15 日

目 录

第一章 总 论 1
一、项目提要 1
二、可行性研究报告编制依据 2
三、综合评价和论证结论 3
四、存在问题与建议 4
第二章 项目背景及必要性 5
一、项目建设背景 5
二、项目区农业产业化经营发展现状 11
三、项目建设的必要性及目的意义 12
第三章 建设条件 15
一、项目区概况 15
二、项目实施的有利条件 17
第四章 建设单位基本情况 19
一、建设单位概况 19
二、研发能力 20
三、财务状况 20
第五章 市场分析与销售方案 21
一、市场分析 21
二、产品生产及销售方案 22
三、销售策略及营销模式 22
四、销售队伍和销售网络建设 23
第六章 项目建设方案 24
一、建设任务和规模 24
二、项目规划和布局 24
三、生产技术方案与工艺流程 25
四、项目建设标准和具体建设内容 26
五、项目实施进度安排 27
第七章 投资估算和资金筹措 28
一、投资估算依据 28
二、项目建设投资估算 28
三、资金来源 29
四、年度投资与资金偿还计划 29
第八章 财务评价 30
一、财务评价的原则 30
二、主要参数的选择 30
三、财务估算 31
四、盈利能力分析 32
五、不确定性分析 33
六、财务评价结论 34
第九章 环境影响评价 35
一、环境影响 35
二、环境保护与治理措施 35
三、环保部门意见 36
第十章 农业产业化经营与农民增收效果评价 37
一、产业化经营 37
二、农民增收 38
三、其它社会影响 38
第十一章 项目组织与管理 40
一、组织机构与职能划分 40
二、项目经营管理模式 42
三、技术培训 42
四、劳动保护与安全卫生 43
第十二章 可行性研究结论与建议 46
一、可行性研究结论 46
二、建议 47