第1章 绪论 1
1.1数据结构的概述 1
1.2基本概念和常用术语 2
1.3数据抽象和抽象数据类型 6
1.3.1数据抽象 6
1.3.2抽象数据类型 7
1.3.3抽象数据类型的描述和实现 8
1.4算法和算法分析 10
1.4.1算法及性能标准 10
1.4.2算法时间复杂度和渐近时间复杂度 11
1.4.3算法的空间复杂度 13
习题1 13
第2章 线性表 17
2.1线性表的逻辑结构 17
2.1.1线性表的定义 17
2.1.2线性表的ADT定义 18
2.2线性表的顺序存储和实现 19
2.2.1线性表顺序存储结构 19
2.2.2线性表在顺序存储结构下的运算 20
2.3线性表的链式存储和实现 23
2.3.1线性链表 23
2.3.2循环链表 30
2.3.3双向循环链表 32
2.3.4循环链表 34
2.4一元多项式的表示及相加 35
习题2 38
第3章 栈和队列 42
3.1栈 42
3.1.1栈的定义 42
3.1.2栈的ADT定义 42
3.1.3顺序栈 44
3.1.4多栈共享邻接空间 46
3.1.5链栈 48
3.1.6栈的应用举例 50
3.1.7栈与递归的实现 56
3.2队列 60
3.2.1队列的定义 60
3.2.2队列的ADT定义 60
3.2.3顺序队列 61
3.2.4链队列 65
3.2.5队列应用举例 66
习题3 69
第4章串 73
4.1串 73
4.1.1串的定义与相关概念 73
4.1.2串的ADT定义 74
4.2串的定长顺序存储 77
4.2.1串的定长顺序存储结构 77
4.2.2定长顺序存储的基本运算 77
4.3串的堆存储结构 80
4.3.1串名存储映像 81
4.3.2堆存储结构 82
4.3.3基于堆存储结构的基本运算 82
4.4串的块链存储结构 85
4.5串的模式匹配 87
习题4 92
第5章 数组和广义表 96
5.1数组类型的定义 96
5.1.1数组的定义 96
5.1.2数组的ADT定义 98
5.2数组的顺序存储和实现 99
5.3矩阵压缩存储 101
5.3.1对称矩阵 101
5.3.2三角矩阵 102
5.3.3带状矩阵 103
5.4稀疏矩阵 104
5.4.1稀疏矩阵三元组表存储 104
5.4.2稀疏矩阵十字链表存储 113
5.5广义表 117
5.5.1广义表的定义和基本运算 117
5.5.2广义表的存储 119
5.5.3广义表基本操作的实现 121
习题5 124
第6章树 128
6.1树的基本概念 128
6.1.1树的定义 128
6.1.2树的逻辑表示方法 129
6.1.3树的基本术语 130
6.1.4树的ADT定义 131
6.2二叉树的概念和性质 132
6.2.1二叉树的概念 132
6.2.2二叉树的性质 133
6.3二叉树的存储结构 135
6.3.1二叉树的顺序存储结构 135
6.3.2二叉树的链式存储结构 136
6.4二叉树的遍历及其他操作 137
6.4.1二叉树遍历的概念 137
6.4.2二叉树遍历的递归算法 138
6.4.3二叉树遍历的非递归算法 140
6.4.4二叉树的其他操作 143
6.5线索二叉树 145
6.5.1线索二叉树的概念 145
6.5.2线索化二叉树 146
6.5.3遍历线索二叉树 148
6.6树和森林 149
6.6.1树的存储结构 149
6.6.2二叉树与树、森林之间的转换 152
6.6.3树和森林的遍历 154
6.7哈夫曼树 155
6.7.1哈夫曼树的概述 155
6.7.2哈夫曼树的构造 156
6.7.3哈夫曼编码 157
6.7.4相关算法 158
习题6 161
第7章图 165
7.1图的概述 165
7.1.1图的定义 165
7.1.2图的相关术语 166
7.1.3图的ADT描述 169
7.2图的存储结构 170
7.2.1邻接矩阵存储结构 170
7.2.2邻接表存储结构 173
7.3图的遍历 176
7.3.1深度优先遍历 177
7.3.2广度优先遍历 179
7.3.3非连通图的遍历 181
7.4最小生成树 182
7.4.1生成树和最小生成树的概念 182
7.4.2普里姆算法 183
7.4.3克鲁斯卡尔算法 185
7.5拓扑排序与关键路径 187
7.5.1拓扑排序 187
7.5.2关键路径 191
7.6最短路径 195
7.6.1单源最短路径 196
7.6.2任意两个顶点间的最短路径 199
习题7 202
第8章 查找 208
8.1基本概念 208
8.1.1相关术语 208
8.1.2查找表结构 209
8.2静态查找表 209
8.2.1顺序查找 210
8.2.2二分查找 210
8.2.3分块查找 213
8.3动态查找表 214
8.3.1二叉排序树 214
8.3.2平衡二叉树 220
8.3.3 B-树 227
8.3.4 B+树 232
8.4哈希表查找 233
8.4.1哈希表的基本概念 233
8.4.2哈希函数构造方法 234
8.4.3哈希冲突解决方法 236
8.4.4哈希表的查找过程 240
8.4.5哈希表的性能分析 240
习题8 241
第9章 排序 246
9.1排序的相关术语与概念 246
9.2插入排序 247
9.2.1直接插入排序 247
9.2.2希尔排序 249
9.3交换排序 251
9.3.1冒泡排序 251
9.3.2快速排序 253
9.4选择排序 256
9.4.1直接选择排序 256
9.4.2堆排序 257
9.5归并排序 261
9.6基数排序 264
9.7各种排序方法比较 267
习题9 268
参考文献 272