單鏈表上的Mergesort C++

我正在尋找某種簡單的方法，我可以學習和理解這些上的合併排序。我在網上看了一下，發現合併排序對單鏈表來說真的很好，但我不知道該怎麼做。這是網站，我發現： Wikipedia Merge sort和 Specifically linked lists 單鏈表上的Mergesort C++

我不知道什麼樣的代碼給你。我基本上只是在我的頭文件中有這個，並且這個新的所以我非常基本。感謝您對您的幫助提前:)

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); 
};

來源

2011-04-29 Tanya Tazzy Hegarty

如果你看一下這一段從維基百科

從概念上講，合併排序工作原理如下

如果列表中長度爲0或1，那麼它已經排序。否則：

將未排序的列表分成大小約一半的兩個子列表。

通過重新應用合併排序來遞歸排序每個子列表。

將兩個子列表合併回一個排序列表。

這很簡潔地告訴你你需要做什麼以及需要什麼樣的操作。句子2和4是您需要能夠執行的操作Split()和Merge()。拆分可以在您的Node類被實現爲

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

類似的合併可以實現爲

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

整體1,2,3,4描述你需要做的，執行實際的排序是什麼通過使用列表操作「合併」和「拆分」，在排序功能中按順序執行這些步驟。

這只是Merge和Split可能看起來像的一種方式，您如何實現它們將取決於您的風格，要求，C++知識和各種其他因素。（我相信你會在答案中看到其他解決方案）。您可能還需要一個Node::Append(Node* val)或類似的基本操作員。它看起來並不像你需要Node::Remove(Node* val)，但它也可能沒有受到影響。

來源

2011-04-29 15:16:02

單鏈表上的Mergesort C++

回答

相關問題