第二章空间数据结构

利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。
例如m的初值为20；n=7，7个人的密码依次是：3，1，7，2，4，8，4，出列的顺序为6，1，4，7，2，3，5。
第二章答案
约瑟夫环问题
约瑟夫问题的一种描述为：编号1,2,…,n的n个人按顺时针方向围坐一圈，每个人持有一个密码（正整数）。一开始任选一个报数上限值m,从第一个人开始顺时针自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有的人全部出列为止。试设计一个程序，求出出列顺序。利用单向循环链表作为存储结构模拟此过程，按照出列顺序打印出各人的编号。
9.假设有一个循环链表的长度大于1，且表中既无头结点也无头指针。已知s为指向链表某个结点的指针，试编写算法在链表中删除指针s所指结点的前趋结点。
10.已知有单链表表示的线性表中含有三类字符的数据元素（如字母字符、数字字符和其它字符），试编写算法来构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。
r=p;
}
}
r->next=L->next;
printf("请输入第一个报数上限值m(m>0):");
scanf("%d",&m);
printf("*****************************************\n");
printf("出列的顺序为:\n");
q=L;
p=L->next;
7.试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（a1, a2..., an）逆置为（an, an-1,..., a1）。

第2章线性表一选择题1．下述哪一条是顺序存储结构的优点？（）【北方交通大学 2001 一、4（2分）】A．存储密度大 B．插入运算方便 C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学 2001 一、14（2分）】A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（）的有限序列（n>0）。

【清华大学 1998 一、4（2分）】A．表元素 B．字符 C．数据元素 D．数据项 E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

【哈尔滨工业大学 2001二、1（2分）】A．顺序表 B．双链表 C．带头结点的双循环链表 D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

【南开大学 2000 一、3】A．单链表 B．仅有头指针的单循环链表 C．双链表 D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学 2000 一、1（2分）】7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学 2000一、1（2分）】A．单链表 B．双链表 C．单循环链表 D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学 2001 六、2（2分）】A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址9. 链表不具有的特点是（）【福州大学 1998 一、8 (2分)】A．插入、删除不需要移动元素 B．可随机访问任一元素C．不必事先估计存储空间 D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学 1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。

即欧氏平面
地理实体：分布于地球表面的人文和自然现象的总称 实体必须符合三个条件：
可被识别
重要（与问题有关） 可被描述（有特征）
3．要素模型
嵌入式空间：是指空间对象存在于“空间”之中。空间对象的定义取 决于嵌入式空间的结构。
常用的嵌入式空间类型： 欧式空间（距离、方位） 量度空间（距离） 拓扑空间（拓扑关系） 面向集合的空间（只采用一般的基于集合的关系）
4.地理空间及其表达
2、空间实体的表达（计算机） 矢量表达 在矢量数据结构中，地理实体的形状和位置是由一组坐标对所确定。矢 量数据结构对地理实体的描述类似于地图对地理信息的描述，一般也把 地理实体分为点、线、面、体等四种，每种实体有不同的编码方法。 栅格表达 在栅格数据结构中，整个地理空间被规则地分为一个个小块（通常为 正方形），地理实体的位置是由占据小块的横排与竖列的位置决定，小 块的位置则由其横排竖列的数码决定，每个地理实体的形态是由栅格或 网格中的一组点来构成。这种数据结构和遥感图象的数据相同，因而数
在各向同性与各向异性场中的旅行时间面
强空间正负自相关模式
2. 场模型
栅格数据模型
栅格数据模型是基 于连续铺盖的，它 是用二维铺盖或划 分覆盖整个连续空 间；铺盖可以分为 规则的和不规则的， 后者可当做拓扑多 边形处理
三角形、方格和六角形划分
栅格数据模型
3．要素模型
1. 基本概念
欧氏空间：带坐标的可测量点之间的距离和方向的空间模型 欧氏平面：把空间特性转换成实数的元组特性，而形成的二维模型
点集拓扑学是拓扑描述的数学基础
空间关系数据
主要是指点-点、点-线、点-面、线-线、线-面、面-面之间的相互

1、DEM数据库结构

DEM数据库结构实质上是DEM的数据结构。 TIN的数据库结构
线（特征线）实体的数 据库结构
点实体的数据库结构
三角形实体的数据库结构
2、DEM数据库组织

指DEM数据的管理和调度方式，实际上是可视范围（即工作区）的数 据管理，可以为用户提供宏观、中观、微观等方式的信息服务。 “工程——工作区——图幅”的层次结构索引模式是当前GIS空间数 据库数据组织的常用方式之一。
(5,2),(0,2),(1,1)
-10 0
20
0
-20 0
索引文件
栅格行序号 逐行游程累计数 01 02 … 100 3 7 … 572
游程序号 0001 0002 0003 0004 0005 0006 0007 … 0572
编码值 R1 R2 R3 R4 R5 R据组织和空间数据库设计的基础。
空间数据模型
空间数据结构
是空间数据模型的表述， 是相互之间存在一种或多 种特定关系的数据元素的 集合。

DEM数据组织的目的是将所有相关的DEM数
据通过数据库有效地管理起来，并根据其 地理分布建立统一的空间索引，进而可以 快速调度数据库中任意范围的数据，实现 对整个研究区域DEM数据的无缝漫游。
9
1e 5
2
6
3 e4 e6
3
e5
关联边： 1）分布在当前边两侧 2）关联边与当前边夹角最小 3）关联边顶点不重复 边表
e10
e7
4
5
e8
4
存储量小，适合等高线提取 编辑、内插、检索不便
No. e1 e2 e3 e4 …
V1 1 2 2 3 …