0

だから私は単独でリンクされたリストを持っています。新しいアイテムはチェーンの先頭に追加されるため、8,4,10 を追加すると、リストは 10,4,8 になります。とにかく、挿入が完了した後にリストをソートしようとしていますが、これらの番号をループして昇順に並べ替える方法がわかりません。おそらくここで休憩して、少し戻ってきます。うまくいけば、これを理解するのに役立ちます.

*これは学校向けのプロジェクトであるため、他のコンテナを使用することを提案しても、作業内容を変更できないため、参考になることを除いて、私の場合は役に立ちません。

リストのレイアウト

struct Node
    {
      int Item;      // User data item
      Node * Succ;   // Link to the node's successor
    };

unsigned Num //number of items in the list
Node * Head //pointer to the first node

私の挿入機能は次のようになります

Node * newOne;
newOne = new (nothrow) Node;
newOne->Item = X;
newOne->Succ = NULL;

if(Head == NULL)
{
        Head = newOne;
}
else
{
        newOne->Succ = Head;
        Head = newOne;
}
Num++;
4

2 に答える 2

4

これは 2 つの方法で実行できます。コードは投稿しませんが、役に立てば幸いです。

1.挿入時に昇順に並べる

これには、要素を常に昇順で追加することが含まれます。たとえば、リンク リストが

            | 1  |

5 を追加すると、新しいリンク リストは次のようになります。

           |1|--->|5|

次に3を追加すると、次のようになります

           |1| ---> |3| ----> |5|

これには、正しい位置が見つかるまでの新しい要素の比較が含まれます。

2. すべての要素が挿入されるまで待ち、昇順に並べます。

これには、linklist の要素に対してマージ ソート、挿入ソート、バブル ソートなどのソート アルゴリズムを使用することが含まれます。

番号のソートが完了したら、リンクリストを正しい順序で書き直します。

例：

リンクリストに含まれる場合

        3 2 5 1 6

アルゴリズムによるソート後

  1 2 3 5 6 (stored in an array)

次に、リンク リストをループして、要素を正しい順序で置き換えます。

ノードに他の要素が含まれている場合は注意してください。それらの他の要素も置き換える必要があります。

注: これには追加のメモリが必要です。他の方法ではノードをスワップするため、時間がかかります。リンクリストに多数のノードが含まれている (したがってメモリが重要になる) か、他の要素が含まれていない限り、配列を使用する方が簡単です。

于 2012-11-15T17:05:15.947 に答える
1

単一リンク リストの並べ替えは、コードにとって厄介です (バブル ソートや挿入並べ替えなどの線形並べ替えが好きでない限り)。内容をベクターにコピーし、ベクターを並べ替えてから、リストを再構築する方がはるかに簡単です。

于 2012-11-15T17:01:23.457 に答える