第1章 概论 1
1.1数据结构基本概念 1
1.1.1数据结构的定义 1
1.1.2有关术语 3
1.2数据的逻辑结构 4
1.3数据的存储结构 6
1.4数据的运算 8
1.5数据算法的评估 9
1.5.1算法的描述 9
1.5.2算法的设计要求 11
1.5.3算法的性能评估 13
1.6小结 15
1.7习题 16
第2章 线性表 18
2.1线性表的基本概念 18
2.1.1线性表的定义及特点 18
2.1.2线性表的基本操作 19
2.2线性表的顺序存储结构 20
2.2.1顺序存储的定义 20
2.2.2顺序存储的算法实现 21
2.3线性表的链式存储结构 26
2.3.1线性链表 27
2.3.2循环链表 32
2.3.3双向链表 33
2.4线性表的应用——多项式的相加 35
2.5小结 39
2.6习题 39
第3章 栈与队列 41
3.1栈 41
3.1.1栈的定义 41
3.1.2栈的基本操作 42
3.1.3栈的存储结构及描述 42
3.1.4栈的应用 45
3.2队列 49
3.2.1队列的定义 49
3.2.2队列的基本操作 50
3.2.3队列的存储结构 50
3.3小结 56
3.4习题 57
第4章 串 58
4.1串的基本概念 58
4.1.1串的定义 58
4.1.2串的基本操作 59
4.2串的存储结构 60
4.2.1顺序存储 60
4.2.2链式存储 61
4.2.3索引存储 63
4.3串的运算及实现 64
4.3.1静态顺序存储串的操作 64
4.3.2动态顺序存储串的操作 68
4.4小结 71
4.5习题 71
第5章 数组 73
5.1数组的基本概念 73
5.1.1数组的定义及特点 73
5.1.2数组的基本操作 74
5.2数组的顺序存储结构 74
5.3矩阵的压缩存储 76
5.3.1特殊矩阵 77
5.3.2稀疏矩阵 78
5.4小结 85
5.5习题 86
第6章 树和二叉树 87
6.1树结构的定义与基本操作 87
6.1.1树的定义及相关术语 87
6.1.2树的基本操作 89
6.2二叉树 89
6.2.1二叉树的定义与基本操作 90
6.2.2二叉树的性质 92
6.2.3二叉树的存储结构 94
6.3遍历二叉树 96
6.3.1先序遍历 96
6.3.2中序遍历 98
6.3.3后序遍历 99
6.3.4线索二叉树及其算法 100
6.4树和森林 105
6.4.1树的存储结构 105
6.4.2树和森林的遍历 107
6.4.3森林与二叉树的相互转换 108
6.5哈夫曼树及其应用 111
6.5.1哈夫曼树的定义 111
6.5.2哈夫曼树的构造 112
6.5.3哈夫曼树的应用 113
6.6小结 116
6.7习题 117
第7章 图 120
7.1图的基本概念及其操作 120
7.1.1图的基本概念 120
7.1.2图的基本操作 123
7.2图的存储结构 124
7.2.1邻接矩阵 124
7.2.2邻接链表 128
7.3图的遍历 133
7.3.1图的深度优先遍历 133
7.3.2图的广度优先遍历 135
7.4最小生成树 136
7.4.1最小生成树的定义 136
7.4.2最小生成树的生成算法 138
7.5拓扑排序 140
7.5.1有关拓扑排序的定义 140
7.5.2拓扑排序的方法 142
7.5.3拓扑排序的实现算法 143
7.6关键路径 145
7.6.1有关关键路径的定义 145
7.6.2求关键路径的方法 146
7.7最短路径 148
7.7.1从某一顶点到其余顶点的最短路径 149
7.7.2任意一对顶点间的最短路径 150
7.8小结 152
7.9习题 153
第8章 查找 158
8.1概述 158
8.2顺序查找 160
8.3有序表的查找 162
8.4分块查找 164
8.5动态查找技术 166
8.5.1二叉排序树及其查找方法 167
8.5.2平衡二叉树及其查找方法 172
8.6哈希表的查找技术 176
8.6.1哈希表的基本概念 176
8.6.2哈希函数的构造 178
8.6.3冲突处理的方法 181
8.6.4哈希表的查找及其分析 183
8.7小结 187
8.8习题 188
第9章 排序 190
9.1基本概念 190
9.2插入排序 192
9.2.1直接插入排序 192
9.2.2希尔排序 194
9.3交换排序 197
9.3.1冒泡排序 197
9.3.2快速排序 199
9.4选择排序 202
9.4.1简单选择排序 202
9.4.2树形选择排序 203
9.4.3堆排序 205
9.5归并排序 212
9.6各种内部排序方法的比较和选择 213
9.7小结 214
9.8习题 214
附录 216
自测试题一 216
自测试题二 220
自测试题三 224
自测试题四 228
自测试题五 233
参考文献 238