第1章 数据结构概述 1
1.1 数据结构 1
1.1.1 基本概念 1
1.1.2 数据结构的概念 2
1.1.3 数据结构的逻辑结构和物理结构 3
1.1.4 数据的逻辑结构 4
1.1.5 数据的操作 5
1.1.6 数据结构讨论的内容及作用 7
1.2 算法 8
1.2.1 算法的概念 8
1.2.2 算法的描述 9
1.2.3 算法设计的目标 10
1.2.4 算法效率分析 10
1.2.5 算法存储空间分析 12
1.2.6 算法设计的基本方法 12
1.3 数据结构、算法和程序 14
1.3.1 数据结构与算法 14
1.3.2 数据结构与算法的关系 15
1.4 算法效率的典型例题 16
1.5 本章小结 19
1.6 习题 19
第2章 线性表的顺序存储 21
2.1 线性表的逻辑结构 21
2.1.1 线性表的定义 21
2.1.2 线性表的数学定义和逻辑图 22
2.1.3 线性表的基本操作 22
2.2 线性表的顺序存储结构 23
2.2.1 顺序表定义 23
2.2.2 顺序存储结构类型 24
2.2.3 顺序表的基本运算 25
2.3 顺序表的建立 27
2.4 顺序表的查找 27
2.4.1 按位置查找元素 28
2.4.2 按值查找元素 28
2.4.3 顺序表的查找操作的效率分析 30
2.5 顺序表的插入与删除 30
2.5.1 在顺序表的第i个位置插入一个元素 30
2.5.2 删除顺序表的第i个位置元素 31
2.5.3 顺序表的插入与删除操作的效率分析 32
2.6 顺序表的典型例题 33
2.7 算法设计实训 36
2.7.1 学生成绩管理需求分析 36
2.7.2 学生成绩管理数据结构 36
2.7.3 学生成绩管理的实现 37
2.8 本章小结 38
2.9 习题 39
第3章 线性表的链式存储 41
3.1 线性表的链式存储结构 41
3.1.1 单链表 41
3.1.2 循环链表 43
3.1.3 双向链表 43
3.1.4 静态链表 44
3.2 单链表创建算法的实现 45
3.2.1 头插法单链表的创建实现 45
3.2.2 尾插法单链表的创建实现 47
3.3 单链表运算的实现 49
3.3.1 单链表辅助运算的实现 49
3.3.2 单链表求表长的实现 50
3.3.3 单链表插入操作的实现 51
3.3.4 单链表删除操作的实现 53
3.3.4 单链表查找操作的实现 54
3.4 双向链表基本运算的实现 55
3.4.1 双向链表插入操作的实现 55
3.4.2 双向链表删除操作的实现 57
3.5 顺序表与链表的比较 58
3.6 链表的典型例题 59
3.7 算法设计实训 67
3.7.1 需求分析 67
3.7.2 约瑟夫问题的数据结构 68
3.7.3 约瑟夫问题的算法实现 68
3.8 本章小结 70
3.9 习题 70
第4章 栈和队列 73
4.1 栈 73
4.1.1 栈的定义与基本运算 73
4.1.2 栈的顺序存储 74
4.1.3 栈的链式存储 77
4.2 队列 79
4.2.1 队列的定义与基本运算 80
4.2.2 非循环队列的顺序存储 80
4.2.3 循环队列的顺序存储 83
4.2.4 队列的链式存储 85
4.3 栈和队列的典型例题 88
4.4 算法设计举例 91
4.4.1 括号匹配问题 91
4.4.2 表达式求值问题 92
4.4.3 迷宫问题 95
4.4.4 农夫过河问题 98
4.5 本章小结 100
4.6 习题 100
第5章 串 103
5.1 串的定义、表示和实现 103
5.1.1 串的基本概念 103
5.1.2 串的基本操作 104
5.2 串的顺序存储结构 107
5.2.1 串的初始化 107
5.2.2 求串的长度 108
5.2.3 串的赋值 108
5.2.4 串的复制 109
5.2.5 串的连接 110
5.2.6 求串的子串 110
5.2.7 串的比较 111
5.2.8 求子串在主串中的位置 112
5.2.9 串的插入 113
5.2.10 串的删除 115
5.2.11 串的替换 115
5.3 串的堆存储结构 117
5.3.1 串的初始化 117
5.3.2 串的赋值 117
5.3.3 串的复制 118
5.3.4 串的连接 119
5.3.5 串的比较 119
5.3.6 取子串 120
5.3.7 求子串在主串中的位置 120
5.3.8 串的插入 121
5.3.9 串的删除 121
5.3.10 串的替换 122
5.4 串的链式存储结构 122
5.4.1 串的初始化 123
5.4.2 串的赋值 123
5.4.3 串的连接 124
5.4.4 串的输出 125
5.4.5 串的比较 125
5.4.6 求字符串的长度 126
5.4.7 取子串 126
5.4.8 求子串在主串中的位置 127
5.4.9 串的插入 128
5.4.10 串的删除 128
5.5 串的模式匹配 129
5.5.1 简单的模式匹配算法 130
5.5.2 KMP字符串模式匹配算法 132
5.6 串的典型例题 135
5.7 算法设计举例——行编辑程序 137
5.8 本章小结 143
5.9 习题 144
第6章 数组和广义表 145
6.1 数组 145
6.1.1 数组的定义 145
6.1.2 数组的顺序存储结构 146
6.1.3 结构体描述 148
6.1.4 数组的初始化 148
6.1.5 数组中数据的存储 149
6.1.6 数组中数据的读取 149
6.1.7 数组中数据的修改 149
6.1.8 用堆存储方式存储数组 150
6.2 特殊矩阵的压缩存储 151
6.2.1 对称矩阵 151
6.2.2 对称矩阵的基本操作 153
6.3 三角矩阵 155
6.3.1 三角矩阵相关概念 155
6.3.2 三角矩阵存储操作 157
6.3.3 三角矩阵转置操作 158
6.3.4 三角矩阵输出操作 159
6.4 对角矩阵 160
6.4.1 按对角线存储 161
6.4.2 按行存储 162
6.4.3 对角矩阵操作实现 164
6.5 稀疏矩阵压缩存储 165
6.5.1 稀疏矩阵定义 165
6.5.2 三元组表存储方法 166
6.5.3 十字链表存储方法 169
6.6 广义表 170
6.6.1 广义表的概念和基本操作 170
6.6.2 广义表的存储结构 171
6.6.3 广义表的基本操作实现 174
6.7 本章小结 176
6.8 习题 176
第7章 二叉树 179
7.1 二叉树的定义、性质和操作 179
7.1.1 二叉树的定义 179
7.1.2 二叉树的5种基本形态 180
7.1.3 二叉树的两种特殊形态 180
7.1.4 二叉树的几个特性 181
7.1.5 二叉树的基本操作 182
7.2 二叉树的存储 182
7.2.1 二叉树的顺序存储结构 182
7.2.2 二叉链表存储结构 183
7.2.3 三叉链表存储结构 184
7.2.4 双亲链表存储结构 185
7.2.5 二叉树基本操作的链式实现 186
7.3 二叉树的遍历 188
7.3.1 二叉树遍历的方法和结构 188
7.3.2 二叉链存储结构下二叉树遍历算法的实现 189
7.3.3 非递归的二叉树遍历算法 191
7.3.4 二叉树遍历的应用 194
7.4 线索二叉树 197
7.4.1 线索二叉树的定义 197
7.4.2 线索二叉树的结构 198
7.4.3 线索二叉树的操作 199
7.5 算法设计举例 202
7.5.1 问题描述 203
7.5.2 算法设计 203
7.5.3 算法实现 203
7.6 本章小结 205
7.7 习题 206
第8章 树 211
8.1 树的定义与术语 211
8.2 树的存储结构 212
8.2.1 双亲表示法 212
8.2.2 孩子表示法 213
8.2.3 孩子兄弟表示法 214
8.3 树、森林与二叉树的转换 216
8.3.1 树与二叉树的相互转换 216
8.3.2 森林与二叉树的相互转换 217
8.3.3 树、森林的遍历 218
8.4 哈夫曼树及其应用 219
8.4.1 哈夫曼树的定义 219
8.4.2 哈夫曼树的定义 220
8.4.3 最优前缀编码 221
8.4.4 哈夫曼编码算法的实现 223
8.5 树的典型例题 224
8.6 算法设计举例 227
8.6.1 哈夫曼编码、译码 227
8.6.2 完全二叉树的判断 229
8.7 本章小结 230
8.8 习题 230
第9章 图 233
9.1 图的定义和术语 233
9.1.1 无向图和有向图 234
9.1.2 子图 234
9.1.3 顶点的度 235
9.1.4 无向网和有向网 235
9.1.5 连通 236
9.1.6 图的基本操作 237
9.2 图的存储结构 237
9.2.1 邻接矩阵 238
9.2.2 邻接表 240
9.3 图的遍历 242
9.3.1 深度优先遍历 242
9.3.2 广度优先遍历 244
9.4 最小生成树 245
9.4.1 最小生成树的基本概念 246
9.4.2 普里姆算法 246
9.4.3 克鲁斯卡尔算法 249
9.5 最短路径 249
9.5.1 求某一顶点到其余各顶点的最短路径 250
9.5.2 求任意一对顶点之间的最短路径 252
9.6 关键路径 254
9.6.1 AOV网与拓扑排序 254
9.6.2 AOE网与关键路径 258
9.7 图的典型例题 263
9.8 算法设计举例 268
9.8.1 图的遍历 268
9.8.2 最小生成树 270
9.9 本章小结 271
9.10 习题 272
第10章 排序 277
10.1 基本概念 277
10.2 简单排序方法 278
10.2.1 插入排序——直接插入排序 278
10.2.2 折半插入排序 280
10.2.3 表插入排序 281
10.2.4 冒泡排序 283
10.2.5 选择排序 284
10.3 希尔排序 287
10.4 快速排序 288
10.5 堆排序 291
10.6 二路归并排序 293
10.7 基数排序 295
10.7.1 多关键码排序 296
10.7.2 链式基数排序 296
10.8 排序的典型例题 299
10.9 算法设计举例 302
10.9.1 简单插入排序 302
10.9.2 快速排序 303
10.10 本章小结 304
10.11 习题 304
第11章 查找 309
11.1 查找表 309
11.2 静态查找表 309
11.2.1 顺序查找 310
11.2.2 有序表的折半查找 311
11.2.3 分块查找 313
11.3 动态查找表——二叉排序树 314
11.3.1 二叉排序树查找过程 315
11.3.2 二叉排序树插入操作 315
11.3.3 二叉排序树删除操作 317
11.3.4 二叉排序树的查找分析 319
11.4 动态查找表——平衡二叉树 319
11.4.1 左单旋转 320
11.4.2 右单旋转 321
11.4.3 先左后右双向旋转 321
11.4.4 先右后左双向旋转 322
11.5 动态查找表——B-树和B＋树 326
11.5.1 B-树的定义 326
11.5.2 B-树的查找 326
11.5.3 B-树上插入结点 328
11.5.4 B-树上删除结点 330
11.5.5 B＋树 330
11.6 哈希表 331
11.6.1 哈希表与哈希方法 331
11.6.2 常用的哈希函数 332
11.6.3 处理冲突的方法 334
11.6.4 哈希表的查找分析 336
11.7 查找的典型例题 337
11.8 算法设计举例 338
11.8.1 构造二叉排序树 339
11.8.2 设计哈希表 342
11.9 本章小结 347
11.10 习题 347