循环链表开头删除

Question

如果列表有多个节点，我的函数能够删除列表前面的节点。 如果列表中只剩下一个节点，则不会发生删除操作。

#include<stdio.h>
#include<stdlib.h>

//Circular linked list node structure
typedef struct circularLinkedListNode{
    int data;
    struct circularLinkedListNode *next;
}circularLinkedListNode;

circularLinkedListNode *head = NULL;

//Traversal of circular linked list
void traversal()
{
    circularLinkedListNode *current = head;

    if(current == NULL)
    {
        printf("\nThe list is empty!!");
    }
    else
    {
        do {
            printf("%d--", current->data);
            current = current->next;
        } while (current != head);
    }
}

//Insertion at the beginning of the list
void insertAtBeginning(int data)
{
    circularLinkedListNode *newNode = (circularLinkedListNode *)malloc(sizeof(circularLinkedListNode));

    //Create a new node and point it to itself
    newNode->data = data;
    newNode->next = newNode;

    if(head == NULL)
    {
        head = newNode;
    }
    else
    {
        circularLinkedListNode *current = head;
        while (current->next != head) {
            current = current->next;
        }
        current->next = newNode;
        newNode->next = head;
        head = newNode;
    }
}

//Insertion at the end of the list
void insertAtEnd(int data)
{
    circularLinkedListNode *newNode = (circularLinkedListNode *)malloc(sizeof(circularLinkedListNode));
    newNode->data = data;
    newNode->next = newNode;

    if(head == NULL)
    {
        head = newNode;
    }
    else
    {
        circularLinkedListNode *current = head;
        while(current->next != head)
        {
            current = current->next;
        }
        newNode->next = head;
        current->next = newNode;
    }
}

主要问题出在这个函数上:::::

//Deletion of node at the beginning
void deleteATBeginning()
{
    if(head == NULL)
    {
        printf("\nEmpty list!!");
    }
    else
    {
        circularLinkedListNode *nodeToDelete = head;
        circularLinkedListNode *current = head;
        while(current->next != head)
        {
            current = current->next;
        }
        current->next = head->next;
        head = head->next;
        free(nodeToDelete);
    }
}

int main()
{
    int data, choice;

    while (1)
    {
        printf("\n***CIRCULAR LINKED LIST***\n1.Traversal\n2.Insertion at the beginning\n3.Insertion at the end\n4.Deletion of front node\n5.Deletion of end node\n6.Exit\nEnter your choice: ");
        scanf("%d", &choice);

        switch (choice)
        {
            case 1:
                traversal();
                break;

            case 2:
                printf("Enter the data: ");
                scanf("%d", &data);
                insertAtBeginning(data);
                break;

            case 3:
                printf("Enter the data: ");
                scanf("%d", &data);
                insertAtEnd(data);
                break;

            case 4:
                deleteATBeginning();
                break;

            case 6:
                return 0;
                break;

            default:
                printf("Wrong choice!! Please try again...");
                break;
        }
    }
}

Answer 1

你的代码看起来有点复杂，但它应该可以工作。我认为当你说“列表删除没有发生”时，你并不是在寻找它正确发生。

您正在寻找 head 变为 null 以确认删除已发生:

if(head == NULL)
{
    printf("\nEmpty list!!");

但是你永远不会考虑删除列表中唯一节点的特殊情况，因此 head 永远不会变成 null (这不会自行发生)。

这可以很简单:

if(head->next == head) // if the head's next node is itself
{
    head->next = null;
    free(nodeToDelete);
    head = null;
} 
else
{
    while(current->next != head)
    {
        current = current->next;
    // ...rest of your code as is

您的代码当前正在free'ing head指向的内存，但它没有释放(null'ing)内存位置，因此您的 head 指针仍然指向内存，但该内存不再属于您的程序。这是一个悬空指针。您可能仍会看到节点的内容为“有效”，但这只是偶然，因为此时没有其他内容进入并重新分配内存。