《数据结构》作为一门专业基础课，其教学要求是：学会分析研究计算机所处理的数据结构的特性，以便为应用中涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间和空间分析技术。因此，在本书的编排及选题设计中，主要从上述几方面入手，精心挑选出十多个实际应用问题，并通过解决这些问题的应用程序的设计、开发与实现过程，带领读者一步一步地掌握数据结构课程的精华。要求重点掌握线性表、二叉树和树、图、数组等结构在实践中的应用以及相关算法的设计。其中，线性表是基础，也是数据结构课程的核心。树和图的应用是设计中的难点和重点。

本书是《数据结构课程设计》的教材，在作者多年指导学生完成课程设计的经验基础上编写而成。本书算法全部使用C/C++语言描述，所有应用程序源代码都在Microsoft Visual C++ 6.0下运行通过。

全书共分10章，第1章概述课程设计的目的和要求等；第2章至第7章对应数据结构课程的相关内容，分别讨论了相应数据结构的应用，如线性表、栈、队列、串、数组及广义表、树、图等；第8章和第9章分别讨论了动态存储管理、查找、排序及文件操作的应用；第10章对应用程序主界面的常用设计方法进行了介绍。其中，第2章至第9章是本书的重点。每章由本章知识要点、应用开发实例以及课程设计题选三部分组成。

本书适合作为计算机及相关专业《数据结构》课程设计教材，也可作为学生自学数据结构设计的辅助教材，也是软件开发者的参考书。

第1章 课程设计概述/1

 1.1 课程设计的地位与作用/1

 1.2 课程设计的目标和要求/1

 1.3 课程设计的步骤/2

 1.4 实习报告规范/3

第2章 线性表及其应用/5

 2.1 本章知识要点/5

2.1.1 线性表的存储结构/5

 2.2 “学生通讯录管理系统”的设计与实现/6

2.2.1 设计要求/6

2.2.2 概要设计/6

2.2.3 模块设计/7

2.2.4 详细设计/8

2.2.5 测试分析/9

2.2.6 源程序清单/10

2.2.7 用户手册/16

 2.3 “航空订票系统”的设计与实现/17

2.3.1 设计要求/17

2.3.2 概要设计/17

2.3.3 模块设计/18

2.3.4 详细设计/19

2.3.5 测试分析/26

2.3.6 源程序清单/27

2.3.7 用户手册/33

 2.4 课程设计题选/33

2.4.1 运动会分数统计系统/33

2.4.2 约瑟夫环问题/34

2.4.3 城市链表/34

2.4.4 线性表的逆置/35

2.4.5 长整数运算/35

第3章 栈、队列及其应用/36

 3.1 本章知识要点/36

3.1.1 栈的存储结构/36

3.1.2 队列的存储结构/37

 3.2 “表达式求值问题”的设计与实现/38

3.2.1 设计要求/38

3.2.2 概要设计/38

3.2.3 模块设计/39

3.2.4 详细设计/40

3.2.5 测试分析/41

3.2.6 源程序清单/42

3.2.7 用户手册/43

 3.3 “银行排队系统”的设计与实现/44

3.3.1 设计要求/44

3.3.2 概要设计/44

3.3.3 模块设计/45

3.3.4 详细设计/46

3.3.5 测试分析/48

3.3.6 源程序清单/49

3.3.7 用户手册/57

 3.4 课程设计题选/58

3.4.1 停车场管理系统/58

3.4.2 车厢调度问题/58

3.4.3 数制转换问题/59

3.4.4 回文判断/59

3.4.5 商品货架管理/59

3.4.6 括号匹配的检验/60

第4章 串结构及其应用/61

 4.1 本章知识要点/61

4.1.1 串的定义及基本操作/61

4.1.2 串的存储结构/62

4.1.3 串的模式匹配算法/62

 4.2 “串基本操作演示系统”的设计与实现/64

4.2.1 设计要求/64

4.2.2 概要设计/65

4.2.3 模块设计/65

4.2.4 详细设计/66

4.2.5 测试分析/69

4.2.6 源程序清单/70

4.2.7 用户手册/73

 4.3 “文学研究助手系统”的设计与实现/73

4.3.1 设计要求/73

4.3.2 概要设计/74

4.3.3 模块设计/74

4.3.4 详细设计/75

4.3.5 测试分析/77

4.3.6 源程序清单/78

4.3.7 用户手册/78

4.3.8 “文学研究助手系统”实现方法之二/79

 4.4 课程设计题选/82

4.4.1 文本格式化问题/82

4.4.2 简单行编辑程序/83

第5章 多维数组、矩阵、广义表及其应用/85

 5.1 本章知识要点/85

5.1.1 多维数组/85

5.1.2 稀疏矩阵/86

5.1.3 广义表/87

 5.2 “稀疏矩阵运算器”的设计与实现/90

5.2.1 设计要求/90

5.2.2 概要设计/90

5.2.3 模块设计/91

5.2.4 详细设计/91

5.2.5 测试分析/94

5.2.6 源程序清单/95

5.2.7 用户手册/99

 5.3 “广义表基本操作演示系统”的实现/99

5.3.1 设计要求/99

5.3.2 模块设计/99

5.3.3 详细设计/100

5.3.4 测试分析/105

5.3.5 源程序清单/105

5.3.6 用户手册/111

 5.4 课程设计题选/111

5.4.1 模拟实现多维数组类型/111

5.4.2 稀疏矩阵的转置/112

5.4.3 识别广义表的“头”或“尾”的演示/112

第6章 树结构及其应用/114

 6.1 本章知识要点/114

6.1.1 树与森林/114

6.1.2 二叉树/116

6.1.3 哈夫曼树及其应用/119

 6.2 “二叉树基本操作演示程序”的实现/120

6.2.1 设计要求/120

6.2.2 概要设计/120

6.2.3 模块设计/121

6.2.4 详细设计/122

6.2.5 测试分析/124

6.2.6 源程序清单/125

6.2.7 用户手册/127

 6.3 “哈夫曼树”的建立及其应用/128

6.3.1 设计要求/128

6.3.2 概要设计/128

6.3.3 模块设计/128

6.3.4 详细设计/129

6.3.5 测试分析/131

6.3.6 源程序清单/132

6.3.7 用户手册/134

 6.4 课程设计题选/134

6.4.1 二叉排序树基本操作的实现/134

6.4.2 重言式判别问题/134

6.4.3 表达式类型的实现/135

6.4.4 打印树形结构/136

第7章 图结构及其应用/137

 7.1 本章知识要点/137

7.1.1 图的存储结构/137

7.1.2 图应用的相关算法/138

 7.2 “校园导游系统”的设计与实现/140

7.2.1 设计要求/140

7.2.2 概要设计/140

7.2.3 模块设计/141

7.2.4 详细设计/143

7.2.5 测试分析/149

7.2.6 源程序清单/151

7.2.7 用户手册/159

 7.3 课程设计题选/159

7.3.1 图基本操作的实现/159

7.3.2 教学计划编排问题/159

7.3.3 最小生成树问题/160

7.3.4 交通咨询系统设计/160

第8章 动态存储管理、查找、内排序及其应用/162

 8.1 本章知识要点/162

8.1.1 动态存储管理/162

8.1.2 查找/164

8.1.3 排序/166

 8.2 “模拟动态存储管理演示系统”的设计与实现/168

8.2.1 设计要求/168

8.2.2 概要设计/168

8.2.3 模块设计/169

8.2.4 详细设计/170

8.2.5 测试分析/173

8.2.6 源程序清单/174

8.2.7 用户手册/182

 8.3 “航班信息查询与检索系统”的设计与实现/182

8.3.1 设计要求/182

8.3.2 概要设计/183

8.3.3 模块设计/183

8.3.4 详细设计/184

8.3.5 测试分析/188

8.3.6 源程序清单/189

8.3.7 用户手册/193

 8.4 课程设计题选/193

8.4.1 伙伴存储管理系统演示/193

8.4.2 图书管理系统/194

8.4.3 内部排序算法比较/195

8.4.4 二叉排序树相关操作/195

8.4.5 哈希表设计/196

8.4.6 统计成绩/196

第9章 文件操作及其应用/197

 9.1 本章知识要点/197

9.1.1 文件的基本概念/197

9.1.2 C++ I/O流的概念及流类库/198

9.1.3 键盘输入与屏幕输出/198

9.1.4 文件的输入/输出/200

9.1.5 运算符重载/204

 9.2 二叉排序树与文件操作/206

9.2.1 设计要求/206

9.2.2 概要设计/206

9.2.3 模块设计/208

9.2.4 详细设计/209

9.2.5 测试分析/211

9.2.6 源程序清单/213

9.2.7 用户手册/219

 9.3 课程设计题选/220

9.3.1 外存文件的排序操作/220

9.3.2 索引文件的插入、删除和查找/220

第10章 应用程序主界面设计/222

 10.1 本章知识要点/222

10.1.1 窗体型界面/222

10.1.2 字符型界面/222

 10.2 字符型界面的设计与实现/222

10.2.1 界面背景颜色设置/222

10.2.2 界面背景大小设置/223

10.2.3 字符菜单设计实例一/223

10.2.4 字符菜单设计实例二/226

 10.3 字符型界面设计总结/228

参考文献/229