图解数据结构（第二版）

目 录

第1章  数据结构导论 1
1-1  数据结构简介 2
1-1-1  数据与信息 2
1-1-2  算法 3
1-1-3  算法的条件 3
1-1-4  数据结构的应用 6
1-2  数据抽象化 7
1-2-1  基本数据类型 7
1-2-2  抽象数据类型 7
1-3  算法与程序设计 8
1-3-1  认识程序设计 8
1-3-2  程序开发流程 9
1-3-3  程序设计的风格 9
1-4  面向对象程序设计 11
1-4-1  封装（Encapsulation） 12
1-4-2  继承（Inheritance） 13
1-4-3  多态（Polymorphism） 13
1-5  模块化设计与C语言 13
1-5-1  函数的基本概念 13
1-5-2  参数类型的介绍 14
1-5-3  参数的传递方式 15
1-6  递归算法 15
1-6-1  递归的定义 15
1-6-2  斐波拉契数列 17
1-6-3  汉诺塔问题 18
1-7  程序效率的分析 23
1-7-1  Big-oh 25
1-7-2  Ω(omega)26
1-7-3  θ(theta)27
本章习题 27
第2章  线性表 32
2-1  线性表的定义 33
2-1-1  线性表的用途 33
2-2  数组 34
2-2-1  一维数组 34
2-2-2  二维数组 36
2-2-3  多维数组 40
2-2-4  结构数组 44
2-2-5  字符数组 46
2-2-6  字符串数组 48
2-2-7  指针数组 49
2-3  矩阵 50
2-3-1  矩阵的运算 51
2-3-2  稀疏矩阵 53
2-3-3  上三角形矩阵 55
2-3-4  下三角形矩阵 59
2-3-5  带状矩阵 64
本章习题 65
第3章  链表 69
3-1  动态分配内存 70
3-1-1  C的动态分配变量70
3-1-2  C 的动态分配变量72
3-2  单向链表 73
3-2-1  建立单向链表 74
3-2-2  遍历单向链表 75
3-2-3  释放单向链表节点的空间 76
3-2-4  单向链表插入新节点77
3-2-5  单向链表删除节点79
3-2-6  单向链表的反转 81
3-3  环形链表 83
3-3-1  环形链表的建立与遍历83
3-3-2  环形链表中插入新节点85
3-3-3  环形链表节点的删除86
3-3-4  环形链表的连接功能88
3-4  双向链表 89
3-4-1  双向链表的建立与遍历90
3-4-2  双向链表中加入新节点92
3-4-3  双向链表节点的删除94
3-5  链表相关应用简介 96
3-5-1  多项式表式法 96
3-5-2  稀疏矩阵表示法100
本章习题 102
第4章  堆栈与队列 109
4-1  堆栈简介 110
4-1-1  堆栈的基本操作111
4-1-2  用数组实现堆栈111
4-1-3  用链表实现堆栈112
4-1-4  堆栈类样板的实现114
4-1-5  老鼠走迷宫 116
4-1-6  八皇后问题 119
4-2  算术表达式的表示法120
4-2-1  中序转为前序与后序121
4-2-2  前序与后序转为中序126
4-2-3  中序表示法求值129
4-2-4  前序法的求值运算130
4-2-5  后序法的求值运算131
4-3  队列 132
4-3-1  队列的基本操作133
4-3-2  用数组实现队列133
4-3-3  环形队列 135
4-3-4  双向队列 139
4-3-5  双向队列 141
4-3-6  优先队列 143
本章习题 144
第5章  树状结构 156
5-1  树的基本概念 157
5-1-1  专有名词介绍 158
5-2  二叉树 159
5-2-1  二叉树的特性 159
5-2-2  特殊二叉树简介160
5-3  二叉树的存储方式 161
5-3-1  一维数组表示法161
5-3-2  链表表示法 164
5-4  二叉树的遍历 166
5-4-1  中序遍历 166
5-4-2  后序遍历 167
5-4-3  前序遍历 167
5-4-4  二叉树节点的插入与删除 170
5-4-5  二叉运算树 174
5-5  线索二叉树 176
5-5-1  二叉树转为线索二叉树176
5-6  树的二叉树表示法 180
5-6-1  树转化为二叉树180
5-6-2  二叉树转换成树182
5-6-3  森林化为二叉树183
5-6-4  二叉树转换成森林184
5-6-5  树与森林的遍历185
5-6-6  确定唯一二叉树189
5-7  优化二叉查找树 191
5-7-1  扩充二叉树 191
5-7-2  霍夫曼树 192
5-8  平衡树 194
5-8-1  平衡树的定义 194
5-9  高级树状结构的研究196
5-9-1  决策树 196
5-9-2  B树 198
5-9-3  二叉空间分割树198
5-9-4  四叉树与八叉树199
本章习题 200
第6章  图形结构 210
6-1  图形简介 211
6-1-1  图的定义 212
6-1-2  无向图 212
6-1-3  有向图 214
6-2  图的数据表示法 215
6-2-1  邻接矩阵法 215
6-2-2  邻接表法 218
6-2-3  邻接复合链表法220
6-2-4  索引表格法 222
6-3  图的遍历 225
6-3-1  深度优先遍历法225
6-3-2  广度优先遍历法227
6-4  生成树 229
6-4-1  DFS生成树和BFS生成树 229
6-4-2  最小生成树 231
6-4-3  Kruskal算法231
6-4-4  Prim算法 235
6-5  图的最短路径 236
6-5-1  单点对全部顶点237
6-5-2  两两顶点间的最短路径240
6-6  AOV网络与拓扑排序244
6-6-1  拓扑排列简介 244
6-7  AOE网络 246
6-7-1  关键路径 246
本章习题 248
第7章  排序 257
7-1  排序简介 258
7-1-1  排序的分类 259
7-2  内部排序法 260
7-2-1  冒泡排序法 260
7-2-2  选择排序法 262
7-2-3  插入排序法 264
7-2-4  希尔排序法 266
7-2-5  合并排序法 268
7-2-6  快速排序法 269
7-2-7  堆积排序法 271
7-2-8  基数排序法 278
7-3  外部排序法 280
7-3-1  直接合并排序法280
7-3-2  k路合并法 284
7-3-3  多相合并法 284
本章习题 285
第8章  查找 295
8-1  常见的查找方法 296
8-1-1  顺序查找法 296
8-1-2  二分查找法 297
8-1-3  插值查找法 299
8-1-4  斐波那契查找法301
8-2  哈希查找法 305
8-2-1  哈希法简介 305
8-3  常见的哈希函数 306
8-3-1  除留余数法 306
8-3-2  平方取中法 307
8-3-3  折叠法 308
8-3-4  数字分析法 308
8-4  碰撞与溢出问题的处理309
8-4-1  线性探测法 309
8-4-2  平方探测 310
8-4-3  再哈希 310
8-4-4  链表 311
本章习题 312
附录A  C/C 编译程序的介绍与安装 318
A-1  C/C 编译程序简介319
A-1-1  Visual C 2010 Express 319
A-1-2  C Builder 320
A-1-3  Visual C 320
A-1-4  Dev C 321
A-1-5  GCC 322
A-2  Dev C 的安装与介绍 322
A-2-1  下载Dev-C323
A-2-2  安装Dev C323
附录B  C语言快速入门介绍与安装 329
B-1  轻松学C程序 330
B-1-1  编译与执行 331
B-1-2  编译程序 332
B-1-3  开始执行程序 333
B-2  C的基本数据处理 333
B-2-1  变量 333
B-2-2  常数 334
B-2-3  数据类型简介 334
B-3  C语言的输出与输入 335
B-3-1  printf()函数336
B-3-2  scanf()函数337
B-4  流程控制 338
B-4-1  顺序结构 338
B-4-2  选择结构 339
B-4-3  重复结构 343
B-5  数组简介 346
B-5-1  字符串简介 347
B-5-2  字符串数组 347
B-6  函数介绍 349
B-6-1  传递参数的方式350
B-6-2  标准函数库 352