c - 为什么我的链表删除功能不起作用？

Question

我的 C/C++ 链表删除函数没有从列表中删除元素。以下是我的一些代码；

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

typedef struct listIntElement ListIntElement;
ListIntElement *head = NULL;

/*
 Inserts a new element infront of the list.
*/
bool insert(ListIntElement **head, int data) {

    // Allocate memory for new element. The cast is needed here as we are using a C++ compiler.
    ListIntElement *newElement = (ListIntElement *) malloc(sizeof(ListIntElement));

    // Check if memory allocation was succesfull.
    if (newElement == NULL)
        return false;

    // Set the data for the new element of the list.
    newElement->data = data;
    // Keep track of the new head of the list.
    newElement->next = *head;
    *head = newElement;

    return true;
}

/*
Deleting an element in the list.
*/
bool remove(ListIntElement **head, ListIntElement *elementToDelete) {
    ListIntElement *element = *head;

    // Check for NULL pointers.
    if (head == NULL || *head == NULL || elementToDelete == NULL)
        return false;

    // Special case for the head.
    if (elementToDelete == *head) {
        *head = element->next;
        free(elementToDelete);
        return true;
    }

    // Traversal of the list to find the element to remove.
    while (element != NULL) {
        if (element->next == elementToDelete) {
            // Relink the list so that it does not include the element to be deleted.
            element->next = elementToDelete->next;
            free(elementToDelete);
            return true;
        }
        element = element->next;
    }
    // elementToDelete was not found.
    return false;
}

/*
Finding an element in the list.
*/
ListIntElement find(ListIntElement **head, int data) {
    // Take care of the head as we don't want to use the head
    // in the traversal operation.
    ListIntElement *element = *head;
    while (element != NULL && element->data != data) {
        element = element->next;
    }
    return *element;
}

/*
Displaying the list.
*/
void displayList(ListIntElement **head) {
    ListIntElement *element = *head;

    // Check if list is empty.
    if (head == NULL | *head == NULL) {
        printf("List is empty\n");
    }

    while (element != NULL) {
        printf("%d --> ", element->data);
        element = element->next;
    }
    printf("NULL");
    printf("\n");
}

这是我的测试代码；

/*
 *  Testing a linked list.
 */
ListIntElement found;

printf("Linked list test\n");
insert(&head,0);
insert(&head, 1);
insert(&head, 2);
insert(&head, 3);
insert(&head, 4);
insert(&head, 5);
displayList(&head);
printf("size is: %d\n", size(&head));
found = find(&head, 5);
printf("This was found: %d\n", found.data);
remove(&head,&found);
displayList(&head);

我发现这部分是删除功能出错的部分；

// Special case for the head.
if (elementToDelete == *head) {
    *head = element->next;
    free(elementToDelete);
    return true;
}

请注意，我正在使用 MS Visual Studio 2015 编写 C 代码并使用 C++ 编译器。

Answer 1

在 find 函数中，您返回的是一个副本，而不是地址本身，因此您的更改不会反射(reflect)在调用函数中。修复它。

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

#define true 1
#define false 0

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

typedef struct listIntElement ListIntElement;
ListIntElement *head = NULL;

/*
 Inserts a new element infront of the list.
*/
bool insert(ListIntElement **head, int data) {

    // Allocate memory for new element. The cast is needed here as we are using a C++ compiler.
    ListIntElement *newElement = (ListIntElement *) malloc(sizeof(ListIntElement));

    // Check if memory allocation was succesfull.
    if (newElement == NULL)
        return false;

    // Set the data for the new element of the list.
    newElement->data = data;
    // Keep track of the new head of the list.
    newElement->next = *head;
    *head = newElement;

    return true;
}

/*
Deleting an element in the list.
*/
bool removeElement (ListIntElement **head, ListIntElement *elementToDelete) {
    ListIntElement *element = *head;

    // Check for NULL pointers.
    if (head == NULL || *head == NULL || elementToDelete == NULL)
        return false;

    // Special case for the head.
    if (elementToDelete == *head) {
        *head = element->next;
        free(elementToDelete);
        return true;
    }

    // Traversal of the list to find the element to remove.
    while (element != NULL) {
        if (element->next == elementToDelete) {
            // Relink the list so that it does not include the element to be deleted.
            element->next = elementToDelete->next;
            free(elementToDelete);
            return true;
        }
        element = element->next;
    }
    // elementToDelete was not found.
    return false;
}


/*
Finding an element in the list.
*/
ListIntElement *find(ListIntElement **head, int data) {
    // Take care of the head as we don't want to use the head
    // in the traversal operation.
    ListIntElement *element = *head;
    while (element != NULL && element->data != data) {
        element = element->next;
    }
    return element;
}

/*
Displaying the list.
*/
void displayList(ListIntElement **head) {
    ListIntElement *element = *head;

    // Check if list is empty.
    if (head == NULL | *head == NULL) {
        printf("List is empty\n");
    }

    while (element != NULL) {
        printf("%d --> ", element->data);
        element = element->next;
    }
    printf("NULL");
    printf("\n");
}

int main () {
    ListIntElement *found;

    printf("Linked list test\n");
    insert(&head,0);
    insert(&head, 1);
    insert(&head, 2);
    insert(&head, 3);
    insert(&head, 4);
    insert(&head, 5);
    displayList(&head);
    printf("size is: %d\n", sizeof(&head));
    found = find(&head, 5);
    printf("This was found: %d\n", found->data);
    removeElement(&head,found);
    displayList(&head);

}

输出:

Linked list test
5 --> 4 --> 3 --> 2 --> 1 --> 0 --> NULL
size is: 4
This was found: 5
4 --> 3 --> 2 --> 1 --> 0 --> NULL