第1章概述 1
1.1数据结构的兴起与发展 1
目 录 1
1.2数据结构的研究对象 2
1.3数据结构的概念 3
1.4数据结构的图示 4
1.5.2线性结构 5
1.5.3树形结构 5
1.5.1集合 5
1.5数据结构的分类 5
1.5.4图状结构 6
1.6数据结构的存储 6
1.6.1存储器表示 6
1.6.2存储映像 7
1.6.3基本存储方法 7
1.7数据结构的访问接口 9
1.7.1访问接口与逻辑结构 9
1.8.1对象与类 10
1.8面向对象方法 10
1.7.3基本操作的实现 10
1.7.2基本操作的种类 10
1.8.2面向对象方法要素 11
1.8.3面向对象方法的若干述评* 13
1.8.4面向对象程序设计语言* 14
1.9面向对象与数据结构 18
1.9.1面向对象与数据结构的关系 18
1.9.2面向对象数据结构 18
1.9.3数据结构的对象模型 19
习题 20
本章小结 20
第2章程序设计基本策略与方法 21
2.1算法 21
2.1.1算法的概念 21
2.1.2算法的时间复杂度与空间复杂度 22
2.1.3算法时间复杂度的度量 24
2.2穷举法 26
2.3递推法与迭代法 26
2.3.1递推法 26
2.3.2迭代法 27
2.4.1递归与递归程序的概念 29
2.4递归法 29
2.4.2递归程序设计要点 31
2.4.3递归程序执行机理 31
2.4.4 Hanoi塔问题与运行图 33
2.5逐步求精法 35
2.5.1基本思想 35
2.5.2应用示例 35
2.6.1基本思想 37
2.6分治法 37
2.6.2平面分治法示例——顺序统计 38
2.6.3迭代分治法示例——循环赛赛程安排* 40
本章小结 42
习题 43
第3章线性表 45
3.1线性表的逻辑结构 45
3.1.1基本概念 45
3.1.2线性表抽象模型 45
3.2.1基本存储方法 49
3.2线性表的顺序存储结构 49
3.2.2面向对象描述 50
3.3异常处理与下标选择器* 59
3.3.1异常处理 59
3.3.2下标选择器 62
3.4线性表的链式存储——线性链表 66
3.4.1链式存储方法 66
3.4.2线性链表的面向对象描述 66
3.4.3线性链表的面向对象实现 69
3.5.1带头结点的链表 79
3.5几种特殊线性链表 79
3.5.2循环链表 80
3.5.3双向链表 81
3.6线性表应用示例 82
3.6.1集合运算* 82
3.6.2一元多项式相加 83
3.6.3一元多项式的乘法* 92
本章小结 92
习题 93
4.1.1栈的逻辑结构 94
4.1栈 94
第4章特殊线性表——栈、队列、串 94
4.1.2栈的顺序存储结构 96
4.1.3栈的链式存储结构 100
4.2队列 104
4.2.1队列的逻辑结构 104
4.2.2队列的顺序存储结构 105
4.2.3队列的链式存储结构 110
4.3串 112
4.3.1串的逻辑结构 112
4.3.2串的存储结构 116
本章小结 119
习题 120
第5章数组与十字链表 121
5.1数组 121
5.1.1数组的定义与运算 121
5.1.2数组的存储结构与寻址问题 122
5.1.3一维数组的存储与寻址 122
5.1.4二维数组的存储与寻址 123
5.1.5多维数组的存储与寻址 124
5.1.6寻址公式的计算 125
5.2特殊数组* 126
5.2.1对称矩阵 126
5.2.2下／上三角矩阵 127
5.3稀疏矩阵 127
5.3.1稀疏矩阵的逻辑表示 127
5.3.2三元组表存储法 128
5.3.3三元组表的操作 130
5.3.4转置操作 132
5.4.1存储方式 138
5.4十字链表 138
5.4.2十字链表对象 140
5.4.3基本操作的实现 142
本章小结 146
习题 146
第6章树形结构 148
6.1树形结构的基本概念 148
6.1.1树形结构的定义 148
6.1.2基本术语 151
6.2.2几种特殊二叉树 152
6.2.1二叉树的基本概念 152
6.2二叉树 152
6.2.3二叉树的基本性质 153
6.2.4二叉树的遍历 155
6.3二叉树的存储结构 157
6.3.1顺序存储结构 157
6.3.2链式存储结构 158
6.4二叉树对象模型 160
6.4.1二叉树结点对象 160
6.4.2二叉树对象 161
6.5二叉树的遍历操作 165
6.5.1前序遍历操作 165
6.5.2中序遍历操作 169
6.5.3后序遍历操作 170
6.6二叉树的解析表示与存储结构之间的转化 173
6.6.1双遍历结果转化为树 173
6.6.2根据广义表表示创建树 175
6.6.3根据存储结构创建广义表* 178
6.6.4根据前序扩展序列创建树* 179
6.7.1线索化的概念 181
6.7二叉树的线索化 181
6.7.2线索化算法 182
6.8树与森林 184
6.8.1树与森林的遍历 184
6.8.2树、森林与二叉树之间的转化 186
6.8.3树的存储结构 187
6.9树对象模型* 190
6.9.1树结点对象 190
6.9.2树类 191
6.10.1 哈夫曼树的基本概念 194
6.10树的应用示例——哈夫曼树 194
6.10.2哈夫曼树构造算法 195
6.10.3哈夫曼树构造算法的实现 196
6.10.4哈夫曼判定树 199
6.10.5哈夫曼编码与数据压缩 200
本章小结 201
习题 202
第7章图结构 204
7.1图的基本概念 204
7.1.1图的概念 204
7.2图的对象抽象模型 207
7.1.2图的基本操作 207
7.2.1图结点抽象模型 208
7.2.2图的边对象抽象模型 208
7.2.3图抽象对象模型 209
7.3图的存储结构 211
7.3.1邻接矩阵法 212
7.3.2邻接表 214
7.3.3十字链表* 218
7.3.4邻接多重表* 220
7.4图的遍历 222
7.4.1概述 222
7.4.2深度优先遍历 222
7.4.3深度优先遍历的性质 227
7.4.4广度优先遍历 228
7.4.5广度优先遍历的性质 232
7.5拓扑排序 232
7.5.1拓扑序列与AOV网 233
7.5.2拓扑排序算法与实现 234
7.6.1AOE网与关键路径的概念 238
7.6 AOE网与关键路径 238
7.6.2关键路径的识别 241
本章小结 242
习题 242
第8章广义表 244
8.1广义表的逻辑结构 244
8.1.1基本概念 244
8.1.2 广义表逻辑图 246
8.1.3 广义表的遍历 246
8.2广义表的存储结构 247
8.2.1基本存储方法 247
8.1.5基本操作 247
8.1.4基本特性 247
8.2.2链式结构的高级语言描述 249
8.3 广义表对象模型* 250
8.3.1广义表元素接口 250
8.3.2 广义表接口 251
8.4广义表的分支单链表对象* 254
8.4.1结点对象 254
8.4.2分支单链表对象 255
8.5.1一般问题 256
8.5广义表操作的实现* 256
8.5.2遍历操作 257
8.5.3 广义表统计计数 258
8.5.4广义表的串行化与逆串行化 259
8.5.5 广义表的复制与求尾 261
8.6广义表结构的应用 262
8.6.1多元多项式的表示 262
8.6.2层次结构的表示 263
本章小结 264
习题 264
9.1.1检索的概念 266
第9章检索结构 266
9.1概述 266
9.1.2检索结构 267
9.1.3检索算法的时间与空间复杂度分析 267
9.1.4检索算法的判定树 268
9.2线性结构的检索 270
9.2.1顺序检索 270
9.2.2折半检索 271
9.2.3斐波那契检索* 275
9.3.1概述 280
9.2.4插值检索* 280
9.3线性索引结构 280
9.3.2稠密索引 281
9.3.3分块索引 281
9.4树形索引结构与二叉排序树 283
9.4.1树形索引结构概述 283
9.4.2二叉排序树的概念 283
9.4.3二叉排序树的检索 284
9.4.4二叉排序树的插入* 286
9.4.5二叉排序树的删除* 287
9.4.6二叉排序树的分析与最优二叉排序树* 292
9.5平衡二叉排序树* 293
9.5.1基本概念 293
9.5.2若干性质 293
9.5.3局部平衡调整算法 294
9.6 B树 299
9.6.1 B树的概念 299
9.6.2 B树的存储结构 300
9.6.5 B树的插入 301
9.6.3 B树的基本操作 301
9.6.4 B树的检索方法 301
9.6.6 B树的删除 304
9.6.7 B+树 306
9.6.8 B树对象模型 307
9.7散列结构 307
9.7.1概念 307
9.7.2散列技术中的主要问题 308
9.7.3散列过程 308
9.7.4散列函数的设计 308
9.7.5冲突解决 310
本章小结 311
习题 312
第10章外存与文件组织 313
10.1 外存结构 313
10.1.1 外存简介 313
10.1.2磁带结构 313
10.1.3磁盘结构 314
10.2 文件 315
10.2.1文件的概念 315
10.2.3文件的物理组织 316
10.2.2文件操作与存取方式 316
10.2.4缓冲技术 318
10.3顺序文件 318
10.4索引文件 319
10.5 ISAM* 320
10.5.1 ISAM的概念 320
10.5.2 ISAM结构的操作 321
10.6 VSAM 322
10.6.1 VSAM的概念 322
10.6.2 VSAM结构的操作 323
10.7散列方式 324
10.8多索引文件 325
10.8.1多重表文件 325
10.8.2倒排文件 326
本章小结 327
习题 327
第11章排序算法 329
11.1概述 329
11.2插入排序 330
11.2.1直接插入排序 331
11.2.2其他插入排序算法 332
11.3交换排序 332
11.3.1 冒泡排序 333
11.3.2 冒泡算法的改进 334
11.3.3快速排序* 335
11.4选择排序 336
11.4.1直接选择排序 336
11.4.2堆排序 337
11.5.2多段二路合并 345
11.5.1二路合并 345
11.5归并排序 345
11.5.3二路归并排序 346
11.6外排序简介 348
本章小结 348
习题 349
第12章算法设计基本方法 350
12.1 回溯法与限界剪枝法 350
12.1.1基本思想 350
12.1.2迷宫问题 351
12.1.3稳定婚姻问题* 357
12.1.4 n皇后问题 365
12.1.5限界剪枝法简介* 368
12.2动态规划法 368
12.2.1动态规划法要素与最优性原理 368
12.2.2最长公共子序列 369
12.2.3流水线调度问题* 374
12.2.4多源最短路径的Floyd算法 380
12.2.5 0-1背包问题 383
12.3贪心法 385
12.3.2背包问题 386
12.3.1基本思想 386
12.3.3 Prim最小生成树算法 389
12.3.4 Kruskal最小生成树算法 396
12.3.5单源最短路径 399
12.3.6贪心法要素总结 405
本章小结 406
习题 407
词汇索引 408
参考文献 413