并行算法-结构

---

要正确应用任何算法，选择正确的数据结构非常重要。这是因为与对另一个数据结构执行相同的操作相比，对一个数据结构执行的特定操作可能需要更多的时间。

示例- 要使用数组访问集合中的第 i 个元素，可能需要恒定的时间，但通过使用链表，执行相同操作所需的时间可能会变成多项式^。

因此，数据结构的选择必须考虑架构和要执行的操作类型。

以下数据结构常用于并行编程 -

• 链表
• 数组
• 超立方网络

链表

链表是具有通过指针连接的零个或多个节点的数据结构。节点可能占用也可能不占用连续的内存位置。每个节点有两个或三个部分 - 一个数据部分存储数据，另外两个是存储前一个或下一个节点的地址的链接字段。第一个节点的地址存储在称为head 的外部指针中。最后一个节点称为尾部，通常不包含任何地址。

链表分为三种类型 -

• 单链表
• 双向链表
• 循环链表

单链表

单链表的一个节点包含数据和下一个节点的地址。称为head 的外部指针存储第一个节点的地址。

双向链表

双向链表的节点包含数据以及前一个和下一个节点的地址。称为head 的外部指针存储第一个节点的地址，称为tail的外部指针存储最后一个节点的地址。

循环链表

循环链表与单链表非常相似，只是最后一个节点保存了第一个节点的地址。

数组

数组是一种数据结构，我们可以在其中存储相似类型的数据。它可以是一维或多维的。数组可以静态或动态创建。

• 在静态声明的数组中，数组的维数和大小在编译时已知。

• 在动态声明的数组中，数组的维数和大小在运行时是已知的。

对于共享内存编程，数组可以用作公共内存，而对于数据并行编程，可以通过划分为子数组来使用数组。

超立方网络

超立方体架构对于每个任务必须与其他任务通信的并行算法很有帮助。超立方体拓扑可以轻松嵌入其他拓扑，例如环形和网状拓扑。它也称为 n 立方体，其中n是维度数。超立方体可以递归地构造。