空间数据结构

第五章空间数据结构

数据结构即指数据组织的形式，是适合于计算机存储、管理和处理的数据逻辑结构。地理信息系统空间数据结构是指空间数据在系统内的组织和编码形式（GIS数据结构也可称为图形数据格式），它是指适合于计算机系统存储、管理和处理地理图形的逻辑结构。GIS中，空间数据一般有着较为复杂的数据结构，目前，主要有两种数据模型表示空间数据，即矢量数据模型和栅格数据模型。

4.1 栅格数据结构

4.1.1概述

栅格数据是计算机和其它信息输入输出设备广泛使用的一种数据模型，如电视机、显示器、打印机等的空间寻址。甚至专门用于矢量图形的输入输出设备，如数字化仪、矢量绘图仪及扫描仪等，其内部结构实质上是栅格的。遥感数据也是采用特殊扫描平台获得的栅格数据。

栅格数据就是用数字表示的像元阵列，其中，栅格的行和列规定了实体所在的坐标空间，而数字矩阵本身则描述了实体的属性或属性编码。栅格数据最显著的特点就是存在着最小的、不能再分的栅格单元，在形式上常表现为整齐的数字矩阵，因而便于计算机进行处理，特别是存储和显示。

4.1.2编码方案

以图4-1为例，介绍几种编码方法的编码思路、方案和特点。

图4-1 栅格数据结构

1. 游程长度编码

地理数据往往有较强的相关性，也就是说相邻象元的值往往是相同的。游程长度编码的基本思想是：按行扫描，将相邻等值的象元合并，并记录代码的重复个数。游程长度编码的数据结构: 行号,属性,重复次数。图4-1的游程长度编码为：

1,A,4,R,1,A,6…

对于游程长度编码，区域越大，数据的相关性越强，则压缩越大。其特点是，压缩效率较高，叠加、合并等运算简单，编码和解码运算快。

2. 块式编码

块式编码是将游程扩大到二维情况，把多边形范围划分成若干具有同一属性的正方形，然后对各个正方形进行编码。块式编码的基本思想：由初始位置（行列号）、半径和属性代码组成。图4-1的块状编码为：

(1,1,3,A),(1,5,1,R),(1,6,2,A),…

块状编码对大而简单的多边形更为有效，对一些虽不较多的复杂多边形效果并不好。块状编码在合并、插入、检查延伸型、计算面积等操作时有明显的优越性，而对某些运算不适应，必须在转换成简单的数据形式才能顺利进行运算。

3. 四叉树编码

四叉树编码是最有效的栅格数据压缩编码方法之一，是一种可变分率的非均匀网格系统，在GIS中有广泛的应用。其基本思路为：2n×2n象元组成的图像(不

足的用背景补上)按四个象限进行递归分割，直到子象限的数据单调为止,最后得到一棵四分叉的倒向树（图4-1）。四叉树有两种,一种是常规四叉树,在子节点与父节点之间设立指针,由于指针占用空间较大,难以达到数据压缩的目的。所以，常规四叉树并不广泛用于存储数据，其价值在于建立索引文件，进行数据检索。另一种是线性四叉树,它不需要记录中间节点和使用指针,仅记录叶节点,并用地址码表示叶节点的位置。因而,线性四叉树广泛应用于数据压缩和GIS 中的数据结构。下面介绍最常用的线性四叉树编码。

图4-1 四分叉的倒向树

线性四叉树编码的基本思想是：不需记录中间结点和使用指针，仅记录叶结点，并用地址码（定位码、Morton 码）表示叶结点的位置——深度（几次分割）和属性。为了得到线性四叉树的地址码，首先将二维栅格数据的行列号转化为二进制数，然后交叉放入Morton 码中，即为线性四叉树的地址码。实质上是按左上、右上、左下、右下的顺序，从零开始对每个栅格进行自然编码。这样，在一个2n ×2n 的图像中，每个像元点都给出一个Morton 码，当n ＝3时即为(表3—1)：

表3—1 Morton 码

行

这样就可将用行列表示的二维图像，用Morton码写成一维数据，通过Morton 码就可知道象元的位置。把一幅2n×2n的图像压缩成线性四叉树的过程为：

1、按Morton码把图象读入一维数组。第一维为Morton码，第二维为象元值。

2、相邻的四个象元比较，一致的合并，只记录第一个象元的Morton码。循环比较所形成的大块，相同的再合并，直到不能合并为止。

3、进一步用游程长度编码压缩。压缩时只记录第一个象元的Morton码。

解码时，根据Morton码就可知道象元在图像中的位置(左上角)，本Morton 码和下一个Morton码之差即为象元个数。知道了象元的个数和象元的位置就可恢复出图像了。

4.1.3栅格数据结构的特点

（1）离散的量化栅格值表示空间对象

（2）位置隐含,属性明显

（3）几何和属性偏差

（4）数据结构简单,易于遥感数据结合,但数据量大

（5）面向位置的数据结构,难以建立空间对象之间的关系

此外，栅格数据存在着的“最小数据单元”，非常适宜于地理信息的“模型化”。因为无论怎样复杂的模型算法，在一个栅格单元内就成为了纯粹的属性运算。

4.2 矢量数据结构

4.1.1概述

矢量数据结构是另一种常见的图形数据结构，它是用一系列有序的x、y坐标对表示地理实体的空间位置。GIS的矢量数据模型可以用相对较少的数据量，记录大量的地理信息，而且精度高，制图效果好，在地理信息系统发展早期，受计算机存储能力及计算速度的限制，其扮演了更为重要的角色，是地理信息系统基本的数据模型之一。矢量型数据结构按其是否明确表示各地理实体的空间相互关系可分为实体型（简单的数据结构）和拓扑型（拓扑数据结构）两大类。

4.1.2实体型数据结构

实体型数据结构通常以坐标来定义：一个点的位置可以二维或者三维中的坐标的单一集合来描述。一条线通常由有序的两个或者多个坐标对集合来表示。一个面通常由一个边界来定义，而边界是由形成一个封闭的环状的一条或多条线所组成。我们又把这种结构称为“面条”（SPAGHETTI）结构。

实体型编码的优点结构简单、直观，编码容易；缺点：①数据冗余，相邻多边形的公共边易产生分歧；②实体互相独立，缺乏联系。代表商用软件Arcview3.2的shapefile数据格式为实体型数据结构。

4.1.3拓扑型数据结构

带有拓扑结构的编码方法，我们称之为拓扑型编码。双重独立编码是著名的拓扑编码结构，这种数据结构最早是由美国人口统计局研制来进行人口普查分析和制图的，简称为DIME(Dual lndependent Map Encoding)系统或双重独立式的地图编码法。它以城市街道为编码的主体。其特点是采用了拓扑编码结构。

双重独立式数据结构是对图上网状或面状要素的任何一条线段，用其两端的节点及相邻面域来予以定义。例如对图4-3所示的多边形数据，用双重独立数据结构表示如表4-1所示。我们在前面已经介绍过了拓扑结构表以及其描述的空间关系，这里不在赘述。

图4-3 多边形原始数据

拓扑型代表软件为ARC/INFO，Coverage是ESRI公司在公布Shapefile文件格式之后，推出的又一矢量数据的存贮格式，其特点是拓扑型的数据编码。目前ArcGIS中仍然有一些分析操作只能基于这种数据格式进行操作。

实体型与拓扑型数据结构各有特点：（1）实体型虽然会产生数据冗余和歧异，但易于编辑；（2）拓扑型消除了数据的冗余和歧异，但操作复杂，甚至会产生新的数据冗余。

4.1.4矢量数据结构的特点

（1）用离散的点描述空间对象与特征，定位明显，属性隐含

（2）用拓扑关系描述空间对象之间的关系

（3）面向目标操作，精度高，数据冗余度小

（4）与遥感等图象数据难以结合

（5）输出图形质量号，精度高

4.3 本章小结

通过对空间数据两种主要数据结构的介绍，我们可以把这两种数据结构比较如下：

（1）矢量模型用(x,y)坐标来代表地理对象，而栅格模型通过单元的行和列值来确定位置。

（2）矢量模型精确地表现地理对象的形状，而栅格模型用小的矩形即单元(Cell)组合构成，因此精度上不如矢量模型高。

（3）利用矢量模型进行空间分析的过程比较复杂，而栅格模型则在此方面有优势。

（4）矢量模型中的地理对象容易与多种专题属性信息产生关联，而栅格模型只能给相应的位置联接一种属性。

选择何种数据结构存贮空间数据，需要结合特定的分析和应用来决定。

数据结构概述

教材：《数据结构》严蔚敏吴伟民清华大学出版社 《数据结构算法实现及解析》高一凡西安电子科技大学出版社 第一部分数据结构概述 一、定义（研究是数据结构的存储和数据的操作的） 如何把现实中大量而复杂的问题以特定的数据类型和特定的存储结构保存到主存储器（内存）中，以及在此基础上为实现某个功能（比如查找某个元素，删除某个元素，对所有元素进行排序）而执行的相应操作，这个相应的操作也叫做算法。 数据结构= 个体的存储（从某个角度而言，可忽略）+ 个体与个体之间关系的存储（核心） 算法= 对存储数据的操作 二、算法 解题的方法和步骤 衡量算法的标准 1.时间复杂度 大概程序要执行的次数，而非执行的时间 2.空间复杂度 算法执行过程中大概所占用的最大内存 3.难易程度（即可读性） 4.健壮性 三、数据结构的地位 数据结构是软件中最核心的内容 程序= 数据的存储+ 数据的操作+ 可以被计算机执行的语言 第二部分预备知识 一、指针

指针的重要性：指针是C语言的灵魂 定义 地址：内存单元的编号 从零开始的非负整数 范围：0--FFFFFFFF（即0--4G-1） 指针： 指针就是地址，地址就是指针 指针变量是存放内存单元地址的变量 指针的本质是一个操作受限的非负整数（只能进行减运算）分类： 1.基本类型的指针 2.指针和一维数组的关系 二、结构体 为什么会出现结构体 为了表示一些复杂的数据，而普通的基本类型变量无法满足要求什么叫结构体 结构体是用户根据实际需要自己定义的数据类型 如何使用结构体 两种方式： struct Student st = {1000, "zhangsan", 20} struct Student * pst = &st; 1.st.sid 2.pst->sid pst所指向的结构体变量中的sid这个成员

空间数据组织与管理

空间数据组织空间数据管理

?空间数据结构 ●矢量数据结构●栅格数据结构 ?矢量、栅格结构对比?空间数据库特点 ?传统数据库模型及特点 ●层次数据模型●网络数据模型●关系数据模型 ?现行空间数据库管理方案 ●混合数据管理模式●扩展数据管理模式●统一数据管理模式 空间数据组织与管理

定义： ?矢量数据结构通过记录空间对象的坐标及空间关系来表达空间对象的位置。?点：空间的一个坐标点；?线：多个点组成的弧段； ?面：多个弧段组成的封闭多边形； 获取方法 ?定位设备（全站仪、GPS 、常规测量等）?地图数字化?间接获取 ●栅格数据转换 ●空间分析（叠置、缓冲等操作产生的新的矢量数据） 矢量数据表达考虑内容 ?矢量数据自身的存储和管理?几何数据和属性数据的联系 ?空间对象的空间关系（拓扑关系） 矢量数据表达 ?简单数据结构?拓扑数据结构?属性数据组织 矢量数据结构

矢量数据表达—简单数据结构 只记录空间对象的位置坐标和属性信息，不记录拓扑关系。又称面条结构。 存储： ?独立存储：空间对象位置直接跟随空间对象；?点位字典：点坐标独立存储，线、面由点号组成 特征 ●无拓扑关系，主要用于显示、输出及一般查询 ●公共边重复存储，存在数据冗余，难以保证数据独立性和一致性 ●多边形分解和合并不易进行，邻域处理较复杂；●处理嵌套多边形比较麻烦 适用范围： 制图及一般查询，不适合复杂的空间分析 量数据结构（续）

标识码属性码空间对象编码唯一 连接几何和属性数据 数据库 独立编码 点: ( x ,y ) 线: ( x 1 , y 1 ) , (x 2 , y 2 ) , … , ( x n , y n )面: ( x 1, y 1) , (x 2, y 2) , …, ( x 1, y 1) 点位字典 点: 点号文件 线: 点号串面: 点号串 点号X Y 1112223344………n 55 66 存储方法 量数据结构（续）

数据结构复习提纲(整理)

复习提纲 第一章数据结构概述 基本概念与术语（P3） 1．数据结构是一门研究非数值计算程序设计问题中计算机的操作对象以及他们之间的关系和操作的学科. 2．数据是用来描述现实世界的数字,字符,图像,声音,以及能够输入到计算机中并能被计算机识别的符号的集合 2．数据元素是数据的基本单位 3．数据对象相同性质的数据元素的集合 4．数据结构包括三方面内容:数据的逻辑结构.数据的存储结构.数据的操作. （1）数据的逻辑结构指数据元素之间固有的逻辑关系. （2）数据的存储结构指数据元素及其关系在计算机内的表示 ( 3 ) 数据的操作指在数据逻辑结构上定义的操作算法,如插入,删除等. 5.时间复杂度分析 -------------------------------------------------------------------------------------------------------------------- 1、名词解释：数据结构、二元组 2、根据数据元素之间关系的不同，数据的逻辑结构可以分为 集合、线性结构、树形结构和图状结构四种类型。 3、常见的数据存储结构一般有四种类型，它们分别是___顺序存储结构_____、___链式存储结构_____、___索引存储结构_____和___散列存储结构_____。 4、以下程序段的时间复杂度为___O(N2)_____。 int i,j,x; for(i=0;i

空间数据结构

空间数据结构 摘要：空间数据模型和空间数据结构是地理信息系统（GIS）课题的中心内容。本文对空间数据结构的定义、分类进行了一定的研究性的归纳与总结。 关键词：空间数据结构，矢量数据，栅格数据 引言 GIS中空间数据结构和空间数据模型是紧密相关的。数据模型的建立必须通过一定的数据结构，但两者之间也有非常大的区别。数据模型是一个总得概念，是人为概念化的真实，是对现实世界的提取，对现实世界的认识和选择。而数据结构指数据元素之间的相互关系，它是软件常规内涵，根据空间数据结构和数据模型的特点及其关系，可以建立空间数据库系统。 空间数据结构定义 空间数据结构是带有空间数据单元的集合。这些数据单元是数据的基本单 位，一个数据单元可以有几个数据项组成，数据单元之间存在某种联系叫做结构。 所以，研究空间数据结构，是指空间目标间的相互关系，包括几何和非几何的关 系，数据结构是数据模型的表述，数据结构往往通过一系列的图表和矩阵，以及 计算机码的数据记录来说明。 空间数据结构的分类 矢量数据结构 定义 矢量数据结构是基于矢量模型，利用欧几里得(EUCLID)几何学中的点、线、 面及其组合体来表示地理实体的空间分布，是通过记录坐标的方式，尽可能精确 地表示点线多边形等地理实体，自然地理实体的位置是用其在坐标参考系中的空 间位置来定义的，坐标空间设为连续，允许任意位置长度和面积的精确定义，其 特点是定位明显，属性隐含。 GIS采用的矢量数据结构模型，是将空间地质实体抽象成点、线、面三种几 何要素，矢量数据结构通过优化拓扑结构表达空间实体的相关关系，为空间数据 库建立基本框架。 矢量数据结构的特点 优点：数据按照点、线或多边形为单元进行组织，结构简单、直观、易实现 以实体为单位的运算和显示。 缺点：

ArcGis数据结构转换

ArcGis数据结构转换 地理信息系统的空间数据结构主要有栅格结构和矢量结构，它们是表示地理信息的两种不同方式。栅格结构是最简单最直观的空间数据结构，又称为网格结构（raster或grid cell）或象元结构（pixel），是指将地球表面划分为大小均匀紧密相邻的网格阵列，每个网格作为一个象元或象素，由行、列号定义，并包含一个代码，表示该象素的属性类型或量值，或仅仅包含指向其属性记录的指针。因此，栅格结构是以规则的阵列来表示空间地物或现象分布的数据组织，组织中的每个数据表示地物或现象的非几何属性特征。矢量结构是通过记录坐标的方式尽可能精确地表示点、线、多边形等地理实体。在地理信息系统中栅格数据与矢量数据各具特点与适用性，为了在一个系统中可以兼容这两种数据，以便有利于进一步的分析处理，常常需要实现两种结构的转换。 1.栅格数据向矢量数据的转换 栅格向矢量转换处理的目的，是为了将栅格数据分析的结果，通过矢量绘图装置输出，或者为了数据压缩的需要，将大量的面状栅格数据转换为由少量数据表示的多边形边界，但是主要目的是为了能将自动扫描仪获取的栅格数据加入矢量形式的数据库。 由栅格数据可以转换为3种不同的矢量数据，分为点状、线状和面状的矢量数据。下面以栅格数据转换为面状矢量数据为例进行说明，其他两种转换操作大同小异，这里不再具体说明。 （1）展开Conversion Tools工具箱，打开From Raster 工具集，双击Raster to Polygon，打开Raster to Polygon对话框（图1）。 图1 Raster to Polygon对话框 （2）在Input raster文本框中选择输入需要转换的栅格数据。 （3）在Output Polygon Features文本框键入输出的面状矢量数据的路径与名称。 （4）选择Simplify Polygons按钮（默认状态是选择），可以简化面状矢量数据的边界形状。（5）单击OK按钮，执行转换操作。

数据结构习题集

1 概述 一、选择题： 1、下列算法的时间复杂度是（） for(i=0;i

(完整版)数据结构概论

数据结构概论考核题

C. 0 1 3 2 D.0 3 1 2 （第9题配图：数组的下标为0,1,2,3） 10.对于哈希函数H(key)=key%13,被称为同义词的关键字是( D ) A.35和41 B.23和39 C.15和44 D.25和51 11.图的深度优先遍历类似于二叉树的( A ) A.先序遍历 B.中序遍历 C.后序遍历 D.层次遍历 12.下述几种排序方法中，稳定的排序算法是( A ) A.直接插入排序 B.快速排序 C.堆排序 D.希尔排序 13.依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位 置上的方法，称为( C ) A.希尔排序 B.冒泡排序 C.插入排序 D.选择排序 14.二叉树是非线性数据结构，所以 ( A ) A.它不能用顺序存储结构存储 B.它不能用链式存储结构存储 C.顺序存储结构和链式存储结构都能存储 D.顺序存储结构和链式存储结构都不能使用 15.有8个结点的无向图最多有( B )条边。 A.14 B.28 C.56 D.112 二、填空题（每小题1分，共15分） 1 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的__时间复杂度______。 2 设数组a[M](M为最大空间个数)作为循环队列Q的存储空间，front为队头指针(指向第一个存

（3）重复（2），直到U=V为止。 此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。 2. 假设通信电文使用的字符集为{a,b,c,d,e,f,g}，若这些字符在电文中出现的频度分别为：3， 35，13，15，20，5和9，分别求出这些字符的等长编码以及哈夫曼编码，并比较他们的编码长度。

《空间数据结构基础》第四讲习题参考答案

《空间数据结构基础》第四讲习题参考答案 一、判断题（在正确说法的题后括号中打“√”，错误说法的题后括号中打“×”） 1、KMP算法的特点是在模式匹配时指示主串的指针不会变小。( √ ) 2、串是一种数据对象和操作都特殊的线性表。( √ ) 3、只包含空白字符的串称为空串。( × ) 4、稀疏矩阵压缩存储后，必会失去随机存取功能。( × ) 5、使用三元组表示稀疏矩阵的非零元素能节省存储空间。( √ ) 6、插入与删除操作是数据结构中最基本的两种操作，因此这两种操作在数组中也经常使用。（×） 7、若采用三元组表存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算。（×） 二、单项选择题 1．下面关于串的的叙述中，哪一个是不正确的？（ B ） A．串是字符的有限序列B．空串是由空格构成的串 C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储 2．有串S1=’ABCDEFG’，S2 = ’PQRST’，假设函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回中s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（ D ）。 A．BCDEF B．BCDEFG C．BCPQRST D．CDEFGFG 3、串的长度是指（ B ） A．串中所含不同字母的个数B．串中所含字符的个数 C．串中所含不同字符的个数D．串中所含非空格字符的个数 三、填空题 1、串是一种特殊的线性表，其特殊性表现在数据元素为字符，操作集也不同；两个串相等的充分必要条件是两串的长度相等且两串中对应位置的字符也相等。 2、设正文串长度为n，模式串长度为m，则串匹配的Brute－Force算法的时间复杂度为 O(m*n) ；KMP算法的时间复杂度为 O(m+n) 。 3、已知数组A[0..9,0..9]的每个元素占5个存储单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[6，8]的地址为 1340 。 四、综合题 1、KMP算法较Brute-Force算法有哪些改进? 【参考解答】

第二章 空间数据结构和空间数据库

第二章空间数据结构和空间数据库本章概述：地理信息系统的操作对象是空间地理实体，建立一个地理信息系统的首要任务是建立空间数据库，即将反映地理实体特性的地理数据存储在计算机中，这需要解决地理数据具体以什么形式在计算机中存储和处理即空间数据结构问题和如何描述实体及其相互关系即空间数据库模型问题。本章重点介绍主要的空间数据结构和空间数据库模型。 §2.1 地理实体及其描述 介绍地理实体的概念，地理实体需要描述的内容，实体的空间特征和实体间的空间关系。 §2.2 矢量数据结构 讲述矢量数据的图形表示、获取方式和表示(即矢量编码方法)。§2.3 栅格数据结构 讲述栅格数据的图形表示、栅格数据的组织、栅格结构的建立和栅格数据的表示。 §2.4 矢量栅格一体化数据结构

针对矢量栅格数据结构互为优缺点状况，介绍集两者优点为一体的矢量栅格一体化数据结构的概念和具体数据结构设计方法。 §2.5 三维数据结构 主要阐述基于栅格的八叉树三维数据结构的基本原理和存储结构。在矢量结构方面，介绍常用的三维边界表示法的方法原理、特点和应用。§2.6 空间数据模型 首先介绍数据库有关基础知识，传统数据模型如何存储图形数据及其局限性，重点阐述面向对象技术、面向对象模型和用于地理信息系统的空间数据库管理系统的类型。 §2.7 空间数据库的设计、建立和维护 介绍空间数据库的设计的内容、建立过程和维护方法。 您可能还想看前贴【GIS原理学习（一）】【GIS原理学习（二）】【GIS 原理学习（三）】【GIS原理学习（四）】 §2.1 地理实体及其描述 地理信息系统是以地理实体作为描述、反映现实世界中空间对象的单体。在地理信息系统中需要描述地理实体的名称、位置、形状、功能等内容，这些内容反映了地理实体的时间、空间和属性三种特性，其中空

第1章概论答案 数据结构 田鲁怀著

第一章概论自测题答案 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象 以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合， R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4.数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11.一个算法的效率可分为时间效率和空间效率。

二、单项选择题 （B）1. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一关系 （ C ）2. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理C) 逻辑D) 物理和存储 （C）3. 算法分析的目的是： A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性 （A）4. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性B) 正确性和简明性 C) 可读性和文档性D) 数据复杂性和程序复杂性 （ C ）5. 计算机算法指的是： A) 计算方法B) 排序方法 C) 解决问题的有限运算序列D) 调度方法 （B）6. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性D) 易读性、稳定性和安全性 三、简答题 2.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素。数据类型不仅定义了一组带结构的数据元素，而且还在其上定义了一组操作。

实用数据结构基础第四版课后习题

一、判断题 （第一章绪论） 1.数据元素是数据的最小单元。 答案：错误 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的基本运算集构成的整体。 答案：错误 3.数据的存储结构是数据元素之间的逻辑关系和逻辑结构在计算机存储器内的映像。 答案：正确 4.数据的逻辑结构是描述元素之间的逻辑关系，它是依赖于计算机的。 答案：错误 5.用语句频度来表示算法的时间复杂度的最大好处是可以独立于计算机的软硬件，分析算法的时间 答案：正确 （第二章线性表） 6.取顺序存储线性表的第i个元素的时间同i的大小有关。 答案：错误 7.线性表链式存储的特点是可以用一组任意的存储单元存储表中的数据元素。 答案：正确 8.线性链表的每一个节点都恰好包含一个指针域。 答案：错误 9.顺序存储方式的优点的存储密度大，插入和删除效率不如练市存储方式好。 答案：正确 10.插入和删除操作是数据结构中最基本的两种操作，所以这两种操作在数组中也经常使用。答案：错误 （第三章栈） 11.栈是一种对进栈和出栈作了限制的线性表。 答案：错误 12.在C（或C++）语言中设顺序栈的长度为MAXLEN，则top=MAXLEN表示栈满。 答案：错误 13.链栈与顺序栈相比，其特点之一是通常不会出现满栈的情况。 答案：正确 14.空栈就是所有元素都为0上的栈。 答案：错误 15.将十进制数转换为二进制数是栈的典型应用之一。 答案：正确 （第四章队列） 16.队列式限制在两端进行操作的线性表。 答案：正确 17.判断顺序队列为空的标准是头指针和尾指针都指向同一结点。 答案：错误 18.在循环链列队中无溢出现像。 答案：错误 19.在循环队列中，若尾指针rear大于头指针front，则元素个数为rear-front。 答案：正确

空间数据的组织模板可修订

实验一空间数据的组织 一、实验目的 1. 熟悉ArcGIS的工作环境 2. 掌握创建Shapefile文件、Coverage文件等基本数据文件的操作 3. 掌握ArcGIS进行图像配准、数字化、编辑、获取顶点坐标等基本操作的方法 4 了解矢量数据结构的索引编码或拓扑编码的方法 5. 了解为某地区地块建立拓扑关系的方法 二、主要实验器材（软硬件、实验数据等） 计算机硬件：性能较高的PC机 计算机软件：ArcGIS9.3软件 实验数据：《ArcGIS地理信息系统空间分析实验教程》随书光盘的第三章等 三、实验内容与要求 1 ArcGIS基本操作练习 操作指导见《ArcGIS地理信息系统空间分析实验教程》第二章p15-35。 实验数据具体见《ArcGIS地理信息系统空间分析实验教程》随书光盘\ch3\EX1。 要求： （1）了解ArcMap的窗口组成 ArcMap窗口主要由主菜单、标准工具栏、内容表、显示窗口、绘图工具和状态 条等六部分组成。 I、主菜单：主要有File、Edit、View、Bookmarks、Insert、Selection、Tool、 Windows和Help等9个子菜单。如图1.1。 图1.1 ArcMap的主菜单 II、标准工具栏:标准工具栏共有17个按钮，前面10个按钮为通用的软件功能 按钮，后面7个依次为加载地图、设置显示比例、调用编辑工具、启动ArcCatalog、 启动ArcToolbox、启动命令和调用实时帮助等按钮，如图1.2。 图1.2 ArcMap的标准工具栏 III、窗口内容表：主要显示地图所包含的数据组、数据层、地理要素及其显示 状态。可以控制数据组、数据层的显示与否，可以设置地理要素的显示方法。 内容表有三种状态：地图要素显示状态[图1.3(a）]、地图数据源显示状态[图 1.3(b）]、数据选择状态[图1.3(c）]。

数据结构复习资料复习提纲知识要点归纳

第一章数据结构概述 基本概念与术语 1．数据：数据是用来描述现实世界的文字，字符，图像，声音，以及能够输入到计算机中并能被计算机处理的符号。 2.数据元素：数据元素是数据的基本单位，是数据这个集合中的个体，也称之为元素，结点，顶点记录。 （补充：一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。）3．数据对象：数据对象是具有相同性质的数据元素的集合，是数据的一个子集。（有时候也叫做属性。） 4．数据结构：数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 （1）数据的逻辑结构：数据的逻辑结构是指数据元素之间存在的固有逻辑关系，常称为数据结构。 数据的逻辑结构是从数据元素之间存在的逻辑关系上描述数据与数据的存储无关，是独立于计算机的。 依据数据元素之间的关系，可以把数据的逻辑结构分成以下几种： a.集合：数据中的数据元素之间除了“同属于一个集合“的关系以外，没有其他关系。 b.线性结构：结构中的数据元素之间存在“一对一“的关系。若结构为非空集合，则除了第一个元素之外，和最后一个元素之外，其他每个元素都只有一个直接前驱和一个直接后继。 c.树形结构：结构中的数据元素之间存在“一对多“的关系。若数据为非空集，则除了第一个元素（根）之外，其它每个数据元素都只有一个直接前驱，以及多个或零个直接后继。 d.图状结构：结构中的数据元素存在“多对多”的关系。若结构为非空集，折每个数据可有多个（或零个）直接后继。 （2）数据的存储结构：数据元素及其关系在计算机内的表示称为数据的存储结构。 想要计算机处理数据，就必须把数据的逻辑结构映射为数据的存储结构。逻辑结构可以映射为以下两种存储结构： a.顺序存储结构：把逻辑上相邻的数据元素存储在物理位置也相邻的存储单元中，借助元素在存储器中的相对位置来表示数据之间的逻辑关系。 b.链式存储结构：借助指针表达数据元素之间的逻辑关系。不要求逻辑上相邻的数据元素物理位置上也相邻。 5.时间复杂度分析：a.常量阶：算法的时间复杂度与问题规模n无关系T(n)=O(1) b.线性阶：算法的时间复杂度与问题规模n成线性关系T(n)=O(n) c.平方阶和立方阶：一般为循环的嵌套，循环体最后条件为i++ 时间复杂度的大小比较： O(1)< O(log 2 n)< O(n )< O(n log 2 n)< O(n2)< O(n3)< O(2 n )

第一部分数据结构概论及算法分析答案

第一部分数据结构概论及算法分析 一、选择题 1．数据结构是一门研究计算机中__ __对象及其关系的学科。 （1）数值运算（2）非数值运算（3）集合（4）非集合 2．数据结构的定义为(K，R)，其中K是__ __的集合。 （1）算法（2）数据元素（3）数据操作（4）逻辑结构 3．算法分析的目的是____。 （1）找出数据结构的合理性（2）研究算法中输入和输出的关系 （3）分析算法的效率以求改进（4）分析算法的易懂性和文档性 4. 数据的不可分割的基本单位是_ ___。 A.元素 B.结点 C.数据类型 D.数据项 5．下列算法suanfa2的时间复杂度为____。 int suanfa2(int n) { int t=1； while(t<=n) t=t*2； return t； } (log2n) (2n) (n2) (n) 6.（）是具有相同特性数据元素的集合，是数据的子集。 A 数据符号 B 数据对象 C 数据 D 数据结构 7．与数据元素本身的形式、内容、相对位置、个数无关的是数据的( )。 A. 存储结构 B. 逻辑结构 C. 算法 D. 操作 8．数据结构是研究数据的（）及它们之间的相互联系。 A、理想结构，物理结构b、理想结构，逻辑结构 C、物理结构，逻辑结构d、抽象结构，逻辑结构 9．组成数据的基本单位是（）。 a、数据项 b、数据类型 c、数据元素 d、数据变量 10．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：

（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构11．算法指的是（） A．计算机程序B．解决问题的计算方法 C．排序算法D．解决问题的有限运算序列 12．下列算法suanfa1中语句"x=x*2；"的执行次数是（）。 void suanfa1(int n) { int i,j,x=1； for(i=1；i<=n；i++) for(j=i；j<=n；j++) x=x*2； printf("%d",x)； } (n-1)/2 (n+1)/2 C.n2 D.?nlog2n? 13. 由____组成的集合是一个数据对象。 A.不同类型的数据项 B.不同类型的数据元素 C.相同类型的数据项 D.相同类型的数据元素 14．在下列选项中，哪个不是一个算法一般应该具有的基本特征_____。 A. 确定性 B. 可行性 C. 无穷性 D. 拥有足够的情报15．在计算机中，算法是指______。 A. 查询方法 B. 加工方法 C. 解题方案准确而完整的描述 D. 排序方法16．算法的时间复杂度是指________。 A. 执行算法程序所需要的时间 B. 算法程序的长度 C. 算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数17．算法的空间复杂度是指________。 A. 算法程序的长度 B. 算法程序中的指令条数 C. 算法程序所占的存储空间 D. 算法执行过程中所需要的存储空间18．下面叙述正确的是_______。 A. 算法的执行效率与数据的存储结构无关 B. 算法的空间复杂度是指算法程序中指令（或语句）的条数 C. 算法的有穷性是指算法必须能在执行有限个步骤之后终止 D. 以上三种描述都不对 19．数据的存储结构是指______。

空间数据结构word版

第二章空间数据结构 地理信息系统空间数据结构就是指空间数据的编排方式和组织关系。空间数据编码是空间数据结构的实现，目的是将图形数据、影像数据、统计数据等资料，按一定的数据结构转换为适用于计算机存储和处理的过程，不同的数据源，其数据结构相差很大，同一数据源，也可以用许多方式来组织数据，按不同的数据结构去处理，得到截然不同的内容。计算机存储和处理数据的效率，在很大程度上取决于数据组织方式的优劣。数据结构在GIS 中对于数据采集、存储、查询、检索和应用分析等操作方式有着重要的影响；一种高效率的数据结构，应具备几方面的要求：(1)组织的数据能够表示要素之间的层次关系，便于不同数据联接和覆盖。(2)正确反映地理实体的空间排列方式和各实体间相互关系。(3)便于存取和检索。(4)节省存贮空间，减少数据冗余。(5)存取速度快，在运算速度较慢的微机上要达到快速响应。(6)足够灵活性，数据组织应具有插入新的数据、删除或修改部分数据的基本功能。 空间数据结构选择对于GIS设计和建立起着十分关键的作用，只有充分理解了GIS的特定的数据结构，才能正确有效地使用系统。GIS软件支持的主要空间数据结构有矢量数据结构和栅格数据结构两种形式。 §2.1 栅格数据结构 一、栅格数据的基本概念 将工作区域的平面表象按一定分解力作行和列的规则划分，形成许多格网，每个网格单元称为像素，栅格数据结构实际上就是像元阵列，即像元按矩阵形式的集合，栅格中的每个像元是栅格数据中最基本的信息存储单元，其坐标位置可以用行号和列号确定。由于栅格数据是按一定规则排列的，所以表示的实体位置关系是隐含在行号、列号之中的。网格中每个元素的代码代表了实体的属性或属性的编码，根据所表示实体的表象信息差异，各像元可用不同的“灰度值”来表示。若每个像元规定N比特，则其灰度值范围可在0到2n—1之间；把白～灰色～黑的连续变化量化成8比特（bit），其灰度值范围就允许在0～255之间，共256级；若每个像元只规定1比特，则灰度值仅为0和1，这就是所谓二值图像，0代表背景，1代表前景。实体可分为点实体、线实体和面实体。点实体在栅格数据中表示为一个像元；线实体则表示为在一定方向上连接成串的相邻像元集合；面实体由聚集在一起的相邻像元集合表示。这种数据结构便于计算机对面状要素的处理。 用栅格数据表示的地表是不连续的，是量化和近似离散的数据，这意味着地表一定面积内（像元地面分辩率范围内）地理数据的近似性，例如平均值、主成分值或按某种规则在像元内提取的值等。另一方面，栅格数据的比例尺就是栅格大小与地表相应单元大小之 22 / 1

第1章习题解答 数据结构概论

第1章 数据结构概论 一、判断题 1 算法可以没有输入语句。 解：对。按照算法定义，它包括输入、输出、确定性、有穷性和有效性这五条。其中，算法允许有零个或多个输入语句，但必须至少有一个输出语句。 2 数据的逻辑结构按照数据元素前驱的个数划分为线性与非线性两类，线性的数据结构指数据元素只有一个前驱，非线性的则有多个前驱。 解：错。正确的表述应为：线性的数据结构是指每个数据元素至多只有一个前驱，至多只有一个后继。 3 数据结构包括数据间的逻辑结构、数据的存储方式和数据的运算三个方面。 解：对。数据结构的研究内容为：数据的逻辑结构、存储方式与数据运算。 二、选择题 1 算法的时间复杂度取决于 。 (A)．问题的规模 (B)．待处理数据的初态 (C)．编码的语言 (D)．占用内存的大小 解：选A 。时间复杂度与空间复杂度均取决于问题规模。 2 算法与程序的主要区别在于程序可以不满足算法的 B 。 (A)．确定性 (B)．有穷性 (C)．可行性 (D)．健壮性 解：选B 。 算法包含有五个特性：（1）输入。（2）输出。（3）确定性。（4）有穷性。（5）有效性 程序可以不满足有穷性，亦即程序允许无限次地运行。例如，在以下程序中，当不输入-1时，程序将无限次地运行。 #include void main() { int n; cout<<"输入正整数n,输入-1结束"<