第1章 绪论 1
1.1 数据、数据表示和数据处理 1
1.1.1 数据 1
1.1.2 数据表示 2
1.1.3 数据处理 2
1.2 什么是数据结构 2
1.2.1 数据的逻辑结构 2
1.2.2 数据的存储结构 5
1.2.3 数据的运算 5
1.3.1 什么是算法 6
1.3 算法及其描述 6
1.3.2 算法的描述 7
1.4 算法分析 8
1.4.1 算法的性能标准 8
1.4.2 算法的效率分析 8
习题 10
实习参考题 12
第2章 线性表 13
2.1 线性表的定义及其基本算法 13
2.1.1 线性表的定义 13
2.1.2 线性表的逻辑结构 13
2.2.1 线性表的顺序存储结构 14
2.1.3 线性表的基本算法 14
2.2 线性表的顺序存储结构 14
2.2.2 顺序表基本算法的实现 15
2.2.3 顺序表基本算法的时间复杂度分析 18
2.3 线性表的链式存储结构 18
2.3.1 单链表 18
2.3.2 单链表基本算法的实现 19
2.3.3 单链表的建立 24
2.4 双链表和循环链表 25
2.4.1 双链表 25
2.5.1 空间性能的比较 29
2.4.2 循环链表 29
2.5 线性表的顺序存储结构与链式存储结构的性能比较 29
2.5.2 时间性能的比较 30
习题 30
实习参考题 31
第3章 栈和队列 32
3.1 栈 32
3.1.1 栈的定义及其基本操作算法 32
3.1.2 栈的顺序存储结构及其基本操作算法的实现 34
3.1.3 栈的链式存储结构及其基本操作算法的实现 37
3.1.4 栈的应用举例 40
3.2 队列 43
3.2.1 队列的定义 44
3.2.2 队列的顺序存储结构及其基本操作算法的实现 44
3.2.3 队列的链式存储结构及其基本操作算法的实现 50
3.3 栈和队列的综合应用举例 53
习题 58
实习参考题 58
第4章 串 60
4.1 串的基本概念 60
4.1.1 串的定义 60
4.2 串的存储结构 61
4.1.2 串的基本操作算法 61
4.2.1 串的顺序存储结构 62
4.2.2 串的链式存储结构 62
4.3 串的基本操作算法的实现 63
习题 68
实习参考题 69
第5章 数组 70
5.1 数组的基本概念 70
5.2 数组的存储和数组元素的地址 71
5.3 特殊矩阵的压缩存储 72
5.3.1 对称矩阵 73
5.3.2 三角矩阵 74
5.3.3 稀疏矩阵 75
5.4 数组基本操作的实现 80
习题 81
实习参考题 82
第6章 树 83
6.1 树的基本概念 83
6.1.1 树的定义 83
6.1.2 树的表示 84
6.1.3 树的基本术语 84
6.2 二叉树及其性质 85
6.2.1 二叉树的定义 86
6.2.2 二叉树的重要性质 86
6.3 二叉树的存储结构 88
6.3.1 顺序存储结构 88
6.3.2 链式存储结构 88
6.3.3 二叉树二叉链表的建立 89
6.4 二叉树的遍历 90
6.4.1 遍历二叉树的规则 90
6.4.2 先根遍历 91
6.4.3 中根遍历 92
6.4.4 后根遍历 93
6.4.5 二叉树遍历算法的一个简单应用 94
6.5 线索二叉树 94
6.5.1 线索二叉树的基本概念 95
6.5.2 线索二叉树的逻辑表示图 95
6.5.3 中根次序线索化算法 96
6.5.4 在中根线索树上检索某结点的前趋和后继 97
6.5.5 在中根线索树上遍历二叉树 98
6.6 二叉树、一般树和森林 99
6.6.1 一般树的存储结构 99
6.6.2 一般树与二叉树之间的转换 100
6.6.3 森林与二叉树间的转换 101
6.6.4 一般树和森林的遍历 103
6.7 二叉排序树 104
6.7.1 二叉排序树的定义与特点 104
6.7.2 二叉排序树的建立 105
6.7.3 在二叉排序树中删除结点 106
6.7.4 在二叉排序树上查找结点 107
6.8 哈夫曼树及其应用 107
6.8.1 哈夫曼树的定义 108
6.8.2 哈夫曼树的构造及其算法的实现 109
6.8.3 哈夫曼树的应用 111
6.9 二叉树建立与遍历的C源程序示例 112
习题 114
实习参考题 116
第7章 图 117
7.1 图的基本概念 117
7.1.1 图的定义 117
7.1.2 图的基本术语 118
7.2 图的存储结构 120
7.2.1 邻接矩阵 121
7.2.2 邻接链表 121
7.3.1 深度优先搜索 123
7.3 图的遍历 123
7.3.2 广度优先搜索 124
7.4 图的生成树 126
7.4.1 生成树 126
7.4.2 最小生成树 126
7.4.3 求最小生成树的常用算法 127
7.5 最短路径 131
7.5.1 最短路径的概念 131
7.5.2 单源最短路径 132
7.6 拓扑排序 134
7.6.1 AOV网 134
7.6.2 拓扑排序 135
习题 138
实习参考题 140
第8章 查找 141
8.1 查找的基本概念 141
8.2 静态查找表 142
8.2.1 顺序查找 142
8.2.2 二分查找 143
8.2.3 分块查找 144
8.3 动态查找表 146
8.3.1 二叉排序树 146
8.3.2 平衡二叉排序树 151
8.4 哈希表 154
8.4.1 哈希表和哈希函数 155
8.4.2 哈希函数的构造方法 156
8.4.3 处理冲突的主要方法 158
习题 164
实习参考题 165
第9章 排序 166
9.1 概述 166
9.2 插入排序 167
9.2.1 直接插入排序 167
9.2.2 折半插入排序 168
9.2.3 希尔排序 169
9.3 交换排序 171
9.3.1 冒泡排序 171
9.3.2 快速排序 172
9.4 选择排序 174
9.4.1 直接选择排序 174
9.4.2 堆排序 175
9.5 归并排序 179
9.5.1 两个有序序列的合并 180
9.5.2 归并排序 180
实习参考题 182
习题 182
第10章 文件 183
10.1 文件的基本概念 183
10.1.1 文件及其基本运算 183
10.1.2 外存储器简介 184
10.2 顺序文件 185
10.3 散列文件 186
10.4 索引文件 187
10.5 ISAM文件 188
习题 189
参考文献 191