第2讲 控制网的数据结构.pptVIP

问题思考 智能通用控制网数据处理软件的设计 间接平差中计算机如何自动推算复杂网的近似坐标 GPS网中如何自动寻找独立同步环和异步环 条件平差计算机如何自动列立独立线性无关的条件式 * 第2讲 控制网的数据结构 主讲人：张献州（教授） 西南交通大学测量工程系 工程控制网建网理论 第2讲 控制网的数据结构 一、概述 网形的数字化 将控制网的图形转化为一系列数据的工作，所得到的一组数据称为数字网形，用计算机的专业术语来说就是控制网的数据结构。 对控制网来说 它的数据结构就是表达一个控制网（已知数据、观测数据以及网中元素和它们之间的关系）的全部数据的集合。 对一般程序设计 数据量少或者非结构性的在数据的表达与组织上不会遇到困难。 二、图及其数学化 1．图的定义 图论是研究事物之间关系的一种数学工具，它用点表示事物，用线段表示事物之间的关系。 其中：点——图的顶点 线段——图的边 工程控制网建网理论 第2讲控制网的数据结构 控制网不考虑其中的几何关系，而只考虑点和点之间的联系，即可用图论进行研究。图是由点和边构成的，因而可定义为顶点集V与边集E的集合。记作：G=（V，E） 例如对下图而言 G： 2 1 3 4 2 1 3 4 （a） （b） 边集中的元素（1,2），（2,3）… 称为点偶。 无向图：点偶中的两顶点号的顺序可任意。 有向图：点偶中的两顶点号的顺序不可任意。 有向图用符号G= V，E 表示。 工程控制网建网理论 第2讲控制网的数据结构 其中边集为E= n个顶点的无向图，边的最大数目是 n个顶点的有向图，边的最大数目是 2．图的数字表示方法 图论中，对图的数字表示方法有 1. 相关矩阵 a. 无向图 i，j两点有边相连，矩阵i行j列为1，否则为0， 此外对角线元素为O 1 2 3 4 关于对角线上下对称 工程控制网建网理论 第2讲控制网的数据结构 b．有向图 相关矩阵不对称 1 2 3 2. 邻接表 按照图中的顶点号顺序，将与该点有边相联的另一顶点号（称为可达顶点），排成一行，所有这些行形成为表，称为邻接表。 a．有向图 如右图可写出它的邻接表 1 2 3 4 5 工程控制网建网理论 第2讲控制网的数据结构 为节约存贮空间，把邻接表排成一行，另外构成一行可达顶点数表，因此，邻接表包括下列：可达顶点数表和可达顶点表。 ←可达顶点表 1 3 2 4 b．无向图 无向图每条边端点号的先后次序可颠倒，为了使每条边只表示一次，可应用最小点号原则，即规定必须把最小点号排在前面。 如右图的邻接表为： 1 2 3 4 3．边目录 按图的定义 ，但V中元素包含在E中。因此可只用边集E表示图。 边目录：用两端端点号表示图中各边的表。 a．有向图，边目录 工程控制网建网理论 第2讲控制网的数据结构 表中每一列表示一条边，上下各为一个端点号 b．无向图，边目录 与无向图的邻接表类似，采用最小点原则。 1 2 3 4 4. 各种方法比较 相关矩阵法元素是最多，随顶点数增加，0元素增加。 有向图 邻接表要比边目录节省元素。 因此邻接表更适合表示有向图。 无向图 邻接表与边目录相当，边目录缺点不明显。 工程控制网建网理论 第2讲控制网的数据结构 三、控制网的数据结构 1．对控制网的映射 图的顶点 ——→ 网的控制点 有向图的边 ——→ 网中的有向边（方向、高差、基线坐标分量） 无向图的边 ——→ 网中的有向边（单向测距边） 2．控制网的数据结构的组成部分 控制网数据结构包括 网图数据可视边的性质处理成下表： 工程控制网建网理论 第2讲控制网的数据结构 3．两种常用的数据结构方式 网图数结构 混合结构 对有向边用邻接表方式 对元向边用边目录方式 邻接表结构 无论有向边还是无向边都用邻接表方式。 1 2 2 4 工程控制网建网理论 第2讲控制网的数据结构 工程控制网建网理论 第2讲控制网的数据结构 工程控制网建网理论 第2讲控制网的数据结构 * * *