链表指定元素定位删除代码实现：计算机课程双函数开发技术问询

Hey there! Let's walk through implementing the linked list element removal functionality you need. We'll break this into two core parts: the locateNode helper function and the Remove function that uses it. First, let's make sure we have our linked list node structure defined—since that's the foundation of everything here.

1. Linked List Node Structure #

We'll use a simple integer node for this example (adjust if your course uses a different data type):

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

// Define the node structure
typedef struct Node {
    int data;
    struct Node* next;
} Node;

2. Implement the locateNode Helper Function #

This function needs to traverse the list, find the target integer, and return two pieces of info: the index of the target node, and the index of its previous node. Since C doesn't let us return multiple values directly, we can use pointers to integers to store these outputs (a common approach in course assignments).

The function will return 1 if the target is found, 0 if it doesn't exist in the list:

// locates target element, fills targetIdx and prevIdx with respective indices
// returns 1 if found, 0 otherwise
int locateNode(Node* head, int target, int* targetIdx, int* prevIdx) {
    if (head == NULL) {
        *targetIdx = -1;
        *prevIdx = -1;
        return 0; // empty list
    }

    int currentIdx = 0;
    Node* current = head;
    Node* prev = NULL;

    while (current != NULL) {
        if (current->data == target) {
            *targetIdx = currentIdx;
            *prevIdx = (prev == NULL) ? -1 : currentIdx - 1;
            return 1;
        }
        prev = current;
        current = current->next;
        currentIdx++;
    }

    // target not found
    *targetIdx = -1;
    *prevIdx = -1;
    return 0;
}

Key Notes on locateNode: #

• We handle empty lists first to avoid null pointer errors.
• We keep track of both the current node and its predecessor as we traverse.
• If the target is the head node, prevIdx is set to -1 (since there's no previous node).

3. Implement the Remove Function #

Now, using locateNode, we can adjust the pointers to remove the target node. We need to handle three main cases:

1. The target isn't in the list (do nothing).
2. The target is the head node (update the head pointer).
3. The target is a middle or tail node (make the previous node point to the target's next node).

Here's the implementation:

// Removes the first occurrence of target from the list
// Returns 1 if removal was successful, 0 otherwise
int Remove(Node** head, int target) {
    int targetIdx, prevIdx;
    if (!locateNode(*head, target, &targetIdx, &prevIdx)) {
        return 0; // target not found
    }

    Node* toDelete = NULL;

    if (prevIdx == -1) {
        // Target is the head node
        toDelete = *head;
        *head = (*head)->next;
    } else {
        // Traverse to the previous node
        Node* prevNode = *head;
        for (int i = 0; i < prevIdx; i++) {
            prevNode = prevNode->next;
        }
        toDelete = prevNode->next;
        prevNode->next = toDelete->next;
    }

    free(toDelete); // Don't forget to free allocated memory!
    return 1;
}

Key Notes on Remove: #

• We use a double pointer (Node** head) because we might need to modify the head of the list (when removing the first node).
• After finding the target's position with locateNode, we handle the head node case separately since it has no predecessor.
• Always free the memory of the deleted node to avoid memory leaks—this is crucial in languages like C!

Quick Test Example #

To make sure this works, here's a small test snippet you can run:

// Helper function to print the list
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL\n");
}

int main() {
    // Create a sample list: 10 -> 20 -> 30 -> 40
    Node* head = (Node*)malloc(sizeof(Node));
    head->data = 10;
    head->next = (Node*)malloc(sizeof(Node));
    head->next->data = 20;
    head->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->data = 30;
    head->next->next->next = (Node*)malloc(sizeof(Node));
    head->next->next->next->data = 40;
    head->next->next->next->next = NULL;

    printf("Original list: ");
    printList(head);

    // Remove 30
    Remove(&head, 30);
    printf("After removing 30: ");
    printList(head);

    // Remove head (10)
    Remove(&head, 10);
    printf("After removing head (10): ");
    printList(head);

    // Remove non-existent element
    if (!Remove(&head, 50)) {
        printf("Element 50 not found, no removal done.\n");
    }

    return 0;
}

This should output:

Original list: 10 -> 20 -> 30 -> 40 -> NULL
After removing 30: 10 -> 20 -> 40 -> NULL
After removing head (10): 20 -> 40 -> NULL
Element 50 not found, no removal done.

内容的提问来源于stack exchange，提问作者DemonSlayer730