在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

回答

相關問題