第1章 绪论 1
1.1集合 1
1.1.1集合及其基本运算 1
1.1.2自然数集与数学归纳法 3
1.1.3笛卡儿积 5
1.1.4二元关系 5
1.2算法 7
1.2.1算法的基本概念 7
1.2.2算法设计基本方法 8
1.2.3算法的复杂度分析 13
1.3数据结构的基本概念 16
1.3.1两个例子 16
1.3.2什么是数据结构 19
1.3.3数据结构的图形表示 21
1.3.4线性数据结构与非线性数据结构 23
习题 23
第2章 线性表及其顺序存储结构 25
2.1线性表的基本概念 25
2.1.1什么是线性表 25
2.1.2线性表的顺序存储结构——顺序表 26
2.1.3顺序表的基本运算——插入与删除 28
2.1.4顺序表类 31
2.2栈及其应用 35
2.2.1什么是栈 35
2.2.2栈的顺序存储及其运算 37
2.2.3顺序栈类 39
2.2.4表达式的计算 42
2.3队列及其应用 51
2.3.1什么是队列 51
2.3.2循环队列及其运算 52
2.3.3循环队列类 55
2.3.4队列的应用 59
2.4字符串 66
2.4.1字符串的基本概念 66
2.4.2字符串匹配 67
习题 72
第3章 线性链表 74
3.1线性链表的基本概念 74
3.1.1线性表顺序存储的问题 74
3.1.2线性链表的存储结构 75
3.2线性链表的插入与删除 79
3.2.1线性链表的插入 79
3.2.2线性链表的删除 81
3.2.3线性链表类 83
3.3带链的栈 88
3.3.1带链栈及其基本运算 88
3.3.2带链栈类 89
3.4带链的队列 92
3.4.1带链队列及其基本运算 92
3.4.2带链队列类 94
3.5循环链表 97
3.5.1循环链表及其基本运算 97
3.5.2循环链表类 99
3.6多项式的表示与运算 102
习题 110
第4章 线性表的索引存储结构 111
4.1索引存储的概念 111
4.2“顺序-索引-顺序”存储方式 112
4.3“顺序-索引-链接”存储方式 113
4.4多重索引存储结构 114
习题 115
第5章 数组 116
5.1数组的顺序存储结构 116
5.2规则矩阵的压缩 117
5.3三列二维数组 120
5.3.1稀疏矩阵的三列二维数组表示及其运算 121
5.3.2三列二维数组表示的稀疏矩阵类 133
5.4三元组链表 140
5.4.1稀疏矩阵的三元组链表表示及其运算 140
5.4.2三元组链表表示的稀疏矩阵类 148
5.5十字链表 154
5.5.1稀疏矩阵的十字链表表示 154
5.5.2十字链表表示的稀疏矩阵类 158
习题 162
第6查 树与二叉树 164
6.1树 164
6.2二叉树及其基本性质 167
6.2.1什么是二叉树 167
6.2.2二叉树的基本性质 167
6.2.3满二叉树与完全二叉树 168
6.3二叉树的存储结构 170
6.4二叉树的遍历 173
6.5二叉链表类 176
6.6穿线二叉树 179
6.6.1穿线二叉树的概念 179
6.6.2中序穿线二叉树 180
6.6.3前序穿线二叉树 187
6.6.4后序穿线二叉树 192
6.7表达式的线性化 199
6.7.1有序树的二叉树表示 199
6.7.2表达式的线性化 200
6.8最优二叉树及其应用 201
6.8.1什么是最优二叉树 201
6.8.2最优二叉树的构造 203
6.8.3最优二叉树类 208
6.8.4霍夫曼编码 210
习题 211
第7章图 213
7.1图的基本概念 213
7.2图的存储结构 214
7.2.1关联矩阵 214
7.2.2求值矩阵 215
7.2.3邻接表 216
7.2.4邻接多重表 220
7.3图的遍历 221
7.3.1纵向优先搜索法 221
7.3.2横向优先搜索法 222
7.4最短距离问题 225
7.5图的邻接表类 232
习题 239
第8章查找技术 240
8.1顺序查找 240
8.2顺序存储的有序表 240
8.2.1顺序有序表的对分查找 240
8.2.2顺序有序表类 241
8.3分块查找 246
8.4二叉排序树 247
8.4.1二叉排序树的基本概念 247
8.4.2二叉排序树的插入 248
8.4.3二叉排序树的删除 250
8.4.4二叉排序树的查找 252
8.4.5二叉排序树类 256
8.5多层索引树查找 259
8.5.1 B-树 259
8.5.2 B+树 277
习题 295
第9章Hash表技术 296
9.1 Hash表的基本概念 296
9.1.1直接查找技术 296
9.1.2 Hash表 297
9.1.3 Hash码的构造 298
9.2几种常用的Hash表 299
9.2.1线性Hash表 299
9.2.2随机Hash表 305
9.2.3溢出Hash表 310
9.2.4拉链Hash表 317
9.2.5指标Hash表 324
习题 324
第10章 排序技术 326
10.1互换类排序 326
10.1.1冒泡排序 326
10.1.2快速排序 329
10.2插入类排序 332
10.2.1简单插入排序 332
10.2.2希尔排序 334
10.3选择类排序 336
10.3.1简单选择排序 336
10.3.2堆排序 338
10.4拓扑分类 341
10.5其他排序方法简介 344
10.5.1归并排序 344
10.5.2基数排序 347
习题 348
参考文献 349