时间戳

首页 > 解决方案 > 在 C++ 中删除有序链表中的节点

c++ - 在 C++ 中删除有序链表中的节点

问题描述

我正在处理 C++ 中的有序链表。任务是从列表中删除笔记，我有两种方法/函数可以做到这一点。

/*
 * delete_head: Auxiliary function that deletes the first node of the list.
*/
book *delete_head(book*& deleteNode){
    head = deleteNode->next;
    delete deleteNode;
    
    return head;
} 

/*
 * delete_node: Method that deletes a node from the list. 
 */
 void delete_node(int c){
     book *aux = head;
     
     // Verify list isn't empty.
     if (head != NULL){
         // Case 1: the head should be deleted.
         if (aux->code == c){
             head = delete_head(head);
         } else {
             book *aux2 = head->next;
             while (aux2 != nullptr && aux2->code < c){
                 aux = aux2;
                 aux2 = aux2->next;
             } 
             // Case 2: node wasn't found.
             if (aux2 == NULL){
                 printf("Error: Node doesn't exist. \n");
             } else {
                 // Case 3: the tail should be removed.
                 if (aux2->next == NULL){
                     aux->next = NULL;
                     delete aux2;
                 } else {
                     // Case 4: A node from the middle should be removed.
                     aux->next = aux2->next;
                     delete aux2;
                 } 
             } 
         } 
     } else {
         printf("Error: Empty list. \n");
     } 
 }

我已经测试了代码和删除列表尾部或中间节点的情况确实有效。给我带来一些麻烦的是我需要删除头部的情况，我不确定它是否与指针的处理方式有关。

标签： c++linked-list

解决方案

您的辅助功能很无聊：

book *delete_head(book*& deleteNode){
    head = deleteNode->next;
    delete deleteNode;
    
    return head;
}

你用 来调用它head = delete_head(head);，但是当你这样做时，它deleteNode被设置为对指向头的指针的引用。这意味着你对你做的任何事情deleteNode也会对你做head——反之亦然。

这意味着在这里：delete deleteNode;您删除了两个 deleteNodeand head，这在您返回时有点问题head。

将功能更改为book *delete_head(book* deleteNode){，它应该做你想做的事。

推荐阅读