本书是《数据结构课程设计》的教材，在作者多年指导学生完成课程设计的经验基础上编写而成。本书算法全部使用C/C++语言描述，所有应用程序源代码都在Microsoft Visual C++ 6.0下运行通过。 全书共分10章，第1章概述课程设计的目的和要求等；第2章至第7章对应数据结构课程的相关内容，分别讨论了相应数据结构的应用，如线性表、栈、队列、串、数组及广义表、树、图等；第8章和第9章分别讨论了动态存储管理、查找、排序及文件操作的应用；第10章对应用程序主界面的常用设计方法进行了介绍。其中，第2章至第9章是本书的重点。每章由本章知识要点、应用开发实例以及课程设计题选三部分组成。

前 言 数据结构是计算机程序设计的重要理论技术基础，《数据结构》课程对计算机学科具有承前启后的地位和作用。由于课堂教学和实践的深度和广度有限，要学生很好地理解和掌握数据结构的理论、相关算法及其应用往往比较困难。针对这种情况，我们编写了这本《数据结构课程设计（C/C++描述）》实践教材，其内容安排与《数据结构》课程主教材的相关章节知识点对应，符合数据结构课程教学大纲的要求。 《数据结构》作为一门专业基础课，其教学要求是：学会分析研究计算机所处理的数据结构的特性，以便为应用中涉及的数据选择适当的逻辑结构、存储结构及其相应的算法，并初步掌握算法的时间和空间分析技术。因此，在本书的编排及选题设计中，主要从上述几方面入手，精心挑选出十多个实际应用问题，并通过解决这些问题的应用程序的设计、开发与实现过程，带领读者一步一步地掌握数据结构课程的精华。要求重点掌握线性表、二叉树和树、图、数组等结构在实践中的应用以及相关算法的设计。其中，线性表是基础，也是数据结构课程的核心。树和图的应用是设计中的难点和重点。 本书的编写力求思路清晰、概念准确、算法精湛、格式规范、典型实用。考虑到本课程设计一般在大学二年级开设，所以本书主要采用C语言或引进部分C++的基本概念和语句来实现各种算法。本课程设计的实验环境选择在Microsoft Visual VC++6.0之下，所有应用程序源代码都在Microsoft Visual C++6.0下运行通过。 全书共分10章。第1章概述课程设计的目的和要求等；第2章至第7章对应数据结构课程的相关内容，分别讨论了相应数据结构的应用，如线性表、栈、队列、串、数组及广义表、树、图等；第8章和第9章分别讨论了动态存储管理、查找、排序及文件操作的应用；第10章介绍应用程序主界面的常用设计方法。其中，第2章至第9章是本书的重点。 各章的内容由以下三部分组成： 第一部分是本章知识要点，是对本章主要知识点的提示，包括数据结构的定义、常用存储方法及经典算法等。 第二部分是应用设计实例，从设计要求、概要设计、模块设计、详细设计到测试分析、源程序清单等，按照应用设计开发的全过程进行编写，并对源程序进行了详细注释。目的是帮助读者在无形中学会模仿，起到潜移默化的效果。希望书中的应用实例能起到抛砖引玉的作用，以引来读者更多更优良的设计范例。 第三部分是课程设计题选，目的是希望读者在学习了相关章节的内容后能自己练习提高。选题有难有易。每个选题由问题描述、基本要求、测试数据、实现提示和选做内容五部分组成，希望能够帮助读者在实践过程中得到一些启发，各部分具体目标如下： （1）问题描述。旨在为读者建立问题提出的背景环境，指明问题“是什么”。 （2）基本要求。对问题进一步求精，划出问题的边界，指出具体的参数或前提条件，并规定该题的最低限度和要求等。 （3）测试数据。旨在为检查学生上机作业提供方便，在完成实习题时读者应自行设计完整和严格的测试方案，当数据输入量较大时，提倡以文件形式向程序提供输入数据。 （4）实现提示。对实现中的难点及其算法思路等问题作出简要提示，个别问题给出了参考算法。 （5）选做内容。向那些尚有余力的读者提出了更高的要求，同时也希望开拓读者的思路，在完成基本要求之后，尽可能寻求更优的算法，使得程序结构更合理，更容易修改和扩充。 本书由阮宏一、鲁静主编，并负责全书的总体策划与统稿、定稿工作，宋婉娟、张琪、史毓达、白红武任副主编。各章主要编写人员分工如下：第1章、第7章、第9章由阮宏一、史毓达、杜超编写，第2章、第3章、第10章由宋婉娟、张剑编写，第4章、第5章、第8章由鲁静、吴士泓编写，第6章由张琪和白红武编写。 本书适合作为计算机及相关专业《数据结构》课程设计教材，也可作为学生自学数据结构设计的辅助教材，也是软件开发者的参考书。 本书应用程序源代码可在华信教育资源网上免费注册下载，网址是www.hxedu.com.cn。 由于时间仓促及作者水平有限，书中难免存在欠妥和疏漏之处，敬请广大读者批评指正。作者的E-mail：hyruan@hue.edu.cn。

第1章 课程设计概述 1 1.1 课程设计的地位与作用 1 1.2 课程设计的目标和要求 1 1.3 课程设计的步骤 2 1.5 实习报告规范 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

http://www.hxedu.com.cn/hxedu/fg/book/bookinfo.html?code=G0124450