假设我在 C 程序的内存中有一个保留空间,用于包含 1000 个项目的链表。每个项目只包含列表中下一个项目的引用(最后一个指向第一个)。但是现在它们都设置为空,它只是保留空间。
接下来我有一个rand()
函数,它给了我一个从 1 到 1000 的随机数。我的问题是,有没有简单的方法可以通过以下方式使用这个函数随机化这个列表:当我从第一个元素开始时,我将遍历整个列表,即列表中不会有比整个列表小的圆圈。
假设我在 C 程序的内存中有一个保留空间,用于包含 1000 个项目的链表。每个项目只包含列表中下一个项目的引用(最后一个指向第一个)。但是现在它们都设置为空,它只是保留空间。
接下来我有一个rand()
函数,它给了我一个从 1 到 1000 的随机数。我的问题是,有没有简单的方法可以通过以下方式使用这个函数随机化这个列表:当我从第一个元素开始时,我将遍历整个列表,即列表中不会有比整个列表小的圆圈。
根据您的描述,您有一个由 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]];
}
等等...
不需要额外空间的解决方案。虽然注意这rand()
被称为每个节点分配的随机次数:
struct Node
{
Node* next;
};
int main()
{
Node nodes[1000];
Node* pNext = NULL;
Node* pHead = NULL;
Node* pTail = NULL;
int i = 0;
// reset .next to NULL
memset(nodes, 0, sizeof(nodes));
srand ( time(NULL) );
pHead = &nodes[ rand() % (1000)];
pTail = pHead;
// need only 999 runs as one node is already assigned
for (i = 0; i < 999; ++i)
{
pTail->next = pTail;
while ((pNext = &nodes[ rand() % (1000)]) && pNext->next);
pTail->next = pNext;
pTail = pNext;
}
// pTail->next = pHead; // uncomment if you need circular list
}