1.1 基本概念和术语 1
1.1.1 引言 1
第1章 绪论 1
1.1.2 基本概念和术语 5
1.1.3 C语言的数据类型 5
1.1.4 动态存储分配 6
1.2 算法的描述和分析 6
1.2.1 什么是算法 6
1.2.3 算法分析 7
1.2.2 几个数学符号 7
1.2.4 简单的算法分析举例 8
习题1 10
第2章 线性表 11
2.1 线性表的定义及其运算 11
2.1.1 线性表的定义 11
2.1.2 各种运算简介 11
2.2.2 顺序表上实现的基本运算 12
2.2.1 顺序表 12
2.2 线性表的顺序存储结构 12
2.3 线性表的链式存储结构 15
2.3.1 线性表的链接分配——单链表 15
2.3.2 单链表的基本运算 16
2.4 循环链表和双向链表 25
2.4.1 循环链表 25
2.4.2 双向链表 26
2.5.2 基于时间的考虑 28
2.5.1 基于空间的考虑 28
2.5 顺序表和链表的比较 28
习题2 29
第3章 栈和队列 31
3.1 栈 31
3.1.1 栈的定义及基本运算 31
3.1.2 顺序栈及基本运算 31
3.1.3 双向栈 33
3.1.4 栈的链表存储结构 34
3.2.1 队列的定义及运算 35
3.2 队列 35
3.2.2 队列的顺序存储结构(向量) 36
3.2.3 队列的链表存储结构 39
3.3 栈和队列的应用 41
3.3.1 函数的嵌套调用 41
3.3.2 函数的递归调用 41
3.3.3 栈与队列的应用 42
习题3 43
4.1.1 字符串的基本概念 46
4.1.2 串的运算简介 46
第4章 串 46
4.1 字符串及其运算 46
4.2 串的存储结构 49
4.2.1 串的顺序存储结构 49
4.2.2 串的链式存储 50
4.2.3 串运算的实现 52
习题4 55
5.1 多维数组 57
第5章 多维数组和广义表 57
5.2 矩阵的压缩存储 59
5.2.1 特殊矩阵 59
5.2.2 稀疏矩阵 62
5.3 广义表的概念和特性 65
习题5 66
第6章 树 68
6.1 树的概念 68
6.1.1 树的定义 68
6.1.2 基本术语 69
6.2 二叉树 70
6.2.1 二叉树的定义 70
6.2.2 二叉树的性质 71
6.2.3 二叉树的存储结构 72
6.3 二叉树的遍历 75
6.3.1 中序遍历二叉树的递归算法 76
6.3.2 中序遍历二叉树的非递归算法 77
6.4 线索二叉树 78
6.4.1 中序线索化 79
6.4.2 线索二叉树上的运算 80
6.5 树和森林 81
6.4.3 遍历线索二叉树 81
6.5.1 树、森林与二叉树的转换 82
6.5.2 树的存储结构 84
6.5.3 树和森林的遍历 86
6.6 赫夫曼树及其应用 87
6.6.1 最优二叉树(赫夫曼树) 87
6.6.2 赫夫曼编码 93
习题6 95
7.1 图的概念 98
第7章 图 98
7.2 图的存储结构 101
7.2.1 邻接矩阵表示法 101
7.2.2 邻接表表示法 103
7.3 图的遍历 105
7.3.1 深度优先搜索 105
7.3.2 广度优先遍历 109
7.4.1 生成树的概念 111
7.4.2 最小生成树 111
7.4 图的生成树 111
7.5 最短路径 114
7.5.1 单源最短路径 114
7.5.2 每对顶点之间的最短路径 115
7.6 拓扑排序 116
习题7 121
第8章 排序 124
8.1 三个简单的排序算法 124
8.1.1 冒泡排序 124
8.1.2 直接选择排序 126
8.1.3 直接插入排序 127
8.2 快速排序 128
8.3 谢尔排序 133
8.3.1 方法 133
8.3.2 增量的选择 135
8.4 堆排序 136
8.5 基数排序 138
8.6 合并已整序的表 142
8.6.1 简单的合并算法 142
8.6.2 二路归并排序 143
8.7 字符串排序 144
习题8 149
第9章 查找 153
9.1 基本概念 153
9.2 静态查找表 153
9.2.1 顺序表的查找 153
9.2.2 有序表的二分查找 154
9.2.3 索引顺序表的查找 155
9.3.1 二叉排序树和二叉平衡树 156
9.3 动态查找表 156
9.3.2 B-树和B+树 159
9.4 哈希表及其查找 163
9.4.1 哈希表与哈希函数 163
9.4.2 构造哈希函数的常用方法 164
9.4.3 解决冲突的主要方法 165
习题9 170
第0章 文件 173
10.1 文件的基本概念 173
10.1.1 文件 173
10.1.2 外存储器及信息特点 175
10.2.1 顺序文件 177
10.2 文件的组织 177
10.2.2 散列文件 178
10.2.3 索引文件 179
10.2.4 索引顺序文件 181
10.3 多关键字文件 183
10.3.1 多重表文件 183
10.3.2 倒排文件 185
习题10 185
11.1 线性表及其运算 187
第11章 实验内容与上机指导 187
11.2 链表及其运算 190
11.3 二叉树的存储与遍历 196
11.4 图的存储与遍历 202
11.5 排序 206
11.6 查找 211
附录A 216
附录B 225
参考文献 233