第1章 绪论 1
1.1什么是数据结构 1
1.2基本术语 3
1.3算法和算法的分析 5
1.3.1算法 5
1.3.2算法的设计要求 6
1.3.3算法分析 6
本章小结 9
习题 9
第2章 线性表 11
2.1线性表及其基本运算 11
2.1.1线性表的定义 11
2.1.2线性表的基本运算 12
2.2顺序表 12
2.2.1顺序表的定义 12
2.2.2顺序表的存储定义和运算 13
2.2.3顺序表的实例源程序 18
2.3单链表 20
2.3.1单链表的定义 21
2.3.2单链表的实例源程序 26
2.3.3静态链表 29
2.3.4循环单链表 32
2.4双向链表 35
2.4.1双向链表的定义 35
2.4.2双向链表的基本运算的实现 36
2.4.3双向循环链表 38
2.4.4顺序表和链表的比较 38
2.5链表的应用 39
本章小结 43
习题 43
第3章 栈和队列 45
3.1栈及其运算 45
3.1.1栈的基本概念 45
3.1.2栈的基本操作 45
3.2栈的顺序存储结构 46
3.2.1顺序栈的表示和实现 46
3.2.2两个栈共享存储空间 48
3.3栈的链式存储结构 50
3.4栈的应用举例 51
3.4.1数制的转换问题 51
3.4.2括号匹配的检测 51
3.4.3栈与递归 53
3.4.4算术表达式求值 54
3.4.5栈的实例源程序 56
3.5队列 58
3.5.1队列的定义 58
3.5.2队列的运算 59
3.5.3队列的链式存储结构 59
3.5.4队列的顺序存储结构 61
3.5.5队列实例源程序 65
本章小结 67
习题 67
第4章 数组及其应用 69
4.1数组及其顺序存储结构 69
4.1.1数组的概念 69
4.1.2数组的主要运算 70
4.1.3数组的顺序存储结构 70
4.2矩阵的压缩存储 73
4.2.1特殊矩阵及其压缩存储 73
4.2.2稀疏矩阵 74
本章小结 80
习题 80
第5章串 82
5.1串和串的主要运算 82
5.1.1串的基本概念 82
5.1.2串的主要运算 83
5.2串的存储结构和基本运算的实现 85
5.2.1定长顺序存储结构 85
5.2.2堆分配存储结构 87
5.2.3块链存储结构 90
5.3串的模式匹配算法 92
5.4串的应用实例 95
本章小结 97
习题 97
第6章 树和二叉树 100
6.1树的概念和存储表示 100
6.1.1树的基本概念 100
6.1.2树的存储表示 102
6.2二叉树 104
6.2.1二叉树的概念 105
6.2.2二叉树的性质 106
6.2.3二叉树的存储表示 109
6.3二叉树的遍历 111
6.3.1前序遍历 111
6.3.2中序遍历 112
6.3.3后序遍历 113
6.4线索二叉树 115
6.5树、森林与二叉树的转换与遍历 118
6.5.1树的二叉树表示 118
6.5.2森林与二叉树的转换 119
6.5.3树与森林的遍历 121
6.6哈夫曼树及其应用 122
6.6.1路径长度 122
6.6.2哈夫曼树 122
6.6.3哈夫曼编码 124
本章小结 127
习题 128
第7章图 131
7.1图的基本概念 131
7.1.1图、有向图、无向图 131
7.1.2图的运算 132
7.1.3图的基本术语 132
7.2图的存储结构 135
7.2.1邻接矩阵表示法 135
7.2.2邻接表表示法 138
7.3图的遍历 141
7.3.1深度优先搜索 141
7.3.2广度优先搜索 142
7.4生成树和最小生成树 144
7.4.1生成树和最小生成树的概念 144
7.4.2 Kruskal算法 146
7.4.3 Prim算法 147
7.5 AOV网和拓扑排序 148
7.5.1 AOV网和拓扑排序的概念 148
7.5.2拓扑排序算法 149
7.6 AOE网和关键路径 152
7.6.1 AOE网和关键路径的概念 152
7.6.2关键路径的确定 153
7.7最短路径 156
7.7.1最短路径的概念 156
7.7.2 Dijkstra算法 157
7.7.3 Floyd算法 159
本章小结 160
习题 160
第8章 排序 163
8.1基本概念 163
8.2插入排序 164
8.3交换排序 166
8.3.1冒泡排序 166
8.3.2快速排序 168
8.4选择排序 170
8.4.1简单选择排序 170
8.4.2堆排序 172
8.5归并排序 177
8.6基数排序 179
8.7各种内部排序的比较 183
8.8外部排序、 184
8.8.1外部排序的方法 184
8.8.2置换-选择排序 185
8.8.3最佳归并树 186
本章小结 187
习题 188
第9章 查找 190
9.1静态查找表 192
9.1.1静态查找表结构 192
9.1.2顺序查找 192
9.1.3折半查找 193
9.1.4插值查找和斐波那契查找 196
9.1.5索引查找 199
9.2动态查找表 200
9.2.1二叉排序树 200
9.2.2平衡二叉树 206
9.2.3 B-树和B+树 212
9.3哈希表 217
9.3.1哈希表的基本概念 217
9.3.2哈希函数的构造 218
9.3.3处理冲突的方法 221
9.3.4哈希表的查找分析 223
本章小结 225
习题 225
第10章 文件 227
10.1外存储设备 227
10.1.1磁带 227
10.1.2磁盘 228
10.2文件的基本概念 229
10.3顺序文件 230
10.4索引文件 232
10.5直接存取文件 233
10.6链接文件和多重链表文件 234
10.7倒排文件 236
本章小结 237
习题 237