数据结构教程习题解析与上机指导/黑新宏

**篇 习 题 解 析
第1章 绪论习题解析 2
第2章 线性表习题解析 8
第3章 栈和队列习题解析 16
第4章 串习题解析 26
第5章 数组与广义表习题解析 36
第6章 树与二叉树习题解析 48
第7章 图习题解析 69
第8章 查找习题解析 92
第9章 排序习题解析 111
第二篇 算法上机实现
第10章 线性表算法上机实现 132
10．1 顺序表基本运算 132
10．2 在表头插入生成单链表 134
10．3 在表尾插入生成单链表 135
10．4 单链表基本运算 136
10．5 双向链表基本运算 139
10．6 静态链表 142
10．7 例2．1算法实现 144
10．8 例2．2算法实现 145
10．9 例2．3算法实现 147
10．10 例2．4算法实现 148
10．11 例2．5算法实现 150
第11章 栈和队列算法上机实现 152
11．1 顺序栈基本运算 152
11．2 链栈基本运算 154
11．3 循环队列基本运算 157
11．4 链队列基本运算 158
11．5 例3．1算法实现 160
11．6 例3．5算法实现 163
第12章 串算法上机实现 166
12．1 顺序串基本运算 166
12．2 生成链串与求串长、串连接运算 168
12．3 链串中求子串运算 170
12．4 链串中串插入运算 171
12．5 串的简单模式匹配 173
12．6 串的无回溯KMP匹配 174
第13章 数组与广义表算法上机实现 177
13．1 矩阵转置 177
13．2 矩阵的快速转置 179
13．3 稀疏矩阵的十字链表存储 181
13．4 生成广义表及求广义表长度和深度的运算 184
第14章 树与二叉树算法上机实现 188
14．1 二叉树的遍历 188
14．2 二叉树的非递归遍历 190
14．3 另一种后序非递归遍历二叉树的方法 192
14．4 按层次遍历二叉树 194
14．5 由二叉树的遍历序列恢复二叉树 196
14．6 二叉树遍历的应用 198
14．7 中序线索二叉树 200
14．8 哈夫曼树及哈夫曼编码 203
14．9 例6．4算法实现 207
第15章 图算法上机实现 210
15．1 建立无向图的邻接矩阵 210
15．2 图的深度优先搜索 211
15．3 图的广度优先搜索 213
15．4 图的连通性 216
15．5 深度优先生成树 219
15．6 广度优先生成树 221
15．7 *小生成树的Prim算法 224
15．8 *小生成树的Kruskal算法 225
15．9 单源点*短路径的Dijkstra算法 227
15．10 每一对顶点间*短路径的Floyd算法 229
15．11 拓扑排序 231
15．12 关键路径 233
第16章 查找算法上机实现 239
16．1 顺序查找 239
16．2 折半（二分）查找 240
16．3 分块查找 241
16．4 二叉排序树建立、节点的查找和删除 242
16．5 平衡二叉树的建立、节点的查找和删除 246
16．6 哈希（Hash）查找 252
第17章 排序算法上机实现 256
17．1 插入排序 256
17．2 折半插入排序 257
17．3 希尔（Shell）排序 258
17．4 冒泡排序 259
17．5 双向冒泡排序 260
17．6 快速排序 262
17．7 选择排序 263
17．8 双向选择排序 264
17．9 堆排序 265
17．10 归并排序的递归算法实现 267
17．11 归并排序的非递归算法实现 268
17．12 基数排序 270
参考文献 273