寫一個列表的合併方法

我想寫一個方法以交替的方式合併一個雙向鏈表。所以如果我們有兩個int列表（0,1,2,3）和（4,5,6），我們只有一個最終的列表（0,4,1,5,2,6,3）。每個列表都有一個頭部，一個尾部，一個下一個和一個prev指針。寫一個列表的合併方法

它傷害了我的想法，試圖找出從哪裏開始或如何工作。我試圖在紙上追蹤它，但沒有進展。

任何人都可以引導我在正確的方向嗎？這是一個很好的方式來「描繪」或制定計劃，因爲我甚至不知道從哪裏開始。

來源

2011-02-14 iRobot

這聽起來像作業。你應該提到，如果是。 – Aidanc 2011-02-14 23:48:00

@Aidanc：爲什麼？我的答案（和我認爲詹姆斯'）無論如何都是相同的。 – 2011-02-15 00:08:53

@Fred：爲清晰起見。例如有些學生希望找到所有「家庭作業C++」的自學問題，或其他的東西。 – 2011-02-15 00:39:25

創建第三個空列表（稱爲「結果列表」）。

循環while仍有殘留在列表中的一個元素：

如果第一列表不爲空，彈出元件斷第一列表的前面並將其推入結果的背面名單。
如果第二個列表不爲空，則從第二個列表的前面彈出一個元素，並將其推送到結果列表的後面。

它看起來像這樣與C++ std::list容器（該算法略有不同，因爲它是一個有點容易處理主循環之外「額外」的元素）：

template <typename T> 
std::list<T> merge_lists(const std::list<T>& a, const std::list<T>& b) 
{ 
    std::list<T> r; 
    while (!a.empty() && !b.empty()) 
    { 
     r.splice(r.end(), a, a.begin()); 
     r.splice(r.end(), b, b.begin()); 
    } 

    r.splice(r.end(), a, a.begin(), a.end()); 
    r.splice(r.end(), b, b.begin(), b.end()); 

    return r; 
}

來源

2011-02-14 23:48:06

取下面的步驟沿每條線向下，箭頭代表移動。例如，第一步之後，0已經從一個刪除，最後只有一個項目：

List: A  final  B 
     0 --> 0 
       4 <-- 4 
     1 --> 1 
       5 <-- 5 
     2 --> 2 
       6 <-- 6 
     3 --> 3

用的std ::列表中的一個例子：

std::list<int> A, B; 
A.push_back(0); A.push_back(1); A.push_back(2); A.push_back(3); 
B.push_back(4); A.push_back(5); A.push_back(6); 

std::list<int> final; 
for (std::list<int>::iterator a, b; 
    (a = A.begin()) != A.end() and (b = B.begin()) != B.end();) 
{ 
    final.splice(final.end(), A, a); 
    final.splice(final.end(), B, b); 
} 
for (std::list<int>::iterator x; (x = A.begin()) != A.end();) { 
    final.splice(final.end(), A, x); 
} 
for (std::list<int>::iterator x; (x = B.begin()) != B.end();) { 
    final.splice(final.end(), B, x); 
}

提取拼接清理東西一點點，但是，更重要的是，你應該能夠編寫下面move_back你（顯然定製）列表類型，然後使用它是相同的std ::名單：

// Moves pos from source into dest; returns what was the position after 
// pos in the source list. 
template<class List> 
typename List::iterator move_back(List &dest, List &source, 
               typename List::iterator pos) 
{ 
    typename List::iterator next = pos; 
    ++next; 
    dest.splice(dest.end(), source, pos); 
    return next; 
} 
template<class List> 
void move_back(List &dest, List &source) { 
    dest.splice(dest.end(), source, source.begin(), source.end()); 
} 

void example() { 
    std::list<int> A, B; 
    A.push_back(0); A.push_back(1); A.push_back(2); A.push_back(3); 
    B.push_back(4); A.push_back(5); A.push_back(6); 

    std::list<int> final; 
    for (std::list<int>::iterator a = A.begin(), b = B.end(); 
     a != A.end() and b != B.end();) 
    { 
    a = move_back(final, A, a); 
    b = move_back(final, B, b); 
    } 
    move_back(final, A); 
    move_back(final, B); 
}

來源

2011-02-15 00:06:29

在你不想要改變e輸入列表，然後您可以複製第一個列表，然後插入第二個列表中的每個其他位置的新列表元素。

#include <iostream> 
#include <list> 
#include <iterator> 

int main(int argc, char* argv[]) 
{ 
    typedef std::list<int> list; 
    list a; // and fill it ... 
    list b; // and fill that too ... 

    list c(a); 
    for(list::iterator p(++c.begin()), i(b.begin()); i != b.end(); ++i) { 
     p = ++ ++ c.insert(p, *i); 
    } 
    return 0; 
}

另外感興趣的是Boost Zip Iterator。它允許您同時迭代兩個或更多個容器。因此，您可以創建一個空列表，並行迭代兩個輸入列表，並將每個元素插入到新列表中。

來源

2011-02-15 00:08:39 wilhelmtell

寫一個列表的合併方法

回答

相關問題