GIS算法与数据结构
2021-04-26 15:05:59 0 举报
AI智能生成
DingDing
作者其他创作
大纲/内容
算法
定义
An algorithm is a self-contained step-by-step set of
operations to be performed.
operations to be performed.
特点
操作集合
可分离的、步进式的
独立的、自主的
数据
范围广泛、形式抽象
信息的载体
客观的
功能是表达信息
结构
不涉及具体事物
搭配、安排→关系、关联
结构决定整体的功能
数据结构
定义
数据结构是计算机存储 、 组织数据的方式 。 数据结构
是指相互之间存在一种或多种特定关系的数据元素的集合
是指相互之间存在一种或多种特定关系的数据元素的集合
特点
计算机科学领域的概念
功能有两个层面
表达层面
准确有效地表达信息
存储层面
有效的存储和访问数据
解释规则
数据联系的规则—— 逻辑结构
数据存储的规则—— 存储结构
2D矢量图形的量算
文件的基本特征
一段连续的存储空间
线性连续存储结构
格式规范,如何分割
文件的存储结构
.shp文件的基本存储结构
文件头(100字节)
基本识别信息
空间信息概况
最小外接矩形的意义
用来给出一个地理要素的大致位置。空间查询、空间索引,以及建立R树都需要用到最小外接矩形。
信息记录
记录头(8字节)
记录号(4字节)
记录长度(4字节)
空间信息记录(记录长度*2字节)
ShapeType(4字节)
空间坐标记录
点的空间坐标记录存储格式(20字节)
ShapeType(4字节)
X坐标、Y坐标(16字节)
多义线存储结构
ShapeType(4字节)
空间坐标记录
MER
所有 分段 的数目
所有节点的数目
每个分段的 首节点 在节
点集合中的 索引值
点集合中的 索引值
节点集合
多边形的存储格式
与多义线一致
多边形的条件
尾到尾存储
边界是有方向的
边界折线不能在线段内部产生交叉
IPO过程
Input
Process
Output
2D矢量图形的空间拓扑关系
算法的时间复杂度
算法运行
时间分析
最坏情况下的运行时间
期望运行时间
主要的评价指标
大O表示法
f(n)~O(g(n))
Bently-Ottman算法
事件
扫描线状态
数量
顺序
数据的排序问题
Quick Sort算法
二叉树数据结构
二叉查找树的平衡性
二叉查找树的生长效率依赖于树的高度
以根节点为起点的最短分支与最长分支的长度比
二叉查找树越平衡,其生长效率越高
AVL树
它的任何节点的两个子树的高度差别都<=1
AVL树的生长
LL
LR
RL
RR
红黑树
特点
红黑树的生长
网络数据结构和最短路径搜索算法
BFS
DFS
单源路径遍历的搜索策略
BFS
DFS
赋权图
赋权图的最短路径搜索
最短路径搜索算法的优化
子主题
收藏
0 条评论
下一页