C++链表不删除头节点

我有一个非常简单的节点类来实现链表（它只有数据和下一个指针）。下面的函数应该删除其“数据”=值的FIRST节点。该功能可以正常工作。但是当我尝试删除第一个元素（列表的头部）时，它不会。那么，问题在哪里？下面是代码C++链表不删除头节点

class Node{ 
    public: 
     int data; 
     Node *next; 
....some other functions... 

}; 
void deleteNode(Node *n, int value){ 
    cout<<"after deleting node with data = "<<value<<" : "; 
    if(n->data == value){ 
     n = n->next;  //I guess the problem is somewhere here! 
     return; 
    } 
    while(n){ 
     if(n->next->data == value){ 
      n->next = n->next->next; 
      return; 
     } 
     n = n->next; 
    } 
} 

void printTheLinkedList(Node *n){ 
    while(n){ 
     cout<<n->data<<" --> "; 
     n = n->next; 
    } 
    cout<<"NULL"<<endl; 
} 


int main(){ 
    Node N(0); 
    for(int i = 1; i < 10; i++) 
     N.appendNode(i); 

    printTheLinkedList(&N); 
    deleteNode(&N, 3); 
    printTheLinkedList(&N); 
    deleteNode(&N, 0); 
    printTheLinkedList(&N); 


    return 0; 
}

这里是代码的输出（注：3被删除，但0不是）

0 --> 1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> NULL 
0 --> 1 --> 2 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> NULL 
0 --> 1 --> 2 --> 4 --> 5 --> 6 --> 7 --> 8 --> 9 --> NULL

来源

2014-02-17 CSawy

相关：让所有* *在你的链接列表中的节点动态。没有必要保持一个哨兵非动态头节点。 'nullptr'是用于推导“list-is-empty”状态的不够精确的哨兵值。 – WhozCraig

你改变局部变量n是n->next， main的头值实际上并未改变。试试这个，它返回新的头部。

Node* deleteNode(Node *n, int value){ 
    cout<<"after deleting node with data = "<<value<<" : "; 
    if(n->data == value){ 
     n = n->next;  //I guess the problem is somewhere here! 
     return n; 
    } 
    Node* root = n; 
    while(n){ 
     if(n->next->data == value){ 
      n->next = n->next->next; 
      return; 
     } 
     n = n->next; 
    } 
    return root; 
}

然后调用，如：

printTheLinkedList(&N); 
Node* head = deleteNode(&N, 3); 
printTheLinkedList(head); 
head = deleteNode(head, 0); 
printTheLinkedList(head);

来源

2014-02-17 01:41:12 user1520427

我个人认为NobuGames的回答比较好，请确保遵循他的建议！ – user1520427

首先，你是对的，在你的代码注释你的猜测。这条线与这个问题有关。

有三个问题：因为它是在栈上分配为您main函数的局部变量

根节点不能删除。
链接的节点需要封装在容器数据结构中，如linked_list。它将在内部（至少）存储指向链表的head（例如开始）的指针。如果head节点被删除，你可以设置下一个指针作为head
你删除的代码目前不会释放动态分配的节点，所以您的应用程序正在泄漏内存。

由于您使用的是C++编码，因此您可以使用智能指针来处理自动释放。

来源

2014-02-17 01:43:15 tiguchi

+1我同意智能指针的思路，并*全心全意地支持它的使用。在使用链接节点系统时应特别小心，特别是在删除它们时。如何释放这样的节点系统（例如100,000个项目的链接列表）*而不会引发快速消耗呼叫激活栈遗忘的节点析构函数的递归并不一定直观。它*非常好，适合使用它们，不会犯错。但是这样做需要一些额外的技巧。 – WhozCraig

@WhozCraig感谢您分享您的意见！这种情况根本不存在，但非常合理。在C++中有很多小陷阱可供发现：-D – tiguchi

完全没问题。以我所指的为例，[**见它现场**]（http://ideone.com/DfTa0s） – WhozCraig

你定义头

Node N(0);

因此，你不能删除这个节点（头）。你应该声明头指向节点

Node *N(nullptr);

在这种情况下，功能可以看看下面的方式

void deleteNode(Node * &n, int value) 
{ 
    cout << "after deleting node with data = " << value << " : "; 

    Node *current = n; 
    Node *previous = nullptr;; 

    while (current && current->data != value) 
    { 
     previous = current; 
     current = current->next; 
    } 

    if (current) 
    { 
     if (previous) previous->next = current->next; 
     else n = nullptr; 

     delete current; 
    } 
}

来源

2014-02-17 02:00:23

C++链表不删除头节点

回答

相关问题