第1章 绪论 1
【本章导读】 1
【本章目标】 1
1.1 数据结构的基本知识 1
1.1.1 数据结构的基本概念和术语 1
1.1.2 数据结构的常用结构 4
1.2 算法和算法分析 5
1.2.1 算法 5
1.2.2 算法的描述 5
1.2.3 算法评价 9
【实训】验证哥德巴赫猜想 10
本章小结 12
本章习题 12
第2章 线性表 14
【本章导读】 14
【本章目标】 14
2.1 线性表的逻辑结构 14
2.2 线性表的顺序存储结构 16
2.2.1 线性表的顺序存储结构 16
2.2.2 线性表在顺序存储结构下的运算 17
2.3 线性表的链式存储结构 21
2.3.1 线性链表 21
2.3.2 循环链表 29
2.3.3 双向链表 31
2.4 一元多项式的表示及相加 34
【实训1】顺序表的应用 37
【实训2】链表的应用 37
本章小结 38
本章习题 38
第3章 栈和队列 42
【本章导读】 42
【本章目标】 42
3.1 栈 42
3.1.1 栈的运算 43
3.1.2 栈的顺序存储结构 43
3.1.3 多栈共享邻接空间 45
3.1.4 栈的链式存储结构 47
3.2 算术表达式求值 49
3.2.1 算术四则运算的规则 49
3.2.2 表达式的计算过程 50
3.3 队列 54
3.3.1 队列的基本运算 55
3.3.2 队列的顺序存储结构 55
3.3.3 队列的链式存储结构 59
3.3.4 其他队列 61
【实训1】栈的应用 61
【实训2】队列的应用 62
本章小结 67
本章习题 67
第4章 串 70
【本章导读】 70
【本章目标】 70
4.1 串的基本知识 70
4.1.1 串的定义 70
4.1.2 主串和子串 71
4.2 串的存储结构 71
4.2.1 串值的存储 71
4.2.2 串名的存储映像 74
4.3 串的基本运算及其实现 74
4.3.1 串的基本运算 75
4.3.2 实现串的基本运算的方式 75
4.4 串的文本编辑 77
【实训】成绩管理系统 79
本章小结 88
本章习题 88
第5章 递归 90
【本章导读】 90
【本章目标】 90
5.1 递归的基本知识 90
5.1.1 递归的定义 90
5.1.2 采用递归方法应符合的条件 91
5.1.3 递归程序遵循的步骤 91
5.2 阶乘问题 92
5.3 背包问题 95
5.4 汉诺塔问题 100
【实训】迷宫问题 108
本章小结 116
本章习题 117
第6章 树 118
【本章导读】 118
【本章目标】 118
6.1 树的基本知识 118
6.1.1 树的相关术语 119
6.1.2 树的存储结构 120
6.1.3 树的基本操作 120
6.2 二叉树 121
6.2.1 二叉树的五种形态 121
6.2.2 二叉树的性质 122
6.2.3 二叉树的基本操作 123
6.2.4 二叉树的存储结构 125
6.2.5 树与二叉树的相互转换 127
6.3 遍历二叉树 128
6.3.1 先序遍历 129
6.3.2 中序遍历 129
6.3.3 后序遍历 130
6.3.4 层次遍历 130
6.3.5 遍历算法的应用 131
6.4 线索二叉树 133
6.4.1 中序次序线索化算法 135
6.4.2 在中根线索树上检索某节点的前驱算法 136
6.4.3 在中根线索树上检索某节点的后继算法 136
6.5 二叉排序树 137
6.5.1 二叉排序树的生成 137
6.5.2 删除二叉排序树上的节点 138
6.6 哈夫曼树 140
6.6.1 哈夫曼树的相关术语 140
6.6.2 构造哈夫曼树——哈夫曼算法 141
6.6.3 哈夫曼树的应用 142
【实训】哈夫曼编码应用 145
本章小结 148
本章习题 148
第7章 图 151
【本章导读】 151
【本章目标】 151
7.1 图的基本知识 151
7.1.1 图的概念 151
7.1.2 图的基本术语 152
7.2 图的存储结构 155
7.2.1 邻接矩阵 155
7.2.2 邻接表 157
7.3 最短路径 160
7.3.1 单源点最短路径 160
7.3.2 所有顶点之间的最短路径 164
7.4 最小生成树 166
7.5 拓扑排序 172
7.5.1 拓扑排序基本知识 172
7.5.2 实现拓扑排序步骤 173
7.6 图的遍历 174
7.6.1 深度优先遍历法 175
7.6.2 广度优先遍历法 178
【实训】无向图的遍历 180
本章小结 184
本章习题 184
第8章 查找 188
【本章导读】 188
【本章目标】 188
8.1 顺序查找 188
8.1.1 顺序查找的流程 188
8.1.2 顺序查找的实现 189
8.2 折半查找 190
8.2.1 折半查找的流程 190
8.2.2 折半查找的实现 191
8.3 分块查找 193
8.3.1 分块有序表的索引存储表示 193
8.3.2 分块查找的实现 194
8.4 哈希表 195
8.4.1 哈希表的基本知识 195
8.4.2 哈希函数的构造方法 197
8.4.3 冲突处理 199
【实训】学生成绩修改系统 204
本章小结 210
本章习题 210
第9章 排序 213
【本章导读】 213
【本章目标】 213
9.1 直接插入排序 213
9.1.1 线性插入排序 213
9.1.2 折半插入排序 215
9.2 希尔排序 217
9.3 简单选择排序 219
9.4 堆排序 221
9.5 快速排序 227
9.6 冒泡排序 230
9.7 归并排序 231
9.8 基数排序 234
9.9 排序方法的比较 239
【实训】排序系统 240
本章小结 248
本章习题 248
参考文献 251