C语言实现前缀树ip查找

前缀树（Trie树）是一种多叉树结构，用于存储字符串集合，并支持高效的字符串匹配操作。在IP地址查找中，我们可以将每个IP地址转化为字符串，然后将这些字符串插入到前缀树中。具体实现如下：

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

#define IP_SIZE 32 // IP地址的二进制位数
#define MAX_IP_NUM 100 // 最大IP地址数

// 前缀树节点结构体
typedef struct TrieNode {
    int count; // 记录该节点对应的IP地址数量
    struct TrieNode *next[2]; // 0表示左子树，1表示右子树
} TrieNode;

// 初始化前缀树
TrieNode *initTrie() {
    TrieNode *root = (TrieNode*)malloc(sizeof(TrieNode));
    memset(root, 0, sizeof(TrieNode));
    return root;
}

// 插入IP地址到前缀树中
void insertTrie(TrieNode *root, uint32_t ip) {
    TrieNode *p = root;
    for (int i = 0; i < IP_SIZE; i++) {
        int bit = (ip & (1 << (IP_SIZE - i - 1))) ? 1 : 0;
        if (!p->next[bit]) {
            p->next[bit] = (TrieNode*)malloc(sizeof(TrieNode));
            memset(p->next[bit], 0, sizeof(TrieNode));
        }
        p = p->next[bit];
    }
    p->count++;
}

// 在前缀树中查找IP地址，返回IP地址数量
int searchTrie(TrieNode *root, uint32_t ip) {
    TrieNode *p = root;
    for (int i = 0; i < IP_SIZE; i++) {
        int bit = (ip & (1 << (IP_SIZE - i - 1))) ? 1 : 0;
        if (!p->next[bit]) {
            return 0;
        }
        p = p->next[bit];
    }
    return p->count;
}

int main() {
    TrieNode *root = initTrie();
    uint32_t ips[MAX_IP_NUM] = {0}; // 存储IP地址
    int n = 0; // IP地址数量
    printf("请输入IP地址数量：");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        uint32_t ip = 0;
        printf("请输入第%d个IP地址：", i+1);
        scanf("%u", &ip);
        ips[i] = ip;
        insertTrie(root, ip);
    }
    while (1) {
        uint32_t ip = 0;
        printf("请输入要查找的IP地址（输入0退出）：");
        scanf("%u", &ip);
        if (ip == 0) {
            break;
        }
        int count = searchTrie(root, ip);
        printf("IP地址 %u 在前缀树中出现了 %d 次\n", ip, count);
    }
    return 0;
}

在上面的代码中，我们使用了位运算来处理IP地址的二进制位，将每个IP地址插入到前缀树中，然后可以在前缀树中查找指定IP地址。