第1章数据结构入门 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.10 C的数据类型 16
1.1.11 C中的指针 16
1.1.12 C中的数据结构 18
1.2 C中的数组 19
1.1.13 练习 19
1.2.1数组的抽象数据类型定义 20
1.2.2使用一维数组 21
1.2.3一维数组的实现 23
1.2.4将数组作为参数 25
1.2.5 C 中的字符串 25
1.2.6字符串操作 26
1.2.7二维数组 27
1.2.8多维数组 29
1.2.9练习2 31
1.3 C中的结构 33
1.3.1结构的实现 37
1.3.2联合（Union） 38
1.3.3联合的实现 41
1.3.4结构参数 42
1.3.6有理数 44
1.3.5表示其他数据结构 44
1.3.7内存的分配和变量的作用域 47
1.3.8练习3 51
1.4 C++中的类 53
1.4.1 Rational类 53
1.4.2 Rational类的使用 54
1.4.3方法的实现 56
1.4.4重载 61
1.4.5继承 61
1.4.6构造函数 63
1.4.7练习4 64
2.1定义和示例 65
8.3.3调度的应用 65
第2章堆栈 65
2.1.1基本操作 66
2.1.2示例 67
8.3.4 C程序 69
2.1.3堆栈的抽象数据类型定义 70
2.1.4练习1 71
2.2用C描述堆栈 71
2.2.1 pop操作的实现 75
2.2.2测试异常情况 76
2.2.3实现push操作 77
8.4.2生成森林 77
2.2.4练习2 79
2.3 示例：中缀、后缀和前缀 80
2.3.1基本定义和示例 80
2.3.2后缀表达式的计算 82
2.3.3计算后缀表达式的程序 83
6.1.1 效率方面的考虑 84
2.3.4程序的局限性 85
2.3.5中缀表达式转换为后缀表达式 86
6.1.3排序的效率 87
2.3.6将中缀表达式转换为后缀表达式的程序 90
2.3.7用C++模板实现的堆栈 92
2.3.8练习3 97
3.1.1阶乘函数 100
3.1 递归定义和递归过程 100
第3章递归 100
3.1.2自然数的乘法 102
3.1.3斐波纳契数列 103
3.1.4对分查找 104
3.1.6练习1 107
3.1.5递归定义或算法的特点 107
3.2 C中的递归 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.3 insert操作 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.3 getnode和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.3 C中的链表 173
4.3.1链表的数组实现 173
4.3.3动态变量的分配和释放 176
4.3.2数组实现的局限性 176
4.3.4使用动态变量实现的链表 180
4.3.5用链表实现的队列 181
4.3.6 C中链表操作的例子 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.4循环链表的基本操作 197
4.5.3用循环链表表示队列 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.6 C++中的链表 210
5.1 二叉树 214
第5章树 214
5.1.1 二叉树中的操作 218
5.1.2二叉树的应用 219
5.1.3练习1 223
5.2.1 二叉树的结点表示 224
5.2二叉树的表示 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.2 C程序 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.5树及其应用 262
5.4.6练习4 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.2符号O 285
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.2 Cook-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.7使用索引的顺序搜索 335
7.1.6在有序表中进行搜索 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.1 多路搜索树 362
7.3广义搜索树 362
7.3.2在多路树中进行搜索 364
7.3.3 实现多路树 365
7.3.4遍历多路树 366
7.3.5在多路搜索树中进行插入 368
7.3.6 B树 372
7.3.7 B树插入算法 377
7.3.8计算father和index 380
7.3.9在多路搜索树中进行删除 383
7.3.10多路搜索树的效率 387
7.3.11 改进B树 390
7.3.12 B+树 392
7.3.13数字搜索树 393
7.3.14 Trie 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.5 Brent方法 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.4 Warshall算法 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.5练习3 472
8.4 图的遍历以及生成森林 474
8.4.1 图的遍历方法 474
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.9 Kruskal算法 487
8.4.10 Round-Robin算法 488
8.4.11练习4 488
9.1 广义表 490
第9章存储管理 490
9.1.1修改表的操作 492
9.1.2示例 493
9.1.3表的链表表示 494
9.1.4表的表示 495
9.1.5 crlist操作 497
9.1.6表头的用法 499
9.1.7释放表结点 499
9.1.8 C中的广义表 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.6练习2 521
9.2.5无用信息收集的变种 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.6 Buddy System 533
9.3.7其他的Buddy System 538
9.3.8练习3 540