c - 头部单链表中的元素删除不起作用

Question

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

struct node {
   int data;
   struct node *next;
};

struct node *head = NULL;
struct node *second = NULL;
struct node *third = NULL;

void insertAtBeg(struct node *n, int data) {
    struct node *temp;
    temp = (struct node *)malloc(sizeof(struct node));
    temp->data = data;
    temp->next = head;
    head = temp;
}
void insertAtEnd(struct node *n, int data) {
    struct node *temp;
    temp = (struct node*)malloc(sizeof(struct node));
    temp->data = data;
    temp->next = NULL;
    while (n->next != NULL) {
        n = n->next;
    }
    n->next = temp;
}
void deleteElement(struct node *head, int data) {
    if (head->data == data) {
        struct node *temp;
        temp = head;
        head = head->next;
        free(temp);
        printf("after deletion at head in function\n");
        printList(head);
    }
}
void printList(struct node *n) {
    while (n != NULL) {
        printf("%d\n", n->data);
        n = n->next;
    }
}
void main() {
    head = (struct node*)malloc(sizeof(struct node));
    second = (struct node*)malloc(sizeof(struct node));
    third = (struct node*)malloc(sizeof(struct node));
    head->data = 1;
    head->next = second;
    second->data = 2;
    second->next = third;
    third->data = 3;
    third->next = NULL;
    printList(head);
    insertAtBeg(head, 0);
    printf("after insertion at beginning\n");
    printList(head);
    insertAtEnd(head, 4);
    printf("after insertion at End\n");
    printList(head);
    deleteElement(head, 0);
    printf("after deletion at head in main\n");
    printList(head);
}

代码的输出是

1
2
3
after insertion at beginning
0
1
2
3
after insertion at End
0
1
2
3
4
after deletion at head in function
1
2
3
4
after deletion at head in main
0
1
2
3
4

为什么在 main 中调用的函数和在另一个函数中调用的函数的输出存在差异。即在函数​​中的 head 删除后和 main 中的 head 删除后，当两者都应该从同一个列表中删除元素时

标签： cpointersdata-structuressingly-linked-list

Answer 1

问题是在从列表中插入和/或删除元素时，您需要一种修改列表头部的方法。

一个简单的方法是让这些函数返回一个可能更新的头指针值，并让调用者将此返回值存储到它的head变量中。

这是具有这些语义的代码的修改版本：

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

struct node {
   int data;
   struct node *next;
};

struct node *insertAtBeg(struct node *head, int data) {
    struct node *temp;
    temp = (struct node *)malloc(sizeof(struct node));
    // should test for memory allocation failure
    temp->data = data;
    temp->next = head;
    return temp;
}
struct node *insertAtEnd(struct node *head, int data) {
    struct node *temp;
    struct node *n;
    temp = (struct node*)malloc(sizeof(struct node));
    // should test for memory allocation failure
    temp->data = data;
    temp->next = NULL;
    if (head == NULL)
        return temp;
    n = head;
    while (n->next != NULL) {
        n = n->next;
    }
    n->next = temp;
    return head;
}
struct node *deleteElement(struct node *head, int data) {
    // delete the first node with a given data
    if (head->data == data) {
        struct node *temp = head;
        head = head->next;
        free(temp);
    } else {
        struct node *n = head;
        while (n->next != NULL) {
            if (n->next->data == data) {
                struct node *temp = n->next;
                n->next = temp->next;
                free(temp);
                break;
            }
        }
    }
    return head;
}
void printList(const struct node *n) {
    while (n != NULL) {
        printf("%d\n", n->data);
        n = n->next;
    }
}
int main() {
    struct node *head = NULL;
    head = insertAtBeg(head, 1);
    head = insertAtEnd(head, 2);
    head = insertAtEnd(head, 3);
    printList(head);
    head = insertAtBeg(head, 0);
    printf("after insertion at beginning\n");
    printList(head);
    head = insertAtEnd(head, 4);
    printf("after insertion at End\n");
    printList(head);
    head = deleteElement(head, 0);
    printf("after deletion at head in main\n");
    printList(head);
    // should free the list
    return 0;
}

另一种方法是传递列表头指针的地址，以便函数可以在需要时对其进行修改。

这是使用这种替代方法的代码的修改版本：

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

struct node {
   int data;
   struct node *next;
};

struct node *insertAtBeg(struct node **headp, int data) {
    struct node *temp = malloc(sizeof(*temp));
    if (temp != NULL) {
        temp->data = data;
        temp->next = *headp;
        *headp = temp;
    }
    return temp;
}
struct node *insertAtEnd(struct node **headp, int data) {
    struct node *temp = malloc(sizeof(*temp));
    if (temp != NULL) {
        temp->data = data;
        temp->next = NULL;
        if (*headp == NULL) {
            *headp = temp;
        } else {
            struct node *n = *headp;
            while (n->next != NULL) {
                n = n->next;
            }
            n->next = temp;
        }
    }
    return temp;
}
int deleteElement(struct node **headp, int data) {
    // delete the first node with a given data
    struct node *head = *headp;
    if (head->data == data) {
        *headp = head->next;
        free(temp);
        return 1;  // node was found and freed
   } else {
        struct node *n = head;
        while (n->next != NULL) {
            if (n->next->data == data) {
                struct node *temp = n->next;
                n->next = temp->next;
                free(temp);
                return 1;  // node was found and freed
            }
        }
        return 0;  // node not found
    }
}
void printList(const struct node *n) {
    while (n != NULL) {
        printf("%d\n", n->data);
        n = n->next;
    }
}
int main() {
    struct node *head = NULL;
    insertAtBeg(&head, 1);
    insertAtEnd(&head, 2);
    insertAtEnd(&head, 3);
    printList(head);
    insertAtBeg(&head, 0);
    printf("after insertion at beginning\n");
    printList(head);
    insertAtEnd(&head, 4);
    printf("after insertion at End\n");
    printList(head);
    deleteElement(&head, 0);
    printf("after deletion at head in main\n");
    printList(head);
    // free the list
    while (head != NULL) {
        deleteElement(&head, head->data);
    }
    return 0;
}

这种替代方法使用双指针，因此初学者理解起来有点困难，但它有一个强大的优势：函数可以更新列表指针并提供有意义的返回值，可以通过测试来检测错误。例如insertAtBeg()，如果无法分配新节点但保留列表，则insertAtEnd()返回。NULL类似地deleteElement()可以返回一个指示元素是否找到的指示符。

使用这种方法，您可以编写函数来弹出列表的第一个或最后一个元素，或者给定索引处的元素，或者具有给定 的元素data，同时根据需要更新列表指针。