本书第一版面市以来，受到广大读者的欢迎并被部分院校选为教材。看到自己辛勤劳
动的成果得到读者认可，欣慰之余更感到责任重大。本着对读者负责、精益求精的精神，
为了更好地发挥本书的作用，对第一版进行了修订。
1056
修订内容主要有以下几个方面：
(1) 增加了一些叙述性的文字。如在2.1 节，不仅说明算法2.1 和2.2 在两个程序中实
现，而且提示其原因。
(2) 增加了一些图示。如在程序algo4-3.cpp 中，增加了图4–11 关于文本结构的示例。
目的是克服仅通过文字描述存储结构不直观、不形象的缺点，便于读者掌握程序和算法的
精髓。
(3) 增删了一些存储结构及其基本操作。在第2 章增加了不带头结点的单链表的存储
结构及其基本操作。另外，删去了诸如线性表的扩展操作等有些重复的程序。这样，既使
得程序简明，又将本书前后内容有机结合，融会贯通。
(4) 修改了一些算法。如在程序algo3-1.cpp 中加了一个常量，使algo3-1.cpp 从将十进
制的整数转换为八进制的功能扩展到将十进制的整数转换为二～九进制。
(5) 增加了几个算法。如在7.4.3 节，教科书中描述了克鲁斯卡尔算法的原理，但没有
给出相应的算法，程序algo7-8.cpp 实现了克鲁斯卡尔算法。
(6) 增加了几个算法应用程序。如程序algo7-9.cpp 将算法7.16 应用于教科书的图7.33
（全国交通网），显示了算法的实用性，同时也增加了趣味性。
(7) 增加了1 个可视化的应用程序。将algo7-9.cpp 改编为Visual C++ 6.0 下的可视化的
程序(在光盘的\VC\shortest 子目录下)。其目的是增加趣味性，提高读者的学习兴趣。同时
也说明，“算法与数据结构”不仅能用于传统的DOS 界面，也能应用于视窗界面。
(8) 订正了第1 版中出现的错误。如在程序bo4-1.cpp 的StrInsert()函数中将语句
for(i=MAXSTRLEN;i<=pos;i--) S [i]=S[i-T[0]]; 改为 for(i=MAXSTRLEN;i>=pos+T[0];i--)
S

[i]=S[i-T[0]];
(9) 修改了一些程序。目的是使程序更加合理、简明。如将程序bo7-1.cpp 的DFS()函
数中的
for(w=FirstAdjVex(G,v1);w>=0;w=NextAdjVex(G,v1,strcpy(w1,GetVex(G,w))))
改为
for(w=FirstAdjVex(G,G.vexs[v]);w>=0;w=NextAdjVex(G,G.vexs[v],G.vexs[w]))
虽然经过作者的精心修订，书中疏漏、错误及可改进之处恐仍在所难免，希望读者不
吝赐教，以便有机会时改正。

目 录
第1章绪论......1
1.1 什么是数据结构.......................................... 1
1.2 基本概念和术语.......................................... 1
1.3 抽象数据类型的表示与实现......................... 1
1.4 算法和算法分析.......................................... 7
1.4.1 算法........... 7
1.4.2 算法设计的要求.................................... 7
1.4.3 算法效率的度量.................................... 7
第2章线性表..9
2.1 线性表的类型定义........................................ 9
2.2 线性表的顺序表示和实现............................ 9
2.3 线性表的链式表示和实现.......................... 21
2.3.1 线性链表. 21
2.3.2 循环链表. 60
2.3.3 双向链表. 65
2.4 一元多项式的表示及相加.......................... 80
第3章栈和队列....................................... 86
3.1 栈.................... 86
3.1.1 抽象数据类型栈的定义....................... 86
3.1.2 栈的表示和实现.................................. 86
3.2 栈的应用举例. 90
3.2.1 数制转换. 90
3.2.2 括号匹配的检验.................................. 92
3.2.3 行编辑程序......................................... 93
3.2.4 迷宫求解. 95
3.2.5 表达式求值........................................ 100
3.3 栈与递归的实现....................................... 104
3.4 队列.............. 108
3.4.1 抽象数据类型的定义......................... 108
3.4.2 链队列——队列的链式表示和实现.. 108
3.4.3 循环队列——队列的顺序表示和实现......................................... 114
3.5 离散事件模拟 130
第4章串...... 140
4.1 串类型的定义.......................................... 140
- 2 -
4.2 串的表示和实现....................................... 140
4.2.1 定长顺序存储表示............................ 140
4.2.2 堆分配存储表示................................ 146
4.2.3 串的块链存储表示............................ 151
4.3 串的模式匹配算法.................................... 158
4.3.1 求子串位置的定位函数Index(S,T,pos).......................................... 158
4.3.2 模式匹配的一种改进算法................. 159
4.4 串操作应用举例....................................... 161
4.4.1 文本编辑.......................................... 161
4.4.2 建立词索引表.................................... 167
第5章数组和广义表............................ 177
5.1 数组的定义... 177
5.2 数组的顺序表示和实现............................ 177
5.3 矩阵的压缩存储....................................... 181
5.3.1 特殊矩阵.......................................... 181
5.3.2 稀疏矩阵.......................................... 181
5.4 广义表的定义.......................................... 206
5.5 广义表的存储结构.................................... 206
5.6 m元多项式的表示.................................... 207
5.7 广义表的递归算法.................................... 207
5.7.1 求广义表的深度................................ 207
5.7.2 复制广义表........................................ 208
5.7.3 建立广义表的存储结构..................... 208
第6章树和二叉树................................. 218
6.1 树的定义和基本术语................................ 218
6.2 二叉树.......... 218
6.2.1 二叉树的定义.................................... 218
6.2.2 二叉树的性质.................................... 218
6.2.3 二叉树的存储结构............................ 218
6.3 遍历二叉树和线索二叉树........................ 245
6.3.1 遍历二叉树........................................ 245
6.3.2 线索二叉树........................................ 245
6.4 树和森林....... 254
6.4.1 树的存储结构.................................... 254
6.4.2 森林与二叉树的转换......................... 270
6.4.3 树和森林的遍历................................ 270
6.5 树与等价问题.......................................... 271
6.6 赫夫曼树及其应用.................................... 271
6.6.1 最优二叉树(赫夫曼树)..................... 271
6.6.2 赫夫曼编码........................................ 271
- 3 -
第7章图...... 277
7.1 图的定义和术语....................................... 277
7.2 图的存储结构.......................................... 277
7.2.1 数组表示法........................................ 277
7.2.2 邻接表... 292
7.2.3 十字链表.......................................... 306
7.2.4 邻接多重表........................................ 317
7.3 图的遍历....... 328
7.3.1 深度优先搜索.................................... 328
7.3.2 广度优先搜索.................................... 329
7.4 图的连通性问题....................................... 335
7.4.1 无向图的连通分量和生成树............. 335
7.4.2 有向图的强连通分量......................... 338
7.4.3 最小生成树........................................ 338
7.4.4 关节点和重连通分量......................... 343
7.5 有向无环图及其应用................................ 347
7.5.1 拓扑排序.......................................... 347
7.5.2 关键路径.......................................... 350
7.6 最短路径....... 353
7.6.1 从某个源点到其余各顶点的最短路径......................................... 353
7.6.2 每一对顶点之间的最短路径............. 356
第8章动态存储管理............................ 366
8.1 概述.............. 366
8.2 可利用空间表.......................................... 366
8.3 边界标识法... 366
8.3.1 可利用空间表的结构......................... 366
8.3.2 分配算法.......................................... 367
8.3.3 回收算法.......................................... 374
8.4 伙伴系统....... 374
8.4.1 可利用空间表的结构......................... 374
8.4.2 分配算法.......................................... 375
8.4.3 回收算法.......................................... 380
8.5 无用单元收集.......................................... 381
第9章查找.. 384
9.1 静态查找表... 384
9.1.1 顺序表的查找.................................... 384
9.1.2 有序表的查找.................................... 387
9.1.3 静态树表的查找................................ 388
9.1.4 索引顺序表的查找............................ 390
- 4 -
9.2 动态查找表... 391
9.2.1 二叉排序树和平衡二叉树................. 391
9.2.2 B
树和B+树........................................ 399
9.2.3 键树....... 404
9.3 哈希表.......... 413
9.3.1 什么是哈希表.................................... 413
9.3.2 哈希函数的构造方法......................... 413
9.3.3 处理冲突的方法................................ 413
9.3.4 哈希表的查找及其分析..................... 414
第10章内部排序................................... 419
10.1 概述............ 419
10.2 插入排序..... 419
10.2.1 直接插入排序.................................. 419
10.2.2 其它插入排序.................................. 422
10.2.3 希尔排序......................................... 425
10.3 快速排序..... 426
10.4 选择排序..... 429
10.4.1 简单选择排序.................................. 429
10.4.2 树形选择排序.................................. 431
10.4.3 堆排序. 432
10.5 归并排序..... 434
10.6 基数排序..... 435
10.6.1 多关键字的排序.............................. 435
10.6.2 链式基数排序.................................. 435
10.7 各种内部排序方法的比较讨论............... 440
第11章外部排序................................... 441
11.1 外存信息的存取...................................... 441
11.2 外部排序的方法...................................... 441
11.3 多路平衡归并的实现.............................. 441
11.4 置换—选择排序...................................... 446
第12章文件 452
12.1 有关文件的基本概念.............................. 452
12.2 顺序文件..... 452
附录A 关于标准C程序.......................... 456
附录B 光盘文件目录............................ 457