数据结构 C/C++版PDF电子书下载

第1章　数据结构概论 1

1.1 数据与信息 1

1.2　数据处理 2

1.3　计算器操作方式 4

1.4　程序的产生 4

1.5　程序的分析 5

1.5.1　如何分析程序 8

1.6　算法 8

1.6.1　算法的书写 9

1.6.2　算法效率的评估 12

1.7 复杂度 12

1.7.1　复杂度的表示法 13

1.8　NP-Complete 15

1.9　参数的传递 17

1.10　数据结构 19

1.10.1 数据结构探讨问题 19

1.11 魔术方阵 20

1.12　习题 21

第2章　数组结构 23

2.1　数组的定义 23

2.2　数组表示法 24

2.2.1 一维数组 24

2.2.2 二维数组 24

2.2.3　三维数组 26

2.2.4　多维数组 27

2.3　稀疏矩阵 28

2.3.1　稀疏矩阵的转置 29

2.4.1 多项式的数据结构 31

2.4　数组的应用 31

2.4.2　多项式相加 32

2.4.3　上三角矩阵储存方式 34

2.4.4　下三角矩阵储存方式 39

2.4.5　带状矩阵 44

2.4.6　矩阵相乘 48

2.5　最佳洗牌法 49

2.6 习题 50

3.2　动态内存配置 52

3.2.2　函数free（） 52

3.2.1 函数malloc（） 52

3.1　链表的定义 52

第3章　链表 52

3.3　链表的创建 53

3.3.1 动态数据结构的声明 53

3.3.2　内存的配置 53

3.3.3　基本链表的创建 54

3.4　链表的遍历 56

3.5　链表的连结 57

3.6　链表内节点的删除 57

3.7　释放链表的内存空间 58

3.8　链表内节点的插入 59

3.9　链表结构的反转 60

3.10　环状链表结构 62

3.10.1　环状链表的创建 62

3.10.2　环状链表内节点的插入 63

3.10.3 环状链表内节点的删除 64

3.11　使用环状链表结构表示稀疏矩阵 66

3.12　双向链表结构 70

3.12.1　双向链表的创建 71

3.12.2　双向链表内节点的插入 72

3.12.3　双向链表内节点的删除 74

3.13　环状双向链表结构 75

3.14 习题 78

第4章　递归 80

4.1　递归的定义 80

4.2　递归工作原则 82

4.3　递归的执行过程 83

4.3.1　递归树 84

4.3.2　费氏数列 86

4.4　递归的应用 89

4.4.1　汉诺塔问题 89

4.4.2　迷宫问题 92

4.4.3　八皇后问题 96

4.4.4　骑士问题 99

4.4.5　最大公因子 102

4.4.6　史波克先生的难题 103

4.5　递归程序与非递归程序的差异 104

4.6　习题 106

第5章　栈 107

5.1　栈的定义 107

5.2　栈的制作及操作方式 107

5.3.1 算术表达式的转换（Expression Conversion） 112

5.3　栈的应用 112

5.3.2　处理子程序调用 115

5.3.3　处理中断例程 116

5.3.4　编译错误处理 117

5.3.5　汉诺塔问题 117

5.3.6　迷宫问题 121

5.3.7　八皇后问题 125

5.4　习题 127

第6章　队列 129

6.1　队列的定义 129

6.2　线性队列的制作及操作方式 129

6.2.1 以数组制作线性队列 129

6.2.2　以链表制作线性队列 134

6.3.1 以数组制作环状队列 137

6.3　环状队列的制作及操作方式 137

6.3.2　以链表制作环状队列 141

6.4 双向队列 143

6.5　优先队列 144

6.5.1　优先队列的特性 145

6.5.2 用双队列表示优先队列 145

6.6 多重队列 145

6.7　队列的应用 146

6.7.1　买票问题 146

6.7.2　Josephus问题 150

6.8 习题 151

7.1 基本术语 152

第7章　树状结构 152

7.2　树的表示法 153

7.3　二叉树 156

7.3.1　二叉树的创建 160

7.3.2　二叉树的遍历 161

7.3.3　二叉树的搜索 164

7.3.4　二元树的删除 164

7.3.5　二元树的比较 165

7.3.6　一般树转换至二叉树 166

7.3.7　二叉表示树 168

7.4　相关二叉树 170

7.4.1　完全平衡树 170

7.4.2　满二叉树 171

7.4.4　线索二叉树（Threaded Binary Tree） 172

7.4.3　完全二叉树 172

7.4.5　扩充二叉树 173

7.4.6　赫夫曼树 174

7.4.7　贪婪二元树（Greedy Binary Tree） 178

7.4.8　高度平衡二叉树 180

7.4.9　扇形树 183

7.5　二元树的衍生 186

7.5.1　2-3树与2-3-4树 186

7.5.2　红-黑树（Red-Black Tree） 190

7.5.3　最小-最大堆树 192

7.5.4　双堆树 194

7.5.5　B树 195

7.6.1　皇后问题 198

7.6　树的应用 198

7.6.2　游戏树 199

7.6.3　决策树 201

7.7 习题 202

第8章　图 205

8.1 前言 205

8.2　图的基本观念 206

8.2.1　无向图的一些重要术语 207

8.2.2　有向图的一些重要术语 208

8.2.3　其他重要术语 210

8.3　图的表示法 210

8.3.1　邻接矩阵 210

8.3.2　邻接表 212

8.3.3　邻接多重表 214

8.3.4　索引表格法 215

8.4　图的遍历 215

8.4.1　深度优先搜索法 215

8.4.2 广度优先搜索法 216

8.5　扩张树 217

8.5.1 克鲁斯卡（Kruskal）法 220

8.5.2　普瑞法 222

8.6　拓朴排序 226

8.7　最短路径 229

8.8　习题 235

第9章　排序 238

9.1　前言 238

9.2.1　交换式排序 239

9.2　内部排序法 239

9.2.2　插入式排序 248

9.2.3　选择和树状排序 257

9.2.4　其他排序 270

9.3　外部排序法 281

9.3.1　直接合并排序法 281

9.3.2 自然合并排序法 281

9.3.3　k-路合并法 282

9.3.4　多阶段合并法 285

9.4　排序法的效益评估 287

9.5　习题 288

10.1 前言 290

10.2　顺序查找法 290

第10章　查找 290

10.3　折半查找法 292

10.4　费氏查找法 293

10.5　区块查找法 298

10.6　插补查找法 299

10.7　基数查找法 302

10.8　树状查找法 303

10.8.1　折半查找树 303

10.8.2　B树查找法 304

10.8.3　B＋树（B+Tree） 305

10.8.4　数字查找树 307

10.8.5　补偿树 308

10.9　散列查找法 311

10.9.2　摘取法 312

10.9.1　直接定址法 312

10.9.3　除法 313

10.9.4　乘法 314

10.9.5　平方取中法 314

10.9.6　折叠法 314

10.9.7　解决散列冲突方法 315

10.9.8　自哈希表删除项目 318

10.9.9　哈希法的评估 318

10.10　习题 318

第11章　动态内存管理 320

11.1　前言 320

11.2　内存分配方法 321

11.3　边界标记法 322

11.3.1 可利用空间链表的结构 323

11.3.2　分配算法 324

11.3.3　回收算法 325

11.4　伙伴系统 327

11.4.1 可利用空间链表的结构 327

11.4.2　分配算法 328

11.4.3　回收算法 329

11.5　费氏伙伴系统 330

11.6　无用单元收集 331

11.7　无用单元收集的改良 333

11.8 内存压缩 333

11.9 习题 334