数据结构课程设计报告
班 级： 计算机科学与技术132班 姓 名： 赖恒财 指导教师： 董跃华 成 绩：
32
信息工程学院
2015 年 7月 8日
图的最短路径算法实现
1. 需求分析 ............................................................................................................................................ 1
1.1 程序设计内容........................................................................................................................ 1 1.2 设计要求 ................................................................................................................................ 1 2.概要设计 ............................................................................................................................................. 2 3.详细设计 ............................................................................................................................................. 2
3.1 数据类型的定义 ................................................................................................................... 2 3.2 功能模块的设计 ................................................................................................................... 2 3.3 主程序流程 ............................................................................................................................ 9 4.调试分析 ........................................................................................................................................... 10
4.1 问题回顾和分析 ................................................................................................................. 10 4.2.经验和体会 ........................................................................................................................... 11 5.测试结果 ........................................................................................................................................... 12
二叉树的遍历
1.设计目的 ........................................................................................................................................... 13 2.需求分析 ........................................................................................................................................... 14
2.1课程设计的内容和要求 ...................................................................................................... 14 2.2选题的意义及背景 .............................................................................................................. 14
1
目录
3.概要设计 ........................................................................................................................................... 14
3.1设计思想 ............................................................................................................................... 14 3.2程序数据类型....................................................................................................................... 16 3.3程序模块分析....................................................................................................................... 16 3.3.1置空栈 ........................................................................................................................................ 16 3.3.2入栈 ............................................................................................................................................ 17 3.3.3出栈 ............................................................................................................................................ 17 3.3.4取栈顶操作 ................................................................................................................................ 17 3.3.5判空栈 ........................................................................................................................................ 17
3.4函数关系： ........................................................................................................................... 18 4.详细设计 ........................................................................................................................................... 18
4.1二叉树算法程序截图和结果.............................................................................................. 18 5.程序测试结果及问题分析.............................................................................................................. 19 6.总结 ................................................................................................................................................... 20 参考文献 .............................................................................................................................................. 21 附录1 ................................................................................................................................................... 22 附录2 ................................................................................................................................................... 26
2
图的最短路径算法实现
----基于floyd最短路径算法
1. 需求分析
设计校园平面图，所含景点不少于8个。以图中顶点表示学校内各景点，存放景
点的名称、景点介绍信息等；以边表示路径，存放路径长度信息。要求将这些信息保存在文件graph.txt中，系统执行时所处理的数据要对此文件分别进行读写操作。
1.1 程序设计内容
1．从文件graph.txt中读取相应数据, 创建一个图,使用邻接矩阵表示图 ； 2．景点信息查询：为来访客人提供校园任意景点相关信息的介绍； 3．问路查询：为来访客人提供校园任意两个景点之间的一条最短路径 。
1.2 设计要求
(1) 程序要具在一定的健壮性，即当输入数据非法时，程序也能适当地做出反应。 (2) 程序要添加适当的注释，程序的书写要采用缩进格式。
(3) 根据实验报告模板详细书写实验报告，在实验报告中给出校园平面图。 (4) 校园平面图中的校园景点信息保存在文件graph.txt中。
1
2.概要设计
此程序主要实现以下几个模块, 基于下面几个模块完全可以实现此题要求.
(1). 图的创建
(2). 输出提供可选查询景点 (3). 景点介绍查询处理 (4). 查找两景点间的最短路径 (5). Floyd算法(核心)
3.详细设计
3.1 数据类型的定义
校园道路是双向通行的，可设校园平面图是一个带权的无向图，用邻接矩阵表示此无向
网。邻接矩阵的数据类型定义如下：
typedef struct{ char name[100];
char info[10000]; }VertexType;
typedef struct{
VertexType vexs[10]; int arcs[100][100]; int vexnum,arcnum; }MGraph;
//邻接矩阵
//顶点个数，边的个数 //图结构
//名字 //介绍 //顶点结构
3.2 功能模块的设计
3.2.1 图的创建
2