1.1数据结构的概念 1
第1章 概述 1
1.2数据结构的存储 3
1.2.1存储器表示 3
1.2.2数据结构的映像 3
1.2.3数据结构的几种常见存储方式 4
1.3数据结构课程研究的内容 5
1.4 C语言与数据结构 6
1.4.1数据类型及抽象数据类型 6
1.4.2 C言的数据类型 8
1.5.2“好”的算法 9
1.5算法 9
1.5.1算法的概念 9
1.5.3算法的描述 10
1.6程序性能分析 12
1.6.1程序分析的方法 12
1.6.2 时间复杂度的分析 13
1.6.3空间复杂度 16
1.7习题 18
第2章 线性表 20
2.1线性表的基本概念 20
2.3单链表 21
2.2线性表的顺序存储结构 21
2.4单链表的建立 24
2.4.1内存的动态分配与释放 24
2.4.2单链表结点的配置与释放 28
2.4.3单链表的建立与释放 30
2.5链表的基本操作 34
2.5.1单链表的查找 34
2.5.2单链表结点的插入 38
2.5.3单链表结点的删除 44
2.5.4单链表的链接 50
2.5.5单链表的反转 54
2.6线性表的应用 59
2.7习题 62
第3章 高级链表 63
3.1循环链表 63
3.1.1循环链表的建立与释放 63
3.1.2循环链表结点的插入 67
3.1.3循环链表结点的删除 72
3.2双向链表 78
3.2.1双向链表的建立与释放 79
3.2.2双向链表结点的插入 82
3.2.3 双向链表结点的删除 86
3.3循环双向链表 91
3.4题 95
第4章 栈 96
4.1栈 96
4.1.1栈的定义 96
4.1.2顺序栈 97
4.1.3链栈 101
4.2表达式表示法 104
4.2.1几种表达式表示法 105
4.2.2表达式表示法的转换 107
4.3栈的应用 111
4.3.1数制转换 111
4.3.2括号匹配问题 112
4.3.3栈与递归 115
4.4习题 117
第5章 队列 118
5.1队列的基本概念 118
5.1.1队列的概念 118
5.1.2顺序队列 119
5.1.3链队列 121
5.2循环队列 125
5.3队列的应用范例 129
5.3.1键盘输入循环缓冲区问题 129
5.3.2售票问题 132
5.4题 135
第6章 数组、广义表和串 136
6.1数组 136
6.1.1数组的定义 136
6.1.2数组的基本操作 137
6.2数组的存储结构 137
6.3矩阵的压缩存储 138
6.3.1特殊矩阵 138
6.3.2稀疏矩阵 140
6.4广义表 147
6.4.1广义表的定义 147
6.4.2广义表的存储结构 148
6.5串 149
6.5.1串的基本概念 149
6.5.2串的存储结构 150
6.6模式匹配 152
6.6.1简单的模式匹配算法Brute-Force算法 152
6.6.2 KMP算法 155
6.7习题 159
第7章 递归 161
7.1递归与递归程序的概念 161
7.2递归程序设计的技巧 162
7.3用递归的方法创建一个单链表 163
7.4.1汉诺塔问题(Tower of Hanoi) 165
7.4经典递归实例 165
7.4.2迷宫问题 169
7.5习题 178
第8章 树与二叉树 179
8.1树 179
8.1.1树的定义 179
8.1.2树的表示 180
8.1.3树的基本术语 181
8.2二叉树的基本概念 182
8.2.2二叉树的重要性质 182
8.3二叉树的存储结构 184
8.3.1二叉树的顺序存储 184
8.3.2二叉链表 186
8.3.3二叉链表的递归创建及其基本操作的实现 186
8.3.4二叉链表的非递归创建 189
8.4二叉树的遍历 192
8.4.1二叉树遍历的定义 192
8.4.2 二叉树遍历的递归算法实现 193
8.4.3二叉树遍历的非递归算法 195
8.5线索二叉树 198
8.5.1线索二叉树的概念 198
8.5.2线索二叉树的创建和遍历 199
8.6二叉排序树 202
8.7哈夫曼树 204
8.7.1哈夫曼树的定义 205
8.7.2哈夫曼树的构造 206
8.7.3哈夫曼编码 207
8.8树与森林 211
8.8.1树的存储结构 211
8.8.2树、森林与二叉树 214
8.8.3树和森林的运算 216
8.9习题 217
第9章 图 219
9.1图的定义和相关术语 219
9.2图的存储结构 221
9.2.1邻接矩阵 221
9.2.2邻接表 225
9.3图的遍历 228
9.3.1深度优先搜索 228
9.3.2广度优先搜索 231
9.4生成树问题 234
9.4.1生成树和最小生成树问题 234
9.4.2 Prim算法 235
9.4.3 Kruskal算法 238
9.5最短路径问题 241
9.5.1单源点最短路径 241
9.5.2每对顶点之间的最短路径 244
9.6图的应用——拓扑排序 246
9.7习题 248
第10章 查找 250
10.1基本概念 250
10.2顺序查找 251
10.3折半查找 253
10.4分块查找 255
10.5哈希查找 258
10.5.1哈希表技术 258
10.5.2哈希函数的构造方法 260
10.5.3处理哈希冲突的方法 262
10.5.4哈希查找算法 264
10.5.5哈希查找算法的性能分析 271
10.6习题 272
第11章 排序 273
11.1排序的概念 273
11.2交换式排序 274
11.2.1冒泡排序 274
11.2.2快速排序 276
11.3选择排序 279
11.3.1选择排序 279
11.3.2堆排序 281
11.4插入排序 286
11.4.1直接插入排序 286
11.4.2希尔排序 289
11.5归并排序 291
11.6几种排序方法的比较 294
11.7外排序简介 294
11.8习题 295
12.1.1文件有关术语 296
12.1文件的基本概念 296
12.1.2文件的操作 296
第12章 文件 296
12.1.3文件的物理组织 297
12.2顺序文件 298
12.3索引文件 299
12.4 ISAM文件 300
12.4.1 ISAM的概念 300
12.4.2 ISAM结构的操作 302
12.5散列文件 302
12.6多索引文件 303
12.6.1多重表文件 304
12.6.2倒排文件 305
12.7习题 305
参考文献 306
8.2.1二叉树的定义及其基本操作 6182