C++添加到雙向鏈表的末尾

Question

我是新來的，所以我幾乎沒有學習如何實現鏈表。我輸入一個數字時程序崩潰了。我想將節點添加到名單的後面。

這是節點

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

這是附加功能

void Add(node* &head, int newdata) 
{ 
    //create a new node to hold the data with a terminal (NULL) next pointer   
     node *tmp = new node; 
     tmp->data = newdata; 
     tmp->next; 
     node *current = head; 
    //check whether head has been initialized (is NULL) 
    // if not, make the new node head and set prev 
     if (head != NULL) 
     { 
      tmp = head; 
      tmp->prev = NULL; 
     } 

    //if head has been initialized 
    //find the end of the chain with a pointer 
     else 
     { 
      while (current->next != NULL) 
      { 
       current = current->next; 
      } 
     } 

    //add the new node on to the last node in the list 
    //set pointers both forward and backwards 
    tmp = current; 
    tmp->prev = current->prev->next; 
    tmp->next = current->next; 



} 

Answer 1

在開始的時候，你需要設置tmp->next和tmp->prev爲NULL。 垃圾指針每次都會殺死你。

那麼你似乎認爲head == NULL意味着它已被初始化，當它可能意味着相反。

最後，你設置了tmp = current;，所以你扔掉了你想添加的節點。

試着再次通過最後三行。

此外，使用調試器對其進行分步操作，以防您無法看到您正在做什麼。

Answer 2

那麼你有一些奇怪的東西在add功能回事，這裏的東西，可以幫助你理解這個過程：

void add(node* &head, int dataToAdd){ 
    node* newNode = new node(); 
    newNode->data = dataToAdd; 

    if(!head){ // checking to see if head was passed in or is null 
     head = newNode; 
     return; 
    } 

    node* current = head; 
    node* next = current->next; 
    // iterate through the list till next == Null(hits 1 after the end) 
    while(current->next){ 
     current = next; 
     next = next->next; 
    } 

    //Set the end of the list to the newly added node 
    next = newNode; 
    next->prev = current; 

} 

Answer 3

這是排什麼是應該做的？

tmp->next; 

使用鏈表可以是一個真正的大腦鍛鍊不時。我建議你直接將指針初始化爲NULL。關於最後三行，他們需要再次思考。

tmp = current; //This discards your newly created node, which results in a memory leak 
tmp->prev = current->prev->next; // The previous node is simply 'current' 
tmp->next = current->next; // You know that the next node will be NULL 

的current節點也需要知道新current->next將是什麼。

Answer 4

你需要做的更像是這個：

void Add(node* &head, int newdata) 
{ 
    //create a new node to hold the data with a terminal (NULL) next pointer   
    node *tmp = new node; 
    tmp->data = newdata; 
    tmp->next = NULL; 
    tmp->prev = NULL; 

    if (!head) 
     head = tmp; 
    else 
    { 
     //find the end of the chain with a pointer 
     node *last = head; 
     while (last->next != NULL) 
      last = last->next; 

     //add the new node on to the last node in the list 
     //set pointers both forward and backwards 
     last->next = tmp; 
     tmp->prev = last; 
    } 
} 

如果跟蹤的最後一個節點的用頭一起，你的插入會快得多，你就不必遍歷整個列表每一次，如：

struct list 
{ 
    node *head; 
    node *tail; 
}; 

void Add(list &l, int newdata) 
{ 
    node *tmp = new node; 
    tmp->data = newdata; 
    tmp->next = NULL; 

    if (!l.head) 
     l.head = tmp; 

    tmp->prev = l.tail; 
    if (tmp->prev) 
     tmp->prev->next = tmp; 

    l.tail = tmp; 
} 

話雖這麼說，因爲你正在使用C++，你真的應該使用std::list，它處理這一切爲您：

#include <list> 

std::list<int> mylist; 
mylist.push_back(12345); 
// etc...