第1章 绪论 1
1.1数据结构的发展概况 1
1.2数据结构的基本概念和术语 2
1.3 数据的逻辑结构和存储结构 5
1.3.1数据的逻辑结构 5
1.3.2数据的存储结构 6
1.4算法及其描述形式 8
1.4.1 算法简介 8
1.4.2算法的描述形式 8
1.5算法分析 12
1.5.1算法效率及其度量 12
1.5.2算法时间复杂度的计算 14
1.5.3空间复杂度 16
小结 16
综合练习一 16
一、选择题 16
二、填空题 17
三、综合题 18
第2章 线性表 20
2.1 线性表的定义和基本运算 20
2.1.1线性表的定义 20
2.1.2线性表的基本运算 21
2.2线性表的顺序存储结构及其运算 21
2.2.1顺序表的表示和实现 21
2.2.2顺序表的基本运算 22
2.3线性表的链式存储结构及其运算 25
2.3.1线性单链表及其运算 26
2.3.2循环链表 36
2.3.3 双链表 38
2.4一元多项式相加 41
小结 44
综合练习二 44
一、选择题 44
二、填空题 45
三、综合题 46
3.1.1 栈的定义 47
3.1 栈 47
第3章 栈和队列 47
3.1.2栈的顺序存储及其基本运算 49
3.1.3栈的链式存储及其基本运算 54
3.1.4栈的应用——算术表达式求值 56
3.1.5栈与递归 61
3.2 队列 64
3.2.1 队列的定义 64
3.2.2队列的顺序存储结构——顺序队列 65
3.2.3循环顺序队列 68
3.2.4队列的链式存储结构——链队列 71
3.2.5队列的应用举例 75
一、选择题 80
小结 80
综合练习三 80
二、填空题 81
三、综合题 82
第4章 串 84
4.1 串的基本概念 84
4.2串的存储结构 85
4.2.1 串的顺序存储结构 86
4.2.2串的链式存储结构 87
4.3 串的基本运算 87
4.3.4判断串相等 88
4.3.3求串长 88
4.3.2 串复制 88
4.3.1 串赋值运算 88
4.3.5 串连接 89
43.6求子串 89
4.3.7子串定位 90
4.3.8子串插入 90
4.3.9子串删除 91
4.3.10子串替换 92
小结 92
综合练习四 93
一、选择题 93
二、填空题 93
三、综合题 94
第5章 数组和广义表 95
5.1数组的定义和运算 95
5.1.1数组的定义 95
5.1.2数组的运算 96
5.2数组的顺序存储结构及其实现 97
5.3特殊矩阵和稀疏矩阵的压缩存储 99
5.3.1特殊矩阵及其压缩存储 99
5.3.2稀疏矩阵及其压缩存储 100
5.4广义表 110
5.4.1 广义表的定义 110
5.4.2 广义表的存储结构 111
小结 115
综合练习五 116
一、选择题 116
二、填空题 116
三、综合题 117
第6章 树和二叉树 118
6.1树的基本概念和术语 118
6.1.1树的定义 118
6.1.2树的常用术语 119
6.1.3树的表示方法 121
6.1.4树的运算 121
6.2.1二叉树的基本概念 122
6.2二叉树 122
6.2.2 二叉树的基本运算 123
6.2.3二叉树的基本性质 124
6.2.4二叉树的存储结构 126
6.3遍历二叉树 128
6.3.1 遍历二叉树的定义及递归算法 128
6.3.2遍历二叉树的非递归算法 130
6.3.3二叉树基本操作举例 133
6.4线索二叉树 138
6.5树和森林 142
6.5.1树的存储结构 142
6.5.2树和二叉树之间的转换 144
6.5.4树和森林的遍历 146
6.5.3森林和二叉树之间的转换 146
6.6哈夫曼树 148
6.6.1 有关术语及哈夫曼树的定义 148
6.6.2构造哈夫曼树 149
6.6.3哈夫曼编码 149
6.6.4哈夫曼算法的实现 151
小结 153
综合练习六 153
一、选择题 153
二、填空题 154
三、综合题 156
7.1.1图的定义 159
第7章 图 159
7.1 图的基本概念 159
7.1.2图的有关术语 160
7.1.3 图的基本运算 164
7.2 图的存储结构 164
7.2.1邻接矩阵 165
7.2.2邻接表 166
7.3图的遍历 168
7.3.1深度优先搜索 168
7.3.2广度优先搜索 170
7.4最小生成树 172
7.4.1 Prim（普里姆）算法 173
7.4.2 Kruskal（克鲁斯卡尔）算法 175
7.5最短路径 176
7.5.1 求单源点最短路径的Dijkstra（迪杰斯特拉）算法 176
7.5.2求每对顶点之间的最短路径 179
7.6拓扑排序 180
7.6.1 拓扑排序的有关概念 180
7.6.2拓扑排序算法 182
小结 186
综合练习七 186
一、选择题 186
二、填空题 187
三、综合题 190
第8章 查找 191
8.1查找的基本概念 191
8.2顺序查找 193
8.3 折半查找 194
8.4分块查找 198
8.5动态查找表 201
8.5.1二叉排序树的查找 202
8.5.2平衡二叉树 210
8.6哈希表查找 212
8.6.1 哈希表的概念 212
8.6.2哈希函数的构造方法 214
8.6.3 哈希表处理冲突的方法 217
8.6.4哈希表查找运算及性能分析 219
小结 224
综合练习八 224
一、选择题 224
二、填空题 225
三、综合题 227
第9章 排序 228
9.1排序的基本概念 228
9.2插入排序 229
9.2.1直接插入排序 229
9.2.2希尔排序 231
9.3.1 冒泡排序 233
9.3交换排序 233
9.3.2快速排序 235
9.4选择排序 238
9.4.1直接选择排序 238
9.4.2堆排序 239
9.5归并排序 245
9.6基数排序 248
9.7各种内部排序方法的比较 252
小结 253
综合练习九 253
一、选择题 253
二、填空题 254
三、综合题 255
参考答案 257
第1章 257
第2章 257
第3章 262
第4章 267
第5章 268
第6章 272
第7章 275
第8章 278
第9章 281
参考文献 286