我如何在MPI中創建一個包含自引用字段的結構？

Question

我想創建一個二叉樹，爲此我需要能夠引用自身內部的結構。

樹的形式

struct tree 
    { 
    int val; 
    struct tree *lchild, *rchild; 
    }; 

的我怎麼能在MPI做到這一點？

Answer 1

MPI中沒有指針類型 - 它沒有任何意義。 MPI進程具有完全獨立的地址空間，因此當轉移到另一個級別時，指針將毫無用處。

您應該從根本上重新考慮分佈式計算方面的數據結構。沒有關於這個問題的更多細節，我不能提出一般性建議。

Answer 2

這類問題在這裏出現a lot，我們應該試着寫一個規範問題。如Zulan所指出的，指針在分配內存的過程之外沒有意義，所以這一般不能完成。暫時忘掉MPI，簡單想象將數據寫入磁盤 - 指針值本身不會對重構樹結構有任何幫助。

但是樹和圖結構是非常有用的，甚至在分佈式內存計算中也被廣泛使用，因此您需要一種表示可以序列化的數據（通過網絡到另一個進程或到磁盤）高效爲您的使用案例。

如果你的結構是非常動態的 - 包括高度（或度，圖）的變化 - 將鏈接樹類型表示中的數據保存在內存中，並將需要發送的塊序列化根據需要提供數組。另一方面，如果樹的結構保持相對穩定，即使對於計算，也可以將數據保留在數組表示中。

無論哪種方式，您都需要能夠以某種有意義的方式序列化數據。堅持與二叉樹，考慮以下內容：

  A 
     /\ 
     / \ 
     B  E 
     /\ /\ 
     C . . F 
    /\  /\ 
    D .  . . 
    /\ 
    . . 

有很多方法可以代表此線性數組中;哪一個最好取決於你需要什麼。首先，你必須決定是否代表完整的二叉樹（全部爲2 ^（height + 1）-1個節點），或者只有那些存在的節點，在樹尾有顯式的空節點代表子樹的末端;第一個更快，更節省空間如果您的樹將接近完整和平衡，並且給出的優勢是能夠明確計算給定節點索引的子節點或父節點的索引，其中第二個空間更多如果不是這樣，那麼效率很高，但是你沒有明確的計算優勢（這些優點和缺點是相同的，比如說，密集矩陣表示與稀疏矩陣表示;這是一套常見的折衷方案）。在下面我假設你不是一個完整的二叉樹。

然後，您必須決定如何將樹中的位置轉換爲數組的線性順序的位置;規範表示是預購：

A B C D . . . . E . F . . 

或按序

. D . C . B . A . E . F . 

或後序

. . D . C . B . . . F E A 

三個保持子樹連續的，這是圍繞把他們很好;預訂對很多應用程序來說都很好，因爲它可以很容易地找到子樹，但是您使用的排序應該與您要使用/搜索數據的排序相匹配。

但是，對於各種選擇的最佳決策 - 完全vs稀疏表示法，計算線性排序的方法，以及是否將數組表示法用作計算的本地表示形式，而不是將序列化表示法用於通信 - 都來直到你將如何使用這些結構。