在这种情况下要考虑的有效C++数据结构

我正在写一个算法来连接Region_A的node_A和Region_D的node_D。（node_A和node_D只是整数）。可能有100k +这样的节点。

假设A和D之间的线段经过了许多其他区域B，C，Z。这两个节点之间最多会有20个区域。

每个区域都有自己的属性，可能会根据连接A-D而有所不同。我想在稍后的时间访问这些信息。

我正在寻找一个好的数据结构（也许是一个STL容器），可以为特定连接保存此信息。

例如，对于连接A - DI想存储：

node_A, 
node_D, 
crosssectional area (computed elsewhere) , 
regionB, 
regionB_thickness, 
regionB other properties, 
regionC, ....

的数据可以是双，整型，字符串和也可以是阵列/载体等

首先我考虑为regionB，regionC等创建结构或类。但是，对于每个连接A-D，某些属性（如连接所经过的区域的厚度）是不同的。我只需要存储3到4种与某个地区相关的不同内容。我应该在这里考虑哪个数据结构（像vector这样的任何STL容器？）你能推荐一个吗？（会喜欢的代码片段）
要访问节点A-D之间的连接，我想利用int node_A（一个索引）。这可能意味着我需要使用散列表或类似的数据结构。任何人都可以请建议一个良好的数据结构在C + +可以有效地持有这种类型的数据连接A -D上述？（将欣赏代码片段）

谢谢！

UPDATE 因为某些原因，我不能使用像升压PKGS的。所以想知道我是否可以使用STL中的任何库

来源

2010-02-01 memC

它看起来像我的图。 – Drakosha 2010-02-01 08:35:47

感谢Drakosha的超级快速回复。 ..我现在正在审查'图'的文档 – memC 2010-02-01 08:40:32

http://en.wikipedia.org/wiki/Graph_%28data_structure%29 – Drakosha 2010-02-01 08:44:45

你应该尽量在可以的时候将东西分组在一起。你可以组类似下面一起在各区域的信息：

class Region_Info { 
    Region *ptr; 
    int thickness; 
    // Put other properties here. 
};

然后，您可以更轻松地创建一个数据结构的线段，可能像下面：

class Line_Segment { 
    int node_A; 
    int node_D; 
    int crosssectional_area; 
    std::list<Region_Info>; 
};

如果你只限于20个地区，那么列表应该可以正常工作。如果你愿意，矢量也很好。

来源

2010-02-01 08:56:57 Swiss

您好瑞士，请您详细说明如何在Line_Segment中使用Region_Info类？ ...你的意思是我应该为每个连接创建一个单独的类Region_Info实例吗？（因为attrs喜欢厚度等因连接而异）。另外，如何使用指针Region * ptr？ .. 再一次感谢你！ – memC 2010-02-01 09:18:09

您是否考虑过每个节点的邻接阵列以及其他数据，该节点存储连接的节点？

首先，定义一个节点

class Node 
{ 
    int id_; 
    std::vector<AdjacencyInfo> adjacency_; 

}

所在类别AdjacencyInfo可以存储你所需要的大量数据。如果查找速度是一个问题，您可以将Vector更改为以节点ID作为关键字的散列表。对于奇特的访问，如果它是一个基本要求，你可能想要重载[]运算符。

因此，作为一个例子

class Graph 
{ 
    std::map<int, Node> graph_; 
}

来源

2010-02-01 08:46:52 Extrakun

感谢您的答复Extrakun ...如果我正确理解您的答复：我宁愿不为每个节点创建类节点的实例。也许一个简单的以node id为关键字的hashmap和一个包含我所需要的所有数据的向量就足够了。请让我知道你的想法！ – memC 2010-02-01 09:11:50

一个类可以帮助您封装功能和数据;你可以采用你的方法 - 它完成了工作，但我会关心可用性和可维护性。 – Extrakun 2010-02-01 09:57:24

提升具有图形库：boost.graph。如果它对你的情况有用，请检查它。

来源

2010-02-01 08:55:50 stefaanv

谢谢..但我忘了提及，我无法使用任何外部库如boost.graph。我只能使用STL – memC 2010-02-01 09:02:13

不用担心，它只是一个“检查提升”答案的完整性;-) – stefaanv 2010-02-01 09:14:42

好吧，正如其他人都注意到的那样，这是一张图。问题是，它是一个稀疏图，还是一个密集图？通常有较图表两种方式（更多，但你可能只需要考虑这两种）：

邻接矩阵
邻接表

邻接矩阵基本上是一个N×N个矩阵将第一行和第一列中的所有节点以及连接数据（边）存储为单元格，因此您可以通过顶点对边进行索引。对不起，如果我的英语很烂，不是我的母语。无论如何，如果你有一个密集的图，你只应该考虑邻接矩阵，并且需要真正快速地找到节点 - >边 - >节点连接。但是，通过邻居迭代或在邻接矩阵中添加/删除顶点很慢，第一次需要N次迭代，第二次调整用于存储矩阵的数组/矢量的大小。

您的其他选项是使用邻接列表。基本上，您有一个类表示一个节点，一个表示边的类，存储该边的所有数据，以及两个指向它所连接的节点的指针。节点类具有某种类型的集合（列表将执行），并跟踪它所连接的所有边。然后你需要一个经理类，或者只需要一堆在你的节点上运行的函数。在这种情况下添加/连接节点并不重要，因为列出了邻居或连接的边缘。但是，遍历所有边很难。这种结构比邻接矩阵更灵活，对于稀疏图更好。

我不确定我完全理解了你的问题，但如果我这样做了，我认为你会更好地使用邻接矩阵，好像你有一个密集的图，有很多相互连接的节点，只需要连接信息。

维基百科作为一个数据结构，以及良好的参考和链接，有一个好的关于图的文章，找到的例子不应该很难。希望这有助于：
Link

来源

2010-02-01 10:39:16 fingerprint211b

在这种情况下要考虑的有效C++数据结构

回答

相关问题