如何向後顯示一個有序的雙向鏈表？

Question

我正在爲此苦苦掙扎。我已經得到它顯示大部分的列表，但其中的一個沒有顯示出來，我不能爲我的生活弄清楚如何解決它。

這裏是相關的代碼，我想。

我插入功能：

template <class T> 
void DoublyLinkedList<T>::insert(T data) 
{ 
    DoublyLinkedList<T> *newNode, *tmp, *oneBefore; 

    newNode = new DoublyLinkedList(data); 

if (mNext == NULL) 
    mNext = newNode; 

else 
{ 
    oneBefore = mNext; 
    tmp = mNext; 

    while (tmp != NULL && tmp->mData < data) 
    { 
     oneBefore = tmp; 
     tmp = tmp->mNext; 
    } 

    if (tmp == mNext) 
    { 
     newNode->mNext = mNext; 
     mNext = newNode; 
    } 
    else 
    { 
     oneBefore->mNext = newNode; 
     newNode->mNext = tmp; 
     newNode->mPrevious = oneBefore; 
    } 

    } 
} 

我displayBackwards功能：

void displayBackward(DoublyLinkedList<int> *ptr) 
{ 
    DoublyLinkedList<int> *tmp; 

    tmp = ptr; 
    while (tmp != NULL) 
    { 
     cout << tmp->getData() << endl; 
     tmp = tmp->getPrevious(); 
    } 
} 

我的主要功能的相關部分：

DoublyLinkedList<int> *ptr, *head, *tail; 

    ptr = new DoublyLinkedList<int>; 

    cout << "Testing Insert\n"; 
    ptr->insert(1); 
    ptr->insert(2); 
    ptr->insert(3); 
    ptr->insert(1); 

    tail = ptr; 
    while (tail->getNext() != NULL) 
     tail = tail->getNext(); 

    cout << "\n\nTesting displayBackward\n"; 
    displayBackward(tail); 

我的輸出是目前：

Testing displayBackward 
3 
2 
1 

Answer 1

這段代碼有問題（在插入功能）

if (tmp == mNext) 
    { 
     newNode->mNext = mNext; 
     mNext = newNode; 
    } 

你需要

if (tmp == mNext) 
    { 
     newNode->mNext = mNext; 
     mNext->mPrevious = newNode; 
     mNext = newNode; 
    } 

您的原始代碼的情況下工作，除了當您嘗試插入數據小於或等於您當前第一個節點中的數據。

此外，我假設你的構造函數初始化mNext & m以前爲NULL。如果沒有，你會有其他問題。

Answer 2

template <class T> 
void DoublyLinkedList<T>::insert(T data) 
{ 
    DoublyLinkedList<T> *newNode, *tmp, *oneBefore; 

    newNode = new DoublyLinkedList(data); 

if (mNext == NULL) 
    mNext = newNode; 

else 

這不會連接新節點的返回指針。

你的代碼也可能有更多的錯誤。

---

一個簡單的方法編寫了一個雙向鏈表是

• 分化列表和節點
之間類型，
• 使每個列表始終有一個虛擬節點，稱爲一個頭節點。

這樣，你不會有任何NULL指針來處理。

它真的簡化了事情。