基于跳表数据结构的企业局域网监控异常连接实时检测 C++ 算法研究

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <string>
#include <vector>
// 定义最大层级
const int MAX_LEVEL = 16;
// 层级提升概率
const double P = 0.5;
// 连接记录节点结构
struct ConnectionNode {
    std::string ip;          // 客户端IP
    time_t timestamp;        // 连接时间戳
    std::string url;         // 访问URL
    int level;               // 节点层级
    ConnectionNode**forward; // 各层级的前驱指针
    ConnectionNode(std::string ip_, time_t ts, std::string url_, int level_)
        : ip(ip_), timestamp(ts), url(url_), level(level_) {
        forward = new ConnectionNode*[level];
        for (int i = 0; i < level; ++i) {
            forward[i] = nullptr;
        }
    }
    ~ConnectionNode() {
        delete[] forward;
    }
};
// 跳表类实现
class SkipList {
private:
    ConnectionNode* head;     // 表头节点
    int level;                // 当前最高层级
    int size;                 // 节点数量
    // 随机生成节点层级
    int randomLevel() {
        int lev = 1;
        while ((rand() % 100) < P * 100 && lev < MAX_LEVEL) {
            lev++;
        }
        return lev;
    }
public:
    SkipList() {
        head = new ConnectionNode("", 0, "", MAX_LEVEL);
        level = 1;
        size = 0;
        srand(time(nullptr));
    }
    ~SkipList() {
        ConnectionNode* curr = head->forward[0];
        while (curr) {
            ConnectionNode* next = curr->forward[0];
            delete curr;
            curr = next;
        }
        delete head;
    }
    // 插入连接记录
    void insert(std::string ip, time_t ts, std::string url) {
        ConnectionNode* update[MAX_LEVEL];
        ConnectionNode* curr = head;
        // 查找插入位置
        for (int i = level - 1; i >= 0; --i) {
            while (curr->forward[i] &&
                   (curr->forward[i]->timestamp < ts ||
                    (curr->forward[i]->timestamp == ts && curr->forward[i]->ip < ip))) {
                curr = curr->forward[i];
            }
            update[i] = curr;
        }
        int newLevel = randomLevel();
        if (newLevel > level) {
            for (int i = level; i < newLevel; ++i) {
                update[i] = head;
            }
            level = newLevel;
        }
        // 创建新节点并插入
        ConnectionNode* newNode = new ConnectionNode(ip, ts, url, newLevel);
        for (int i = 0; i < newLevel; ++i) {
            newNode->forward[i] = update[i]->forward[i];
            update[i]->forward[i] = newNode;
        }
        size++;
    }
    // 查询指定IP在时间范围内的连接记录
    std::vector<ConnectionNode*> query(std::string ip, time_t start, time_t end) {
        std::vector<ConnectionNode*> result;
        ConnectionNode* curr = head;
        // 定位到起始时间点
        for (int i = level - 1; i >= 0; --i) {
            while (curr->forward[i] && curr->forward[i]->timestamp < start) {
                curr = curr->forward[i];
            }
        }
        curr = curr->forward[0];
        // 收集时间范围内的目标IP记录
        while (curr && curr->timestamp <= end) {
            if (curr->ip == ip) {
                result.push_back(curr);
            }
            curr = curr->forward[0];
        }
        return result;
    }
};
// 企业局域网监控系统中的应用示例
int main() {
    SkipList* connList = new SkipList();
    // 模拟插入局域网连接记录
    time_t now = time(nullptr);
    connList->insert("192.168.1.101", now - 300, "https://www.vipshare.com");
    connList->insert("192.168.1.102", now - 200, "http://internal.corp.com");
    connList->insert("192.168.1.101", now - 100, "http://mail.corp.com");
    // 查询192.168.1.101在最近5分钟的连接记录
    std::vector<ConnectionNode*> records = connList->query("192.168.1.101", now - 300, now);
    std::cout << "查询到" << records.size() << "条连接记录：" << std::endl;
    for (auto node : records) {
        std::cout << "IP: " << node->ip << " 时间: " << ctime(&node->timestamp)
                  << " URL: " << node->url << std::endl;
    }
    delete connList;
    return 0;
}