在C中随机化链表C

假设我在C程序的内存中有一个保留空间，用于包含1000个项目的链接列表。每个项目只包含列表中下一个项目的参考（最后一个项目指向第一个项目）。但现在它们全部设置为空，它只是预留的空间。在C中随机化链表C

接下来我有一个rand()函数，它给了我一个从1到1000的随机数。我的问题是，是否有任何简单的方法如何使用此函数以下列方式随机化该列表：当我从第一个元素开始时，I将遍历整个列表，也就是说，列表中的圆圈不会比整个列表小。

来源

2012-11-20 user561838

什么用这里的随机数？ – djechlin

听起来很简单 - 你试过了什么？ – Useless

我应该使用它来随机化列表。但我不知道如何......天真的方法将按顺序遍历项目，并将此数字用作“下一个”元素的索引。但是有两个项目指向同一个项目的可能性很大。 – user561838

从您的描述中可以看出，有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瞧...

来源

2012-11-20 21:13:25

这似乎是我想要做的。谢谢:-) – user561838

仔细检查0..999与1..1000并注意一个一个的错误。未经测试的代码！你刚刚被警告。 –

是的，我只是想要如何做到这一点。我会测试它，谢谢。 – user561838

解决方案，不需要额外的空间。虽然注意到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 
}

来源

2012-11-20 21:51:07

在C中随机化链表C

回答

相关问题