章概论1
1.1问题求解方法1
1.1.1问题和问题求解1
1.1.2问题求解过程1
1.1.3计算机求解问题的过程2
1.2什么是数据结构2
1.2.1算法与数据结构2
1.2.2数据结构基本概念3
1.2.3数据的逻辑结构4
1.2.4数据的存储表示5
1.2.5数据结构的操作6
1.3数据抽象和抽象数据类型7
1.3.1数据抽象和过程抽象7
1.3.2模块化、封装与信息隐蔽7
1.3.3数据类型和抽象数据类型8
1.4面向对象方法10
1.4.1面向对象方法的由来10
1.4.2面向对象方法的基本思想10
1.4.3面向对象方法的基本要素11
1.4.4抽象数据类型和面向对象方法12
1.4.5C++语言对抽象数据类型的支持13
1.5描述数据结构和算法13
1.5.1数据结构的规范13
1.5.2实现数据结构14
1.6算法分析的基本方法15
1.6.1算法及其性能标准15
1.6.2算法的时间复杂度16
1.6.3渐近时间复杂度18
1.6.4最好、最坏和平均情况时间复杂度19
1.6.5算法按时间复杂度分类19
1.6.6算法的空间复杂度19
本章小结20
习题120
第2章数组和链表22
2.1两种基本的存储表示方式22
2.2结构和类22
2.2.1结构22
2.2.2结构表示元素23
2.3指针和动态存储分配24
2.3.1指针24
2.3.2动态存储分配25
2.3.3静态变量和动态变量26
2.4数组26
2.4.1一维数组26
2.4.2二维数组27
2.4.3多维数组28
2.4.4数组和指针28
2.4.5固定长度数组和可变长度数组28
2.5链表29
2.5.1指向结构的指针30
2.5.2单链表30
2.5.3带表头结点的单链表33
2.5.4单循环链表33
2.5.5双向链表33
2.6采用模拟指针的链表35
2.6.1结点结构35
2.6.2可用空间表35
2.7异常处理37
本章小结38
习题238
第3章栈和队列40
3.1栈40
3.1.1栈ADT40
3.1.2栈的顺序表示41
3.1.3栈的链接表示44
3.2队列47
3.2.1队列ADT47
3.2.2队列的顺序表示48
3.2.3队列的链接表示51
3.3表达式计算51
3.3.1表达式51
3.3.2中缀表达式转换为后缀表达式52
3.3.3计算后缀表达式的值55
3.4演示与测试58
本章小结61
习题361
第4章递归63
4.1递归和递归算法63
4.1.1递归的概念63
4.1.2递归算法示例64
4.2归纳证明66
4.3递推关系67
4.4实现递归67
4.4.1函数调用和系统栈68
4.4.2递归函数的性能69
4.4.3尾递归69
4.4.4消去递归70
本章小结70
习题470
第5章线性表和串72
5.1线性表72
5.1.1线性表ADT72
5.1.2线性表的顺序表示73
5.1.3线性表的链接表示76
5.1.4两种存储表示的比较79
5.2一元多项式算术运算80
5.2.1多项式ADT80
5.2.2多项式的链接表示80
5.2.3项结点类81
5.2.4多项式类82
5.2.5多项式的输入和输出83
5.2.6多项式相加84
5.2.7多项式相乘85
5.2.8重载运算符86
5.3串86
5.3.1串ADT86
5.3.2串的存储表示87
5.3.3串运算的实现88
5.3.4简单模式匹配算法89
5.3.5KMP算法91
本章小结95
习题595
第6章数组和广义表97
6.1数组作为抽象数据类型97
6.1.1数组ADT97
6.1.2一维数组的C++类98
6.2矩阵99
6.2.1矩阵的概念99
6.2.2矩阵ADT99
6.2.3矩阵的二维数组表示100
6.3特殊矩阵101
6.3.1对称矩阵101
6.3.2带状矩阵102
6.4稀疏矩阵103
6.4.1稀疏矩阵的三元组表103
6.4.2稀疏矩阵转置105
6.4.3稀疏矩阵相加107
6.4.4稀疏矩阵相乘108
6.5稀疏矩阵的正交链表109
6.5.1正交链表结构109
6.5.2正交链表结点类110
6.5.3正交链表类111
6.5.4建立正交链表111
6.5.5输出正交链表113
6.6广义表113
6.6.1广义表的概念113
6.6.2广义表ADT114
6.6.3广义表的存储表示115
6.6.4广义表算法116
本章小结116
习题6117
第7章树118
7.1树的基本概念118
7.1.1树的定义118
7.1.2基本术语119
7.2二叉树120
7.2.1二叉树的定义120
7.2.2二叉树的性质121
7.2.3二叉树ADT122
7.2.4二叉树的存储表示123
7.2.5二叉树类123
7.2.6实现二叉树的基本操作124
7.3二叉树的遍历126
7.3.1二叉树遍历算法126
7.3.2二叉树遍历的递归算法128
7.3.3二叉树遍历的应用实例129
7.4二叉树遍历的非递归算法131
7.4.1遍历器类131
7.4.2中序遍历器类132
7.4.3后序遍历器类134
7.5二叉线索树136
7.5.1二叉线索树的定义136
7.5.2构造中序线索树137
7.5.3遍历中序线索树138
7.6树和森林139
7.6.1森林与二叉树的转换139
7.6.2树和森林的存储表示141
7.6.3树和森林的遍历142
本章小结143
习题7143
第8章树的应用145
8.1堆145
8.1.1堆的定义145
8.1.2堆的顺序表示145
8.1.3向下调整和建堆操作145
8.2优先权队列147
8.2.1优先权队列ADT147
8.2.2优先权队列类148
8.2.3实现优先权队列148
8.3哈夫曼树和哈夫曼编码150
8.3.1树的路径长度151
8.3.2哈夫曼算法152
8.3.3哈夫曼树类152
8.3.4构造哈夫曼树153
8.3.5哈夫曼编码155
8.3.6哈夫曼编码算法156
8.4并查集和等价关系156
8.4.1并查集ADT157
8.4.2并查集的存储表示157
8.4.3并查集类158
8.4.4Union和Find函数159
8.4.5改进的Union和Find函数159
8.4.6按等价关系分组160
本章小结161
习题8161
第9章字典和查找162
9.1字典及其表示162
9.1.1字典162
9.1.2字典查找163
9.1.3字典ADT163
9.1.4字典的存储表示164
9.2顺序查找165
9.2.1无序表的顺序查找165
9.2.2有序表的顺序查找165
9.2.3平均查找长度166
9.2.4自组织表166
9.3二分查找167
9.3.1二分查找算法167
9.3.2对半查找算法168
9.3.3二叉判定树169
9.3.4斐波那契查找算法170
9.3.5插值查找172
9.4分块查找172
9.5查找算法的时间复杂度下界173
本章小结174
习题9174
0章二叉查找树175
10.1二叉查找树表示字典175
10.1.1二叉查找树的定义175
10.1.2二叉查找树的查找操作176
10.1.3二叉查找树的插入操作177
10.1.4二叉查找树的删除操作178
10.1.5二叉查找树的高度179
10.2二叉平衡树179
10.2.1二叉平衡树的定义179
10.2.2二叉平衡树类180
10.2.3二叉平衡树的平衡旋转181
10.2.4二叉平衡树的插入操作185
10.2.5二叉平衡树的删除操作187
10.2.6二叉平衡树的高度189
10.3伸展树190
10.3.1自调节树和伸展树190
10.3.2伸展树的伸展操作191
10.3.3伸展树类193
10.3.4旋转的实现193
10.3.5伸展树的插入操作194
10.3.6分摊时间分析195
10.4红黑树195
10.4.1红黑树的定义195
10.4.2红黑树的查找操作196
10.4.3红黑树的插入操作196
10.4.4红黑树的删除操作198
10.4.5红黑树的高度199
本章小结199
习题10199
1章多叉查找树201
11.1m叉查找树201
11.2Bˉ树202
11.2.1Bˉ树的定义203
11.2.2Bˉ树的高度203
11.2.3Bˉ树的查找操作203
11.2.4Bˉ树的插入操作204
11.2.5Bˉ树的删除操作206
11.2.6Bˉ树类207
11.2.7Bˉ树的查找操作208
11.2.8Bˉ树的插入函数209
11.2.9Bˉ树的删除函数210
11.3键树212
11.3.1键树的定义212
11.3.2双链树213
11.3.3Trie树214
11.3.4Trie树的查找操作216
11.3.5Trie树的插入操作216
11.3.6Trie树的删除操作217
11.3.7Trie树性能分析217
本章小结218
习题11218
2章跳表和散列表219
12.1跳表219
12.1.1跳表的概念219
12.1.2跳表类221
12.1.3跳表的查找函数222
12.1.4跳表的插入函数223
12.1.5跳表的删除函数224
12.1.6性能分析224
12.2散列表224
12.2.1散列技术225
12.2.2散列函数226
12.2.3拉链法227
12.2.4开地址法228
12.2.5线性探查法228
12.2.6其他开地址法231
12.2.7性能分析233
本章小结233
习题12234
3章图235
13.1图的基本概念235
13.1.1图的定义与术语235
13.1.2图的抽象数据类型237
13.2图的存储结构238
13.2.1图的矩阵表示238
13.2.2图的邻接矩阵实现239
13.2.3图的邻接表表示241
13.2.4图的邻接表实现242
13.2.5有向图的正交链表表示245
13.2.6无向图的邻接多重表表示245
13.3图的遍历246
13.3.1扩充的图类246
13.3.2深度优先遍历247
13.3.3广度优先遍历248
13.3.4基本遍历方法249
13.4拓扑排序250
13.4.1AOV网络250
13.4.2拓扑排序算法252
13.4.3拓扑排序算法实现252
13.5关键路径254
13.5.1AOE网254
13.5.2关键路径算法255
13.5.3关键路径算法实现257
13.6最小代价生成树258
13.6.1基本概念258
13.6.2普里姆算法258
13.6.3克鲁斯卡尔算法260
13.6.4算法正确性262
13.7单源最短路径262
13.7.1最短路径问题262
13.7.2迪杰斯特拉算法263
13.7.3数据结构选择263
13.7.4迪杰斯特拉算法实现264
13.8所有顶点之间的最短路径266
13.8.1弗洛伊德算法266
13.8.2弗洛伊德算法实现267
本章小结268
习题13268
4章内排序270
14.1基本概念270
14.2插入排序271
14.2.1直接插入排序271
14.2.2顺序表的直接插入排序272
14.2.3单链表的直接插入排序273
14.2.4希尔排序274
14.2.5对半插入排序276
14.3选择排序276
14.3.1简单选择排序276
14.3.2堆排序277
14.4交换排序278
14.4.1冒泡排序278
14.4.2快速排序280
14.4.3快速排序性能分析281
14.5两路合并排序283
14.5.1合并两个有序序列284
14.5.2两路合并排序迭代算法284
14.5.3两路合并排序递归算法285
14.5.4单链表两路合并排序285
14.6排序算法的时间复杂度下界287
14.7基数排序288
14.7.1分配排序289
14.7.2基数排序算法289
14.7.3基数排序实现290
本章小结292
习题14292
5章文件和外排序294
15.1辅助存储器简介294
15.1.1主存储器和辅助存储器294
15.1.2磁盘存储器294
15.2文件295
15.2.1文件的基本概念295
15.2.2文件的组织方式296
15.3文件的索引结构298
15.3.1静态索引结构298
15.3.2动态索引结构299
15.4外排序300
15.4.1外排序的基本过程300
15.4.2初始游程的生成300
15.4.3多路合并302
15.4.4最佳合并树304
本章小结304
习题15305
6章实习指导和实习题306
16.1实习目的、要求和步骤306
16.2面向对象表示法307
16.3实习报告和范例308
16.3.1实习报告308
16.3.2实习题范例309
16.3.3实习报告范例309
16.4实习题312
实习1C++语言的类及模板的使用312
实习2数组和链表操作313
实习3栈、队列及表达式计算313
实习4线性表的操作及应用314
实习5一元多项式的相加和相乘314
实习6对称矩阵和稀疏矩阵的压缩存储315
实习7字符串操作和文本处理315
实习8二叉树操作和哈夫曼编码315
实习9有序表查找316
实习10Bˉ树检索317
实习11散列表查找317
实习12图的操作及应用318
实习13内排序算法及其性能比较318
实习14置换选择和K路合并的外排序算法318
附录A程序测试和调试319
A.1面向对象程序测试319
A.2程序测试步骤319
A.3测试方法320
A.4程序调试321
附录B2019年计算机考研大纲与教材内容对照323
B.12019年计算机考研大纲323
B.2教材内容对2019年计算机考研大纲的适应性324
参考文献326