第1章 绪论 1
1.1数据结构的基础概念 1
1.2数据结构的内容 6
1.3算法 9
1.4算法描述 10
1.5算法性能评价 11
1.5.1算法的时间性能分析 12
1.5.2算法的空间性能分析 16
1.5.3算法性能选择 17
1.6数据结构与C语言表示 17
1.6.1数据结构与程序设计的关联性 17
1.6.2结构化程序设计与函数的模块化 18
1.6.3面向对象与抽象数据类型 20
1.6.4算法描述规范与设计风格 25
1.7关于学习数据结构 31
1.8总结与提高 34
习题 35
实习题 36
第2章 线性表 37
2.1线性表的概念及其抽象数据类型定义 37
2.1.1线性表的逻辑结构 37
2.1.2线性表的抽象数据类型定义 38
2.2线性表的顺序存储 39
2.2.1线性表的顺序存储结构 39
2.2.2线性表顺序存储结构上的基本运算 41
2.3线性表的链式存储 46
2.3.1单链表 46
2.3.2单链表上的基本运算 48
2.3.3循环链表 55
2.3.4双向链表 57
2.3.5静态链表 59
2.4线性表应用——一元多项式的表示及相加 62
2.5顺序表与链表的综合比较 66
2.5.1顺序表和链表的比较 66
2.5.2线性表链式存储方式的比较 67
2.6总结与提高 68
2.6.1主要知识点 68
2.6.2典型题例 69
习题 72
实习题 74
第3章 限定性线性表——栈与队列 76
3.1栈 76
3.1.1栈的定义 76
3.1.2栈的表示和实现 78
3.1.3栈的应用举例 85
3.1.4栈与递归的实现 89
3.2队列 96
3.2.1队列的定义 96
3.2.2队列的表示和实现 97
3.2.3队列的应用举例 102
3.3总结与提高 105
3.3.1主要知识点 105
3.3.2典型题例 106
习题 108
实习题 110
第4章串 112
4.1串的基本概念 112
4.2串的存储实现 114
4.2.1定长顺序串 114
4.2.2堆串 120
4.2.3块链串 123
4.3串的应用举例：简单的行编辑器 124
4.4总结与提高 125
4.4.1主要知识点 125
4.4.2典型题例 125
习题 126
实习题 127
第5章 数组与广义表 129
5.1数组的定义与运算 129
5.2数组的顺序存储与实现 131
5.3特殊矩阵的压缩存储 134
5.3.1规律分布的特殊矩阵 134
5.3.2稀疏矩阵 137
5.4广义表 146
5.4.1广义表的概念 146
5.4.2广义表的存储结构 147
5.4.3广义表的操作实现 149
5.5总结与提高 151
5.5.1主要知识点 151
5.5.2典型题例 152
习题 153
实习题 154
第6章 树与二叉树 155
6.1树的定义与基本术语 155
6.2二叉树 159
6.2.1二叉树的定义与基本操作 159
6.2.2二叉树的性质 160
6.2.3二叉树的存储结构 162
6.3二叉树的遍历与线索化 164
6.3.1二叉树的遍历 164
6.3.2遍历算法应用 167
6.3.3基于栈的递归消除 172
6.3.4线索二叉树 177
6.3.5由遍历序列确定二叉树 183
6.4树、森林和二叉树的关系 184
6.4.1树的存储结构 184
6.4.2树、森林与二叉树的相互转换 187
6.4.3树与森林的遍历 190
6.5哈夫曼树及其应用 192
6.5.1哈夫曼树 192
6.5.2哈夫曼编码 197
6.6并查集与等价类划分 202
6.7总结与提高 207
6.7.1主要知识点 207
6.7.2典型题例 208
习题 211
实习题 213
第7章图 215
7.1图的定义与基本术语 215
7.1.1图的定义 215
7.1.2基本术语 217
7.2图的存储结构 220
7.2.1邻接矩阵表示法 220
7.2.2邻接表表示法 222
7.2.3十字链表 225
7.2.4邻接多重表 227
7.3图的遍历 229
7.3.1深度优先搜索 229
7.3.2广度优先搜索 233
7.4图的应用 235
7.4.1图的连通性问题 235
7.4.2有向无环图的应用 243
7.4.3最短路径问题 253
7.5总结与提高 259
7.5.1主要知识点 259
7.5.2典型题例 260
习题 263
实习题 266
第8章 查找 268
8.1查找的基本概念 268
8.2基于线性表的查找法 269
8.2.1顺序查找法 269
8.2.2折半查找法 270
8.2.3分块查找法 273
8.3基于树的查找法 275
8.3.1二叉排序树 275
8.3.2平衡二叉排序树 282
8.3.3 B树 292
8.4计算式查找法——哈希法 302
8.4.1哈希函数的构造方法 304
8.4.2处理冲突的方法 306
8.4.3哈希表的查找过程 308
8.4.4哈希法性能分析 309
8.5总结与提高 312
8.5.1主要知识点 312
8.5.2典型题例 315
习题 319
实习题 320
第9章 内部排序 321
9.1排序的基本概念 321
9.2插入类排序 322
9.2.1直接插入排序 323
9.2.2折半插入排序 325
9.2.3希尔排序 326
9.2.4小结 329
9.3交换类排序法 330
9.3.1冒泡排序 330
9.3.2快速排序 332
9.3.3小结 335
9.4选择类排序法 336
9.4.1简单选择排序 336
9.4.2树形选择排序 337
9.4.3堆排序 339
9.4.4小结 345
9.5归并排序 346
9.6分配类排序 348
9.6.1多关键字排序 348
9.6.2链式基数排序 349
9.6.3基数排序的顺序表实现 353
9.7各种排序方法的综合比较 353
9.8总结与提高 355
9.8.1主要知识点 355
9.8.2典型题例 355
习题 359
实习题 361
第10章 外部排序 362
10.1外排序的基本方法 362
10.1.1磁盘排序 362
10.1.2磁带排序 363
10.2总结与提高 363
习题 364
附录一 学期样卷 365
学期样卷一 365
学期样卷二 367
学期样卷三 370
附录二 硕士研究生入学考试样题 373
2011年全国硕士研究生入学统一考试数据结构试题 373
2010年全国硕士研究生入学统一考试数据结构试题 374
2009年全国硕士研究生入学统一考试数据结构试题 376
工程硕士学位研究生模拟试题 378
附录三 光盘目录 381
参考文献 382