本书结合作者多年教学实践，循序渐进地讲述了数据结构与算法的基本概念和知识。全书共分10章，分别讨论了数据结构与算法的基础知识和表示方式，基本线性结构（线性表、栈、队列、串、数组及广义表）、树形结构、图形结构等的定义、表示和实现，排序和查找的各种方法及其实现技巧，最后简要介绍了一些扩展数据结构以及算法设计方法。
　　本书可作为本科、专科院校计算机专业及相关专业的教材或教学参考书。

无

随着计算机科学技术的不断发展和应用领域的不断扩大，在许多非数值处理的应用问题中，计算机所面对的数据结构十分复杂、数据量巨大且形式多样，如何根据各类实际问题归纳、抽象出对象的数据特征及对象间的相互联系，从而选择合适的数据组织方法和存储方法，设计高效的求解算法，成为数据结构课程需要解决的最迫切的任务。
　　本书采用比较通俗、由浅入深和循序渐进的方式叙述了数据结构的知识。每当给出一个新的数据结构概念时，以流行的抽象数据类型（ADT）进行定义，而描述其对应的存储结构及基本操作算法时则使用C语言函数的形式，以便读者通过上机实验来理解和验证课程的具体内容和算法过程。
　　本书强调实用，注重理论指导下的实际可操作性，注重实际问题的解决。各章配有小结，目的在于引导读者复习该章内容；另外各章还设计了习题和实验课题，以期通过练习与实验提高学生的算法分析和设计的能力。
　　本书共分10章。第1章介绍数据结构和算法的基本概念，第2章、第3章和第4章介绍线性结构，第5章介绍树形结构，第6章介绍图形结构，第7章介绍排序方法，第8章介绍查找技术，第9章介绍算法设计方法，第10章介绍集合和一些扩展的数据结构。其中，前8章为数据结构课程的基本内容，不同的专业可根据需要选择讲解有关内容。另外，带“*”的章节为选学内容。
　　本书可作为本科、专科院校计算机科学与技术、信息管理与信息系统、计算机信息管理、计算机应用、软件工程、网络工程、电子商务等专业学生的教材或参考书。
　　参加本书编写的有邹永林（第1章、第2章、第10章），周蓓（第4章、第5章、第7章），唐晓阳（第3章、第6章、第8章），杨剑勇（第9章）；最后由邹永林完成本书的统稿工作。
　　由于作者水平有限，难免有缺点和欠妥之处，恳请读者指正。

作　　　者
2003年10月

第1章　　　概论　 1
11　　　引言　 1
111　　　几个例子　 1
112　　　数据结构的产生和发展　 3
113　　　基本概念和术语　 4
12　　　问题、算法和程序　 9
121　　　问题　 9
122　　　算法　 9
123　　　程序　 10
13　　　算法描述和分析　 10
131　　　算法描述　 10
132　　　算法分析　 12
14　　　小结　 15
习题　 15
第2章　　　线性表　 17
21　　　概述　 17
211　　　线性表的概念　 17
212　　　线性表的类型定义　 19
22　　　顺序表　 20
221　　　线性表的顺序表示　 20
222　　　顺序表的实现　 21
23　　　链表　 25
231　　　线性表的链式表示　 25
232　　　线性链表的实现　 25
233　　　循环链表的实现　 29
234　　　双向链表的实现　 30
235　　　静态链表的实现　 31
24　　　栈　 31
241　　　栈的类型定义　 31
242　　　顺序栈的表示和实现　 33
243　　　链栈的表示和实现　 34
25　　　队列　 36
251　　　队列的类型定义　 36
252　　　顺序队列的表示和实现　 37
253　　　链队的表示和实现　 39
26　　　应用举例　 41
27　　　小结　 44
习题　 44
第3章　　　串　 45
31　　　概述　 45
311　　　串的概念　 45
312　　　串的基本操作　 46
32　　　串的存储表示和操作算法　 47
321　　　定长顺序存储表示　 47
322　　　块链存储表示　 49
*323　　　堆分配存储表示　 50
33　　　模式匹配　 54
331　　　〖ZK（〗模式匹配的基本算法（BF算法）〖ZK）〗　 54
332　　　〖ZK（〗模式匹配的改进算法（KMP算法）〖ZK）〗　 56
34　　　应用举例　 59
341　　　文本编辑　 59
342　　　建立词索引表　 60
35　　　 小结　 62
习题　 62
第4章　　　数组和广义表　 65
41　　　数组的定义、表示和实现　 65
411　　　数组的定义　 65
412　　　数组的表示　 66
413　　　数组的实现　 67
42　　　矩阵的压缩存储　 69
421　　　特殊矩阵　 69
422　　　稀疏矩阵　 71
43　　　广义表的定义和表示　 78
431　　　广义表的定义　 78
432　　　广义表的存储结构　 79
433　　　广义表的基本算法　 81
44　　　小结　 84
习题　 84
第5章　　　树和二叉树　 87
51　　　树的定义和术语　 87
511　　　树的定义　 87
512　　　树的基本术语　 88
513　　　树的表示　 89
514　　　树的遍历　 90
52　　　二叉树　 90
521　　　二叉树的定义　 90
522　　　二叉树的重要性质　 91
523　　　二叉树的存储结构　 92
53　　　二叉树的遍历和线索二叉树　 94
531　　　二叉树的遍历　 94
532　　　线索二叉树　 96
54　　　树和森林　 100
541　　　树的存储结构　 100
542　　　森林与二叉树的转换　 102
543　　　森林的遍历　 103
55　　　哈夫曼树及其应用　 104
551　　　哈夫曼树　 104
552　　　〖ZK（〗哈夫曼树的应用——哈夫曼编码〖ZK）〗　 105
56　　　小结　 106
习题　 106
第6章　　　图　 109
61　　　图的基本概念　 109
611　　　图的定义　 109
612　　　基本术语　 110
62　　　图的表示和实现　 112
621　　　邻接矩阵　 112
622　　　邻接表　 114
623　　　十字链表　 116
624　　　邻接多重表　 117
63　　　图的遍历　 119
631　　　深度优先搜索　 119
632　　　广度优先搜索　 121
633　　　非连通图的遍历　 122
64　　　应用举例　 123
641　　　生成树　 123
642　　　拓扑排序　 128
643　　　关键路径　 132
644　　　最短路径　 137
65　　　小结　 140
习题　 140
第7章　　　排序　 143
71　　　内部排序　 144
711　　　简单排序　 144
712　　　希尔排序　 148
713　　　快速排序　 149
714　　　归并排序　 152
715　　　堆排序　 154
716　　　基数排序　 156
72　　　外部排序　 158
721　　　外部排序方法　 158
722　　　自然归并　 159
723　　　多路平衡归并　 160
724　　　置换 〖CD*2〗 选择排序　 161
725　　　最佳归并树　 163
73　　　排序效益评估　 164
74　　　小结　 164
习题　 164
第8章　　　查找　 167
81　　　基本概念　 167
811　　　查找的定义　 167
812　　　基本术语　 168
82　　　线性表的查找　 169
821　　　顺序查找　 169
822　　　二分查找　 170
823　　　分块查找　 173
83　　　树表的查找　 175
831　　　二叉排序树和平衡二叉树　 175
*832　　　B树　 187
*833　　　键树　 196
84　　　散列查找　 199
841　　　散列表　 199
842　　　散列函数的构造方法　 201
843　　　处理冲突的方法　 203
844　　　散列表的查找及分析　 206
85　　　小结　 209
习题　 209
*第〖BFQ〗9章　　　算法设计方法　 211
91　　　递归与分治法　 211
911　　　递归技术　 211
912　　　分治法　 214
92　　　回溯法　 217
921　　　回溯法的基本思想　 217
922　　　01背包问题　 217
923　　　旅行售货员问题　 219
924　　　n皇后问题　 220
93　　　动态规划法　 222
931　　　动态规划法的基本思想　 222
932　　　计算矩阵连乘积　 223
933　　　动态规划法的基本要素　 223
94　　　贪心法　 227
941　　　贪心法的基本思想　 227
942　　　哈夫曼编码问题　 227
943　　　贪心法与动态规划法的差异　 231
95　　　分支限界法　 232
951　　　分支限界法的基本思想　 232
952　　　01背包问题　 233
953　　　旅行售货员问题　 234
96　　　小结　 238
习题　 238
*第10章　　　高级专题　 239
101　　　集合　 239
1011　　　集合的定义　 239
1012　　　字典　 243
1013　　　有序字典　 248
1014　　　优先队列　 250
102　　　线性结构的扩展　 253
1021　　　自组织线性表　 253
1022　　　跳跃表　 254
1023　　　动态存储管理　 256
103　　　树形结构的扩展　 259
1031　　　竞赛树　 259
1032　　　Trie树　 260
1033　　　伸展树　 262
104　　　小结　 263
习题　 263
附录　　　数学预备知识　 265
参考文献　 269