数据结构及其空间数据应用

第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类型说明符、显式类型转换等。