2015-05-06 105 views
0

我正在嘗試使用以下程序來反轉鏈接列表。但最後head仍錯誤地指向原始列表的第一個元素。我在哪裏犯錯?反轉鏈接列表,爲什麼head不指向原始第一個元素?

#include <iostream> 

struct node{ 
    node(int val): 
     value(val), 
     next(nullptr) 
    {} 

    ~node(){ 
     delete next; 
     std::cout << "Deleting " << value << std::endl; 
    } 

    int value; 
    node* next; 
}; 

node* create() 
{ 
    node * head = new node(1); 
    head->next = new node(2); 
    head->next->next = new node(3); 
    head->next->next->next = new node(4); 
    head->next->next->next->next = new node(5); 
    return head; 
} 

void print(node* head) 
{ 
    auto ptr = head; 
    while(ptr !=nullptr) 
    { 
     std::cout << ptr->value << " -> " ; 
     ptr = ptr->next; 
    } 
    std::cout << "nullptr" << std::endl; 
} 

void reverse(node** head_p) 
{ 
    auto head = *head_p; 

    auto p2 = head->next; 
    head->next = nullptr; 

    while(p2!=nullptr) 
    { 
     auto temp = head; 
     head = p2; 
     p2 = p2->next; 
     head->next = temp; 
    } 
} 

int main() 
{ 
    auto head = create(); 
    print(head); 

    reverse(&head); 

    print(head); 
    delete head; 
    return 0; 
} 
+0

什麼是'刪除下一個';'應該在'node'的析構函數中做? – Lingxi

+0

@靈溪,它刪除下一個節點。 – sank

+0

[相關](http://codereview.stackexchange.com/q/45918/489)。 –

回答

3

在這個函數:

void reverse(node** head_p) 
{ 
    auto head = *head_p; 

    auto p2 = head->next; 
    head->next = nullptr; 

    while (p2 != nullptr) 
    { 
     auto temp = head; 
     head = p2; 
     p2 = p2->next; 
     head->next = temp; 
    } 
} 

除非我讀了這個錯誤,您操縱了列表,但未能更新head_p,這是您通過其地址的head的指針。

+0

我很困惑。我正在傳遞變量的地址。不應該在調用者程序中反映這些更改嗎? – sank

+2

@sank,當你做'auto head = * head_p'時,你用'* head_p'指針(即你傳遞的指針的地址)初始化'head'。所以'head'就像'0xA0FF014'(即一個地址)。要修改該地址處的內容(即,通過指向「reverse」的指針傳遞的指針),您需要解除引用head。想想你如何修改一個通過指針傳遞的簡單變量,然後你會看到發生了什麼。或者,爲了簡化事情,我建議對'node *'使用'typedef',那麼你的代碼將變得更加清晰。 – vsoftco

1

在你reverse()功能你正在做auto head = *head_p;,但在那之後你不修改指針*head_p。要修改指針*head_p,您需要解除引用head,如*head = nullptr(套數head指向nullptr)。

快速修復:將auto head替換爲auto& head以使用對*head_p的引用。或者,更好,只是通過引用傳遞直接headreverse()功能,如

void reverse(node*& head_p) 
{ 
    auto p2 = head_p->next; 
    head_p->next = nullptr; 

    while(p2!=nullptr) 
    { 
     auto temp = head_p; 
     head_p = p2; 
     p2 = p2->next; 
     head_p->next = temp; 
    } 
} 

並調用它作爲

reverse(head); 
+0

我不認爲你的修復解決OP的要求「*在最後頭仍然指向原始列表的第一個元素。*」 – Lingxi

+0

@Lingxi我認爲它的工作原理,請參見[這裏](http:// ideone的.com/JMwPsS)。 '頭'肯定是修改過的。我認爲*「最後頭仍然指向原列表的第一個元素。」*是問題,而不是要求:) – vsoftco

+0

@靈溪對不起,我不明白。 OP想要反轉一個鏈表,我的代碼正在反轉一個鏈表(這就是爲什麼我加了一個額外的'reverse(head); print(head);'來看看這個鏈表是否確實顛倒了。我在這裏誤解了一些東西 – vsoftco

0

我認爲,當我們有做出頭的標準庫,我們應該使用它們

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

using namespace std ; 

list <int> ls ; 

int main() 
{ 
    ls.push_back(1) ; 
    ls.push_back(2) ; 
    for (auto x : ls){ 
     cout << x << endl ; 
    } 
    reverse (ls.begin() , ls.end()) ; 
    for (auto x : ls){ 
     cout << x << endl ; 
    } 
    return 0; 
} 

您可以使用結構列表例如

struct mystruct{ 
    int a , b ; 
    char c ; 
}; 

list <mystruct> ls ; 

更多信息,請參閱this

相關問題