1.1 数据结构的概念及分类 1
1.1.1 数据与数据结构 1
第1章 绪论 1
1.1.2 数据结构的分类 2
1.2 抽象数据类型 4
1.2.1 数据类型 4
1.2.2 数据抽象与抽象数据类型 5
1.2.3 用于描述数据结构的语言 6
1.3 算法定义 6
1.4 算法性能分析与度量 7
1.4.2 算法的后期测试 8
1.4.1 算法的性能标准 8
1.4.3 算法的事前估计 9
1.4.4 渐进的时间复杂度 12
1.4.5 渐进的空间复杂度 15
本章小结 16
实验1 程序的执行时间 17
习题 18
第2章 线性表 20
2.1 线性表实例及概念 20
2.2.1 线性表的顺序存储结构 21
2.2 线性表的存储方式 21
2.2.2 线性表的链式存储结构 23
2.3 线性表的有关操作 26
2.3.1 顺序表的操作实现 26
2.3.2 单链表的操作实现 30
2.3.3 双向循环链表的操作实现 34
2.4 线性表的ADT定义 37
2.5 线性表的应用——多项式相加问题 38
2.5.1 存储结构的选取 38
2.5.2 一元多项加法运算的实现 38
本章小结 39
实验2 线性表的综合运算 42
习题 45
第3章 栈 48
3.1 栈的应用实例及概念 48
3.2 栈的存储方式 49
3.2.1 栈的顺序存储结构 49
3.2.2 栈的链式存储结构 51
3.3 栈的有关操作 51
3.3.1 顺序栈的操作实现 51
3.3.2 链栈的操作实现 53
3.4 栈的ADT定义 54
3.5 栈的应用实例——算术表达式的求值 55
3.5.1 表达式的构成 55
3.5.2 运算符的优先关系 55
3.5.3 算法思路 56
本章小结 57
实验3 栈的操作 58
习题 60
4.1 队列的应用实例及概念 62
第4章 队列 62
4.2 队列的存储方式 63
4.2.1 队列的链式存储结构 63
4.2.2 队列的顺序存储结构 65
4.3 队列的有关操作 68
4.3.1 循环队列的操作实现 68
4.3.2 链队列的操作实现 70
4.4 队列的ADT定义 73
4.5 顺序循环队列的应用 74
本章小结 75
实验4 队列的操作 76
习题 79
5.1 串的应用实例及基本概念 82
第5章 串 82
5.2 串的存储结构 83
5.2.1 串的顺序存储 83
5.2.2 串的链式存储 84
5.3 串运算的实现 85
5.4 串的ADT定义 93
本章小结 94
实验5 串的操作 95
习题 98
6.1 二维数组应用实例及概念 100
第6章 数组 100
6.2 数组的顺序存储和实现 101
6.2.1 数组的顺序存储 101
6.2.2 数组的实现 102
6.3 特殊矩阵的压缩存储 104
6.3.1 三角矩阵 105
6.3.2 稀疏矩阵 106
6.4 数组应用实例 111
本章小结 113
实验6 数组的定义与实现 114
习题 116
第7章 树 117
7.1 树的实例和基本概念 117
7.1.1 树的实例 117
7.1.2 树的基本概念 118
7.1.3 树的常用术语 119
7.1.4 树的表示方法 120
7.2 二叉树 120
7.2.1 二叉树的定义 120
7.2.2 二叉树的重要性质 121
7.2.3 二叉树的存储结构 122
7.2.4 二叉树二叉链表的一个生成算法 124
7.3 二叉树的遍历 125
7.3.1 二叉树遍历的定义 125
7.3.2 遍历的递归方法 125
7.3.3 二叉树遍历的非递归实现 127
7.4 二叉树其他运算的实现 130
7.5 线索二叉树 131
7.5.1 线索二叉树的基本概念 131
7.5.2 线索二叉树的逻辑表示图 133
7.5.3 中序线索化算法 133
7.5.4 在中序线索树上检索某结点的前驱或后继 134
7.5.5 在中序线索树上遍历二叉树 135
7.6 树与森林 135
7.6.1 树的存储结构 135
7.6.2 树、森林和二叉树的转换 137
7.6.3 一般树或森林的遍历 139
7.7 哈夫曼树及其应用 140
7.7.1 哈夫曼树的基本概念 140
7.7.2 哈夫曼树的构造及其算法 141
7.7.3 哈夫曼树的应用 143
7.8 二叉树的ADT定义 145
本章小结 146
实验7 二叉树的建立与遍历 148
习题 150
第8章 图 153
8.1 图的实例及概念 153
8.1.1 实例 154
8.1.2 图的定义和基本概念 154
8.2 图的存储结构及实现 157
8.2.1 邻接矩阵 157
8.2.2 邻接链表 164
8.3 遍历图 172
8.2.3 图的ADT定义 172
8.3.1 深度优先遍历 173
8.3.2 广度优先遍历 174
8.4 最小生成树 176
8.4.1 最小生成树的基本概念 176
8.4.2 普里姆算法 177
8.4.3 克鲁斯卡尔算法 180
8.5 最短路径 181
8.5.1 从某个源点到其他各项点的最短路径 182
8.5.2 求每一对顶点之间的最短路径 185
本章小结 187
实验8 图的基本算法实现 190
习题 193
第9章 排序 197
9.1 排序的基本概念 197
9.2 插入排序 198
9.2.1 直接插入排序 198
9.2.2 希尔排序 200
9.3 交换排序 201
9.3.1 冒泡排序 201
9.3.2 快速排序 203
9.4.2 堆排序 205
9.4 选择排序 205
9.4.1 直接选择排序 205
本章小结 210
实验9 各种排序方法实现 211
习题 212
第10章 查找 214
10.1 静态查找表 214
10.1.1 无序顺序表的查找 214
10.1.2 有序顺序表的查找 216
10.1.3 索引顺序表的查找 218
10.2 动态查找表 220
10.2.1 二叉排序树 221
10.2.2 平衡二叉树 225
10.3 哈希表及其查找 226
10.3.1 哈希表与哈希函数 226
10.3.2 构造哈希函数的常用方法 227
10.3.3 解决冲突的主要方法 228
本章小结 230
实验10 查找方法实现 230
习题 233
参考文献 235