1

私のプログラムでは、Linked List を使用して Radix Sort を使用して 9 桁の数字を並べ替えていますが、何らかの理由で正しく並べ替えられません。

これが私が自分の番号を生成する方法です：

void genData(int *dta, int n) 
{
    // generate the numbers at random
    for(int i=0; i < n; i++)
        dta[i] =  rand()%889 + 111 + 1000*(rand()%889 + 111) + 1000000*(rand()%889 + 111);
}

これが Radix Sort 関数です。外側のループは 3 回実行されます。3 桁のセットごとに 1 回。

int radixSort(int *dta, int n, int *out)
{ 
    // the dta array contains the data to be sorted.
    // n is the number of data items in the array
    // out is the array to put the sorted data

    node *bucket[1000]; 
    int count = 0; 
    for(int i = 0; i < n; i++)out[i] = dta[i]; 

    for (int pass = 0; pass < 3; pass++)  // outer loop
    {
        for(int j = 0; j < 1000; j++) // set bucket[] to all zeroes (NULL) for each pass 
        {
            bucket[j] = NULL;
        }

        for(int i = 0; i < n; i++) // inner loop -- walks through the out array (which contains the data to be sorted)
        {
            int index = 0; 
            int tmp = 0;
            switch(pass) 
            {
                case 0:
                    index = out[i] % 1000;
                    break;
                case 1:
                    tmp = out[i]/1000; // tmp = 123456
                    index = tmp%1000; // mid = 456// set index to the middle 3 digits
                    break;
                case 2:
                    tmp = out[i]/1000;  // set index to the first 3 digits
                    index = tmp/1000;
                    break;
            };

            //Create new head node if nothing is stored in location
            if(bucket[index] == NULL)           
            {   
                node *newNode = new node(0, bucket[0]); 
            }
            else
            {
                node *newNode =  new node(out[i], NULL); //Created new node, stores out[i] in it
                node *temp = bucket[index];
                while(temp->next != NULL) // finds the tail of the Linked List
                {
                    temp = temp->next;
                    count++; //For Big-O
                }
                temp->next = newNode;   // make tail point to the new node.
            }
            count++; //For Big-O
        } // end of the inner (i) loop

        int idx = 0; // for loading the out array
        for(int i = 0; i < 1000; i++)  // walk through the bucket
        {
            if(bucket[i] == NULL)continue; // nothing was stored here so skip to the next item

            // something is stored here, so it is put into the out array starting at the beginning (idx)
            out[idx++] = bucket[i]->data;

            if(bucket[i]->next->next != NULL || bucket[i]->next->next)
            // now see if there are more nodes in the linked list that starts at bucket[i]. If there are, put their data into out[idx++]
            {
                out[idx++] = bucket[i]->data;
            }
            count++; //For Big-O
        }


    }// end of the outer loop pass). The output (out) from this pass becomes the input for the next pass

    return count; // Again -- for Big-O 
}

問題は、作成した新しいノードにある可能性があると思います。私は何を間違っていますか？

4

1 に答える 1

1

リンクされたリストに数値を格納するためのロジックが正しくありません。

推奨される概要は次のとおりです。

  • 番号を格納するために常に新しいノードを作成します。
  • next新しいノードのポインタを常に に設定しますNULL。

  • でリンクされたリストの最後を見つけますbucket[index]。

    • リンクされたリストがない場合は、bucket[index]すでに終わりを見つけています。

      node *newNode = new node(out[i], NULL);
if (bucket[index] == NULL)           
{
    // there was no linked list there before; start one now.
    bucket[index] = newNode; 
}
else
{
    // find tail of linked list and append newNode
    node *temp = bucket[index];
    while (temp->next != NULL)
    {
        temp = temp->next;
        count++; //For Big-O
    }
    temp->next = newNode;   // make tail point to the new node.
}

編集:whileリンクされたリストを先頭から末尾までたどるループが既にありました。

リンクされたリストから値を取得するには、先頭から開始し、末尾に到達するまでリストをたどります。しかし、リスト内の各ノードにアクセスすると、値が得られます。

            if (bucket[i] == NULL)continue; // nothing was stored here so skip to the next item

            // if we reach this point there is at least one value stored here

            // get values out
            node *temp = bucket[i];
            out[idx++] = temp->data;
            while (temp->next != NULL)
            {
                temp = temp->next;
                out[idx++] = temp->data;
            }

doしかし、これを/whileループでよりきれいにすることができます。何かを少なくとも 1 回、できれば複数回実行したい場合はdo/を使用します。whileこの場合、このループを実行するのは、少なくとも 1 つの数値を取得したいからです。そう：

            if (bucket[i] == NULL)continue; // nothing was stored here so skip to the next item

            // if we reach this point there is at least one value stored here

            // get values out
            node *temp = bucket[i];
            do
            {
                out[idx++] = temp->data;
                temp = temp->next;
            }
            while (temp != NULL);

に値を格納する行を繰り返すよりも、 do/ループを使用する方がクリーンです。whileout

ループは、長さ 0 以外の任意の長さのリストを処理できます。また、 にcontinueリンクされたリストがない場合を処理するためのチェックが既にありますbucket[i]。

于 2013-10-17T01:54:40.760 に答える