欢迎光临本站!

数据存储结构

来源:技术探讨    更新时间:2019-12-20 15:52:19    编辑:老王    浏览:300

  最短路径搜索问题一般都采用结点一弧结构的存储结构表示。这一方面清晰地表达了网络的拓扑结构,另一方面更加便于Dijkstra算法的实现。根据堆优化结合直线优化Dijkstra算法的特点,设计的数据结构如图4所示。

数据存储结构

  以下对数据结构进行简单的描述;

  (1)网络结点数据结构说明(PointReeord)

  Arclndex:以此结点为起点的第1个弧在弧数组中的下标

  Latitude:结点纬度

  Longitude:结点经度

  (2)弧数据结构说明(AreRecord)

  FirstNode:弧的起点编号

  EndNode:弧的终点编号

  Length:弧的长度

  lndexGraphies:此弧在网络数组中的索引(网络数组下标)

  (3)弧描述点数据结构说明(Point)(包括弧结点在内的整个弧的描述点)

  Latitude:结点纬度

  Longitude:结点经度

  (4)阿络数据结构说明(GraphieReeord):

  CountPoint:弧的结点个数

  ArePoint:结点数组指针

  (5)最短路径结点数据结构说明(DijkstraPoint)

  HeapID:此结点在堆中的编号

  PreNode:最短路径中此结点的前一结点

  ShortestLen:源点到此结点的最短路径长度

  由图4可见,此数据结构完全是为最短路径搜索算法量身定制的。其能够提高效率的最突出一点是:网络结点数据结构存储了以此结点为起点的第1个弧的数组下标,这样就不需要遍历整个弧数组来搜索以此结点为起点的弧}此外,弧数组中各个弧的信息,以弧的起始结点为关键字排序存储·所以起始结点相同的弧是连续存储的,这种结构极大方便了查找某一结点的所有连通结点。此数据结构的其他环节都按照这样的指导思想设计,使算法实现起来更加流畅。

  最短路径结点数据结构为最短路径搜索算法中使用的结点数据结构。网络结点数据结构、弧数据结构和网络数据结构联合构成整个网络描述结构。在全国主要城市问公路信息查询系统的开发中,最短路径结点数据是每个客户请求线程都需要建立的数据结构。整个网络的描述结构只在服务器响应第1个客户的请求时建立,并存储在应用程序的数据堆中,其他客户的请求虽然都需要访问此数据,但不需要重新建立整个拓扑网络的描述数据。

  最短路径搜索数据文件。文件结构描述如表3所示。

数据存储结构

评论区

表情

共0条评论
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~

相关内容

点击排行

随机新闻

评论排行榜