图解数据结构

第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-C++ 323

A-2-2 安装Dev C++ 323

附录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

本书用轻松的图解方式来讲解数据结构，全书采用丰富的图例阐述数据结构的基本概念及应用，并将重要理论、演算方法做详细的诠释与举例，是一本兼具内容及专业的数据结构的教学用书。 　　由于作者长期从事信息教育及写作，在文字的表达上简洁明了、逻辑清晰，并安排了大量的习题，供读者检验学习成果。

数据结构毫无疑问是计算机科学既经典又核心的课程之一，不管是从事计算机软件还是硬件的开发工作，如果没有系统地学习数据结构或者是没有专心自学过，很容易被人打上“非专业”的标签。对于任何在信息技术行业工作的专业人员或者想进入此行业的人来说，什么时候开始学数据结构都不会晚，更不会过时。
　　从“数据结构”的名字看，它不仅仅只是讲授数据的结构以及在计算机内如何存储和组织数据的方式，这些只是它的表面现象。数据结构背后真正蕴含的是与之息息相关的算法，精心选择的数据结构配合恰如其分的算法就意味着数据或者信息在计算机内被高效率地存储和高效率地处理。算法其实就是数据结构的灵魂，它既神秘又神奇“好玩”，当然对初学者也比较难，算法可以说是“聪明人在计算机上的游戏”。
　　本书是一本综合而且全面讲述数据结构及其算法分析的教科书，为了便于高校的教学或者读者自学，作者在描述数据结构原理和算法时文字清晰并且严谨，为每个算法及其数据结构提供了演算的详细图解。另外，为了适合在教学中让学生上机实践或者自学者上机“操练”，本书为每个经典的算法都提供了C语言编写的完整范例程序的源代码，每个范例程序都不需要经过修改，直接通过编译就可以运行，目的就是让本书的学习者以这些范例程序作为参照迅速掌握数据结构和算法的要点。
　　全书的所有范例程序都可以在标准的C语言编程环境中编译通过并且成功运行，我们在改编本书的过程中选用了免费的Dev C++ 5.11集成开发环境，对原书的所有范例程序进行编译、修改、调试和测试，并确保它们都可以准确无误地运行。附录A包含了“C/C++编译程序的介绍与安装”，其中重点就介绍了Dev C++。附录B则包含了“C语言快速入门”。