第1章 绪论 1
1.1 数据结构的基本概念 1
1.1.1 数据结构的研究对象 1
1.1.2 数据结构的研究内容 2
1.1.3 数据结构的表示方法 5
1.2 算法与算法分析 6
1.2.1 算法的概念 6
1.2.2 算法的描述方法 6
1.2.3 算法分析 7
1.2.4 常用算法设计方法 8
1.3 数据结构和算法的学习与考试软件 9
1.3.1 教师端 9
1.3.2 学生端 12
习题 13
第2章 线性表 15
2.1 线性表的逻辑结构 15
2.1.1 线性表的引出 15
2.1.2 线性表的逻辑结构 16
2.1.3 线性表的运算 16
2.2 线性表的顺序存储结构——顺序表 17
2.2.1 顺序表的概念 17
2.2.2 顺序表的运算 18
2.2.3 顺序表的特点 22
2.3 线性表的链式存储结构——链表 22
2.3.1 链表的概念 22
2.3.2 链表的运算 23
2.4 循环链表和双向链表 30
2.4.1 循环链表 30
2.4.2 双向链表 31
习题 33
第3章 栈和队列 35
3.1 栈 35
3.1.1 栈的基本概念 35
3.1.2 栈的顺序存储结构——顺序栈 36
3.1.3 栈的链式存储结构——链栈 38
3.2 栈的应用 40
3.2.1 表达式求值 41
3.2.2 栈与递归 43
3.3 队列 45
3.3.1 队列的基本概念 45
3.3.2 队列的顺序存储结构——顺序队列 45
3.3.3 队列的链式存储结构——链式队列 48
3.3.4 循环队列 50
3.4 队列的应用 52
习题 53
第4章 字符串 55
4.1 字符串概述 55
4.2 字符串的存储结构 56
4.2.1 字符串的顺序存储结构 56
4.2.2 字符串的链式存储结构 56
4.3 字符串的运算 57
习题 63
第5章 数组和广义表 64
5.1 数组 64
5.1.1 多维数组的顺序存储 64
5.1.2 特殊矩阵的压缩存储 65
5.2 广义表 72
5.2.1 广义表的概念 72
5.2.2 广义表的存储 73
5.2.3 广义表的运算 75
习题 76
第6章 树和二叉树 78
6.1 树 78
6.1.1 树的基本概念 78
6.1.2 树的运算 80
6.2 二叉树 80
6.2.1 二叉树的基本概念 80
6.2.2 二叉树的性质 82
6.2.3 二叉树的存储结构 83
6.2.4 二叉树的运算 85
6.3 特殊的二叉树 89
6.3.1 线索二叉树 89
6.3.2 二叉排序树 92
6.3.3 最优二叉树 100
6.3.4 堆 104
6.4 树的存储结构与运算 109
6.4.1 树的存储结构 109
6.4.2 树的运算 111
6.5 森林 114
6.5.1 森林与二叉树的转换 114
6.5.2 森林的遍历 115
习题 115
第7章 图 116
7.1 概述 116
7.1.1 图的相关概念 116
7.1.2 图的连通性 117
7.1.3 图的基本操作 118
7.2 图的存储结构 119
7.2.1 图的邻接矩阵表示 119
7.2.2 图的邻接表表示 122
7.2.3 图的边集数组表示 129
7.2.4 图的十字链表表示 129
7.3 图的遍历 130
7.3.1 图的深度优先遍历 131
7.3.2 图的广度优先遍历 132
7.4 最小生成树 134
7.4.1 图的生成树 134
7.4.2 普里姆算法 134
7.4.3 克鲁斯卡尔算法 137
7.5 最短路径问题 140
7.5.1 单源最短路径 140
7.5.2 全源最短路径 142
7.6 有向无环图 145
7.6.1 拓扑排序 145
7.6.2 关键路径 147
习题 150
第8章 查找 152
8.1 线性查找表 152
8.1.1 顺序查找 152
8.1.2 折半查找 153
8.1.3 斐波那契查找 154
8.1.4 分块查找 156
8.2 二叉排序树 157
8.2.1 二叉排序树的查找性能 157
8.2.2 平衡二叉树 158
8.3 B－树 161
8.3.1 B－树的概念 161
8.3.2 B－树的查找 162
8.3.3 B－树的插入 162
8.3.4 B－树的删除 163
8.4 哈希查找 165
8.4.1 哈希表查找 165
8.4.2 哈希函数 166
8.4.3 冲突处理 168
8.4.4 哈希查找的性能 170
习题 171
第9章 排序 172
9.1 基本概念 172
9.2 简单排序方法 173
9.2.1 选择排序 173
9.2.2 插入排序 174
9.2.3 冒泡排序 177
9.3 快速排序 179
9.4 堆排序 181
9.5 归并排序 183
9.5.1 归并 183
9.5.2 归并排序过程 184
9.6 基数排序 185
9.7 内部排序算法性能比较 187
9.8 外部排序 188
习题 188
附录A 习题参考答案 189