1

1000 項目を含むリンク リスト用に、C プログラムのメモリに予約済みの領域があるとします。各アイテムには、リスト内の次のアイテムへの参照のみが含まれます (最後のアイテムは最初のアイテムを指します)。しかし、現在はすべて null に設定されています。これは予約済みの領域です。

次にrand()、1 から 1000 までの乱数を与える関数があります。私の質問は、次の方法でこの関数を使用してこのリストをランダム化する簡単な方法があるかどうかです。最初の要素から開始すると、リスト全体をトラバースします。 、つまり、リスト全体よりも小さい円がリストに含まれることはありません。

4

2 に答える 2

1

あなたの説明から、1000 個のノードの配列がすべてゼロになっています。議論のために、その配列の名前node_arrayは 、リンク フィールドの名前はnextです。headまた、ノードの 1 つを指すことができるというポインターもあります。

1000 個の整数の配列を割り当てることができます。

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

リストを初期化して、各番号が 1 回表示されるようにすることができます。

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

リストをシャッフルできます。(実際には、Knuth (The Art of Computer Programming) または Bentley (Programming Pearls または More Programming Pearls) を確認する必要がありますが、ランダム シャッフルの正しいアルゴリズムには別の乱数ジェネレーターが必要だと思います。 [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]];
}

ほら...

于 2012-11-20T21:13:25.543 に答える
0

余分なスペースを必要としないソリューション。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-20T21:51:07.857 に答える