在這種情況下要考慮的有效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++數據結構

回答

相關問題