趣学数据结构

 

本书基于C++语言编写，从趣味故事引入算法复杂性计算及数据结构基础内容，涵盖线性结构、树形结构和图形结构，包括链表、栈和队列、树和图的应用等。本书内容还涉及数据结构的基本应用（包括各种查找、排序等）和高级应用（包括优先队列、并查集、B-树、B+树和红黑树等）。通过大量图解将抽象数据模型简单通俗化，语言表述浅显易懂，并结合有趣的实例帮助读者轻松掌握数据结构。

陈小玉，南阳理工学院副教授，高级程序员，研究方向为智能计算、数据挖掘与机器学习，主要讲授“算法设计与分析”和“人工智能”等课程，多次指导学生获得ACM程序设计大赛亚洲区奖项。

第1章数据结构入门1
1.1数据结构基础知识2
1.2算法复杂度10
1.3一棋盘麦子17
1.4神奇魔鬼序列18
1.5本章要点23
第2章线性表24
2.1顺序表25
2.1.1静态分配25
2.1.2动态分配26
2.1.3顺序表的基本操作28
2.2单链表35
2.2.1单链表的存储方式35
2.2.2单链表的基本操作37
2.3双向链表48
2.3.1双向链表的存储方式48
2.3.2双向链表的基本操作48
2.4循环链表54
2.5线性表的应用55
2.5.1合并有序顺序表55
2.5.2合并有序链表60
2.5.3就地逆置单链表64
2.5.4查找链表的中间节点68
2.5.5删除链表中的重复元素71
2.6线性表学习秘籍75
第3章栈和队列78
3.1顺序栈79
3.2链栈83
3.3顺序队列87
3.3.1顺序队列的定义88
3.3.2循环队列的定义92
3.3.3循环队列的基本操作96
3.4链队列98
3.5栈和队列的应用102
3.5.1数制的转换102
3.5.2回文判定104
3.5.3双端队列106
3.6栈和队列学习秘籍116
第4章字符串121
4.1字符串122
4.2模式匹配BF算法124
4.3模式匹配KMP算法128
4.4改进的KMP算法133
4.5字符串的应用——病毒检测135
4.6字符串学习秘籍137
第5章数组与广义表139
5.1数组的顺序存储140
5.2特殊矩阵的压缩存储143
5.2.1对称矩阵143
5.2.2三角矩阵145
5.2.3对角矩阵146
5.2.4稀疏矩阵150
5.3广义表151
5.4好玩贪吃蛇——数字矩阵151
5.5数组与广义表学习秘籍156
第6章树158
6.1树159
6.1.1树的定义159
6.1.2树的存储结构162
6.1.3树、森林与二叉树的转换165
6.2二叉树167
6.2.1二叉树的性质168
6.2.2二叉树的存储结构173
6.2.3二叉树的创建175
6.3二叉树的遍历183
6.3.1先序遍历183
6.3.2中序遍历186
6.3.3后序遍历188
6.3.4层次遍历192
6.4线索二叉树196
6.4.1线索二叉树存储结构196
6.4.2构造线索二叉树197
6.4.3遍历线索二叉树201
6.5树和森林的遍历204
6.5.1树的遍历204
6.5.2森林的遍历209
6.6树的应用212
6.6.1二叉树的深度212
6.6.2二叉树的叶子数213
6.6.3三元组创建二叉树214
6.6.4遍历序列还原树218
6.6.5哈夫曼树223
6.7树学习秘籍239
第7章图241
7.1图的基本术语242
7.2图的存储结构249
7.2.1邻接矩阵250
7.2.2邻接表256
7.2.3十字链表266
7.2.4邻接多重表268
7.3图的遍历270
7.3.1广度优先搜索270
7.3.2深度优先搜索275
7.4图的应用279
7.4.1单源最短路径——Dijkstra279
7.4.2各顶点之间最短路径——Floyd287
7.4.3最小生成树——prim293
7.4.4最小生成树——kruskal305
7.4.5拓扑排序308
7.4.6关键路径316
7.5图学习秘籍324
第8章查找327
8.1线性表查找328
8.1.1顺序查找328
8.1.2折半查找330
8.2树表查找335
8.2.1二叉查找树335
8.2.2平衡二叉查找树346
8.3散列表的查找361
8.3.1散列函数361
8.3.2处理冲突的方法364
8.3.3散列查找及性能分析376
8.4查找学习秘籍378
第9章排序379
9.1插入排序381
9.1.1直接插入排序381
9.1.2希尔排序387
9.2交换排序389
9.2.1冒泡排序389
9.2.2快速排序392
9.3选择排序401
9.3.1简单选择排序401
9.3.2堆排序403
9.4合并排序412
9.5分配排序417
9.5.1桶排序417
9.5.2基数排序418
9.6排序学习秘籍421
第10章高级数据结构425
10.1并查集426
10.2优先队列430
10.2.1出队431
10.2.2入队433
10.2.3构建初始堆435
10.3B-树437
10.3.1树高与性能439
10.3.2查找440
10.3.3插入441
10.3.4删除444
10.4B+树449
10.4.1查找450
10.4.2插入451
10.4.3删除454
10.5红黑树457
10.5.1红黑树的定义457
10.5.2树高与性能458
10.5.3红黑树与4阶B树459
10.5.4查找460
10.5.5插入460
10.5.6删除466
10.6高级数据结构学习秘籍476