0

これらのマージソートを学び、理解できる簡単な方法を探しています。Web を調べたところ、マージ ソートは単一リンク リストに非常に適していることがわかりましたが、その方法がわかりません。これは私が見つけたウェブサイトです: ウィキペディアのマージソートと 具体的にリンクされたリスト

どのコードを提供すればよいかわかりません。私は基本的にヘッダーファイルにこれを持っているだけで、これは初めてなので、非常に基本的です。事前にご協力いただきありがとうございます:)

class Node
{
public:
    int data;
    Node* next;
    Node()
    {
        next = NULL;
        data = 0;
    }
};

class SLLIntStorage
{
public:
    Node* head;
    Node* current;
    Node* tail;

    void Read(istream&);
    void Write(ostream&);
    void setReadSort(bool);
    void sortOwn();
    void print();

    bool _sortRead;
    int numberOfInts;

    SLLIntStorage(const SLLIntStorage& copying)
    {

    }

    SLLIntStorage(void);
    ~SLLIntStorage(void);
};
4

1 に答える 1

2

ウィキペディアからこの段落を見ると

概念的には、マージソートは次のように機能します

  1. リストの長さが 0 または 1 の場合、リストは既にソートされています。さもないと：
  2. ソートされていないリストを、サイズが約半分の 2 つのサブリストに分割します。
  3. マージソートを再適用して、各サブリストを再帰的にソートします。
  4. 2 つのサブリストを 1 つのソート済みリストにマージします。

これにより、何をする必要があり、どのような操作が必要かが非常に簡潔にわかります。Split()文 2と4 は、実行できる必要がある操作ですMerge()。NodeSplit はクラスに次のように実装できます。

// Split: removes half of the list and returns a pointer to it
Node* Node::Split()
{
}

同様に、Merge は次のように実装できます。

// Merge: insert elements from source in order
Node::Merge(Node* source)
{
}

全体として 1、2、3、4 では、実際の並べ替えを実行するために必要なことを説明します。リスト操作の Merge と Split を使用して、並べ替え関数でこれらの手順を順番に実装します。

これは 1 つの方法MergeにすぎずSplit、どのように実装するかは、スタイル、要件、c++ の知識、およびその他のさまざまな要因によって異なります。（答えには他の解決策がいくつかあると確信しています）。Node::Append(Node* val)おそらく、基本的な演算子として a または類似のものも必要になるでしょう。あなたが必要とするようには見えませんNode::Remove(Node* val)が、それを実装しても害はないかもしれません.

于 2011-04-29T15:16:02.080 に答える