反向雙向鏈表

這是我的簡單鏈表列表程序，它創建一個雙向鏈表，它起作用。反向雙向鏈表

#include <iostream> 
using namespace std; 

typedef struct node { 
    int data; 
    node *next; 
    node *prev; 
}node; 

void printList(node *temp); 

int main() 
{ 
    node *head; 
    head = new node; 
    head->prev = NULL; 
    node *next = head; 
    node *prev = head; 
    node *temp = head; 
    node *current = head; 

    //creates 100 nodes, last one points to next 
    for(int x = 0; x<100; x++) 
    { 
    temp->data = x; 
    current = temp; 
    temp = new node; 
    current->next = temp; 
    temp->prev = current; 
    temp->next = NULL; 
    } 
    //========================================= 

    printList(head); 

    //=========== set everything to head =========== 
    current = head; 
    prev = head; 

    //============= reverses linked list ============ 
    while(current->next != NULL) 
    { 
    next = current->next; //moves next pointer to next node 
    current->prev = next; //points current's previous to next node 
    current = next;   //set current pointer to next node 
    current->next = prev; //set current's next to previous node 
    prev = current;   //move prev node up to current 
    } 
    //================================================ 

    printList(head); 
    cout<<"done"; 

    return 0; 
}  

void printList(node *temp) 
{ 
    while(temp->next != NULL) 
    { 
     cout<<temp->data<<'\n'; 
     temp = temp->next; 
    } 
}

雖然我添加了反轉功能，但它掛起。實際上，函數本身是有效的，但是在IDE中，當我打開它時，它會打印出所有的值，然後掛起（在閃爍的光標處），不執行任何操作。

解決方案：明白了。這是我的功能最終成爲。

current = head;   //set current pointer to head 
prev = head;   //set previous pointer to head 


next = current->next; //moves next pointer to next node 
current->next = NULL; //set the next of the header to NULL, because it will actually be the last 
         //node of reversed list. 
current->prev = next; //set previous of the header to the next node. 

while(next != NULL) 
{ 
current = next; 
next = current->next; 
current->prev = next; 
current->next = prev; 
prev = current; 
}

來源

2014-01-06 Andrew Tsay

您是否在代碼中的每個有趣的點處插入了打印語句並追蹤了會發生什麼？由於您使用的是IDE，您是否已經逐步瞭解了代碼，並確定了代碼中IDE「剛掛起」的位置。無論如何，「掛起」意味着什麼？ – GreenAsJade

我繼續向反向功能添加打印語句。這就是我得到的。有任何想法嗎？ http://ideone.com/nvDNK2 –

你的反向算法基本上是壞的。

在第一遍通：

current = head; // Current is pointing at node 0, node0->next is 1 from before 
prev = head; // Prev is pointing at node 0 

next = current->next; // next is pointing at 1 
current->prev = next; // node0->prev is pointing at 1 
current = next;  // current is pointing at 1 
current->next = prev // node1->next is pointing at 0

那麼下一次

next = current->next // read up there ^^^ node1->next is pointing at 0

...所以下次追溯到到節點0

那不是你的意思是做 - 它會導致您重複循環遍歷節點1和零，而不是進展到節點2和更遠......

請注意，你可以，如果你把這個代碼到反向環路都容易調試這樣的：

cout<<"\nStarting iteration" 
cout<<"\nNext is at" << next->data 
cout<<"\nCurrent is at" << current->data 
cout<<"\nCurrent->next is" << current->next->data

等等並不需要很長時間打字，揭示了所有:)

（可能你會剪下來做100 3代替）

我只是做手工爲3個節點的步驟（在紙上）推斷這個答案...

來源

2014-01-06 09:00:56 GreenAsJade

順便說一下，您的創建算法將使用未初始化的數據保留最後一個節點。這可能會在稍後造成疼痛;） – GreenAsJade

那麼，如果電流是在節點1。不會'next = current-> next'移動到節點2旁邊嗎？ –

這取決於node1的「下一個」指向哪個節點。正如我所說的，您將節點1的「下一個」設置爲指向節點0.因此，當電流指向1並且節點1的下一個指向零時... next = current-> next將您帶到節點零。 – GreenAsJade

看看這個簡單的解決方案..

Node* Reverse(Node* head) 
{ 
Node * curr=head; 
Node * prev=NULL,* nxt=NULL; 

while(curr!=NULL) 
    { 
    nxt=curr->next; 

    curr->next=prev; 
    curr->prev=nxt; 

    prev=curr; 
    curr=nxt; 
    } 

return prev; 
// Complete this function 
// Do not write the main method. 
}

來源

2017-03-14 18:11:26 Vishal

反向雙向鏈表

回答

相關問題