第1章 绪论 1
1.1 重点难点 1
1.2 主要内容 1
1.2.1 数据的逻辑结构 1
1.2.2 数据结构的存储实现 2
1.2.3 算法分析 2
1.3 习题解答 4
1.3.1 简答题 4
1.3.2 程序设计题 6
1.4 进一步拓展 8
1.4.1 最大公因子问题 8
1.4.2 递归函数的时间复杂度的计算 10
第2章 线性表 11
2.1 重点难点 11
2.2 主要内容 11
2.2.1 线性表的定义及基本运算 11
2.2.2 线性表的顺序实现 12
2.2.3 线性表的链接实现 15
2.3 习题解答 19
2.3.1 简答题 19
2.3.2 程序设计题 21
2.4 进一步拓展 47
2.4.1 字符串的存储与匹配 48
2.4.2 模拟动态内存分配 52
第3章 栈 57
3.1 重点难点 57
3.2 主要内容 57
3.2.1 栈的基本概念 57
3.2.2 栈的顺序实现 58
3.2.3 栈的链接实现 60
3.3 习题解答 62
3.3.1 简答题 62
3.3.2 程序设计题 63
3.4 进一步拓展 77
3.4.1 基于线性表的栈的实现 78
3.4.2 迷宫问题 79
第4章 队列 82
4.1 重点难点 82
4.2 主要内容 82
4.2.1 队列的概念 82
4.2.2 队列的顺序实现 83
4.2.3 队列的链接实现 85
4.3 习题解答 88
4.3.1 简答题 88
4.3.2 程序设计题 89
4.4 进一步拓展 96
4.4.1 迷宫问题 96
4.4.2 火车车厢重排 100
第5章 树 104
5.1 重点难点 104
5.2 主要内容 104
5.2.1 树的定义和基本概念 104
5.2.2 二叉树的基本概念 105
5.2.3 二叉树的顺序实现 107
5.2.4 二叉树的链接实现 107
5.2.5 二叉树遍历的非递归实现 112
5.2.6 哈夫曼树和哈夫曼编码 114
5.2.7 树、森林和二叉树 117
5.3 习题解答 118
5.3.1 简答题 118
5.3.2 程序设计题 122
5.4 进一步拓展 145
5.4.1 中序线索树 145
5.4.2 中序线索树的存储 145
5.4.3 构造中序穿线 147
5.4.4 遍历二叉线索树 148
第6章 优先级队列 150
6.1 重点难点 150
6.2 主要内容 150
6.2.1 优先级队列的概念 150
6.2.2 二叉堆 151
6.2.3 贝努里队列 155
6.3 习题解答 156
6.3.1 简答题 156
6.3.2 程序设计题 159
6.4 进一步拓展 182
6.4.1 双端队列 182
6.4.2 最小语言集 189
第7章 集合与静态查找表 193
7.1 重点难点 193
7.2 主要内容 193
7.2.1 集合的基本概念 193
7.2.2 查找及静态查找表 193
7.2.3 无序表的查找 194
7.2.4 有序表的查找 194
7.3 习题解答 196
7.3.1 简答题 196
7.3.2 程序设计题 198
第8章 查找树 209
8.1 重点难点 209
8.2 主要内容 209
8.2.1 二叉查找树 209
8.2.2 AVL树 212
8.2.3 红黑树 219
8.2.4 伸展树 223
8.2.5 B＋树 224
8.3 习题解答 225
8.3.1 简答题 225
8.3.2 程序设计题 232
8.4 进一步拓展 261
8.4.1 线段树 261
8.4.2 道路问题 261
第9章 散列表 265
9.1 重点难点 265
9.2 主要内容 265
9.2.1 散列函数 265
9.2.2 碰撞的解决 266
9.3 习题解答 275
9.3.1 简答题 275
9.3.2 程序设计题 276
9.4 进一步拓展 287
第10章 排序 289
10.1 重点难点 289
10.2 主要内容 289
10.2.1 基本概念 289
10.2.2 插入排序 289
10.2.3 选择排序 291
10.2.4 交换排序 293
10.2.5 归并排序 296
10.2.6 外排序 297
10.3 习题解答 299
10.3.1 简答题 299
10.3.2 程序设计题 304
10.4 进一步拓展 315
10.4.1 基数排序的思想 315
10.4.2 基数排序的实现 315
10.4.3 基数排序的性能 317
第11章 不相交集 318
11.1 重点难点 318
11.2 主要内容 318
11.2.1 不相交集的定义 318
11.2.2 不相交集的实现 318
11.3 习题解答 321
11.3.1 简答题 321
11.3.2 程序设计题 323
11.4 进一步拓展 331
第12章 图 333
12.1 重点难点 333
12.2 主要内容 333
12.2.1 图的定义及术语 333
12.2.2 图的存储 335
12.2.3 图的遍历 342
12.3 习题解答 345
12.3.1 简答题 345
12.3.2 程序设计题 349
12.4 进一步拓展 371
12.4.1 逆邻接表 371
12.4.2 十字链表 372
12.4.3 邻接多重表 373
第13章 最小生成树 375
13.1 重点难点 375
13.2 主要内容 375
13.2.1 Kruskal算法 375
13.2.2 Prim算法 377
13.3 习题解答 380
13.3.1 简答题 380
13.3.2 程序发计题 381
13.4 进一步拓展 385
第14章 最短路径问题 387
14.1 重点难点 387
14.2 主要内容 387
14.2.1 单源最短路径 387
14.2.2 所有结点对的最短路径 391
14.3 习题解答 394
14.3.1 简答题 394
14.3.2 程序设计题 398
第15章 算法设计基础 406
15.1 重点难点 406
15.2 主要内容 406
15.2.1 枚举法 406
15.2.2 贪婪法 406
15.2.3 分治法 407
15.2.4 动态规划 407
15.2.5 回溯法 408
15.2.6 随机算法 408
15.3 习题解答 408
15.3.1 简答题 408
15.3.2 程序设计题 411
参考文献 438