如何在二叉搜索树节点的链表中插入IP并处理重复用户？

Got it, let's work through this problem together. You're trying to insert an IP address into the linked list of an existing BST node (where the node's data matches a target username). Let's break this down into manageable parts, starting with the IP linked list insertion since that's where you're stuck, then tying it to the BST lookup.

First, let's write a helper function that takes an IP head pointer and a new IP value, then adds the IP to the linked list. You have two common options here: head insertion (simpler, but IPs are added in reverse order) or tail insertion (preserves insertion order, requires traversing the list).

Option 1: Tail Insertion (Preserves Order) #

This is usually preferable if you want to keep IPs in the order they were added:

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

// Helper function to create a new IP node
IP* createIPNode(int ip) {
    IP* newIP = (IP*)malloc(sizeof(IP));
    if (!newIP) {
        // Handle memory allocation failure (e.g., print error and return NULL)
        return NULL;
    }
    newIP->ip = ip;
    newIP->ipNext = NULL;
    return newIP;
}

// Insert IP at the end of the linked list
int insertIPToList(IP** ipHead, int ip) {
    IP* newIP = createIPNode(ip);
    if (!newIP) {
        return -1; // Indicate failure
    }

    if (*ipHead == NULL) {
        // List is empty; make new IP the head
        *ipHead = newIP;
        return 0;
    }

    // Traverse to the end of the list
    IP* current = *ipHead;
    while (current->ipNext != NULL) {
        current = current->ipNext;
    }
    current->ipNext = newIP;
    return 0; // Success
}

Option 2: Head Insertion (Simpler, Reverse Order) #

If insertion order doesn't matter, this is quicker since you don't need to traverse the list:

int insertIPAtHead(IP** ipHead, int ip) {
    IP* newIP = createIPNode(ip);
    if (!newIP) {
        return -1;
    }
    newIP->ipNext = *ipHead;
    *ipHead = newIP;
    return 0;
}

Next, we need a function to search the BST for the node matching the target username. Remember, BSTs are ordered: left children have smaller strings, right children have larger strings (using strcmp for comparison).

bstNode* findBSTNode(bstNode* root, const char* username) {
    if (root == NULL) {
        return NULL; // User not found
    }

    int cmpResult = strcmp(username, root->data);
    if (cmpResult == 0) {
        return root; // Found the target node
    } else if (cmpResult < 0) {
        // Username is smaller; search left subtree
        return findBSTNode(root->left, username);
    } else {
        // Username is larger; search right subtree
        return findBSTNode(root->right, username);
    }
}

Now, put it all together. The main logic will be:

1. Search the BST for the target user.
2. If found, insert the IP into their linked list.
3. If not found, handle the case (e.g., print an error, or optionally create a new BST node if needed).

// Main function to add IP to user's BST node
int addIPToUser(bstNode* root, const char* username, int ip) {
    bstNode* targetNode = findBSTNode(root, username);
    if (!targetNode) {
        printf("User %s not found in BST.\n", username);
        return -1;
    }

    // Use tail insertion (or replace with insertIPAtHead if preferred)
    int result = insertIPToList(&targetNode->ipHead, ip);
    if (result == 0) {
        printf("Successfully added IP %d to user %s.\n", ip, username);
    } else {
        printf("Failed to add IP %d to user %s.\n", ip, username);
    }
    return result;
}

• Memory Management: Always check if malloc returns NULL to handle out-of-memory errors gracefully.
• String Comparison: Never use == to compare strings in C—always use strcmp (from <string.h>).
• Double Pointers: Notice we use IP** in the insertion functions—this lets us modify the original head pointer if the list was empty.
• BST Order: Ensure your BST is correctly maintained when inserting new user nodes (if you need that functionality later) to keep the search function working properly.

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