將項目插入鏈接列表後排序？

Question

我有一個C++程序來將節點插入鏈表。節點由一個字符串組成，我們將其稱爲數據，以及指向下一個節點的指針，我們將其稱爲下一個。此外，頭節點將被定義爲頭部。

我不知道什麼是更有效 - 1.插入一串字符串到我的名單，然後分類整理後 2或排序列表中我插入。

我認爲這是後者，我想知道我將如何去執行這樣的事情。

我想知道最簡單的方法來實現這樣的功能。

Answer 1

我已經回答了類似的問題（類似99％:)）現在 HERE

其整我猜，字符串可以比較使用C庫提供std::string compare功能或strcmp

根據我的看法和看到其他答案，它會更好地爲您的應用程序（如果它需要排序鏈接列表）排序插入數據。

Answer 2

我認爲它實際上並沒有什麼區別，你在插入時進行排序時，你會在插入時產生O（n），因爲你可能必須遍歷整個列表，然後才能找到正確的位置插入。

但是，當您將所有項目添加到列表中後進行排序時，您至少還將具有O（n）來移動列表中的項目。

Answer 3

第一個解決方案：插入k個元素未排序，只需將它們插入到開始位置，它是每個O（1）。和這些k元素之後的排序：O(nlogn)。你得到amortized時間爲O(nlogn+k)/k = O(n(logn/k))。

第二種解決方案：將元素插入到列表中的順序是O(n)，因爲您需要在列表中找到該位置。對於k個插入，它將是O(n*k)，並且分攤爲O(n*k/k) = O(n)。

所以第一個解決方案是logn < k更好，並且所述第二對logn > k

爲了更好的效率，你可能會想訪問的元素在O排序的數據結構（logn）時間諸如skip-list [這基本上是鏈表的附加信息更容易訪問]的變化或avl tree

Answer 4

最簡單的辦法是用什麼C++已經提供 - std::list和std::list::sort：

#include <list> 
#include <algorithm> 
#include <iostream> 
#include <string> 

class Node { 
public: 
    Node(const std::string& data) : Data(data) { 
    } 
    std::string Data; 
}; 

bool NodeLess(const Node& n1, const Node& n2) { 
    return n1.Data < n2.Data; 
} 

void main() { 

    std::list<Node> l; 
    l.push_back(Node("d")); 
    l.push_back(Node("c")); 
    l.push_back(Node("a")); 
    l.push_back(Node("b")); 

    l.sort(NodeLess); 

    for (auto i = l.begin(); i != l.end(); ++i) 
     std::cout << i->Data.c_str() << " "; 

} 

如果你可以避開它（記憶方式），你也可以使用std::vector預先對項目進行排序（通過std::sort），然後再將它們插入到鏈表中，這可能會更快一些。

您也可以使用std::map（或甚至std::set）而不是列表 - 它會在您插入項目時「自動分類」您的項目。

如果你仍然想使用自己的列表，你可以在其中實現begin和end，並使用std::stable_sort。請注意，std::stable_sort需要雙向迭代器（不像std::sort需要隨機訪問迭代器）。要在列表中實現雙向迭代器，您需要使其雙向鏈接，而不僅僅是單鏈接。

如果您想實施排序本身，可以在鏈接列表上實現Quicksort和Mergesort。