如何從鏈表中刪除節點？

Question

將整數添加到列表中可以正常工作，但是刪除和打印有問題。

我對調試器還不友好，但是我發現節點指針'第一個'有錯誤。它的值是-17891602。我不知道發生了什麼......

#include <iostream> 
using namespace std; 

class nodeList; 

class node { 
    friend class nodeList; 
private: 
    int data; 
    node* link; 
public: 
    node() { //constructor 
     data = 0; 
     link = NULL; 
    } 
    node(int d) { //constructor 
     data = d; 
     link = NULL; 
    } 
    node(int d, node* l){ //constructor 
     data = d; 
     link = l; 
    } 
}; 

class nodeList { 
private: 
    node* first; 
    int num = 0; 
    node* nt; 
public: 
    nodeList() { 
     first = new node(); 
    } 
    node* end(node* t){ //return pointer of last element 
     t = first; 
     for (int i = 0; i < num; i++){ 
      t = t->link; 
     } 
     return t; 
    } 
    void add(int a){ //add 'a' at the end of the list 
     node* x = new node(a); 
     node* y = this->end(nt); 
     y->link = x; 
     num++; 
    } 

    void del(int n){ //n : data of element that you want to delete from list 
     node* temp = first; 
     node* pretemp = NULL; 
     node* x; 
     int i; 
     for (i = 0; i <= this->num; i++){ //loop to find 'n' 
      pretemp = temp; 
      temp = temp->link; 
      if (n == temp->data){ 
       break; 
      } 
     } 
     temp = first; 
     for (int j = 0; j<i; j++){ //i : where 'n' is, 
      temp = temp->link; 
     } 
     x = temp->link; 
     pretemp->link = x; 
     delete temp; 
     num--; 
    } 
    void printList(){ 
     node* temp = first; 
     temp = temp->link; 
     for (int i = 0; i<this->num; i++){ 
      cout << temp->data << endl; 
      temp = temp->link; 
     } 
    } 
}; 

int main(){ 
    nodeList *l = new nodeList(); 
    int a; 
    int select; 
    while (1){ 
     cout << "1. ADD 2. DELETE 3. PRINT" << endl; 
     cin >> select; 

     if (select == 1){ 
      cout << "Enter an integer: "; 
      cin >> a; 
      if (cin.fail()) { 
       cout << "Wrong input" << endl; 
       break; 
      } 
      l->add(a); 
      l->printList(); 
     } 

     if (select == 2){ 
      cout << "Enter the data of the element you want to delete: "; 
      cin >> a; 
      if (cin.fail()) { 
       cout << "Wrong input" << endl; 
       break; 
      } 
      l->del(a); 
      l->printList(); 
     } 

     if (select == 3){ 
      l->printList(); 
     } 
    } 
} 

Answer 1

你del函數刪除pretemp節點（即是，你需要刪除一個節點之前）。

下面是可能的解決辦法：

//n : data of element that you want to delete from list 
void del(int n) 
{ 
    //loop to find 'n' 
    for (node *tmp = first; tmp->link; tmp = tmp->link) 
    { 
     if (n == tmp->link->data) 
     { 
      node *x = tmp->link; 
      tmp->link = tmp->link->link; 
      delete x; 
      num--; 
      break; 
     } 
    } 
} 

此外，被你del應該與data == n刪除所有節點？

Answer 2

這些功能有點複雜。這是一個更簡單的想法：

void del(int n){ 
    node* pretemp = first, *temp = first->link; 
    if(pretemp->data == n) { //handle the deleting of the first node 
      first = first->link; 
      delete pretemp; 
      return; 
    } 
    while(temp != NULL && temp->data != n) { //find the node with the data member "n" 
      pretemp = temp; 
      temp = temp->link; 
    } 
    if(temp != NULL) { //if you found the node, delete it 
      pretemp->link = temp->link; 
      delete temp; 
    } 
    --num; 
} 

Answer 3

你的代碼有點過於複雜，它需要什麼。

嘗試一些更喜歡這個：如果你

class nodeList 
{ 
private: 
    node* first; 
    node* last; 
    int num; 

public: 
    nodeList() 
     : first(NULL), last(NULL), num(0) 
    { 
    } 

    ~nodeList() 
    { 
     node *n = first, *t; 
     while (n) 
     { 
      t = n->link; 
      delete n; 
      n = t; 
     } 
    } 

    void add(int data) //add 'data' at the end of the list 
    { 
     node* n = new node(data); 
     if (!first) 
      first = n; 
     if (last) 
      last->link = n; 
     last = n; 
     ++num; 
    } 

    void del(int data) //data : data of element that you want to delete from list 
    { 
     node* n = first; 
     node* prev = NULL; 

     while (n) //loop to find 'data' 
     { 
      if (data == n->data) 
      { 
       if (prev) 
        prev->link = n->link; 
       if (n == first) 
        first = n->link; 
       if (n == last) 
        last = prev; 
       delete n; 
       --num; 
       return; 
      } 
      prev = n; 
      n = n->link; 
     } 
    } 

    void printList() 
    { 
     for(node* n = first; n != NULL; n = n->link) 
      cout << n->data << endl; 
    } 
}; 

和：

#include <iostream> 
#include <limits> 

using namespace std; 

class nodeList; 

class node 
{ 
    friend class nodeList; 

private: 
    int data; 
    node* link; 

public: 
    node(int d = 0) //constructor 
     : data(d), link(NULL) 
    { 
    } 
}; 

class nodeList 
{ 
private: 
    node* first; 
    int num; 

public: 
    nodeList() 
     : first(NULL), num(0) 
    { 
    } 

    ~nodeList() 
    { 
     node *n = first, *t; 
     while (n) 
     { 
      t = n->link; 
      delete n; 
      n = t; 
     } 
    } 

    void add(int data) //add 'data' at the end of the list 
    { 
     node* n = new node(data); 
     if (!first) 
      first = n; 
     else 
     { 
      node *t = first; 
      while (t->link) 
       t = t->link; 
      t->link = n; 
     } 
     ++num; 
    } 

    void del(int data) //data : data of element that you want to delete from list 
    { 
     node* n = first; 
     node* prev = NULL; 

     while (n) //loop to find 'data' 
     { 
      if (data == n->data) 
      { 
       if (prev) 
        prev->link = n->link; 
       if (n == first) 
        first = n->link; 
       delete n; 
       --num; 
       return; 
      } 
      prev = n; 
      n = n->link; 
     } 
    } 

    void printList() 
    { 
     for(node* n = first; n != NULL; n = n->link) 
      cout << n->data << endl; 
    } 
}; 

int main() 
{ 
    nodeList l; 
    int input; 
    bool keepGoing = true; 

    do 
    { 
     cout << "1. ADD 2. DELETE 3. PRINT 4. EXIT" << endl; 
     if (!(cin >> input)) 
     { 
      cout << "Wrong input" << endl; 
      cin.clear(); 
      cin.ignore(numeric_limits<streamsize_t>::max(), '\n'); 
     } 
     else 
     { 
      switch (input) 
      { 
       case 1: 
        cout << "Enter an integer: "; 
        if (!(cin >> input)) 
        { 
         cout << "Wrong input" << endl; 
         cin.clear(); 
         cin.ignore(numeric_limits<streamsize_t>::max(), '\n'); 
        } 
        else 
        { 
         l.add(input); 
         l.printList(); 
        } 
        break; 

       case 2: 
        cout << "Enter the data of the element you want to delete: "; 
        if(!(cin >> input)) 
        { 
         cout << "Wrong input" << endl; 
         cin.clear(); 
         cin.ignore(numeric_limits<streamsize_t>::max(), '\n'); 
        } 
        else 
        { 
         l.del(input); 
         l.printList(); 
        } 
        break; 

       case 3: 
        l.printList(); 
        break; 

       case 4: 
        keepGoing = false; 
        break; 

       default: 
        cout << "Wrong input" << endl; 
        cin.clear(); 
        cin.ignore(numeric_limits<streamsize_t>::max(), '\n'); 
        break; 
      } 
     } 
    } 
    while (keepGoing); 

    return 0; 
} 

如果一個額外node*成員添加到您的nodeList類，可以簡化和加速您的add()方法可以將列表更改爲雙向鏈接列表而不是單鏈接列表，還可以簡化您的del()方法：

#include <iostream> 
#include <limits> 

using namespace std; 

class nodeList; 

class node 
{ 
    friend class nodeList; 

private: 
    int data; 
    node* prev; 
    node* next; 

public: 
    node(int d = 0) //constructor 
     : data(d), prev(NULL), next(NULL) 
    { 
    } 
}; 

class nodeList 
{ 
private: 
    node* first; 
    node* last; 
    int num; 

public: 
    nodeList() 
     : first(NULL), last(NULL), num(0) 
    { 
    } 

    ~nodeList() 
    { 
     node *n = first, *t; 
     while (n) 
     { 
      t = n->next; 
      delete n; 
      n = t; 
     } 
    } 

    void add(int data) //add 'data' at the end of the list 
    { 
     node* n = new node(data); 
     if (!first) 
      first = n; 
     if (last) 
      last->next = n; 
     n->prev = last; 
     last = n; 
     ++num; 
    } 

    void del(int data) //data : data of element that you want to delete from list 
    { 
     for(node* n = first; n != NULL; n = n->next) //loop to find 'data' 
     { 
      if (data == n->data) 
      { 
       if (n->prev) 
        n->prev->next = n->next; 
       if (n->next) 
        n->next->prev = n->prev; 
       if (n == first) 
        first = n->next; 
       if (n == last) 
        last = n->prev; 
       delete n; 
       --num; 
       return; 
      } 
     } 
    } 

    void printList() 
    { 
     for(node* n = first; n != NULL; n = n->next) 
      cout << n->data << endl; 
    } 
};