圆形链表：如何纠正我的删除节点功能？

我正在学习循环链表。拨打deleteNodeByKey()删除头节点时，我会遇到问题。它适用于其余节点的删除。为什么如果删除节点是头不工作？圆形链表：如何纠正我的删除节点功能？

#include <iostream> 
#include <stdlib.h> 
using namespace std; 

/* structure for a node */ 
struct node 
{ 
    int data; 
    struct node *next; 
}; 

/* Function to insert a node at the begining of a Circular 
    linked list */ 
void push(struct node **head_ref, int data) 
{ 
    struct node *ptr = (struct node*)malloc(sizeof(struct node)); 
    ptr->data = data; 
    ptr->next = *head_ref; 
    struct node *temp = *head_ref; 
    /* If linked list is not NULL then set the next of last node. 
     It is going to last node by circling 1 times. 
    */ 
    if(*head_ref != NULL){ 
     while(temp->next != *head_ref){ 
      temp = temp->next; 
     } 
     //set last node by ptr 
     temp->next = ptr; 
    } 
    else{ 
     // 1 node circular linked list 
     ptr->next = ptr; 
    } 
    // after push ptr is the new node 
    *head_ref = ptr; 
} 

//get the previous node 
struct node* getPreviousNode(struct node* current_node){ 
    struct node* prev = current_node; 
    while(prev->next != NULL && prev->next->data != current_node->data){ 
     prev = prev->next; 
    } 
    return prev; 
} 


/* Given a reference (pointer to pointer) to the head of a list 
    and a key, deletes the first occurrence of key in linked list */ 
void deleteNodeByKey(struct node **head_ref, int key) 
{ 
    // Store head node 
    struct node* current_node = *head_ref, *prev; 


    while(current_node != NULL && current_node->data != key){ 
     current_node = current_node->next; 
    } 

    if(current_node == NULL){ 
     return; 
    } 

    //Removing the node 
    if(current_node->data == key){ 
     prev = getPreviousNode(current_node); 
     prev->next = current_node->next; 
     current_node->next = NULL; 
     free(current_node);    
     return; 
    } 
} 


/* Function to print nodes in a given Circular linked list */ 
void printList(struct node *head) 
{ 
    struct node *temp = head; 
    if(head != NULL){ 
     /* 
      do-while because at 1st temp points head 
      and after 1 rotation temp wil come back to head again 
     */ 
     do{ 
      cout<<temp->data<<' '; 
      temp = temp->next; 
     } 
     while(temp != head); 
     cout<<endl; 
    } 
} 

int main() { 
    /* Initialize lists as empty */ 
    struct node *head = NULL; 
    /* Created linked list will be 11->2->56->12 */ 
    push(&head, 12); 
    push(&head, 56); 
    push(&head, 2); 
    push(&head, 11); 
    cout<<"Contents of Circular Linked List"<<endl; 
    printList(head); 

    deleteNodeByKey(&head, 11); 
    printList(head); 

    return 0; 
}

下面是代码链接：Source Code

来源

2017-02-16 user5005768

你面临什么问题？ – molbdnilo

寻求调试帮助的问题（**为什么不是这个代码工作？**）必须包含所需的行为，特定的问题或错误，以及在问题本身**中重现**所需的最短代码。没有**明确问题陈述**的问题对其他读者没有用处。请参阅：[如何创建最小，完整和可验证示例]（http://stackoverflow.com/help/mcve）。 – Biffen

@ user5005768标签说C++，但代码看起来像C.您可能想纠正一个或另一个。 – Biffen

内部deleteNodeByKey（）函数I添加一个if（）块重新分配头节点到它的下一个节点：

//Removing the node 
    if(current_node->data == key){ 
     //following if() is newly added 
     //key is inside head node 
     if(current_node == *head_ref){ 
      //changing the head point to next 
      *head_ref = current_node->next; 
     } 
     prev = getPreviousNode(current_node); 
     prev->next = current_node->next; 
     current_node->next = NULL; 
     free(current_node);    
     return; 
    }

来源

2017-02-27 09:17:18 user5005768

为了避开有关头部的缺失问题。我总是发现创建一个虚拟节点并设置你的头指针是很有用的。

node dummy; 
dummy.next = *head_ref; 

// Store head node 
struct node* current_node = &dummy, *prev = &dummy; 
current_node = current_node->next;

一旦你完成了操作，将头部设置回dummy.next。通过这种方式，您不再需要跟踪特殊情况的头部，可以将其视为正常节点。您在此修改的代码：deletion with dummy node

来源

2017-02-16 11:34:03

头节点不应该是链接列表的一部分，它应该是一个单独的节点，它保存着链接列表的第一个节点的地址。所以，当你删除第一个节点时，头指向第一个节点的下一个节点，当你遵循这个结构时，头节点将和其他节点一样。

声明头是这样的：

struct node* head; 
head = *first;

删除第一

head = head->next; 
free(first);`

来源

2017-02-16 11:52:26

圆形链表：如何纠正我的删除节点功能？

回答

相关问题