正版新书]数据结构(用面向对象方法与C++语言描述)(第3版)殷人昆

第1章数据结构概论1
1.1数据结构的概念1
1.1.1数据结构举例1
1.1.2数据与数据结构2
1.1.3数据结构的分类3
1.1.4“数据结构”课程的内容4
1.2数据结构的抽象形式6
1.2.1数据类型6
1.2.2数据抽象与抽象数据类型7
1.3作为ADT的C 类9
1.3.1面向对象的概念9
1.3.2C 中的类10
1.3.3C 中的对象12
1.3.4C 的输入输出13
1.3.5C 中的函数14
1.3.6动态存储分配17
1.3.7C 中的继承18
1.3.8多态性19
1.3.9C 的模板23
1.4算法定义24
1.5算法性能分析与度量25
1.5.1算法的性能标准26
1.5.2算法复杂性度量26
1.5.3算法的渐进分析31
1.5.4坏、好和平均情况35
习题36

第2章线性表40
2.1线性表的概念40
2.1.1线性表的定义40
2.1.2线性表的类定义41
2.2顺序表42
2.2.1顺序表的定义和特点42
2.2.2顺序表的类定义及其操作42
2.2.3顺序表的性能分析47
2.2.4顺序表的应用49
2.3单链表49
2.3.1单链表的概念50
2.3.2单链表的类定义51
2.3.3单链表中的插入与删除52
2.3.4带附加头结点的单链表54
2.3.5单链表的模板类56
2.4线性链表的其他变形62
2.4.1循环单链表62
2.4.2双向链表65
2.5单链表的应用： 多项式及其运算69
2.5.1多项式的表示69
2.5.2多项式的类定义71
2.5.3多项式的加法73
2.6静态链表74
习题75

第3章栈和队列81
3.1栈81
3.1.1栈的定义81
3.1.2顺序栈82
3.1.3链式栈85
3.1.4栈的应用之一——括号匹配87
3.1.5栈的应用之二——表达式的计算88
3.2栈与递归93
3.2.1递归的概念93
3.2.2递归过程与递归工作栈97
3.2.3用回溯法求解迷宫问题102
3.3队列105
3.3.1队列的概念105
3.3.2循环队列106
3.3.3链式队列109
3.3.4队列应用举例： 打印二项展开式 (a b)i的系数111
3.4优先级队列113
3.4.1优先级队列的概念113
3.4.2优先级队列的存储表示和实现114
3.5双端队列115
3.5.1双端队列的概念116
3.5.2双端队列的数组表示117
习题119

第4章数组、串与广义表125
4.1多维数组的概念与存储125
4.1.1多维数组的概念125
4.1.2多维数组的存储表示126
4.2特殊矩阵128
4.2.1对称矩阵的压缩存储128
4.2.2三对角/多对角矩阵的压缩存储130
4.3稀疏矩阵131
4.3.1稀疏矩阵及其三元组数组表示131
4.3.2稀疏矩阵的转置134
4.3.3稀疏矩阵的相加137
4.3.4矩阵的十字链表表示139
4.4字符串140
4.4.1字符串的概念140
4.4.2C 有关字符串的库函数141
4.4.3字符串的实现143
4.4.4字符串的自定义类145
4.4.5字符串操作的实现146
4.4.6字符串的模式匹配148
4.4.7字符串的存储方法154
4.5广义表156
4.5.1广义表的定义与性质156
4.5.2广义表的表示157
4.5.3广义表存储结构的实现158
4.5.4广义表的递归算法161
习题168

第5章树174
5.1树的基本概念174
5.1.1树的定义和术语174
5.1.2树的抽象数据类型176
5.2二叉树177
5.2.1二叉树的定义177
5.2.2二叉树的性质178
5.2.3二叉树的抽象数据类型179
5.3二叉树的存储表示180
5.3.1二叉树的数组存储表示180
5.3.2二叉树的链接存储表示181
5.4二叉树遍历及其应用186
5.4.1二叉树遍历的递归算法186
5.4.2二叉树遍历的应用188
5.4.3二叉树遍历的非递归算法190
5.4.4二叉树的计数194
5.5线索二叉树197
5.5.1线索198
5.5.2中序线索二叉树的建立和遍历198
5.5.3前序与后序的线索化二叉树204
5.6树与森林205
5.6.1树的存储表示205
5.6.2树、森林与二叉树的转换211
5.7树与森林的遍历及其应用212
5.7.1树与森林的深度优先遍历213
5.7.2树和森林的广度优先遍历215
5.7.3树遍历算法的应用216
5.8堆217
5.8.1小堆和堆217
5.8.2堆的建立219
5.8.3堆的插入与删除220
5.9Huffman树及其应用222
5.9.1路径长度222
5.9.2Huffman树223
5.9.3Huffman树的应用： 判定树226
5.9.4Huffman树的应用： Huffman编码227
习题229

第6章集合与字典237
6.1集合及其表示237
6.1.1集合的基本概念237
6.1.2用位向量实现集合抽象数据类型238
6.1.3用有序链表实现集合的抽象数据类型243
6.2并查集与等价类248
6.2.1并查集的定义及其实现248
6.2.2并查集的应用： 等价类划分252
6.3字典254
6.3.1字典的概念254
6.3.2字典的线性表描述256
6.4跳表258
6.4.1跳表的概念258
6.4.2跳表的搜索、插入和删除259
6.5散列260
6.5.1散列表与散列方法261
6.5.2散列函数261
6.5.3处理冲突的闭散列方法263
6.5.4处理冲突的开散列方法272
6.5.5散列表分析274
习题276

第7章搜索结构282
7.1静态搜索结构283
7.1.1静态搜索表283
7.1.2顺序搜索285
7.1.3基于有序顺序表的顺序搜索和折半搜索286
7.1.4基于有序顺序表的其他搜索方法291
7.2二叉搜索树293
7.2.1二叉搜索树的概念293
7.2.2二叉搜索树上的搜索295
7.2.3二叉搜索树的插入295
7.2.4二叉搜索树的删除297
7.2.5二叉搜索树的性能分析298
7.3AVL树301
7.3.1AVL树的概念301
7.3.2平衡化旋转302
7.3.3AVL树的插入306
7.3.4AVL树的删除309
7.3.5AVL树的性能分析314
7.4伸展树315
7.5红黑树318
7.5.1红黑树的概念和性质318
7.5.2红黑树的搜索319
7.5.3红黑树的插入319
7.5.4红黑树的删除320
习题323

第8章图330
8.1图的基本概念330
8.1.1与图有关的若干概念330
8.1.2图的抽象数据类型332
8.2图的存储结构333
8.2.1图的邻接矩阵表示334
8.2.2图的邻接表表示339
8.2.3图的邻接多重表表示345
8.3图的遍历347
8.3.1深度优先搜索348
8.3.2广度优先搜索349
8.3.3连通分量350
8.3.4重连通分量352
8.4小生成树354
8.4.1Kruskal算法355
8.4.2Prim算法358
8.5短路径360
8.5.1非负权值的单源短路径360
8.5.2任意权值的单源短路径363
8.5.3所有顶点之间的短路径366
8.6用顶点表示活动的网络（AOV网络）368
8.7用边表示活动的网络（AOE网络）372
习题377

第9章排序384
9.1排序的概念及其算法性能分析384
9.1.1排序的概念384
9.1.2排序算法的性能评估385
9.1.3排序表的类定义387
9.2插入排序388
9.2.1直接插入排序388
9.2.2折半插入排序389
9.2.3希尔排序391
9.3快速排序392
9.3.1快速排序的过程392
9.3.2快速排序的性能分析394
9.3.3快速排序的改进算法395
9.3.4三路划分的快速排序算法398
9.4选择排序400
9.4.1直接选择排序400
9.4.2锦标赛排序401
9.4.3堆排序406
9.5归并排序409
9.5.1归并409
9.5.2归并排序算法410
9.6基于链表的排序算法411
9.6.1链表插入排序412
9.6.2链表归并排序414
9.6.3链表排序结果的重排415
9.7分配排序418
9.7.1桶式排序418
9.7.2基数排序419
9.7.3MSD基数排序420
9.7.4LSD基数排序422
9.8内部排序算法的分析424
9.8.1排序方法的下界424
9.8.2各种内部排序方法的比较426
习题427

第10章文件、外部排序与搜索435
10.1主存储器和外存储器435
10.1.1磁带435
10.1.2磁盘存储器437
10.1.3缓冲区与缓冲池439
10.2文件组织441
10.2.1文件的概念441
10.2.2文件的存储结构442
10.3外排序451
10.3.1外排序的基本过程451
10.3.2k路平衡归并与败者树453
10.3.3初始归并段的生成458
10.3.4并行操作的缓冲区处理462
10.3.5归并树465
10.4多级索引结构467
10.4.1静态的ISAM方法467
10.4.2动态的m路搜索树468
10.4.3B树470
10.4.4B树的插入472
10.4.5B树的删除474
10.4.6B 树478
10.4.7VSAM481
10.5字典树482
10.5.1字典树的概念482
10.5.2双链树表示483
10.5.3Trie树484
习题486

附录A部分习题答案495

参考文献501

作者2021年5月

"
殷人昆，江苏苏州市人，清华大学计算机软件工学硕士，日本东京理科大学工学部经营工学科客座研究员。曾任清华大学计算机系软件工程实验室主任，中国科学院研究生院远程 兼职教授，中央广播电视大学主讲教师，长期从事数据结构、软件工程和软件项目管理的教学及与相关科研，已出版教材二十余部，发表论文多篇。"}}

“数据结构”是计算机专业的核心课程，是从事计算机软件开发和应用的人员应当的专业基础。随着计算机的日益普及，“数据结构”课程也在不断发展。 本书按照清华大学计算机科学与技术系本科“数据结构”大纲的要求，从面向对象的概念、对象类设计的风格和数据结构的层次开始，从线性结构到非线性结构，从简单到复杂，循序渐进，逐步深入地讨论了各种数据结构的内在的逻辑关系及它们在计算机中的实现方式和使用。此外，本书对常用的迭代、递归、回溯等算法设计技巧，搜索和排序算法等都做了详尽描述，并引入了简单的算法分析。 全书采用了面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C 语言作为算法的描述工具，强化基本知识和基本能力的双基训练。全书条理清晰，通俗易懂，图文并茂，适于自学。 本书适合于大专院校计算机或软件专业本科生使用，也可作为教师和有关科研人员的参考书。与本书配套的《数据结构精讲与习题详解（C语言版）（第2版）》一书已由清华大学出版社出版。此外，需要PowerPonit电子教学幻灯片的教师，可与清华大学出版社联系。