圓形鏈表：如何糾正我的刪除節點功能？

我正在學習循環鏈表。撥打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

圓形鏈表：如何糾正我的刪除節點功能？

回答

相關問題