目录 1
第1章 概论 1
1.1 基本概念 1
1.1.1 数据的有关概念 1
1.1.2 数据结构的有关概念 2
1.1.3 算法的有关概念 2
1.2 基本理论 3
1.2.1 数据结构的研究目的和研究内容 3
1.2.2 逻辑结构的4种基本形态及特点 3
1.2.3 引入抽象数据类型概念的好处 3
1.2.4 逻辑结构的特点及意义 4
1.2.5 算法的特征及设计要求 4
1.2.8 算法的分类 5
1.2.7 数据的存储方式 5
1.2.6 算法的计算量的含义及估算的方法 5
1.2.9 数据结构的评价和选择 6
1.3 典型例题 7
1.4 习题 16
第2章 线性表 21
2.1 基本概念 21
2.1.1 顺序线性表的有关概念 21
2.1.2 链式线性表的有关概念 21
2.2 基本理论 22
2.2.1 线性结构的基本特征 22
2.2.2 线性表的特点 22
2.2.3 线性表典型的基本运算 22
2.2.6 线性表的定位运算与算法 23
2.2.4 顺序表示法的基本思想和特点 23
2.2.5 单链表设置头结点的作用 23
2.2.7 单链表插入运算的算法实现 24
2.2.8 单链表的数据域和指针域的作用 24
2.2.9 循环链表和双链表的组织方法 25
2.2.10 线性表的插入运算与算法 25
2.2.11 线性表的删除运算与算法 26
2.2.12 顺序表的类C语言描述 27
2.2.13 单链表的类C语言描述 27
2.2.14 单链表定位运算的算法实现 27
2.2.15 单链表删除运算的算法实现 28
2.2.19 头指针、头结点、首结点的区别 29
2.2.18 链表的主要优点和缺点 29
2.2.17 顺序表的主要优缺点 29
2.2.16 双链表的组织方法和特点 29
2.2.20 线性表的索引存储结构及其优点 30
2.2.21 静态链表的用途和构造方法 30
2.3 典型例题 30
2.4 习题 52
第3章 栈和队列 58
3.1 基本概念 58
3.1.1 栈的有关概念 58
3.1.2 队列的有关概念 58
3.2 基本理论 59
3.2.1 栈的基本运算 59
3.2.2 栈的基本特点 59
3.2.3 顺序栈的组织方法 59
3.2.4 顺序栈上初始化的算法 60
3.2.6 链栈上实现进栈和退栈的算法 61
3.2.5 进栈和退栈运算在顺序栈上的实现算法 61
3.2.7 读栈顶元素的算法 62
3.2.8 判定栈是否为空的算法 63
3.2.9 取栈顶元素的算法 63
3.2.10 数组及其基本运算 63
3.2.11 递归及其特点 64
3.2.12 链队列的组织方法和语言描述 64
3.2.13 链队列上入队、出队的算法 65
3.2.14 循环队列上进行入队、出队的算法 66
3.2.15 循环队列的队满、队空条件 66
3.2.16 顺序队列上的“假溢出”及原因 67
3.2.18 顺序队列的组织方法 68
3.2.17 循环队列的组织方法 68
3.2.19 队列的特点及其基本运算 69
3.2.20 递归方法求解的条件 69
3.3 典型例题 70
3.4 习题 84
第4章 串 88
4.1 基本概念 88
4.2 基本理论 88
4.2.1 串的存储方法 89
4.2.2 串的顺序存储结构 89
4.2.3 顺序存储串的基本运算 89
4.2.4 串的链式存储的基本运算 92
4.3 典型例题 95
4.4 习题 107
第5章 数组与广义表 111
5.1 基本概念 111
5.1.1 数组的有关概念 111
5.1.2 广义表的有关概念 112
5.2 基本理论 112
5.2.1 数组的基本操作 112
5.2.2 数组的特点 113
5.2.3 数组的顺序储存表示 113
5.2.4 数组顺序存储的实现 113
5.2.5 二维数组的基本运算 114
5.2.6 二维数组的顺序存储方式 115
5.2.7 对称矩阵的压缩存储 116
5.2.8 稀疏矩阵的基本操作 116
5.2.9 稀疏矩阵的压缩存储方式 117
5.2.10 广义表的表示 119
5.2.11 广义表的存储结构和表示 119
5.2.12 广义表存储结构的特点 120
5.2.13 广义表的基本算法 120
5.3 典型例题 122
5.4 习题 140
第6章 树和二叉树 144
6.1 基本概念 144
6.1.1 树的基本术语 144
6.1.2 二叉树的有关概念 145
6.2 基本理论 145
6.2.1 树的含义 145
6.2.3 二叉树的基本运算 146
6.2.4 二叉树的性质 146
6.2.2 二叉树的5种基本形态 146
6.2.5 二叉树顺序存储的基本思想 147
6.2.6 二叉树遍历方法 147
6.2.7 二叉树的遍历算法 147
6.2.8 树的表示法 148
6.2.9 二叉树的逻辑结构及特点 149
6.2.10 二叉链表中结点及根指针的作用 149
6.2.11 树的存储结构 150
6.2.12 树的基本运算 151
6.2.13 二叉树的线索化 151
6.2.14 哈夫曼树的构造算法 151
6.2.16 哈夫曼编码 152
6.2.17 树与二叉树的关系 152
6.2.15 树的性质 152
6.2.18 二叉树的存储结构 153
6.2.19 使用线索二叉树的原因 154
6.2.20 线索二叉树的方法 154
6.2.21 二叉树的基本运算 154
6.2.22 树、森林与二叉树的转换 155
6.3 典型例题 156
6.4 习题 192
第7章 图 199
7.1 基本概念 199
7.2 基本理论 200
7.2.1 邻接矩阵的表示方法 200
7.2.2 邻接表的表示方法及特点 201
7.2.3 十字邻接表存储方法 202
7.2.5 非连通图中连通分量的求法 203
7.2.4 非连通图的遍历方法 203
7.2.7 网的邻接矩阵的建立方法 204
7.2.8 无向图的邻接表的建立方法 204
7.2.6 连通图深度和广度优先搜索的基本思想 204
7.2.9 有向图拓扑排序方法 . 205
7.2.10 拓扑排序的基本思想及算法 205
7.2.11 建立无向网络的算法 206
7.2.12 prim算法的基本思想 207
7.2.13 最小生成树的实际背景 207
7.2.14 邻接表的形式及建邻接表的算法 207
7.2.15 最小生成树的性质 208
7.2.16 求最小生成树需考虑的问题 209
7.2.17 构造最小生成树的方法 209
7.2.19 每对顶点之间的最短路径 210
7.2.18 求从某个源点到其余各项点的最短路径 210
7.2.20 求关键路径的计算过程 211
7.3 典型例题 212
7.4 习题 236
第8章 查找表 242
8.1 基本概念 242
8.2 基本理论 243
8.2.1 顺序查找的基本思想 243
8.2.2 顺序表查找的算法 244
8.2.3 折半查找的基本思想及特点 244
8.2.4 折半查找的算法 245
8.2.5 分块查找的基本思想及特点 245
8.2.6 分块查找的算法及时间与空间性能 245
8.2.7 二叉排序树的基本思想及算法 246
8.2.9 生成二叉排序树的算法 . 247
8.2.8 在二叉排序树上插入结点的算法 247
8.2.10 从二叉排序树上删除结点 248
8.2.11 平衡二叉树的方法 249
8.2.12 B-树的含义 249
8.2.13 B-树的查找 249
8.2.14 B-树的插入和生成 250
8.2.15 B-树的删除 250
8.2.16 B-树和B＋树的区别 251
8.2.17 B＋树查找、删除特点 251
8.2.18 哈希表的含义及特点 251
8.2.19 常用的构造哈希函数的方法 252
8.2.20 解决冲突的方法 252
8.2.22 链地址法的优缺点 254
8.2.21 哈希表的查找及算法 254
8.3 典型例题 255
8.4 习题 270
第9章 排序 274
9.1 基本概念 274
9.1.1 内部排序的有关概念 274
9.1.2 外部排序的有关概念 275
9.2 基本理论 275
9.2.1 直接插入排序的基本思想及算法 275
9.2.2 直接插入排序的时空性能 276
9.2.3 希尔排序的基本思想及算法 276
9.2.4 冒泡排序的基本思想及算法 277
9.2.5 快速排序的基本思想及算法 277
9.2.6 直接选择排序的基本思想及算法 278
9.2.7 堆排序的基本思想 279
9.2.8 堆排序的过程及算法 280
9.2.9 二路归并排序的基本思想 281
9.2.10 基数排序的基本思想及算法 282
9.2.11 各种内部排序方法的比较 283
9.2.12 外部排序的基本思想 283
9.2.13 归并排序的基本方法 284
9.2.14 置换-选择排序的基本思想 284
9.2.15 利用“败者树”实现置换选择排序 285
9.2.16 最佳归并树的构造 285
9.3 典型例题 285
9.4 习题 304
10.1 基本概念 309
第10章 文件 309
10.2 基本理论 310
10.2.1 文件的结构 310
10.2.2 文件的组织形式 310
10.2.3 顺序文件的组织形式及特点 311
10.2.4 文件的基本运算 311
10.2.5 散列文件的查找及特点 311
10.2.6 散列文件的结构和操作特点 312
10.2.7 多关键字文件的结构特点 312
10.2.8 顺序文件的检索方法 312
10.2.9 索引文件的组织特点 313
10.3 典型例题 313
10.4 习题 320
附录 习题答案 324