第1章 绪论 1
1.1数据结构的概念 2
1.1.1引言 2
1.1.2数据结构有关概念与术语 4
1.2抽象数据类型 6
1.3算法描述与分析 7
1.3.1什么是算法 7
1.3.2算法分析技术初步 9
1.4基本的算法策略 12
1.4.1穷举法 12
1.4.2递推法与迭代法 13
1.4.3分治法 15
1.4.4贪婪算法 16
1.4.5动态规划 17
1.5案例分析 19
1.6小结 20
讨论小课堂1 21
习题1 22
第2章 线性表 24
2.1线性表的定义及其运算 24
2.1.1线性表的定义 24
2.1.2线性表的基本操作 25
2.2线性表的顺序存储结构及实现 26
2.2.1顺序存储结构 26
2.2.2线性表在向量中基本运算的实现 27
2.3线性表的链表存储结构 32
2.3.1单链表 32
2.3.2线性链表基本运算的实现 35
2.4循环链表和双向链表 41
2.4.1循环链表 41
2.4.2双向链表 42
2.4.3顺序存储结构与链表存储结构的综合分析与比较 43
2.5单链表的应用 44
2.5.1多项式相加的链表存储结构 44
2.5.2多项式相加的算法实现 45
2.6小结 46
讨论小课堂2 47
习题2 47
第3章 栈和队列 49
3.1栈 49
3.1.1栈的定义 49
3.1.2栈的基本操作 50
3.2栈的顺序存储结构及实现 51
3.2.1栈的顺序存储结构 51
3.2.2顺序栈的定义 52
3.3栈的链表存储结构及实现 54
3.4栈的应用 56
3.4.1表达式的计算 56
3.4.2子程序的嵌套调用 58
3.4.3递归调用 59
3.5队列 60
3.5.1队列的定义及运算 60
3.5.2队列的抽象数据类型描述 61
3.6队列的顺序存储结构及实现 61
3.7队列的链表存储结构及实现 64
3.8队列的应用 67
3.9算法实例——Hanoi塔问题 68
3.10小结 70
讨论小课堂3 70
习题3 71
第4章串 72
4.1串的基本概念 72
4.1.1串的定义 72
4.1.2串的基本操作 73
4.2串的存储与基本操作的实现 74
4.2.1定长顺序串 74
4.2.2堆串 75
4.2.3块链串 75
4.2.4串操作的实现 76
4.3串的模式匹配 80
4.3.1朴素模式匹配算法 80
4.3.2模式匹配的KMP算法 81
4.4串的应用举例：文本编辑 85
4.5小结 86
讨论小课堂4 87
习题4 87
第5章 数组和广义表 88
5.1数组 88
5.1.1数组的基本概念 88
5.1.2二维数组 89
5.1.3数组的顺序存储方式 89
5.2矩阵的压缩存储 90
5.2.1特殊矩阵 91
5.2.2稀疏矩阵 93
5.3广义表 98
5.3.1广义表的定义 98
5.3.2广义表的存储结构 99
5.4案例分析 101
5.4.1概述和方法 101
5.4.2算法和程序 103
5.5小结 105
讨论小课堂5 106
习题5 106
第6章 树与二叉树 108
6.1树、二叉树的概念及术语 108
6.1.1树的定义 108
6.1.2树的基本操作 110
6.1.3树的表示方式 110
6.1.4树的存储结构 111
6.2二叉树 112
6.2.1二叉树的定义 112
6.2.2二叉树的重要性质 112
6.2.3二叉树的存储结构 114
6.3二叉树的遍历 115
6.3.1先序遍历 116
6.3.2中序遍历 117
6.3.3后序遍历 117
6.3.4按层遍历 118
6.3.5非递归遍历算法 118
6.3.6二叉树的建立 121
6.3.7二叉树遍历的应用举例 122
6.4二叉树与树、森林的转换 123
6.4.1树与二叉树的转换 124
6.4.2森林与二叉树的转换 124
6.5树的遍历 126
6.5.1一般树的遍历 126
6.5.2森林的遍历 127
6.6二叉树的应用 128
6.6.1哈夫曼树 128
6.6.2哈夫曼树的构造 128
6.6.3哈夫曼树的实现算法 129
6.6.4哈夫曼编码 131
6.7小结 131
讨论小课堂6 132
习题6 132
第7章图 134
7.1图的基本概念 134
7.1.1图的定义 134
7.1.2图的术语 136
7.1.3图的基本操作 137
7.2图的存储结构 138
7.2.1图的邻接矩阵 138
7.2.2邻接矩阵表示法的C语言类型描述 139
7.2.3邻接矩阵表示下的基本操作的实现 140
7.2.4图的邻接链表 141
7.2.5图的邻接表表示法的C语言类型描述 143
7.2.6邻接表表示下基本操作的实现 144
7.3图的遍历与图的连通性 146
7.3.1图的深度优先遍历 146
7.3.2图的广度优先遍历 148
7.3.3非连通图和连通分量 150
7.4图的最小生成树 150
7.4.1最小生成树的基本概念 150
7.4.2普里姆（Prim）算法 151
7.4.3克鲁斯卡尔（Kruskal）算法 153
7.5最短路径 154
7.5.1从某顶点到其余各顶点的最短路径 155
7.5.2每对顶点之间的最短路径 157
7.6拓扑排序与关键路径 159
7.6.1拓扑排序 160
7.6.2关键路径 163
7.7图的应用 168
7.7.1图在路由器寻径中的应用 168
7.7.2图在物流信息系统中的应用 169
7.8小结 169
讨论小课堂7 170
习题7 170
第8章 查找 172
8.1查找的基本概念 172
8.2静态查找表 173
8.2.1顺序表的查找 173
8.2.2有序表的折半查找 174
8.2.3索引顺序表查找 177
8.3动态查找表 178
8.3.1二叉排序树 178
8.3.2平衡二叉树 184
8.4案例分析 191
8.4.1直方图问题 191
8.4.2箱子装载问题 192
8.5小结 194
讨论小课堂8 194
习题8 195
第9章 排序 196
9.1排序的基本概念 196
9.2插入排序 197
9.2.1直接插入排序 197
9.2.2折半插入排序 198
9.2.3希尔排序 198
9.3交换排序 200
9.3.1冒泡排序 200
9.3.2快速排序 201
9.4选择排序 204
9.4.1简单选择排序 204
9.4.2堆排序 205
9.5归并排序 208
9.6基数排序 210
9.7小结 213
讨论小课堂9 214
习题9 215
第10章 索引结构与散列 217
10.1静态索引结构 217
10.1.1索引表 217
10.1.2索引表查找 217
10.2动态索引结构（B一树和B+树） 219
10.2.1 B一树的定义 220
10.2.2 B一树的运算 221
10.2.3 B+树 223
10.3键树及Trie树 224
10.3.1键树的定义 224
10.3.2双链树 225
10.3.3 Trie树 226
10.4散列表及其查找 227
10.4.1哈希表与哈希函数 227
10.4.2构造哈希函数的常用方法 228
10.4.3解决冲突的主要方法 230
10.4.4哈希查找的性能分析 234
10.5小结 234
讨论小课堂10 235
习题10 235
附录 上机实验指导 238
第1部分 上机实验要求及规范 238
第2部分 实验部分 239
实验1复数ADT及其实现 239
实验2线性表 241
实验3栈和队列 248
实验4串 253
实验5数组 255
实验6树与二叉树 257
实验7图 261
实验8查找 265
实验9排序 267
实验10哈希查找 272
参考文献 275