本书为地理信息科学相关专业的数据结构教学和学习编写。全书共分8章，第1章介绍了数据结构的基本概念、内涵和算法分析方法；第2～4章讨论了线性表、栈和队列及其应用，分析了多维数组、特殊矩阵和稀疏矩阵的压缩存储方法等，还对广义表做了扼要介绍；第5、6章讨论了二叉树、优先队列、哈夫曼树及其应用、四叉树空间数据结构与算法，介绍了图及其存储结构、最小生成树、最短路径分析及相关算法；第7、8章讨论了各种查找方法、二叉查找树、B树、R树空间索引，探讨了各种排序方法并给出多种改进的新算法。书中给出的应用实例多数与地理信息科学有关。本书结构合理、内容翔实、视角独特、算法丰富，便于教学和自学。
样章试读
目录
- 目录
前言
第1章 绪论 1
1.1 数据结构的基本概念 1
1.2 基本术语 5
1.3 数据结构的内涵 7
1.3.1 数据的逻辑结构 7
1.3.2 数据的存储结构 8
1.3.3 数据的运算与操作 9
1.4 算法与算法分析 10
1.4.1 算法的基本概念 10
1.4.2 算法的重要特性 10
1.4.3 算法设计的基本方法 11
1.4.4 算法评价要素 12
1.4.5 算法的时间复杂度 13
1.4.6 算法的空间复杂度 17
习题 18
第2章 线性表 19
2.1 线性表的基本概念 19
2.1.1 线性表的定义和特点 19
2.1.2 线性表的基本操作 20
2.2 顺序存储的线性表 21
2.2.1 顺序存储方法 21
2.2.2 顺序表的结构定义及初始化 22
2.2.3 顺序表的基本操作 23
2.2.4 顺序表的特点和适用性 27
2.3 链式存储的线性表 27
2.3.1 链式存储方法 27
2.3.2 单向链表及其结构定义 27
2.3.3 不带头结点单向链表 28
2.3.4 带头结点单向链表 32
2.3.5 循环链表 41
2.3.6 双向链表 44
2.3.7 静态链表 48
2.4 顺序表与链表对比分析 50
2.5 链表的应用 51
2.5.1 一元多项式加法运算 51
2.5.2 Shapefile图形文件的读取 54
习题 59
第3章 栈和队列 61
3.1 栈 61
3.1.1 栈的概念 61
3.1.2 栈的基本操作 62
3.1.3 顺序栈 62
3.1.4 链栈 65
3.2 栈的应用一表达式计算 67
3.2.1 表达式转换为后缀表达式原理 67
3.2.2 表达式转换为后缀表达式算法 68
3.2.3 后缀表达式的计算 70
3.2.4 表达式计算测试 71
3.3 队列 71
3.3.1 队列的概念 71
3.3.2 队列的基本操作 72
3.3.3 顺序队列 73
3.3.4 循环队列 74
3.3.5 链式队列 76
3.4 队列应用 78
3.4.1 数字图像四元组压缩转换原理 78
3.4.2数字图像四元组压缩转换算法 79
习题 82
第4章 数组、矩阵和广义表 84
4.1 数组 84
4.1.1 一维数组 84
4.1.2 多维数组 85
4.1.3 动态多维数组的创建 88
4.1.4 多维数组的一维数组存储 90
4.2 特殊矩阵的压缩存储 91
4.2.1 对称矩阵的压缩存储 92
4.2.2 下三角矩阵的压缩存储 92
4.2.3 上三角矩阵的压缩存储 93
4.2.4 对角矩阵的压缩存储 93
4.2.5 特殊矩阵类型定义与基本运算 94
4.3 稀疏矩阵 96
4.3.1 三元组存储结构 96
4.3.2 十字链表存储结构 103
4.3.3 稀疏矩阵存储性能分析 106
4.4 广义表 107
4.4.1 广义表的概念 107
4.4.2 广义表的性质 107
4.4.3 广义表的链式存储 108
习题 109
第5章 树 111
5.1 树的基本概念 111
5.1.1 树的定义 111
5.1.2 树的基本术语 111
5.2 二叉树 112
5.2.1 二叉树的概念 112
5.2.2 二叉树的性质 113
5.2.3 二叉树的基本操作 114
5.2.4 二叉树的顺序存储实现 116
5.2.5 二叉树的链式存储实现 117
5.2.6 二叉树的遍历及算法118
5.2.7 链式二叉树的创建 122
5.2.8 链式二叉树的基本操作算法 123
5.3 线索二叉树 127
5.3.1 线索二叉树的概念 127
5.3.2 线索二叉树的定义 127
5.3.3 二叉树的中序线索化算法 128
5.3.4 中序线索二叉树的运算 129
5.4 哈夫曼树及其应用 132
5.4.1 哈夫曼树的定义 132
5.4.2 哈夫曼树的构建方法 132
5.4.3 哈夫曼树的存储 133
5.4.4 哈夫曼编码 134
5.4.5 哈夫曼树构建及编码和译码算法 135
5.4.6 哈夫曼树构建及编码和译码示例 139
5.5 优先队列 140
5.5.1 优先队列的概念 140
5.5.2 二叉堆实现的优先队列 141
5.5.3 二叉堆的基本算法 143
5.5.4 四叉堆实现的优先队列 144
5.5.5 四叉堆的基本算法 146
5.6 四叉树及其在空间数据存储中的应用 147
5.6.1 四叉树的概念及性质. 147
5.6.2 常规四叉树编码 148
5.6.3 常规四叉树的构建算法 150
5.6.4 线性四叉树编码 153
5.6.5 线性四叉树的构建算法 156
5.6.6 优势四叉树结构 164
习题 166
第6章 图 169
6.1 图的基本概念 169
6.1.1 图的定义 169
6.1.2 图的术语 169
6.1.3 图的基本操作 172
6.2 图的存储结构 173
6.2.1 图的邻接矩阵存储 174
6.2.2 邻接矩阵图的基本操作算法 176
6.2.3 图的邻接表存储 180
6.2.4 邻接表图的基本操作算法 183
6.3 图的遍历 189
6.3.1 深度优先搜索概念 190
6.3.2 深度优先搜索算法 191
6.3.3 广度优先搜索概念 193
6.3.4 广度优先搜索算法 194
6.3.5 图的连通性 196
6.4 最小生成树 197
6.4.1 最小生成树的概念 197
6.4.2 Prim算法 198
6.4.3 Kruskal算法 202
6.5 最短路径 205
6.5.1 单源最短路径问题 206
6.5.2 单源最短路径算法 207
6.5.3 多源最短路径问题 210
6.5.4 多源最短路径算法 212
习题 214
第7章 查找 217
7.1 查找的概念 217
7.1.1 查找概述 217
7.1.2 查找方法及性能评价 218
7.2 基本查找方法 218
7.2.1 顺序查找 218
7.2.2 折半查找 220
7.2.3 静态树表查找 223
7.2.4 斐波那契查找225
7.2.5 插值查找 227
7.2.6 分块顺序查找 227
7.3 二叉排序树查找 228
7.3.1 二叉排序树的创建与结点插入 229
7.3.2 二叉排序树的查找与结点删除 230
7.3.3 二叉排序树的查找性能分析 233
7.4 平衡二叉树 234
7.4.1 平衡二叉树的定义 234
7.4.2 平衡二叉树的插入与创建 235
7.4.3 平衡二叉树的结点删除 239
7.5 B树与R树空间索引 243
7.5.1 B树及其定义 244
7.5.2 B 树查找 245
7.5.3 B树的插入与删除 246
7.5.4 B+树 247
7.5.5 R树空间索引 248
7.6 散列表及其查找 250
7.6.1 散列和散列表 250
7.6.2 散列函数构造 251
7.6.3 冲突及其解决方法 253
7.6.4 散列表查找与散列法分析 258
习题 260
第8章 排序262
8.1 排序的概念 262
8.2 插入排序 263
8.2.1 直接插入排序 263
8.2.2 折半插入排序 264
8.2.3 链表的直接插入排序 265
8.2.4 算法性能分析 266
8.3 Shell排序 267
8.3.1 Shell排序原理 267
8.3.2 改进的Shell排序方法 268
8.4 堆排序 270
8.4.1 二叉堆排序 270
8.4.2 四叉堆排序 272
8.5 归并排序 274
8.5.1 常规归并排序 274
8.5.2 显式归并排序 276
8.5.3 链式归并排序 278
8.6 快速排序 280
8.6.1 中间记录关键字为基准的快速排序 281
8.6.2 首记录关键字为基准的快速排序 282
8.6.3 链式四分表快速排序算法 284
8.7 基数排序 286
8.7.1 基数排序的原理 286
8.7.2 基数排序算法 288
8.8 各种排序方法的性能比较 289
8.8.1 排序算法的性能特征 289
8.8.2 排序算法性能测试实验 291
8.9 流域离散单元上游集水面积计算中的排序应用 293
8.9.1 集水面积的概念和计算方法 293
8.9.2 计算单元集水面积算法 294
习题 299
主要参考文献 301
京公网安备 11010102004214号