第1章 绪论 1
1.1一个简单的数据结构问题 1
1.2数据结构概述 2
1.2.1数据与数据对象 2
1.2.2数据元素与数据类型 3
1.2.3数据的逻辑结构 6
1.2.4数据的物理结构 8
1.2.5数据结构的基本运算 15
1.2.6数据结构的定义 16
1.3算法 17
1.3.1算法的定义 18
1.3.2对算法的基本要求 18
1.3.3如何设计一个算法 19
1.3.4怎样描述一个算法 21
1.3.5从算法到程序 23
1.4浅谈算法分析 24
1.4.1一个好的算法 24
1.4.2算法的效率分析 25
1.5数据结构应用价值 27
1.6怎样学好数据结构 28
小结 29
习题 30
第2章 线性表 32
2.1一个教务员的一天 32
2.2线性表的基本概念 34
2.2.1线性表的定义 34
2.2.2线性表上的基本运算 35
2.3线性表的顺序结构 36
2.3.1顺序表 36
2.3.2线性表基本运算在顺序表上的实现算法 37
2.3.3建立一个顺序表 42
2.4线性表的链式结构 43
2.4.1单向链表 43
2.4.2线性表基本运算在单向链表上的实现算法 45
2.4.3建立一个单向链表 51
2.4.4循环链表 53
2.4.5双向链表 54
2.5线性表的应用及其算法设计 56
2.5.1数据查重 56
2.5.2有序表的归并 59
2.6基于线性表的查找 63
2.6.1查找的定义 64
2.6.2顺序查找算法 64
2.7基于线性表的排序 68
2.7.1排序的定义 69
2.7.2简单排序算法 71
2.8给教务员的一个解答 77
小结 80
习题 82
第3章 受限的线性表——栈、队列和串 85
3.1栈 85
3.1.1几个栈结构实例 86
3.1.2栈的定义及其基本运算 87
3.1.3顺序栈及其基本运算的实现算法 88
3.1.4链栈及其基本运算的实现算法 91
3.1.5栈结构的应用实例 93
3.2队列 99
3.2.1队列的定义及其基本运算 100
3.2.2顺序队列及其基本运算的实现算法 100
3.2.3循环队列及其基本运算的实现算法 103
3.2.4链队列及其基本运算的实现算法 105
3.2.5队列结构的应用实例 108
3.3串 113
3.3.1串的定义及其基本运算 114
3.3.2串的顺序存储结构及其基本运算算法 115
3.3.3串表达式 120
3.3.4串匹配 121
3.3.5串的应用 127
小结 129
习题 130
第4章 推广的线性表——数组和广义表 133
4.1数组 133
4.1.1数组的定义 133
4.1.2低维数组及其地址映射 134
4.1.3高维数组及其地址映射 137
4.1.4数组的基本运算 137
4.2矩阵与数组 138
4.2.1矩阵及其存储结构 138
4.2.2特殊矩阵及其存储结构 138
4.3广义表 142
4.3.1广义表的定义 142
4.3.2广义表的表示 143
4.3.3广义表的存储结构 144
4.4数组和矩阵、广义表的应用 145
4.4.1数组和矩阵的应用实例 145
4.4.2广义表的应用实例 150
小结 151
习题 152
第5章 树与二叉树 155
5.1两个常见的问题 155
5.2树的基本概念及其基本运算 156
5.2.1树的定义 156
5.2.2树的几个术语 157
5.2.3树的结构特点 158
5.2.4树的表示方法 158
5.2.5树的基本运算 159
5.2.6树的存储结构 159
5.2.7树的遍历 163
5.3二叉树 165
5.3.1二叉树的基本概念与基本运算 165
5.3.2二叉树的基本操作 167
5.3.3二叉树的存储结构 168
5.3.4二叉树的遍历 169
5.3.5从遍历序列构造二叉树 173
5.3.6线索二叉树 174
5.3.7从树、森林到二叉树 177
5.4哈夫曼树 179
5.4.1哈夫曼树的概念和定义 179
5.4.2哈夫曼树的生成算法 181
5.4.3哈夫曼编码技术 183
5.4.4哈夫曼判定树 184
5.5基于树的查找 185
5.5.1折半查找与折半判定二叉树 185
5.5.2二叉排序树 187
5.5.3平衡二叉树 190
5.5.4 B+树 192
5.6基于树的排序 194
5.6.1快速排序与二叉树 194
5.6.2归并排序 197
5.6.3堆排序 199
5.7树在操作系统中的应用 202
小结 202
习题 203
第6章 图 206
6.1几个与图有关的实际问题 206
6.2图的基本概念 208
6.2.1图的定义 208
6.2.2关于图的若干术语 209
6.2.3图的基本性质 211
6.2.4图的基本操作 211
6.3图的存储结构 211
6.3.1 邻接矩阵法 212
6.3.2基于邻接矩阵法的基本运算算法 214
6.3.3邻接表法 215
6.3.4基于邻接表法的基本运算算法 217
6.4图的遍历 219
6.4.1深度优先遍历 220
6.4.2广度优先遍历 221
6.5几个典型问题的算法设计 223
6.5.1最小代价生成树问题 223
6.5.2拓扑排序问题 227
6.5.3最短路径问题 229
小结 236
习题 238
第7章 散列 241
7.1散列的概念 241
7.1.1从一个例子认识散列结构 241
7.1.2散列结构 242
7.1.3冲突 243
7.2散列函数设计 243
7.2.1散列函数的设计原则 244
7.2.2设计散列函数的常用方法 244
7.3解决冲突 246
7.3.1对冲突的分析 246
7.3.2冲突的几个常用解决方案 246
7.4基本运算的算法实现 249
7.4.1基于线性探查法的算法 249
7.4.2基于同义词链表法的算法 252
7.5散列的应用 254
7.5.1散列在编译系统中的应用 254
7.5.2散列在文件系统中的应用 255
7.5.3散列在中医开处方中的应用 257
小结 260
习题 260
参考文献 262