图书简介
本书是一本非常畅销的数据结构基础教材的第2版，它使用标準ANSIC和C++程式设计语言来实现数据结构。我们通过大量实际的问题演示了如何套用C和C++程式来实现抽象概念，并逐步地指导读者标识问题，实现解决方案，以及将方案套用到实际情况中。对于专业程式设计师来说，本书也是极有价值的参考书。
目录
第1章数据结构入门 1
1.1信息和涵义 1
1.1.1二进制整数和十进制整数 2
1.1.2实数 3
1.1.3字元串 4
1.1.4硬体和软体 5
1.1.5实现的概念 6
1.1.6示例 6
1.1.7抽象数据类型 10
1.1.8序列的值定义 13
1.1.9变长字元串的ADT表示 14
1.1.10C的数据类型 16
1.1.11C中的指针 16
1.1.12C中的数据结构 18
1.1.13练习1 19
1.2C中的数组 19
1.2.1数组的抽象数据类型定义 20
1.2.2使用一维数组 21
1.2.3一维数组的实现 23
1.2.4将数组作为参数 25
1.2.5C中的字元串 25
1.2.6字元串操作 26
1.2.7二维数组 27
1.2.8多维数组 29
1.2.9练习2 31
1.3C中的结构 33
1.3.1结构的实现 37
1.3.2联合(Union) 38
1.3.3联合的实现 41
1.3.4结构参数 42
1.3.5表示其他数据结构 44
1.3.6有理数 44
1.3.7记忆体的分配和变数的作用域 47
1.3.8练习3 51
1.4C++中的类 53
1.4.1Rational类 53
1.4.2Rational类的使用 54
1.4.3方法的实现 56
1.4.4重载 61
1.4.5继承 61
1.4.6构造函式 63
1.4.7练习4 64
第2章堆叠 65
2.1定义和示例 65
2.1.1基本操作 66
2.1.2示例 67
2.1.3堆叠的抽象数据类型定义 70
2.1.4练习1 71
2.2用C描述堆叠 71
2.2.1pop操作的实现 75
2.2.2测试异常情况 76
2.2.3实现push操作 77
2.2.4练习2 79
2.3示例：中缀、后缀和前缀 80
2.1.4练习1 71
2.2用C描述堆叠 71
2.2.1pop操作的实现 75
2.2.2测试异常情况 76
2.2.3实现push操作 77
2.2.4练习2 79
2.3示例：中缀、后缀和前缀 80
2.3.1基本定义和示例 80
2.3.2后缀表达式的计算 82
2.3.3计算后缀表达式的程式 83
2.3.4程式的局限性 85
2.3.5中缀表达式转换为后缀表达式 86
2.3.6将中缀表达式转换为后缀表达式的程式 90
2.3.7用C++模板实现的堆叠 92
2.3.8练习3 97
第3章递归 100
3.1递归定义和递归过程 100
3.1.1阶乘函式 100
3.1.2自然数的乘法 102
3.1.3斐波纳契数列 103
3.1.4对分查找 104
3.1.5递归定义或算法的特点 107
3.1.6练习1 107
3.2C中的递归 108
3.2.1用C实现阶乘 108
3.2.2用C实现斐波纳契数列 111
3.2.3用C实现对分查找 113
3.2.4递归链 114
3.2.5代数表达式的递归定义 115
3.2.6练习2 118
3.3编写递归程式 120
3.3.1汉诺塔问题 121
3.3.2使用递归将前缀表达式转换为后缀表达式 125
3.3.3练习3 129
3.4递归的模拟 131
3.4.1从函式中返回 133
3.4.2递归函式的实现 134
3.4.3阶乘的模拟 134
3.4.4最佳化模拟例程 138
3.4.5消除goto语句 140
3.4.6模拟汉诺塔问题 142
3.4.7练习4 147
3.5递归的效率 149
第4章伫列和鍊表 151
4.1伫列及其顺序表示 151
4.1.1伫列的抽象数据类型定义 152
4.1.2伫列的C语言实现 152
4.1.3insert操作 156
4.1.4优先伫列 157
4.1.5用数组实现的优先伫列 157
4.1.6练习1 159
4.2鍊表 160
4.2.1从鍊表中插入和删除结点 161
4.2.2堆叠的鍊表实现 164
4.2.3getnode和freenode操作 165
4.2.4伫列的鍊表实现 166
4.2.5鍊表数据结构 167
4.2.6鍊表操作的例子 169
4.2.7优先伫列的鍊表实现 171
4.2.8头结点 171
4.2.9练习2 172
4.3C中的鍊表 173
4.3.1鍊表的数组实现 173
4.3.2数组实现的局限性 176
4.3.3动态变数的分配和释放 176
4.3.4使用动态变数实现的鍊表 180
4.3.5用鍊表实现的伫列 181
4.3.6C中鍊表操作的例子 183
4.3.7非整数鍊表和非齐次鍊表 184
4.3.8数组实现和动态实现鍊表的比较 186
4.3.9头结点的实现 186
4.3.10练习3 186
4.4示例：用鍊表进行模拟 188
4.4.1模拟进程 188
4.4.2数据结构 189
4.4.3模拟程式 190
4.4.4练习4 193
4.5其他鍊表结构 195
4.5.1循环鍊表 195
4.5.2用循环鍊表表示堆叠 196
4.5.3用循环鍊表表示伫列 197
4.5.4循环鍊表的基本操作 197
4.5.5约瑟夫问题 199
4.5.6头结点 200
4.5.7使用循环鍊表实现长正整数的加法 201
4.5.8双向鍊表 203
4.5.9使用双向鍊表实现长整数的加法 205
4.5.10练习5 209
4.6C++中的鍊表 210
第5章树 214
5.1二叉树 214
5.1.1二叉树中的操作 218
5.1.2二叉树的套用 219
5.1.3练习1 223
5.2二叉树的表示 224
5.2.1二叉树的结点表示 224
5.2.2内部结点和外部结点 227
5.2.3二叉树的隐式数组表示 227
5.2.4选择一个二叉树表示 231
5.2.5二叉树遍历的C语言表示 232
5.2.6线索化二叉树 234
5.2.7使用father栏位的遍历 238
5.2.8异构二叉树 240
5.2.9练习2 241
5.3示例：哈夫曼算法 243
5.3.1哈夫曼算法 245
5.3.2C程式 247
5.3.3练习3 250
5.4将表表示为二叉树 251
5.4.1寻找第k个元素 252
5.4.2删除元素 254
5.4.3用C语言实现用树表示的表 257
5.4.4构建一个用树表示的表 259
5.4.5回顾约瑟夫问题 261
5.4.6练习4 262
5.5树及其套用 262
5.5.1树的C语言表示 264
5.5.2树的遍历 267
5.5.3用树来表示广义表达式 268
5.5.4对表达式树求值 270
5.5.5构建树 272
5.5.6练习5 274
5.6示例：游戏树 275
第6章排序 282
6.1背景 282
6.1.1效率方面的考虑 284
6.1.2符号O 285
6.1.3排序的效率 287
6.1.4练习1 289
6.2交换排序 290
6.2.1冒泡排序 290
6.2.2快速排序 292
6.2.3快速排序的效率 298
6.2.4练习2 300
6.3选择排序以及树排序 301
6.3.1直接选择排序 302
6.3.2二叉树排序 303
6.3.3堆排序 305
6.3.4作为优先权伫列的堆 306
6.3.5使用堆进行排序 308
6.3.6堆排序的过程 310
6.3.7练习3 311
6.4插入排序 312
6.4.1简单插入 312
6.4.2希尔排序 313
6.4.3地址计算排序 316
6.4.4练习4 318
6.5归併排序以及基数排序 320
6.5.1归併排序 320
6.5.2Cook-Kim算法 323
6.5.3基数排序 323
6.5.4练习5 327
第7章搜寻 329
7.1基本搜寻技术 329
7.1.1作为抽象数据类型的目录 330
7.1.2算法符号 331
7.1.3顺序搜寻 331
7.1.4顺序搜寻的效率 333
7.1.5重新排序鍊表以最大化搜寻效率 334
7.1.6在有序表中进行搜寻 335
7.1.7使用索引的顺序搜寻 335
7.1.8二叉树搜寻 338
7.1.9插值搜寻 339
7.1.10练习1 340
7.2树搜寻 342
7.2.1在二叉搜寻树中插入元素 343
7.2.2在二叉搜寻树中删除元素 346
7.2.3二叉搜寻树操作的效率 348
7.2.4不均匀的二叉搜寻树的效率 350
7.2.5最佳搜寻树 351
7.2.6平衡二叉树 353
7.2.7练习2 360
7.3广义搜寻树 362
7.3.1多路搜寻树 362
7.3.2在多路树中进行搜寻 364
7.3.3实现多路树 365
7.3.4遍历多路树 366
7.3.5在多路搜寻树中进行插入 368
7.3.6B树 372
7.3.7B树插入算法 377
7.3.8计算father和index 380
7.3.9在多路搜寻树中进行删除 383
7.3.10多路搜寻树的效率 387
7.3.11改进B树 390
7.3.12B+树 392
7.3.13数字搜寻树 393
7.3.14Trie 396
7.3.15练习3 396
7.4散列 397
7.4.1使用开放定址来解决散列冲突 399
7.4.2从散列表删除项 401
7.4.3再散列方法的效率 402
7.4.4散列表重新排序 404
7.4.5Brent方法 405
7.4.6二叉树散列 407
7.4.7通过额外的存储空间来获得改进 409
7.4.8联合散列 412
7.4.9单独链地址法 414
7.4.10在外部存储器中进行散列 416
7.4.11分离方法 418
7.4.12动态散列以及可扩展散列 419
7.4.13线性散列 423
7.4.14选择散列函式 429
7.4.15理想的散列函式 430
7.4.16散列函式的通用类 434
7.4.17练习4 435
第8章图及其套用 437
8.1图 437
8.1.1图的套用 439
8.1.2图的C语言表示 440
8.1.3传递闭包 442
8.1.4Warshall算法 445
8.1.5最短路径算法 446
8.1.6练习1 448
8.2流问题 449
8.2.1改进流函式 450
8.2.2示例 453
8.2.3算法和程式 454
8.2.4练习2 458
8.3图的连结表示 458
8.3.1再访Dijkstra算法 463
8.3.2组织图结点集合 465
8.3.3调度的套用 465
8.3.4C程式 469
8.3.5练习3 472
8.4图的遍历以及生成森林 474
8.4.1图的遍历方法 474
8.4.2生成森林 477
8.4.3无向图以及它们的遍历 479
8.4.4深度优先遍历 480
8.4.5深度优先遍历的套用 483
8.4.6深度优先遍历的效率 484
8.4.7广度优先遍历 484
8.4.8最小生成树 486
8.4.9Kruskal算法 487
8.4.10Round-Robin算法 488
8.4.11练习4 488
第9章存储管理 490
9.1广义表 490
9.1.1修改表的操作 492
9.1.2示例 493
9.1.3表的鍊表表示 494
9.1.4表的表示 495
9.1.5crlist操作 497
9.1.6表头的用法 499
9.1.7释放表结点 499
9.1.8C中的广义表 500
9.1.9程式语言和表 503
9.1.10练习1 504
9.2自动表管理 504
9.2.1引用计数方法 505
9.2.2无用信息收集 509
9.2.3无用信息收集的算法 510
9.2.4收集和压缩 515
9.2.5无用信息收集的变种 521
9.2.6练习2 521
9.3动态存储管理 522
9.3.1存储块的压缩 523
9.3.2首次匹配、最佳匹配和最差匹配 525
9.3.3首次匹配方法的改进 528
9.3.4释放存储块 529
9.3.5边界标籤方法 531
9.3.6BuddySystem 533
9.3.7其他的BuddySystem 538
9.3.8练习3 540
8.3.2组织图结点集合 465
8.3.3调度的套用 465
8.3.4C程式 469
8.3.5练习3 472
8.4图的遍历以及生成森林 474
8.4.1图的遍历方法 474
8.4.2生成森林 477
8.4.3无向图以及它们的遍历 479
8.4.4深度优先遍历 480
8.4.5深度优先遍历的套用 483
8.4.6深度优先遍历的效率 484
8.4.7广度优先遍历 484
8.4.8最小生成树 486
8.4.9Kruskal算法 487
8.4.10Round-Robin算法 488
8.4.11练习4 488
第9章存储管理 490
9.1广义表 490
9.1.1修改表的操作 492
9.1.2示例 493
9.1.3表的鍊表表示 494
9.1.4表的表示 495
9.1.5crlist操作 497
9.1.6表头的用法 499
9.1.7释放表结点 499
9.1.8C中的广义表 500
9.1.9程式语言和表 503
9.1.10练习1 504
9.2自动表管理 504
9.2.1引用计数方法 505
9.2.2无用信息收集 509
9.2.3无用信息收集的算法 510
9.2.4收集和压缩 515
9.2.5无用信息收集的变种 521
9.2.6练习2 521
9.3动态存储管理 522
9.3.1存储块的压缩 523
9.3.2首次匹配、最佳匹配和最差匹配 525
9.3.3首次匹配方法的改进 528
9.3.4释放存储块 529
9.3.5边界标籤方法 531
9.3.6BuddySystem 533
9.3.7其他的BuddySystem 538
9.3.8练习3 540