本书结合作者多年教学实践,循序渐进地讲述了数据结构与算法的基本概念和知识。全书共分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
11 引言 1
111 几个例子 1
112 数据结构的产生和发展 3
113 基本概念和术语 4
12 问题、算法和程序 9
121 问题 9
122 算法 9
123 程序 10
13 算法描述和分析 10
131 算法描述 10
132 算法分析 12
14 小结 15
习题 15
第2章 线性表 17
21 概述 17
211 线性表的概念 17
212 线性表的类型定义 19
22 顺序表 20
221 线性表的顺序表示 20
222 顺序表的实现 21
23 链表 25
231 线性表的链式表示 25
232 线性链表的实现 25
233 循环链表的实现 29
234 双向链表的实现 30
235 静态链表的实现 31
24 栈 31
241 栈的类型定义 31
242 顺序栈的表示和实现 33
243 链栈的表示和实现 34
25 队列 36
251 队列的类型定义 36
252 顺序队列的表示和实现 37
253 链队的表示和实现 39
26 应用举例 41
27 小结 44
习题 44
第3章 串 45
31 概述 45
311 串的概念 45
312 串的基本操作 46
32 串的存储表示和操作算法 47
321 定长顺序存储表示 47
322 块链存储表示 49
*323 堆分配存储表示 50
33 模式匹配 54
331 〖ZK(〗模式匹配的基本算法(BF算法)〖ZK)〗 54
332 〖ZK(〗模式匹配的改进算法(KMP算法)〖ZK)〗 56
34 应用举例 59
341 文本编辑 59
342 建立词索引表 60
35 小结 62
习题 62
第4章 数组和广义表 65
41 数组的定义、表示和实现 65
411 数组的定义 65
412 数组的表示 66
413 数组的实现 67
42 矩阵的压缩存储 69
421 特殊矩阵 69
422 稀疏矩阵 71
43 广义表的定义和表示 78
431 广义表的定义 78
432 广义表的存储结构 79
433 广义表的基本算法 81
44 小结 84
习题 84
第5章 树和二叉树 87
51 树的定义和术语 87
511 树的定义 87
512 树的基本术语 88
513 树的表示 89
514 树的遍历 90
52 二叉树 90
521 二叉树的定义 90
522 二叉树的重要性质 91
523 二叉树的存储结构 92
53 二叉树的遍历和线索二叉树 94
531 二叉树的遍历 94
532 线索二叉树 96
54 树和森林 100
541 树的存储结构 100
542 森林与二叉树的转换 102
543 森林的遍历 103
55 哈夫曼树及其应用 104
551 哈夫曼树 104
552 〖ZK(〗哈夫曼树的应用——哈夫曼编码〖ZK)〗 105
56 小结 106
习题 106
第6章 图 109
61 图的基本概念 109
611 图的定义 109
612 基本术语 110
62 图的表示和实现 112
621 邻接矩阵 112
622 邻接表 114
623 十字链表 116
624 邻接多重表 117
63 图的遍历 119
631 深度优先搜索 119
632 广度优先搜索 121
633 非连通图的遍历 122
64 应用举例 123
641 生成树 123
642 拓扑排序 128
643 关键路径 132
644 最短路径 137
65 小结 140
习题 140
第7章 排序 143
71 内部排序 144
711 简单排序 144
712 希尔排序 148
713 快速排序 149
714 归并排序 152
715 堆排序 154
716 基数排序 156
72 外部排序 158
721 外部排序方法 158
722 自然归并 159
723 多路平衡归并 160
724 置换 〖CD*2〗 选择排序 161
725 最佳归并树 163
73 排序效益评估 164
74 小结 164
习题 164
第8章 查找 167
81 基本概念 167
811 查找的定义 167
812 基本术语 168
82 线性表的查找 169
821 顺序查找 169
822 二分查找 170
823 分块查找 173
83 树表的查找 175
831 二叉排序树和平衡二叉树 175
*832 B树 187
*833 键树 196
84 散列查找 199
841 散列表 199
842 散列函数的构造方法 201
843 处理冲突的方法 203
844 散列表的查找及分析 206
85 小结 209
习题 209
*第〖BFQ〗9章 算法设计方法 211
91 递归与分治法 211
911 递归技术 211
912 分治法 214
92 回溯法 217
921 回溯法的基本思想 217
922 01背包问题 217
923 旅行售货员问题 219
924 n皇后问题 220
93 动态规划法 222
931 动态规划法的基本思想 222
932 计算矩阵连乘积 223
933 动态规划法的基本要素 223
94 贪心法 227
941 贪心法的基本思想 227
942 哈夫曼编码问题 227
943 贪心法与动态规划法的差异 231
95 分支限界法 232
951 分支限界法的基本思想 232
952 01背包问题 233
953 旅行售货员问题 234
96 小结 238
习题 238
*第10章 高级专题 239
101 集合 239
1011 集合的定义 239
1012 字典 243
1013 有序字典 248
1014 优先队列 250
102 线性结构的扩展 253
1021 自组织线性表 253
1022 跳跃表 254
1023 动态存储管理 256
103 树形结构的扩展 259
1031 竞赛树 259
1032 Trie树 260
1033 伸展树 262
104 小结 263
习题 263
附录 数学预备知识 265
参考文献 269