雙向鏈表的反向部分

我試圖實現我自己的列表類，但是在倒轉列表的一部分時遇到了問題。雙向鏈表的反向部分

Revelant代碼：

void List<T>::reverse(ListNode * & head, ListNode * & tail) 
{ 

    ListNode* t; 
    ListNode* curr = head; 
    ListNode * funtail = tail; 
    int stop=0; 
    while(stop==0) 
    { 
     if(curr==funtail) 
     { 
      stop = 1; 
     } 
     t = curr->prev; 
     curr->prev = curr->next; 
     curr->next = t; 
     curr = curr->prev; 
    } 
    t = tail; 
    tail = head; 
    head = t; 
}

如果我開始與列表

1 2 3 4 5 6 7 8 9 10

和我的指針傳遞給1和4，那麼列表應該看起來像

4 3 2 1 5 6 7 8 9 10

問題是，我的清單僅返回

與列表的其餘部分丟失（好吧，仍然可以從我的全局尾部變量訪問）。有任何想法嗎？我的方法錯了嗎？

來源

2012-02-20 Adam

在'while'循環的第一次迭代中，您將'curr-> prev'分配給't'。如果你開始在沒有前節點的情況下開始逆轉會發生什麼？ – jrok 2012-02-20 17:32:31

你head->prev必須指向NULL在第一個for循環。你更好地思考和實施digramatically它會有所幫助。你需要t->next->next =t->next。

來源

2012-02-20 17:50:05 Invictus

但是，當t-> next爲NULL（列表中的最後一項）時，它不會與t-> next-> next進行段錯誤。我已經在紙上畫出了它，當我在工作節點的頭部添加一個特殊情況時，它好像應該可以正常工作。 – Adam 2012-02-21 18:18:09

-1

在您的方法參數中，您將「指針」與「引用」混合在一起。

void List::reverse(ListNode * & head, ListNode * & tail)

也許你的意思是？

void List::reverse(ListNode* head, ListNode* tail)

來源

2012-02-20 17:24:24

這不回答這個問題。還要注意他*重新分配參數，這就是爲什麼他們是指向指針的原因。不是最好的做法，但是他的代碼根本無法用你的建議。 – vidstige 2012-02-20 18:11:35

如果顛倒段[第一，最後]，你想first->next設置爲last->next，不first->prev，因爲你的代碼一樣。

來源

2012-02-20 17:35:16

第一個節點出現問題，因爲節點1 prev指針爲NULL，並且您將其分配給節點1的下一個節點。您應該分配1的旁邊節點5

來源

2012-02-20 17:42:16 girish

我添加了一個特殊情況，當工作節點是頭部設置其下一個尾 - >下一個（1->下一個應該是5），但現在我只是失去了內部的數字，它只翻轉第一2： <2 1 5 6 7 8 9 10> – Adam 2012-02-21 18:18:39

您需要照顧頭節點和最後一個節點。對於其他節點，您使用的邏輯應該可以工作。這3個場景必須注意：1）頭節點下一個必須指向尾節點下一個節點 2）尾節點下一個必須指向頭節點prev 3）然後對於其餘節點node-> next必須指向節點 - > prev – girish 2012-02-23 15:54:01

你也可以發佈給出結果的代碼<2 1 5 6 7 8 9 10>。我認爲問題在於變量停止設置爲1之間，因此迭代沒有完成。 – girish 2012-02-23 16:11:06

更簡單的解決方案。

/** 
* Traverses half of the list and swaps a node with another node(
    here by termed as the reflection node) 
* which lies at a position = listSize - (i +1) for every i. 
* Reassignment of element is not needed, hence a soul saver from 
* the copy constructor thing ('=' assignment operator stuff). 
*/ 
template <typename E> void DLinkedList<E>::reverse(){ 
    int median = 0; 
    int listSize = size(); 
    int counter = 0; 

    if(listSize == 1) 
     return; 

/** 
* A temporary node for swapping a node and its reflection node 
*/ 
DNode<E>* tempNode = new DNode<E>(); 

for(int i = 0; i < listSize/2 ; i++){ 
    DNode<E>* curNode = nodeAtPos(i); 
    // A node at 'i'th position 
    DNode<E>* reflectionNode = nodeAtPos(listSize - (i + 1)); 
// Reflection of a node considering the same distance from the median 

     /** 
     * swap the connections from previous and next nodes for current and 
      * reflection nodes 
     */ 
     curNode->prev->next = curNode->next->prev = reflectionNode; 

     reflectionNode->prev->next = reflectionNode->next->prev = curNode; 

     /** 
     * swapping of the nodes 
     */ 
     tempNode->prev = curNode->prev; 
     tempNode->next = curNode->next; 

     curNode->next = reflectionNode->next; 
     curNode->prev = reflectionNode->prev; 

     reflectionNode->prev = tempNode->prev; 
     reflectionNode->next = tempNode->next; 
    } 

    delete tempNode; 
} 

template <typename E> int DLinkedList<E>::size(){ 
    int count = 0; 
    DNode<E>* iterator = head; 

    while(iterator->next != tail){ 
     count++; 
     iterator = iterator->next; 
    } 
    return count; 
} 

template <typename E> DNode<E>* DLinkedList<E>::nodeAtPos(int pos){ 
    DNode<E>* iterator = head->next; 
    int listSize = size(); 
    int counter = 0; 
    while(counter < pos){ 
     iterator = iterator->next; 
     counter++; 
    } 

    return iterator; 
}

來源

2013-01-18 05:48:16

雙向鏈表的反向部分

回答

相關問題