数据结构

第1章 绪论 1
1.1 什么是数据结构 1
1.1.1 数据结构基本概念 1
1.1.2 数据结构图形表示 2
1.2 什么是算法 3
1.2.1 算法概念 3
1.2.2 算法设计要求 3
1.2.3 算法复杂度 4
1.3 C语言要点回顾 7
1.3.1 基本数据类型 7
1.3.2 其他复合数据类型 8
1.3.3 指针数据类型 10
1.3.4 常用结构及函数 12
习题 15
第2章 线性表 17
2.1 线性表的逻辑结构 17
2.1.1 线性表的概念 17
2.1.2 线性表的抽象数据类型 18
2.2 线性表的顺序结构及基本运算实现 19
2.2.1 线性表的顺序表示 19
2.2.2 顺序表的基本运算 20
2.3 线性表的链式结构及基本运算实现 32
2.3.1 单链表的表示 32
2.3.2 单链表的操作实现 34
2.3.3 单循环链表 44
2.3.4 双向链表 48
2.3.5 静态链表 49
2.4 线性表综合运用 52
2.4.1 一元多项式的加减法 52
2.4.2 约瑟夫环 55
习题 58
第3章 栈和队列 59
3.1 栈的基本概念 59
3.1.1 栈的定义 59
3.1.2 栈的抽象数据类型 60
3.2 栈的表示与实现 60
3.2.1 栈的顺序表示 60
3.2.2 栈的链式表示 63
3.3 栈的应用 65
3.3.1 整数的数制转换 65
3.3.2 判断字符串是否为回文 69
3.4 队列 70
3.4.1 队列的基本定义与抽象数据类型 70
3.4.2 链队列 72
3.4.3 循环队列 80
习题 87
第4章 数组 88
4.1 数组的概念 88
4.2 数组的顺序存储 89
4.3 矩阵的压缩存储 89
4.3.1 对称矩阵 90
4.3.2 稀疏矩阵 91
习题 100
第5章 树 101
5.1 树的相关基本概念 101
5.1.1 树的定义与基本术语 101
5.1.2 树的抽象数据类型定义 103
5.1.3 树的存储结构表示 105
5.2 二叉树 109
5.2.1 二叉树的定义 109
5.2.2 二叉树的性质 112
5.2.3 二叉树的存储结构 114
5.3 二叉树常用操作 117
5.3.1 二叉链表结构下的常用操作 117
5.3.2 顺序存储结构下的常用操作 139
5.3.3 反推二叉树结构 150
5.4 线索二叉树 151
5.4.1 线索二叉树原理 151
5.4.2 线索二叉树的结构实现 152
5.4.3 线索二叉树的遍历 154
5.5 树、森林和二叉树的转换 156
5.5.1 树转换为二叉树 157
5.5.2 森林转换为二叉树 157
5.5.3 二叉树转换为树 158
5.5.4 二叉树转换为森林 158
5.5.5 树和森林的遍历 159
5.6 哈夫曼树及其应用 159
5.6.1 最优二叉树(哈夫曼树)的定义 159
5.6.2 最优二叉树(哈夫曼树)的应用 160
5.6.3 最优二叉树(哈夫曼树)的创建 163
习题 171
第6章 图 174
6.1 图的基本概念 174
6.1.1 图的定义和术语 174
6.1.2 图的抽象数据类型定义 179
6.2 图的存储结构 181
6.2.1 邻接矩阵表示法 181
6.2.2 邻接表/逆邻接表表示法 186
6.2.3 十字链表表示法 190
6.3 图的遍历 192
6.3.1 深度优先遍历 193
6.3.2 广度优先遍历 199
6.4 最小生成树 202
6.4.1 普里姆(Prim)算法 203
6.4.2 克鲁斯卡尔(Kruskal)算法 209
6.5 有向无环图及其应用 215
6.5.1 拓扑排序问题 215
6.5.2 关键路径问题 219
6.6 最短路径 224
习题 230
第7章 查找 233
7.1 查找表及其相关概念 233
7.2 顺序表的查找 235
7.3 有序表的查找 237
7.4 索引表的查找 243
7.5 二叉排序树 245
7.5.1 二叉排序树的查找 246
7.5.2 二叉排序树的插入和创建 248
7.5.3 二叉排序树的删除 250
7.5.4 二叉排序树的总结 257
7.6 平衡二叉树 257
7.6.1 平衡二叉树实现原理 259
7.6.2 平衡二叉树的实现代码 264
7.7 哈希查找 271
7.7.1 哈希查找概述 271
7.7.2 哈希函数的构造方法 273
7.7.3 处理哈希冲突的方法 275
7.7.4 哈希查找的性能分析 279
习题 280
第8章 排序 282
8.1 排序概述 282
8.2 插入排序 282
8.2.1 直接插入排序 282
8.2.2 希尔排序 284
8.3 交换排序 286
8.3.1 冒泡排序 286
8.3.2 快速排序 288
8.4 选择排序 290
8.4.1 简单选择排序 290
8.4.2 堆排序 292
8.5 归并排序 297
8.6 基数排序 299
8.7 排序方法的总结 306
习题 306