第一篇 数据结构基础 3
第1章 数据结构与算法分析基础 3
1.1 知识点概述 3
1.1.1 基本术语 3
1.1.2 算法和算法的量度 4
1.1.3 C＋＋相关知识 4
1.2 实验项目 5
1.2.1 熟悉Project组织应用程序实验 5
1.2.2 抽象数据类型的表示和实现实验 8
1.2.3 算法和算法分析实验 11
1.3 习题范例解析 14
1.4 习题 17
1.4.1 选择题 17
1.4.2 填空题 18
1.4.3 应用题 20
第2章 线性表 22
2.1 知识点概述 22
2.1.1 线性表的定义和抽象数据类型 22
2.1.2 线性表的顺序存储表示 23
2.1.3 线性表的链接存储表示 24
2.2 实验项目 26
2.2.1 线性表的顺序存储实验 26
2.2.2 线性表的链式存储实验 28
2.2.3 约瑟夫环的实现 29
2.3 习题范例解析 30
2.4 习题 32
2.4.1 选择题 32
2.4.2 填空题 34
2.4.3 应用题 35
2.4.4 算法设计题 36
第3章 栈和队列 45
3.1 知识点概述 45
3.1.1 栈 45
3.1.2 队列 47
3.2 实验项目 50
3.2.1 栈的顺序表示和实现实验 50
3.2.2 队列（循环队列）的表示和实现实验 51
3.2.3 栈与队列的应用实验 52
3.3 习题范例解析 53
3.4 习题 59
3.4.1 选择题 59
3.4.2 填空题 62
3.4.3 应用题 63
3.4.4 算法设计题 64
第4章 树 75
4.1 知识点概述 75
4.1.1 树的定义和基本概念 75
4.1.2 二叉树的定义和基本概念 76
4.1.3 二叉树的存储结构 78
4.1.4 二叉树的遍历 79
4.2 实验项目 80
4.2.1 二叉链表的基本操作实验 80
4.2.2 二叉链表的进一步操作实验 81
4.3 习题范例解析 83
4.4 习题 85
4.4.1 选择题 85
4.4.2 填空题 86
4.4.3 应用题 87
4.4.4 算法设计题 88
第5章 图 92
5.1 知识点概述 92
5.1.1 图的定义 92
5.1.2 图的基本术语 92
5.1.3 图的抽象数据类型 94
5.1.4 图的存储结构 94
5.1.5 图的遍历 97
5.2 实验项目 98
5.2.1 图的基本操作实验——邻接矩阵存储结构 98
5.2.2 图的基本操作实验——邻接表存储结构 99
5.3 习题范例解析 101
5.4 习题 102
5.4.1 选择题 102
5.4.2 填空题 103
5.4.3 应用题 104
5.4.4 算法设计题 105
第二篇 数据结构进阶 111
第6章 线性表和栈的应用 111
6.1 知识点概述 111
6.1.1 线性表的应用——多项式计算 111
6.1.2 栈的应用——算术表达式的计算 112
6.2 实验项目 114
6.2.1 线性表的应用——多项式计算实验 114
6.2.2 栈的应用——算术表达式的计算实验 116
6.3 习题范例解析 117
6.4 习题 118
6.4.1 选择题 118
6.4.2 填空题 119
6.4.3 应用题 120
6.4.4 算法设计题 121
第7章 稀疏矩阵和广义表 126
7.1 知识点概述 126
7.1.1 稀疏矩阵 126
7.1.2 广义表 129
7.2 实验项目 130
7.2.1 稀疏矩阵的顺序存储实验 130
7.2.2 稀疏矩阵的链接存储实验 131
7.2.3 广义表运算实验 133
7.3 习题范例解析 134
7.4 习题 135
7.4.1 选择题 135
7.4.2 填空题 136
7.4.3 应用题 136
7.4.4 算法设计题 137
第8章 特殊二叉树 142
8.1 知识点概述 142
8.1.1 二叉搜索树 142
8.1.2 堆 145
8.1.3 哈夫曼树 147
8.2 实验项目 149
8.2.1 二叉搜索树的基本操作实现 149
8.2.2 堆的基本操作实现 150
8.2.3 哈夫曼树及其应用实验 151
8.3 习题范例解析 152
8.4 习题 153
8.4.1 选择题 153
8.4.2 应用题 155
8.4.3 算法设计题 160
第9章 图的应用 163
9.1 知识点概述 163
9.1.1 最小生成树 163
9.1.2 最短路径 165
9.1.3 拓扑排序 167
9.2 实验项目 168
9.2.1 图的最小生成树实验 168
9.2.2 图的最短路径实验 170
9.2.3 图的拓扑排序实验 173
9.3 习题范例解析 175
9.4 习题 179
9.4.1 选择题 179
9.4.2 填空题 180
9.4.3 应用题 181
9.4.4 算法设计题 183
第10章 查找 188
10.1 知识点概述 188
10.1.1 查找的概念 188
10.1.2 顺序查找 188
10.1.3 二分查找 189
10.1.4 索引查找 189
10.1.5 散列查找 190
10.2 实验项目 193
10.2.1 索引查找的实现 193
10.2.2 散列查找的实现 195
10.3 习题范例解析 197
10.4 习题 199
10.4.1 选择题 199
10.4.2 填空题 201
10.4.3 应用题 201
10.4.4 算法设计题 202
第11章 排序 206
11.1 知识点概述 206
11.1.1 排序的基本概念 206
11.1.2 插入排序 206
11.1.3 选择排序 207
11.1.4 交换排序 208
11.1.5 归并排序 209
11.1.6 内排序方法比较 210
11.2 实验项目 210
11.2.1 排序算法的应用（一） 210
11.2.2 排序算法的应用（二） 212
11.3 习题范例解析 213
11.4 习题 215
11.4.1 选择题 215
11.4.2 填空题 217
11.4.3 应用题 218
11.4.4 算法设计题 219
附录 实验报告格式 223
主要参考文献 224