数据结构与算法----C++实现

数据结构是计算机及相关专业的核心课程，目前的教材普遍采用C 模板描述数据结构中的算法。数据结构又是一门理论与实践并重的课程，编程实现各种数据结构与算法，无疑是提升教学效果的有效途径之一。由于数据结构课程通常在大学二年级开设，学生的软件设计能力较弱，学生普遍反映算法实现困难。
本书为初学者学习编写数据结构与算法程序而著，没有过多地讨论常规教材中已有的基本概念与基础理论，旨在使本书成为一本用于编程参考的工具书。
本书采用标准C 98的模板技术实现算法，编程平台是Visual C 2010，其中控制台程序用本地C 编程，窗体程序用本地C 与C /CLI混合方式编程，C /CLI主要用于窗体界面的设计。所有程序均在Windows 10系统中调试通过。
全书共7章，内容依次为线性表、栈和队列、字符串和多维数组、树和二叉树、图、查找、排序。书中共有例程57个，其中控制台程序21个，窗体程序36个，部分窗体程序可用于教学演示。具体章节的组织与内容如下。
第1章介绍了顺序表、单链表、循环双链表和静态链表类模板及相关算法的设计与实现，此外还设计了单链表窗体演示程序和一元多项式求和应用程序。
第2章介绍了顺序栈、链栈、循环队列和链队列类模板的设计与实现。顺序栈窗体演示程序和循环队列窗体演示程序可用于教学演示。进制转换和舞伴配对问题分别介绍了栈与队列的应用。
第3章首先介绍了BF模式匹配算法和KMP模式匹配算法的实现。其次介绍了对称矩阵的压缩存储、三元组表法和十字链表法进行矩阵压缩存储的实现，其中十字链表法为窗体程序，可用于教学演示。*后介绍了奇数阶幻方矩阵的实现。
第4章介绍了二叉树用顺序存储和链表存储结构实现的类模板，此外还给出了用于教学演示的窗体程序。在线索二叉树一节，介绍了中序线索二叉树的实现。此外，还介绍了二叉树遍历的非递归算法以及哈夫曼树的实现。
第5章介绍了图的邻接矩阵、邻接表和十字链表存储结构，以及深度优先遍历和广度优先遍历算法的实现。用C#语言设计了顶点与边的自定义控件，供窗体程序引用。图中一些重要的算法均用窗体程序给予了实现，包括Prim算法、Kruskal算法、Dijkstra算法、Folyd算法、拓扑排序算法和关键路径算法。*后介绍了七巧板涂色问题的实现。
第6章介绍了顺序、折半、二叉排序树和散列表等查找算法的实现，其中折半查找、树表查找、平衡二叉排序树调整、闭散列表和开散列表查找等窗体程序可用于教学演示。*后介绍了MD5散列算法在密码保护上的应用。
第7章介绍了插入、交换、选择、归并和分配几大类排序算法的实现，所有程序均为窗体程序，可用于教学演示。实现的算法有直接插入排序、希尔排序、冒泡排序、快速排序、简单选择排序、堆排序、二路归并排序、桶排序和基数排序等。*后介绍了荷兰国旗问题的实现。
书中例程绝大多数源自作者从事数据结构课程教学的积累。教材编写力求简明易懂，并为关键部分代码加了注释。书中源代码均可从清华大学出版社官网下载。
限于作者水平，书中不足之处在所难免，敬请读者批评指正。

编 者 

《数据结构与算法——C 实现》主要介绍数据结构与算法的编程实现，内容包括线性表、栈和队列、数组、树和二叉树、图等基础数据结构，以及查找与排序等相关技术。《数据结构与算法——C 实现》分7章，共57个例程，涵盖了数据结构中主要算法的实现，包括KMP、Prim、Kruskal、Dijkstra、Folyd、拓扑排序、关键路径和Shell排序等算法，以及哈夫曼树、七巧板涂色和荷兰国旗等著名问题的实现。 书中程序用C 语言编写，Visual C 2010平台调试通过，分为Windows控制台程序和窗体程序两类，其中窗体程序界面部分用C /CLI语言实现。 《数据结构与算法——C 实现》用结构完整的程序讲授数据结构与算法的实现，适合初学者研习与借鉴，可作为普通高等院校应用型本科相关专业数据结构课程的辅助教材，也可作为编程开发人员的培训或自学用书。

吴克力，南京理工大学教授，硕士生导师，博士。曾获得江苏省高校“青蓝工程”优秀青年骨干教师培养对象，市“十百千”人才第二层次培养对象，学校“我*喜爱的老师”和第六届校教学标兵等荣誉。主讲了《C 程序设计》、《数据结构》等计算机专业课程，主编本科教材3部，均评为江苏省高等学校重点教材。发表专业学术论文三十余篇，获江苏省教学成果二等奖一项，国防科工委国防科学技术奖二等奖一项，省高校优秀教材奖一项。　　

第1章 线性表 1
1.1 线性表抽象类的定义 2
1.2 顺序表类模板 2
1.3 单链表 6
1.3.1 单链表类模板 6
1.3.2 单链表窗体演示程序 10
1.4 循环双链表类模板 14
1.5 静态链表类模板 20
1.6 一元多项式求和 24
习题 27
第2章 栈和队列 33
2.1 栈抽象类的定义 34
2.2 顺序栈 34
2.2.1 顺序栈类模板 34
2.2.2 顺序栈窗体演示程序 37
2.3 链栈类模板 40
2.4 进制转换 42
2.5 队列抽象类的定义 45
2.6 循环队列 46
2.6.1 循环队列类模板 46
2.6.2 循环队列窗体演示程序 48
2.7 链队列类模板 52
2.8 舞伴配对问题 55
习题 57
第3章 字符串和多维数组 63
3.1 BF模式匹配算法 64
3.2 KMP模式匹配算法 67
3.2.1 next数组求解窗体程序 67
3.2.2 KMP算法的实现 71
3.3 特殊矩阵的存储 72
3.3.1 对称矩阵的压缩存储 72
3.3.2 三元组表法存储稀疏矩阵 75
3.3.3 十字链表法存储稀疏矩阵 80
3.4 奇数阶幻方矩阵 89
习题 92
第4章 树和二叉树 95
4.1 树抽象类的定义 96
4.2 二叉树的顺序存储结构 96
4.2.1 二叉树顺序存储控制台
程序 96
4.2.2 二叉树顺序存储窗体
演示程序 100
4.3 二叉树的链式存储结构 103
4.3.1 二叉树链式存储控制台
程序 103
4.3.2 二叉树链式存储窗体
演示程序 108
4.4 线索二叉树 116
4.5 二叉树遍历的非递归算法 120
4.6 哈夫曼树 123
习题 129
第5章 图 133
5.1 图的存储结构 134
5.1.1 邻接矩阵存储结构 134
5.1.2 邻接表存储结构 138
5.1.3 十字链表存储结构 157
5.2 图的遍历 170
5.2.1 深度优先遍历算法实现 171
5.2.2 广度优先遍历算法实现 172
5.3 *小生成树 174
5.3.1 Prim算法实现 175
5.3.2 Kruskal算法实现 186
5.4 *短路径 188
5.4.1 Dijkstra算法实现 189
5.4.2 Folyd算法实现 200
5.5 有向无环图及其应用 202
5.5.1 拓扑排序算法实现 202
5.5.2 关键路径算法实现 209
5.6 七巧板涂色问题 213
习题 218
第6章 查找 225
6.1 线性表的查找 226
6.1.1 顺序查找算法实现 226
6.1.2 折半查找算法实现 230
6.2 树表的查找 234
6.2.1 二叉排序树查找算法实现 234
6.2.2 平衡二叉排序树调整算法
实现 242
6.3 散列表的查找 250
6.3.1 闭散列表查找算法实现 250
6.3.2 开散列表查找算法实现 255
6.4 MD5散列算法 259
习题 262
第7章 排序 265
7.1 插入排序 266
7.1.1 直接插入排序算法实现 266
7.1.2 希尔排序算法实现 271
7.2 交换排序 275
7.2.1 冒泡排序算法实现 275
7.2.2 快速排序算法实现 280
7.3 选择排序 285
7.3.1 简单选择排序算法实现 285
7.3.2 堆排序算法实现 290
7.4 二路归并排序算法实现 293
7.5 分配排序 296
7.5.1 桶排序算法实现 296
7.5.2 基数排序算法实现 303
7.6 荷兰国旗问题 310
习题 315
参考文献 318

《数据结构与算法——C 实现》主要介绍数据结构与算法的编程实现，采用标准C 98的模板技术实现算法，编程平台是Visual C 2010，其中控制台程序用本地C 编程，窗体程序用本地C 与C /CLI混合方式编程，C /CLI主要用于窗体界面的设计。全书共57个例程，涵盖了数据结构中主要算法的实现，是一本合适的编程参考的工具书。