我如何在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稀疏表示法，计算线性排序的方法，以及是否将数组表示法用作计算的本地表示形式，而不是将序列化表示法用于通信 - 都来直到你将如何使用这些结构。