如何以类队列方式在链表中查找匹配项并同步删除LL与文件匹配条目？

Alright, let's break down how to tackle this task step by step. I'll walk you through the core components, code examples, and key considerations to handle up to 60k entries smoothly—no fancy jargon, just practical, working code and explanations.

Here's the high-level flow we'll follow:

• Read the entire input file into a linked list (LL) where each node stores one entry's data.
• Traverse the LL in FIFO (queue-style) order to find matching entries.
• Write matching entries to an output file.
• Remove matching entries from both the LL and the original input file.

First, we need a node that can hold all four fields from your input. Here's a straightforward C implementation (since you mentioned low-level types like int and long long, C is a solid fit here):

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

#define MAX_NAME_LENGTH 51 // Leave 1 byte for the null terminator

// Linked list node to store each entry
typedef struct Node {
    int time;               // Time field (integer)
    char action;            // Action ('A' for ask, 'B' for bid)
    long long pk;           // 11-digit PK (long long to avoid overflow)
    char name[MAX_NAME_LENGTH]; // Name string (max 50 chars)
    struct Node* next;      // Pointer to next node
} Node;

Next, we'll write functions to create nodes and populate the LL from the input file. We'll handle up to 60k entries easily—memory won't be an issue here (each node is ~72 bytes, so 60k nodes are only ~4MB).

// Create a new node with given data
Node* createNode(int time, char action, long long pk, const char* name) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        perror("Failed to allocate memory for node");
        exit(EXIT_FAILURE);
    }
    newNode->time = time;
    newNode->action = action;
    newNode->pk = pk;
    strncpy(newNode->name, name, MAX_NAME_LENGTH - 1);
    newNode->name[MAX_NAME_LENGTH - 1] = '\0'; // Ensure string is null-terminated
    newNode->next = NULL;
    return newNode;
}

// Read input file and build the linked list
Node* readFileToLinkedList(const char* filename) {
    FILE* file = fopen(filename, "r");
    if (!file) {
        perror("Failed to open input file");
        exit(EXIT_FAILURE);
    }

    Node* head = NULL;
    Node* tail = NULL;
    int time;
    char action;
    long long pk;
    char name[MAX_NAME_LENGTH];

    // Read each line in the format: Time Action PK Name
    while (fscanf(file, "%d %c %lld %s", &time, &action, &pk, name) == 4) {
        Node* newNode = createNode(time, action, pk, name);
        if (!head) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }
    }

    fclose(file);
    return head;
}

"Queue-style" means we'll traverse the LL from head to tail (FIFO order) to find matches. We'll also handle deleting matches from the LL and updating the original input file safely (using a temp file to avoid data loss if something goes wrong).

First, define your matching logic—here's an example that matches entries with action 'A' and a specific PK:

// Custom match function: adjust this to your actual matching rules
int isMatch(Node* node, long long targetPk) {
    return (node->action == 'A' && node->pk == targetPk);
}

// Process matches: write to output, remove from LL, update input file
void processMatches(Node** head, const char* outputFilename, const char* inputFilename, long long targetPk) {
    FILE* outputFile = fopen(outputFilename, "w");
    if (!outputFile) {
        perror("Failed to open output file");
        exit(EXIT_FAILURE);
    }

    // Temp file to store non-matching entries (for updating original input)
    FILE* tempFile = fopen("temp_input.txt", "w");
    if (!tempFile) {
        perror("Failed to open temp file");
        fclose(outputFile);
        exit(EXIT_FAILURE);
    }

    Node* current = *head;
    Node* prev = NULL;
    Node* nextNode;

    while (current != NULL) {
        nextNode = current->next; // Save next node before modifying current

        if (isMatch(current, targetPk)) {
            // Write matching entry to output file
            fprintf(outputFile, "%d %c %lld %s\n", current->time, current->action, current->pk, current->name);
            // Remove node from LL
            if (prev == NULL) {
                *head = nextNode; // Update head if we're removing the first node
            } else {
                prev->next = nextNode;
            }
            free(current); // Don't forget to free memory!
        } else {
            // Write non-matching entry to temp file (to replace original input)
            fprintf(tempFile, "%d %c %lld %s\n", current->time, current->action, current->pk, current->name);
            prev = current;
        }

        current = nextNode;
    }

    fclose(outputFile);
    fclose(tempFile);

    // Replace original input file with temp file (handle Windows/Linux differences)
    #ifdef _WIN32
        remove(inputFilename); // Windows requires deleting first before renaming
    #endif
    rename("temp_input.txt", inputFilename);
}

Always clean up allocated memory to avoid leaks. Add this function to free the entire LL when you're done:

// Free all nodes in the linked list
void freeLinkedList(Node* head) {
    Node* current = head;
    Node* nextNode;
    while (current != NULL) {
        nextNode = current->next;
        free(current);
        current = nextNode;
    }
}

Put it all together with a main function that ties everything up:

int main() {
    const char* inputFile = "input.txt";
    const char* outputFile = "matches.txt";
    long long targetPk = 12345678901; // Example target PK to match

    // Read input file into linked list
    Node* head = readFileToLinkedList(inputFile);

    // Process matches and update files/LL
    processMatches(&head, outputFile, inputFile, targetPk);

    // Free remaining nodes in the LL
    freeLinkedList(head);

    printf("Processing complete! Matches saved to %s, input file updated.\n", outputFile);
    return 0;
}

• Input Validation: In production, add checks to ensure action is only 'A' or 'B', pk is exactly 11 digits, and name doesn't exceed 50 characters. This prevents crashes from bad input.
• Matching Flexibility: Modify the isMatch function to fit your actual matching rules (e.g., match a range of times, specific names, etc.).
• Performance: For 60k entries, this approach is more than fast enough—LL traversal is O(n), and file I/O is handled efficiently with buffered writes.
• Safety: Using a temp file to update the input file ensures you don't lose data if the program crashes mid-write.

内容的提问来源于stack exchange，提问作者Kārlis Amoliņš