c - 随机化C中的链表

Question

假设我在 C 程序的内存中有一个保留空间，用于包含 1000 个项目的链表。每个项目仅包含列表中下一项的引用(最后指向第一个)。但是现在都设置为null，只是预留空间。

接下来我有一个 rand() 函数，它给我一个从 1 到 1000 的随机数。我的问题是，是否有任何简单的方法可以通过以下方式使用此函数随机化此列表:当我从第一个元素开始时，我会遍历整个列表，即列表中不会有比整个列表小的圈。

Answer 1

根据您的描述，您有一个包含 1000 个节点的数组，这些节点全部归零。为了便于讨论，该数组被命名为 node_array，链接字段被称为 next。您还有一个名为 head 的指针，它可以指向其中一个节点。

您可以分配一个包含 1000 个整数的数组:

enum { NUM_ITEMS = 1000 };
int mapper[NUM_ITEMS];

您可以初始化列表，使每个数字出现一次:

for (int i = 0; i < NUM_ITEMS; i++)
    mapper[i] = i;

您可以随机排列列表。 (我真的应该查看 Knuth(计算机编程艺术)或 Bentley(编程珍珠或更多编程珍珠)，但我认为随机改组的正确算法需要不同的随机数生成器——生成范围内的随机数的生成器[n..m) — 而不是只生成 0..999 范围内的数字)。

for (int i = 0; i < NUM_ITEMS; i++)
{
    int j = rand();
    int t = mapper[j];
    mapper[j] = mapper[i];
    mapper[i] = t;
}

您现在可以遍历节点数组，将它们按顺序链接到 mapper 数组中。因为数组中没有重复项，所以列表中没有循环。

head = &node_array[mapper[0]];

for (i = 1; i < NUM_ITEMS; i++)
{
    head->next = head;
    head = &node_array[mapper[i]];
}

Et voilà...