第1章 数据结构概述 1
1.1 数据结构的发展概况 1
1.2 数据结构的基本概念 2
1.3 算法的描述与算法的分析 5
1.3.1 算法的定义与特性 5
1 3.2 算法设计的要求 6
1.3.3 算法的描述 6
1.3.4 算法分析 8
1.4 关于数据结构的学习 11
习题 11
第2章 线性表 14
2.1 线性表的概念及抽象数据类型 14
2.1.1 线性表的定义 14
2.1.2 线性表的抽象数据类型 14
2.2 线性表的顺序存储及实现 15
2.2.1 顺序表 16
2.2.2 顺序表的基本运算 17
2.2.3 顺序表应用举例 21
2.3 线性表的链式存储及实现 24
2.3.1 单链表 24
2.3.2 单链表的基本运算 26
2.3.3 循环链表 31
2.3.4 双向链表 33
2.3.5 静态链表 36
2.4 综合案例——一元多项式的相加 40
2.4.1 一元多项式的表示与存储 40
2.4.2 一元多项式的相加 42
2.5 顺序表和链表的比较 44
2.6 小结 44
习题 45
第3章 栈和队列 49
3.1 栈 49
3.1.1 栈的定义 49
3.1.2 栈的抽象数据类型 50
3.1.3 栈的顺序表示与实现 50
3.1.4 顺序栈的基本运算 51
3.1.5 共享栈的问题 53
3.1.6 栈的链式表示与实现 55
3.1.7 栈的应用举例 57
3.1.8 栈与递归 61
3.2 队列 63
3.2.1 队列的定义 63
3.2.2 队列的抽象数据类型 63
3.2.3 队列的表示与实现 64
3.2.4 队列的应用举例 72
3.3 小结 75
习题 75
第4章 串 77
4.1 串的基本概念 77
4.1.1 串的基本概念 77
4.1.2 串的抽象数据类型 78
4.2 串的存储实现 79
4.2.1 定长顺序串 79
4.2.2 串的模式匹配 83
4.3 堆串与块链串 90
4.3.1 堆串的存储结构 90
4.3.2 堆串的基本运算 91
4.3.3 块链串 93
4.4 小结 94
习题 95
第5章 数组和广义表 96
5.1 数组的定义及基本操作 96
5.1.1 数组的定义 96
5.1.2 数组的抽象数据类型 97
5.1.3 数组的存储表示 97
5.2 特殊矩阵的压缩存储 100
5.2.1 对称矩阵 100
5.2.2 三角矩阵 101
5.2.3 带状矩阵 101
5.3 稀疏矩阵 102
5.3.1 稀疏矩阵的三元组表存储 102
5.3.2 稀疏矩阵的十字链表存储 110
5.4 广义表 112
5.4.1 广义表的定义 112
5.4.2 广义表的存储结构 113
5.4.3 广义表基本操作的实现 115
5.5 小结 117
习题 118
第6章 树和二叉树 121
6.1 树 121
6.1.1 树的定义 121
6.1.2 树的基本术语 122
6.1.3 树的表示形式 123
6.1.4 树的抽象数据类型 124
6.2 二叉树 125
6.2.1 二叉树的定义与性质 125
6.2.2 二叉树的存储结构 128
6.2.3 二叉树的基本操作 131
6.3 二叉树的遍历 135
6.3.1 二叉树的递归遍历 135
6.3.2 二叉树的遍历算法的应用 138
6.3.3 二叉树非递归遍历 140
6.4 二叉树的线索化 145
6.4.1 二叉树的线索化定义 145
6.4.2 二叉树的线索化 146
6.4.3 线索二叉树的遍历 148
6.5 树和森林 149
6.5.1 树的存储结构 149
6.5.2 树、森林与二叉树的转换 151
6.5.3 树的遍历 154
6.5.4 森林的遍历 155
6.6 哈夫曼树及其应用 156
6.6.1 哈夫曼树 156
6.6.2 哈夫曼编码 158
6.6.3 哈夫曼编码算法的实现 160
6.7 小结 162
习题 163
第7章 图 168
7.1 图的基本概念 168
7.1.1 图的定义 168
7.1.2 图的相关概念 169
7.1.3 图的抽象数据类型 171
7.2 图的存储结构 173
7.2.1 邻接矩阵表示法 173
7.2.2 邻接表表示法 176
7.2.3 十字链表表示法 180
7.2.4 邻接多重链表表示法 182
7.3 图的遍历 183
7.3.1 图的深度优先搜索 183
7.3.2 图的广度优先搜索 186
7.3.3 图的遍历应用举例 188
7.4 图的应用 190
7.4.1 图的连通性问题 190
7.4.2 有向无环图 197
7.4.3 最短路径 204
7.5 小结 211
习题 211
第8章 查找 215
8.1 查找的基本概念 215
8.2 基于线性表的查找 216
8.2.1 顺序查找 216
8.2.2 折半查找 218
8.2.3 分块查找 221
8.3 基于树的查找 224
8.3.1 二叉排序树 224
8.3.2 平衡二叉排序树 229
8.3.3 B树 238
8.4 哈希表的查找 245
8.4.1 哈希函数的构造方法 245
8.4.2 处理冲突的方法 247
8.4.3 哈希表的查找与分析 249
8.4.4 哈希表的应用举例 250
8.5 小结 252
习题 252
第9章 排序 255
9.1 排序的基本概念 255
9.2 插入排序 257
9.2.1 直接插入排序 257
9.2.2 折半插入排序 259
9.2.3 希尔排序 260
9.3 交换排序 263
9.3.1 冒泡排序 263
9.3.2 快速排序 265
9.4 选择排序 269
9.4.1 简单选择排序 269
9.4.2 堆排序 271
9.5 归并排序 276
9.6 基数排序 278
9.6.1 基数排序的算法思想 278
9.6.2 基数排序的算法实现 280
9.7 各种排序的性能比较 281
9.8 小结 283
习题 284
参考文献 288