1.1 什么是数据结构 1
第1章 绪论 1
1.2基本概念和术语 3
1.3数据类型和抽象数据类型 6
1.4算法描述与算法评价 8
1.4.1 算法描述 8
1.4.2算法的设计要求 10
1.4.3算法的评价 11
习题一 14
2.1.1线性表的逻辑结构 16
2.1.2线性表的运算 16
第2章 线性表 16
2.1 线性表的基本概念 16
2.2线性表的顺序存储结构 17
2.2.1顺序表 17
2.2.2顺序表上的基本运算 18
2.3线性表的链式存储结构 22
2.3.1 单链表 22
2.3.2单链表上的基本运算 24
2.3.3循环链表 29
2.3.4双向链表 30
2.4线性表存储结构的选择 32
2.5线性表的应用举例 33
习题二 36
上机实验题一 37
第3章 栈和队列 39
3.1 栈 39
3.1.1栈的定义及其运算 39
3.1.2栈的顺序存储结构 40
3.1.3栈的链式存储结构 43
3.2栈的应用举例 44
3.2.1表达式求值 44
3.2.2递归的实现 48
3.3 队列 50
3.3.1 队列的定义及其运算 50
3.3.2 队列的顺序存储结构 50
3.3.3 队列的链式存储结构 53
3.4队列的应用举例 55
3.4.1 I/O缓冲区管理 55
习题三 56
3.4.3双端队列 56
3.4.2 优先队列 56
上机实验题二 57
第4章 串 59
4.1 串的基本概念 59
4.2 串的存储实现 60
4.2.1 串的定长顺序存储及运算实现 61
4.2.2 串的堆式动态存储及运算实现 65
4.2.3 串的块链存储表示 68
4.3.1 串的简单模式匹配算法 69
4.3 串的模式匹配算法 69
4.3.2一种改进的模式匹配算法 72
4.4汉字串 77
习题四 80
第5章 数组和广义表 81
5.1数组及其运算 81
5.2数组的顺序存储结构 82
5.3矩阵的压缩存储 83
5.3.1特殊矩阵 84
5.3.2稀疏矩阵 86
5.4.2广义表的存储结构 97
5.4广义表 97
5.4.1广义表的定义 97
5.4.3广义表的运算 99
5.5 m元多项式的表示 100
习题五 102
上机实验题三 102
第6章 树 104
6.1树的基本概念 104
6.1.1树的定义及表示 104
6.1.2树的常用术语 105
6.1.3树的基本运算 106
6.2 二叉树 107
6.2.1 二叉树的概念及运算 107
6.2.2二叉树的性质 108
6.2.3二叉树的存储结构 110
6.2.4 二叉树的简单运算实现 112
6.3 遍历二叉树 113
6.3.1遍历二叉树的递归算法 113
6.3.2遍历二叉树的非递归算法 116
6.3.4二叉树的运算举例 119
6.3.3二叉树的层次遍历 119
6.4线索二叉树 121
6.4.1线索二叉树的概念 121
6.4.2线索二叉链表的建立 122
6.4.3遍历线索二叉树 124
6.5树和森林 124
6.5.1 树的存储结构 124
6.5.2树、森林与二叉树的转换 127
6.5.3树和森林的遍历 129
6.6.1 基本术语 130
6.6 哈夫曼树 130
6.6.2哈夫曼算法 131
6.6.3哈夫曼编码 131
6.6.4哈夫曼算法的实现 133
习题六 137
上机实验题四 138
第7章 图 139
7.1 图的基本概念 139
7.2图的存储结构 141
7.2.1 邻接矩阵 141
7.2.2邻接表 143
7.2.3邻接多重表 145
7.3图的遍历 146
7.3.1 深度优先搜索遍历 147
7.3.2广度优先搜索遍历 148
7.4最小生成树 149
7.4.1 生成树和最小生成树 149
7.4.2普里姆算法 151
7.4.3 克鲁斯卡尔算法 153
7.5.1单源最短路径 154
7.5最短路径 154
7.5.2所有顶点对之间的最短路径 157
7.6 AOV网与拓扑排序 160
习题七 164
上机实验题五 166
第8章 检索 168
8.1检索的基本概念 168
8.2线性表的检索 169
8.2.1 顺序检索 169
8.2.2折半检索 170
8.2.3分块检索 174
8.3树表的检索 177
8.3.1 二叉检索树 177
8.3.2平衡的二叉检索树 184
8.4 B树 187
8.4.1 B－树 187
8.4.2 B＋树 191
8.5散列检索 192
8.5.1散列表技术 192
8.5.2散列表的检索算法及性能分析 196
习题八 198
上机实验题六 199
第9章 排序 201
9.1排序的基本概念 201
9.2插入排序 203
9.2.1直接插入排序 203
9.2.2希尔排序 205
9.2.3其他插入排序 208
9.3交换排序 212
9.3.1 冒泡排序 212
9.3.2快速排序 214
9.4.1直接选择排序 218
9.4选择排序 218
9.4.2堆排序 219
9.5 归并排序 224
9.6基数排序 226
9.7 内部排序方法的比较和选择 230
9.8外排序简介 230
习题九 231
上机实验题七 232
10.1文件的基本概念 234
第10章 文件 234
10.2顺序文件 235
10.3索引文件 235
10.3.1 ISAM文件 236
10.3.2 VSAM文件 238
10.4散列文件 239
10.5多关键字文件 240
习题十 242
参考文献 243