循环链表:如何更正我的删除节点功能?
Circular linked list: How to correct my remove node function?
我正在学习循环 linked 列表。我在调用 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;
}
代码如下link:Source Code
为了解决与删除头部相关的问题。我总是发现创建一个虚拟节点并将头指针指向该节点很有用。
node dummy;
dummy.next = *head_ref;
// Store head node
struct node* current_node = &dummy, *prev = &dummy;
current_node = current_node->next;
完成操作后,将头部设置回 dummy.next。这样你就不再需要跟踪特殊的 case head,它可以被视为一个普通的节点。您在此处修改的代码:deletion with dummy node
头节点不应该是链表的一部分,它应该是一个单独的节点,保存链表第一个节点的地址。因此,当您删除第一个节点时,使 Head 指向第一个节点的下一个节点,并且当您遵循此结构时,head-node 将与其他节点相同。
像这样声明头部:
struct node* head;
head = *first;
先删除
head = head->next;
free(first);`
在 deleteNodeByKey() 函数中,我添加了一个 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;
}
我正在学习循环 linked 列表。我在调用 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;
}
代码如下link:Source Code
为了解决与删除头部相关的问题。我总是发现创建一个虚拟节点并将头指针指向该节点很有用。
node dummy;
dummy.next = *head_ref;
// Store head node
struct node* current_node = &dummy, *prev = &dummy;
current_node = current_node->next;
完成操作后,将头部设置回 dummy.next。这样你就不再需要跟踪特殊的 case head,它可以被视为一个普通的节点。您在此处修改的代码:deletion with dummy node
头节点不应该是链表的一部分,它应该是一个单独的节点,保存链表第一个节点的地址。因此,当您删除第一个节点时,使 Head 指向第一个节点的下一个节点,并且当您遵循此结构时,head-node 将与其他节点相同。
像这样声明头部:
struct node* head;
head = *first;
先删除
head = head->next;
free(first);`
在 deleteNodeByKey() 函数中,我添加了一个 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;
}