第1章 绪论 1
1.1 数据结构的基本概念 1
1.1.1 学习数据结构的意义 1
1.1.2 有关概念和术语 3
1.2 数据类型和抽象数据类型 5
1.2.1 数据类型 6
1.2.2 抽象数据类型 6
1.3 算法和算法分析 6
1.3.1 算法的概念和特性 7
1.3.2 算法的描述 7
1.3.3 算法的效率分析 8
本章小结 9
习题1 9
第2章 线性表 10
2.1 线性表的基本概念 10
2.1.1 线性表的逻辑结构 10
2.1.2 线性表的运算 11
2.2 线性表的顺序存储结构 11
2.2.1 顺序表结构 11
2.2.2 顺序表上实现的基本操作 12
2.3 线性表的链式存储结构 16
2.3.1 单链表结构 16
2.3.2 单链表的基本运算 18
2.3.3 循环链表 21
2.3.4 双向链表 22
本章小结 24
习题2 25
第3章 栈和队列 28
3.1 栈 28
3.1.1 栈的定义及基本运算 28
3.1.2 栈的存储实现和运算实现 29
3.2 栈的应用举例 32
3.3 队列 37
3.3.1 使用数组结构创建队列 38
3.3.2 循环队列 42
3.3.3 使用链表创建队列 45
本章小结 51
习题3 51
第4章 字符串 53
4.1 字符串及其基本运算 53
4.1.1 字符串的基本概念 53
4.1.2 字符串的基本运算 54
4.2 字符串的定长顺序存储及基本运算 55
4.2.1 字符串的定长顺序存储 55
4.2.2 定长顺序字符串的基本运算 56
4.2.3 模式匹配 57
4.3 字符串的堆存储结构 62
4.3.1 字符串名的存储映象 62
4.3.2 堆存储结构 63
4.3.3 基于堆结构的基本运算 63
本章小结 65
习题4 65
第5章 数组和广义表 67
5.1 多维数组 67
5.2 数组的顺序存储结构 68
5.2.1 行顺序优先 68
5.2.2 列优先顺序 70
5.3 矩阵的压缩存储 71
5.3.1 特殊矩阵 71
5.3.2 压缩存储 72
5.3.3 稀疏矩阵 74
5.4 广义表 76
5.4.1 基本概念 76
5.4.2 存储结构 77
5.4.3 基本运算 78
本章小结 79
习题5 79
第6章 树 82
6.1 树 82
6.1.1 树的定义 82
6.1.2 基本术语 84
6.1.3 树的基本运算 85
6.2 二叉树 85
6.2.1 二叉树的定义 86
6.2.2 二叉树的性质 87
6.2.3 二叉树的存储结构 90
6.3 遍历二叉树 91
6.3.1 二叉树遍历的递归算法 92
6.3.2 二叉树遍历的非递归算法 93
6.3.3 二叉树算法举例 96
6.4 线索二叉树 98
6.4.1 线索的概念及描述 98
6.4.2 线索的画法 99
6.4.3 线索的算法实现 99
6.4.4 线索二叉树的运算 101
6.5 树和森林 104
6.5.1 树的存储结构 104
6.5.2 树、森林与二叉树的转换 106
6.5.3 树和森林的遍历 109
6.6 哈夫曼树及其应用 110
6.6.1 基本术语 110
6.6.2 哈夫曼树的构造 111
6.6.3 构造哈夫曼树的算法实现 111
6.6.4 哈夫曼编码 113
本章小结 115
习题6 115
第7章 图 119
7.1 图的基本概念 119
7.1.1 图的定义 119
7.1.2 图的基本术语 120
7.2 图的存储结构 122
7.2.1 邻接矩阵 122
7.2.2 邻接表 125
7.3 图的遍历 129
7.3.1 深度优先搜索遍历 130
7.3.2 广度优先搜索遍历 132
7.4 生成树和最小生成树 134
7.4.1 生成树 134
7.4.2 最小生成树 134
7.5 最短路径 138
7.5.1 单源点最短路径 138
7.5.2 所有顶点之间的最短路径 140
本章小结 141
习题7 141
第8章 查找 147
8.1 基本概念 147
8.2 线性表的查找 148
8.2.1 顺序查找 148
8.2.2 二分查找 149
8.2.3 索引查找 151
8.2.4 分块查找 155
8.3 树型查找 156
8.4 散列查找 158
8.4.1 基本概念 159
8.4.2 散列函数的构造方法 160
8.4.3 冲突处理方法 162
8.4.4 散列查找及分析 164
本章小结 164
习题8 165
第9章 排序 168
9.1 基本概念 168
9.2 插入排序 169
9.2.1 直接插入排序 169
9.2.2 二分插入排序 172
9.2.3 希尔排序 173
9.3 交换排序 175
9.3.1 冒泡排序 175
9.3.2 快速排序 176
9.4 选择排序 179
9.4.1 直接选择排序 179
9.4.2 树形选择排序 180
9.5 归并排序 181
9.5.1 二路归并排序 181
9.5.2 多路归并排序 183
9.6 各种内排序方法的比较和选择 183
9.6.1 各种内排序方法的比较 183
9.6.2 各种内排序方法的选择 184
本章小结 184
习题9 185
第10章 实训 188
实训1 线性表的顺序存储结构 188
一、实训目的 188
二、实训内容 188
三、实训要求 188
四、实训学时：2学时 188
五、实训步骤 188
六、选作实训 188
实训2 链式存储结构（一）——单向链表的有关操作 189
一、实训目的 189
二、实训内容 189
三、实训要求 189
四、实训学时：2学时 189
五、实训步骤 189
六、选作实训 189
实训3 链式存储结构（二）——双向链表的有关操作 189
一、实训目的 189
二、实训内容 190
三、实训要求 190
四、实训学时：2学时 190
五、实训步骤 190
实训4 栈、队列 190
一、实训目的 190
二、实训内容 190
三、实训要求 191
四、实训学时：2学时 191
五、实训步骤 191
六、选作实训 191
实训5 多维数组 191
一、实训目的 191
二、实训内容 192
三、实训要求 192
四、实训学时：2学时 192
五、实训步骤 192
六、选作实训 192
实训6 二叉树的操作 192
一、实训目的 192
二、实训内容 192
三、实训要求 192
四、实训学时：4学时 193
五、实训步骤 193
六、选作实训 193
实训7 图的遍历操作 193
一、实训目的 193
二、实训内容 193
三、实训要求 193
四、实训学时：4学时 193
五、实训步骤 193
实训8 查找 194
一、实训目的 194
二、实训内容 194
三、实训要求 194
四、实训学时：6学时 194
五、实训步骤 194
实训9 排序 194
一、实训目的 194
二、实训内容 194
三、实训要求 194
四、实训学时：6学时 195
五、实训步骤 195
六、选作实训 195
实训10 综合实训 195
一、实训目的 195
二、实训内容 195
三、实训要求 195
四、实训学时：6学时 196
五、实训步骤 196
参考文献 197