本书是作者积多年讲授与研究“数据结构”课程的经验并结合指导学生上机的实践编写而成的。作者力求从实践的角度，帮助读者深入学习、理解和掌握数据结构知识并能灵活应用这些知识。本书涵盖了“数据结构”课程涉及的上机实践内容，并且列举了理论知识对应的算法实现程序，这些程序都已在VC++6.0环境下调试通过。 本书可以配合目前各类数据结构（C语言）教材使用，不仅可以实现教学与上机的衔接，还可以帮助读者开拓学习和应用视野。本书程序设计内容丰富、编程方法全面，因此可以作为计算机应用人员的参考书。

前言 如果把程序设计比作一棵大树，那么数据结构无疑是大树的躯干。因此，可以把数据结构看作程序设计的精髓。计算机各个领域的应用都会涉及各种数据结构，只有较好地掌握了数据结构知识，才能在程序设计中做到游刃有余，从而在计算机应用领域的研究和开发中做到胸有成竹。 “数据结构”是计算机专业的核心课程，其内容是在长期的程序设计实践中提炼、升华而成的，反过来又应用于程序设计。“数据结构”课程是“操作系统”“编译原理”等计算机专业核心课程的基础，在计算机专业课程的学习中具有承上启下的作用。另外，“数据结构”是一门应用广泛且有实用价值的课程，不掌握数据结构知识就难以成为一名合格的软件工程师或计算机工作者。 “数据结构”课程对理论与实践方面的要求都很高，并且内容难度很大。虽然多数教材都强调了实践的重要性，但还是缺乏数据结构算法实践方面的内容。很多教材对算法的描述只是扼要性和概述性的，并且大多数算法都采用类C、类C++或类Pascal语言描述。在这些算法中，有些算法虽然看起来正确但无法上机实现；为了适应运行环境，有些算法需要做重大修改后才能真正上机实现，即使是一些简单的算法也不能直接上机实现。由于数据结构算法的上机实现涉及栈、队列、树和图等具体存储结构，并且一个算法的实现往往要涉及其中几种结构，这就增加了算法实现程序编写的难度，而初学者更是感到无从下手。针对这种情况，我们编写了《数据结构实践教程》（第三版）。在内容方面，我们坚持以理论知识为纲、实践应用为线，侧重创新，以达到开拓学生思维空间和实际动手能力的目的。目前，国家所倡导的“卓越工程师计划”就是要培养程序设计能力强并且具有创新精神的高素质人才。我们所做的正是为实现这一目标奠定坚实的基础。本书可作为“数据结构”课程的辅助与拓展教材，也可帮助计算机专业或其他相关专业的学生学习“数据结构”课程，让他们在尽可能短的时间内对数据结构知识的实践与应用有比较全面、深入和系统的认识，达到理论与实践相结合的目的。 本书中的所有程序都由作者编写并已在VC++6.0环境下调试通过，书中许多算法实现程序的设计思想都是作者独创的。本书对所有程序都添加了详细的注释。由于篇幅有限，仅列举了比较复杂且难度较大的算法实现程序的运行结果。这样可以使本书更为紧凑，使算法实现程序更加容易阅读和理解，也更加适应教学和实践的需要，对读者阅读和理解程序如何实现算法的功能将起到事半功倍的作用。 本书分为9章。第1～8章与数据结构相应的理论知识进行衔接，各章先对其涉及的理论知识进行简要介绍，然后给出涉及理论知识的全部算法实现程序。这些算法实现程序既可作为学习算法的拓展和补充，也可作为实践上机内容。第9章是数据结构算法设计与实现的扩展，给出了数据结构知识更多的应用内容，具有拓展数据结构思维及灵活运用数据结构知识的作用。 本书中的思考题大部分可作为“数据结构”课程设计题目，第9章也可作为“数据结构”课程设计的参考资料。 由于作者水平所限，书中难免存在不足之处，敬请广大读者批评指正。 编 者 2020年8月7日

目录 第1章 线性表 1 1.1 线性表的定义 1 1.2 线性表的顺序存储——顺序表 1 1.3 线性表的链式存储 2 第2章 栈和队列 23 2.1 栈 23 2.2 队列 25 第3章 串 39 第4章 数组与广义表 56 4.1 数组 56 4.2 特殊矩阵 58 4.3 稀疏矩阵 58 4.4 广义表 61 第5章 树与二叉树 76 5.1 树 76 5.2 二叉树 76 5.3 二叉树的性质 78 5.4 二叉树的存储结构 78 5.5 二叉树的遍历方法 80 5.6 线索二叉树 80 5.7 哈夫曼树 82 5.8 哈夫曼编码 84 第6章 图 115 6.1 图的概念 115 6.2 图的基本术语 116 6.3 邻接矩阵 118 6.4 邻接表 120 6.5 图的遍历 121 6.6 图的连通性问题 121 6.7 生成树与最小生成树 122 6.8 最短路径 123 6.9 AOV网与拓扑排序 124 6.10 AOE网与关键路径 126 第7章 查找 167 7.1 顺序查找 167 7.2 有序表的查找 168 7.3 二叉排序树与平衡二叉树 168 7.4 哈希表与哈希方法 169 7.5 哈希函数的构造方法 169 7.6 处理冲突的方法 170 第8章 排序 196 8.1 插入排序 196 8.2 交换排序 197 8.3 选择排序 198 8.4 归并排序 200 8.5 基数排序 200 第9章 数据结构算法应用 228 9.1 顺序表的应用 228 9.1.1 顺序表的逆置 228 9.1.2 将两个升序的顺序表A和B合并为一个升序的顺序表C 229 9.1.3 单链表的逆置 231 9.1.4 将递增有序的单链表A和B合并为递减有序的单链表C 232 9.1.5 删除单链表中值相同的节点 234 9.1.6 按递增次序输出单链表中各节点的数据值 235 9.1.7 用单链表实现约瑟夫（Josephus）问题 237 9.2 栈和队列的应用 239 9.2.1 用栈判断给定的字符序列是否为回文 239 9.2.2 循环链表中只有队尾指针的入队和出队算法 240 9.2.3 算术表达式中的括号匹配 242 9.2.4 将队列中所有元素逆置 245 9.2.5 用两个栈模拟一个队列 248 9.2.6 用栈实现汉诺塔（Tower of Hanoi）问题非递归解法 250 9.3 串的应用 252 9.3.1 将串s1中连续的字符用串s2替换 252 9.3.2 计算一个子串在串中出现的次数 253 9.3.3 输出长度最大的等值子串 255 9.3.4 将链串s中首次与链串t匹配的子串逆置 256 9.4 数组与广义表的应用 258 9.4.1 将所有奇数存放到数组的前半部分，所有偶数存放到数组的后半部分 258 9.4.2 求字符数组中连续相同字符构成的子序列长度 259 9.4.3 求广义表的表头和表尾 260 9.4.4 另一种广义表生成方法 264 9.5 树与二叉树的应用 268 9.5.1 交换二叉树的左子树和右子树 268 9.5.2 统计二叉树叶子节点个数的非递归算法的实现 269 9.5.3 判定一棵二叉树是否为完全二叉树 271 9.5.4 求二叉树中第一条最长的路径并输出此路径上各节点的值 273 9.6 图的应用 276 9.6.1 邻接矩阵转换为邻接表 276 9.6.2 深度优先搜索的非递归算法实现 278 9.6.3 求无向连通图中距顶点v0路径长度为k的所有节点 280 9.6.4 用深度优先搜索对图中所有顶点进行拓扑排序 283 9.7 查找的应用 286 9.7.1 判断一棵二叉树是否为二叉排序树 286 9.7.2 另一种平衡二叉树的生成方法 288 9.8 排序的应用 293 9.8.1 用双向循环链表表示的插入排序 293 9.8.2 双向冒泡排序 295 9.8.3 双向选择排序 297 9.8.4 单链表存储下的选择排序 298 9.8.5 归并排序的迭代算法实现 300 参考文献 303

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