扫一扫
关注中图网
官方微博
¥66.9(6.8折)?
预估到手价是按参与促销活动、以最优惠的购买方案计算出的价格（不含优惠券部分），仅供参考，未必等同于实际到手价。
促销活动:
本类五星书更多>
-
>
宇宙、量子和人类心灵
-
>
(精)BBC地球故事系列-星际旅行
-
>
从一到无穷大
-
>
图说相对论(32开平装)
-
>
一本有趣又有料的化学书
-
>
刘薰宇的数学三书:原来数学可以这样学全3册
-
>
光学零件制造工艺学
数据结构及其空间数据应用 版权信息
- ISBN：9787030743763
- 条形码：9787030743763 ; 978-7-03-074376-3
- 装帧：一般胶版纸
- 册数：暂无
- 重量：暂无
- 所属分类：>>
数据结构及其空间数据应用 本书特色
该书是面向地理信息科学相关专业“数据结构”课程教学编写的实用教材，也可作为相关领域科技人员的参考书。
数据结构及其空间数据应用 内容简介
数据结构作为计算机类专业的基础课程，同时也是地理信息科学专业学生推荐的基础知识。本书从空间数据处理分析需求视角对传统数据结构涉及内容进行适度扩展，主要分为8章，在各章中分别就所涉及的数据结构原理与方法详细介绍了相关的空间数据处理分析应用实例，有助于地理信息科学相关专业学生深入理解和掌握数据结构理论体系及其专业应用方法。
数据结构及其空间数据应用 目录
目录
前言
第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
前言
第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
展开全部
数据结构及其空间数据应用 节选
第1章绪论 自20世纪中叶**台计算机问世以来，计算机技术的发展日新月异，计算机应用领域已由*初单纯的数值计算拓展和深入到人类社会的几乎所有方面，推动了信息技术的革命和社会的巨大进步。早期的计算机应用主要局限于科学计算，后逐步发展到广泛应用于复杂系统控制、行业业务管理、系统仿真模拟、数据获取分析、数字图像处理、人工智能、知识系统与决策支持等诸多领域，这些应用具有显著的非数值计算特征。计算机处理的对象经历了从*初单纯的数值到后来的字符、表格、模式、状态、图形、图像、多媒体等具有一定结构的数据，处理对象的多样性和复杂性给计算机程序设计等带来极大的挑战。为了有效设计出性能优良的数据处理分析程序，必须研究待处理对象的特征、特性以及它们之间的内在逻辑关系，研究适合分析、处理的数据组织、存储和操作方法。这一需求背景促成了“数据结构”这门方法学的诞生和发展。 1.1数据结构的基本概念 数据结构（data structure）可以简单理解为利用计算机存储、组织数据的方式与方法。数据结构针对带有结构性特征的数据集合，研究如何表达数据之间相互关系的逻辑结构以及如何实现与数据逻辑结构和数据运算相适应的物理存储结构，并设计和提供基于这种结构的一组操作运算方法及其算法。数据的逻辑结构和物理存储结构是数据结构的两个密切相关的方面，同一逻辑结构可以采用不同的物理存储结构实现，算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的物理存储结构。 有关数据结构的定义很多，具有典型代表性的有：①数据结构是一门研究非数值计算程序设计问题中计算机操作对象、对象间关系和施加在对象上一些操作的方法学。②数据结构按照某种逻辑关系将一批数据有效地组织起来，以有效合理的存储方式将它们存储在计算机中，并提供了定义在数据上的操作、运算集合。③数据结构是带有结构特性数据元素的集合，它研究数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。数据结构是构造复杂软件系统的基础方法，它的核心技术是分解与抽象。 数据结构是为应对日益增加的非数值计算问题而生的。今天计算机面对的求解问题有90%以上属于非数值计算问题，非数值计算已成为计算机应用的主流，其各种事务处理需求远远超过数值计算需求，处理的数据量非常庞大，数据之间的关系十分复杂，数据的控制和访问成为计算机资源的主要负荷。我们知道数值计算是使用计算机求解数学问题，进行精确或近似计算的方法与过程，它主要研究如何利用计算机更好地解决各种纯数学问题和应用数学问题，可能涉及迭代公式、大型线性或非线性方程组、复杂模型等。而非数值计算的处理对象包括自然界和人类社会的一切事物，如文字、表格、语言、事件、知识、事物的运动过程、状态的演变过程等，其处理和求解的问题很多无法用数学方程和数学模型加以描述。下面通过三个例子说明非数值计算问题中不同结构的数据对象。 首先，看一个地图多边形图形表达与分析问题的例子。图1.1所示为一个具有8个区域、10个多边形的图形，每个区域边界由多条关联链段首尾连接闭合而成，含分离岛屿的区域边界可能由多个多边形组成，复杂的区域边界可能还含有称之为“洞”的内嵌多边形。 为了对地图多边形图形进行分析处理，这里参照DIME模型（双重独立地图编码）组织和表达矢量多边形图形及其空间拓扑关系，以无冗余数据存储方式记录多边形边界链段，相邻多边形的共同边界链段只存储一次。链段作为构成区域多边形边界的基本要素由一组坐标表示，所有链段的坐标集合统一存储在一个顺序表中，如图1.2所示，左侧的关系和索引表除了指示每条链段在坐标顺序表中的起始位置和坐标数外，还通过链段的左区码和右区码表达链段与区域多边形的拓扑关系。可以看出，构成区域边界的多边形是一组有序的链段，构成链段的是一组有序的坐标对。因此，无论是链段-区域多边形之间还是链段坐标之间，都存在一种简单的线性关系，逻辑上适合釆用线性结构表达。 基于上述线-面拓扑关系，可以生成其他的拓扑关系，如点-线拓扑关系、点-面拓扑关系、面-线拓扑关系（图1.3）、面-面拓扑关系等，在此基础上还可以对多边形图形的面积进行量算，对多幅多边形图形进行空间叠置等空间分析处理。 其次，看一个状态空间表达与搜索求解8格拼图问题的例子。在一个3x3的9个网格中摆放1～8八个数字，空出一个格子，可以借助空格左右或上下移动邻近的数字，问题是找到一个合法的移动序列使网格中的数字分布呈现出某种目标格局。与8格拼图类似的还有15格拼图、24格拼图、35格拼图等复杂问题，图1.4给出了8格拼图问题的1种初态和4种目标状态，可选择其中1种目标状态（如终态1）进行问题求解。 在人工智能中求解这类问题釆用状态空间搜索方法，就是将问题的初态作为树或有根图的根结点，将初态所有可能的后继状态作为其下一层的扩展状态，初态指向后继状态的箭头表示对应的合法移动操作，在不产生已有状态的前提下继续向下扩展，直至出现目标状态，从初态到目标状态的路径即为问题的解。图1.5所示为上述8格拼图问题的前4层状态空间。 8格拼图问题的状态数为9！，实际求解过程中可采用一个状态评估函数挑选并扩展那些“有希望”的状态，以降低状态空间的扩展规模。显然，求解8格拼图问题过程中的数据对象及其关系结构一状态空间就是一种树形结构，这种非线性的结构也应用到计算机行棋博弈等人工智能问题的求解中。 *后，再看一个城市路网空间*短路径分析问题的例子。从城市道路上的某点乂出发驱车到目的地凡如图1.6所示，基于城市道路网系统，现要寻找一条行车路程*短的路径。求解这类问题首先需将城市道路网抽象成带权图（网络）的形式，再以适当的结构存储在计算机中。图是由顶点集合及顶点间的连接关系集合组成，图中的顶点代表城市路网中的交通节点（道路汇集点或端点），两个顶点间的连接关系（权值）用对应两个交通节点之间的一段道路长度表示。在此基础上，使用网络*短路径分析Dijkstra算法搜索获得点W到点B的*短路径，包括这条路径的长度和经过的道路路段序列。当然，该问题还可以扩展到求区域内任意两点之间的*优路径问题，包括通行时间*优（交通阻抗*小）、运输成本*优、通行代价*优等。 显然，这一问题面对的数据对象是城市路网中的交通节点和节点之间连接关系或连接强度。由于这种关系具有显著的结构特征，适合采用图模型这类数据结构表达和分析。图模型用于描述自然界和人类社会中的大量事物和事物之间的关系，带权图（即网络）可用于研究电网、交通网络、通信网络以及运筹学中的一些重要课题。 通过上面三个例子可以看出，非数值计算问题面对的数据对象或操作对象以及它们之间的关系有的具有线性特性，有的具有非线性特征，对于前者适合采用诸如线性表、队列和栈等一类的数据结构，对于后者适合采用诸如树、图等一类的数据结构。因此，数据结构是研究如何表达非数值计算程序设计问题中操作对象、对象间关系以及相适应的对象运算与操作方法的科学。由此可见，数据结构与程序设计之间有密不可分的关系，正像图灵奖获得者尼古拉斯 沃斯在他的经典著作中指出的那样：“程序的构成和数据结构是两个不可分割的联系在一起的问题。”关于数据结构对程序设计的重要基础作用，另一位图灵奖获得者托尼 霍尔有句名言：“不了解施加在数据上的算法，就无法构造数据;反之，算法的结构和选择却常常在很大程度上依赖于作为基础的数据结构。” 20世纪70年代末80年代初，国内高校计算机专业相继开设“数据结构”课程，并作为程序设计方法学、操作系统、编译原理、数据库、软件工程等课程的重要基础。随着计算机应用领域的扩大，“数据结构”已不仅是计算机专业的核心课程，也成为其他涉及信息科学和技术的非计算机专业（如地理信息科学各专业）的必修或选修课程。 1.2基本术语 1.数据 数据（data）简言之是信息的载体，是信息在计算机中的表示形式或编码形式，是描述客观世界各种事物的数字、字符以及所有能输入到计算机并能够被计算机识别、存储和加工处理的符号集合的总称。例如通过专业设备接收、采集、探测到的天文信息、气象信息、水文信息、环境信息、地震信息、潮汐信息等，必须表示成具有一定格式和精度的数据形式才能被计算机所输入接受和分析处理。科学计算程序处理的对象是整数、实数或复数（实数对），文字处理软件处理的对象是字符串，地形分析软件处理的对象是数字高程模型等。 2.数据元素 数据元素（data element）是数据的基本单位，也是计算机访问和处理的基本单位，数据元素也可简称为元素、记录、结点等。数据元素可以为简单元素，如整型、实型、字符型数据元素，也可以是由若干数据项构成的复合元素，如学生注册信息表中的学生记录包括学号、姓名、性别、民族、出生日期、出生地、院系、专业等信息；水文管理软件处理的水文站点观测记录包括水位、流速、流向、流量、水温、含沙量、水质等信息；气象分析中心处理的气象台站的观测记录包括气温、气压、湿度、降水量、蒸发量、风向、风速等。 3.数据项 数据项（data item）是具有独立含义的数据，是数据元素中的*小标识单位或不可分割*小成分，也称为字段或域（field）。对于简单数据元素，数据元素本身就是其唯一的数据项；对于复合数据元素，如上述学生记录中的学号等、水文观测记录中的水位等、气象观测记录中的降水量等均是所在数据元素的数据项。 4.数据对象 数据对象（data object）是具有一定关系且性质相同数据元素的集合，如用于描述客观事物发展演变过程的某一数据元素序列。当然，如果单个数据元素能够完整描述客观实体或事物，则也可称为数据对象。从面向对象程序设计角度来看，数据对象是类的实例。在类的声明中包括其所有属性（成员数据）和可用的操作定义，所以数据对象是属性集合和方法集合构成的封装体。 5.抽象数据类型 抽象数据类型（abstract data type，ADT）是描述数据结构的一种理论工具，它使人们能够独立于程序的实现细节来理解数据结构的特性，抽象数据类型的主要作用是数据封装和信息隐藏，让实现与使用相分离。数据及其相关操作的结合称为数据封装，即隐藏对象的属性和实现细节，仅对外公开接口。抽象数据类型也可看作是对数据类型的进一步抽象，即把数据类型和数据类型上的运算结合并封装在一起。可以看出，抽象数据类型的概念与面向对象方法的思想是一致的。抽象数据类型独立于运算的具体实现，使用户程序只能通过抽象数据类型定义的某些操作来访问其中的数据，实现了信息隐藏。抽象数据类型定义的过程和函数以该抽象数据类型的数据所应具有的数据结构为基础。 抽象数据类型由用户定义，是用于表示应用问题的数据模型。抽象数据类型不像C语言中结构类型及其操作那样，数据结构和数据相关操作分别定义，而是把数据成分和一组相关操作封装在一起。在面向对象的程序设计语言C++、Java中抽象数据类型可以用“类”直接描述，而在C语言中没有适当的机制描述抽象数据类型。 顾及本书读者的适用面，本书不要求读者必须完全掌握C++或Java程序设计语言，但需有所了解，本书在以后章节中将不采用抽象数据类型描述的形式定义数据结构及其算法。考虑到算法描述的严谨性、完整性和可读性，本书中的算法采用C/C++描述，涉及部分C++的非面向对象特征、概念及功能，如函数原型接口风格、函数名重载、函数参数的缺省值、函数的引用参数、new和delete运算符、const类型说明符、显式类型转换等。
书友推荐
- >
山海经
山海经
¥13.6¥68.0 - >
我从未如此眷恋人间
我从未如此眷恋人间
¥21.4¥49.8 - >
苦雨斋序跋文-周作人自编集
苦雨斋序跋文-周作人自编集
¥6.9¥16.0 - >
诗经-先民的歌唱
诗经-先民的歌唱
¥12.3¥39.8 - >
罗庸西南联大授课录
罗庸西南联大授课录
¥13.8¥32.0 - >
小考拉的故事-套装共3册
小考拉的故事-套装共3册
¥36.7¥68.0 - >
名家带你读鲁迅:故事新编
名家带你读鲁迅:故事新编
¥13.0¥26.0 - >
新文学天穹两巨星--鲁迅与胡适/红烛学术丛书(红烛学术丛书)
新文学天穹两巨星--鲁迅与胡适/红烛学术丛书(红烛学术丛书)
¥9.9¥23.0
本类畅销
-
2022图书×抽奖盲袋
¥9.9¥25 -
2023读书月阅读盲盒——天黑，闭眼，刀谁？
¥42.3¥158 -
-
2022读者节纪念徽章-三星会员专属
¥45¥45.6 -
2023读书月阅读盲盒——我什么场面没见过？
¥42.3¥158 -
2023读书月阅读盲盒——去码头整点什么薯条？
¥42.3¥158
