《数据结构》课程设计报告

河 南 工 程 学 院

课程设计报告书

姓 名 李永轩

学 号 2

学 院 计算机学院

专业班级 计算机科学与技术 1242

专业课程 数据结构

指导老师 李 芳

2014年 6 月20日 校园导航

I 河南工程学院计算机学院

课程设计报告书

课程设计题目： 校园导航程序设计

课程设计时间： 6月16日～6月20日

课程设计地点： 3号实验楼C405

课程设计单位： 计算机学院

指导教师： 李芳 学院院长： 曲宏山

校园导航

II 本组组长 刘皓冉

本组成员 刘皓冉、李永轩

设计题目 校园导航程序设计

本人分工 资料查询、代码编制、代码调试

考核项目 考核内容 得分

平时考核 （30分）出勤情况、态度、效率、协作精神；知识掌握情况、基本操作技能、知识应用能力、获取知识能力

设计思想 （20分）需求分析能力，算法分析设计能力

编码、调试分析 （30分）编制代码能力，调试分析能力

文档资料 （20分）表达能力、文档写作能力和文档的规范性

总评成绩

指导教师评语：

等 级：

评阅人： 职称：

年 月 日

校园导航

III 目 录

1、设计目标…………………………………1

2、课题分析与设计………………………....1

1.课题需求分析………………………...1

2.存储结构设计………………………...4

3.算法设计……………………………...5

4.程序流程图…………………………...7

3、程序清单…………………………………7

4、测试……………………………………..19

1．测试数据……………………………19

2.测试结果及分析…………………….19

5总结……………………………………...26

1.收获………………………………….26

2.不足………………………………….27

3.算法改进分析……………………….27校园导航

1 1 设计目标

1.设计学校平面图，包含十四个景点；

2.实现景点的查询介绍；

3.设计程序求出两个景点之间最短的距离。

4.通过实习，锻炼实际动手能力，增加相关知识，明确数据结构课程在软件开发中的重要性。

2 课题分析与设计

２．１ 课题需求分析

为完成整个导航系统的实现，需要对其所有功能清楚明白，选择正确高效的算法解决产生的问题，最后实现程序的正确运行。设计思路如下：

（1）结合本校的实际情况，选出14个景点；

（2）为选出的14个景点赋上相关信息内容（名称、序号、简介信息、以及路径权值等等）；

（3）根据14个景点用邻接矩阵存储校园图，并依照景点相关信息进行创建。

（4）把纸质上的内容，利用C编程语言编写查找景点相关信息的程序。

（5）根据人为赋值的路径权值，计算任意两个景点之间的最短路径。

（6）用主函数将所有板块合并，生产一个菜单界面呈现在用户面前。

所以，可将系统分为以下三个核心：图的初始化、图的遍历、求最佳路线。

2.1.1校园景点选取

根据我校情况，选取了以下十四处景点：

编号 名称 编号 名称 编号 名称

1 大西门 2 小西门 3 2号实验楼

4 3号实验楼 5 1-3号教学楼 6 4-6号教学楼

7 B区宿舍 8 图书馆 9 南门

10 大学生活动中心 11 商业活动中心 12 小东门

13 东门 14 A区宿舍

2.1.2图的初始化 校园导航

2 由于邻接矩阵特殊的存储方式，及便于快速的查找两个顶点之间的边上的权值。所以，校园图采用带权的邻接矩阵存储。

决定了图的存储方式后，以河南工程学院14个景点地图作为蓝本，将校园地图抽象化成顶点与边构成的图形式，如图2.1.1所示，途中数字代表路线的权值。

2．2

3 4

5 6

9 8 7

10 14 11

12 13

图2.1.1 校园景点抽象图

2.1.3 图的遍历

图的遍历是图中最基本的操作。图的遍历是指从图中某一顶点出发，对图中所有顶点访问一次且仅访问一次。导航图需要把每条路径的信息展示出来，及需要读取每两个顶点间的路径信息。由于采用了带权的邻接矩阵存储结构进行存储，所以需要针对这一存储结构对路线进行遍历操作。其遍历算法如图2.1.2所示。 1

4

14

13 12 11 10 9 8 7 6 5 3 2

20 20

10

15

15 15

10

20

20 20

20 20 1010 15

25

25 10 10 15 20 校园导航

3

图2.1.2 遍历算法示意图

2.1.4 求最短路径

基于本程序中图的存储是邻接矩阵结构存储的图结构，因而采用适合该存储结构的迪杰斯特拉算法用于解决求最短路径的问题。

迪杰斯特拉提出了一个按路径长度递增的持续产生最短路径的算法，其基本思想是：设置一个集合S存放已经找到最短路径的顶点，S的初始状态只包含源点v，对于vi∈V-S，假设从源点v到vi的有向边为最短路径。以后每求得一条最短路径v，…，vk，就将vk加入集合S中，并将路径v，…，vk，vi，与原来的假设相比较，取路径长度较小者为最短路径。重复上述过程，直到集合V中全部顶点加入到集合S中。如图2.1.3所示。 插入信息内容 For循环语句

（i=0；i

For循环语句

(j=0;j

Y N

Y 开始

结束 如果路径存在

输出该路径信息 N 校园导航

4

图2.1.3 图的遍历算法执行效果示意图

辅助数组dist[n]：元素dist[i]表示当前找到的从源点到终点vi的最短路径的长度。初态为:若从v到vi有弧，则dist[i]为弧上的权值；否则置dist[i]为∞。若当前求得的终点为vk,则根据下式进行迭代：

dist[i]=min{dist[i],dist[k]+arc[k][i]} 1≦i≦n

辅助数组path[n]:元素path[i]是一个串，表示当前所找到的从源点到终点vi的最短路径。初态为：若从v到vi有弧，则path[i]为“vvk”，否则置path[i]为空串。

数组s[n]：存放源点和已经生成的终点（即集合S），初态为只有一个源点v。

算法的伪代码描述是：

1.初始化数组dist、path和s；

2.while（s中的元素个数

2.1 在dist[n]中求最小值，其下标为k（则vk为正在生成的终点）；

2.2 输出dist[j]和path[j]；

2.3 修改数组dist和path;

2.4 将顶点vk添加到数组s中；

２．２ 存储结构设计

1.创建校园图：

（1）依照河南工程学院的地图，先手工画好14个景点的草图，再用C语言输出抽象化的校园地图。

（2）再用C语言定义节点个数N，编写函数name( )为景点赋值各类信息集合S 集合V-S

V Vk

Vi 校园导航

5 项，函数information( )，输入各个景点的简介。

（3）读入道路的起始点，为邻接矩阵的边赋相应的值。

2．利用函数travgraph来查找景点信息。

3．创建一个校园图creat(Matrix_Graph *G)，然后为相应的边赋上现实意义上的权值。

4．用path( )函数来求任意两景点之间的最短路径。

5. 如果不查询则调用exit( )函数退出。

5．用main函数来输出导游界面。

２．３ 算法设计

1 抽象数据类型图的定义

ADT Mgraph{数据对象V:V是具有相同特性的数据元素的集合，即顶点集。 数据关系：Mgraph=(V,R)。其中，R={|v,w∈V且P(v,w),表示从v到w的一条弧}。

基本操作：

}//ADT Mgraph

2 程序中包含的模块

（1）主程序模块

void main()//主函数

{定义主界面的显示；

初始化河南工程学院景点地图creat(&G)；

景点地图的输出打印printf（）；

选择景点并且打印相关信息void travgraph（）；

起点终点的选择和最短路径显示void path()；

程序的退出；}

void clrscr(){ //清屏

system("cls");}

typedef int AdjMatrix[MAX][MAX]; //邻接矩阵

typedef struct{ //点的结构

int vexs[MAX];

AdjMatrix arcs;}Matrix_Graph;