监控电脑操作记录软件的跳表Python语言算法研究与实现

import random
import time
class SkipNode:
    """跳表节点类，存储监控电脑操作记录数据及层级指针"""
    def __init__(self, data, level):
        # 操作记录数据：time_stamp(时间戳), op_type(操作类型), op_content(操作内容)
        self.data = data
        # 节点当前层级
        self.level = level
        # 前驱节点列表：index对应层级
        self.prev = [None] * level
        # 后继节点列表：index对应层级
        self.next = [None] * level
class SkipList:
    """跳表类，适配监控电脑操作记录软件的数据存储与检索需求"""
    def __init__(self, max_level=16, p=0.5):
        # 跳表最大支持层级
        self.max_level = max_level
        # 节点层级提升概率
        self.p = p
        # 跳表当前最大层级
        self.current_max_level = 1
        # 哨兵节点（头部），简化边界处理
        self.head = SkipNode(data={"time_stamp": 0, "op_type": "SENTINEL", "op_content": ""}, level=self.max_level)
        # 操作记录计数器
        self.count = 0
    def _random_level(self):
        """随机生成节点层级，核心随机化机制"""
        level = 1
        while random.random() < self.p and level < self.max_level:
            level += 1
        return level
    def insert(self, data):
        """
        插入监控电脑操作记录
        :param data: 操作记录字典，必须包含time_stamp字段作为排序关键字
        """
        if not isinstance(data, dict) or "time_stamp" not in data:
            raise ValueError("操作记录必须为字典类型且包含time_stamp字段")
        
        # 记录各层级待插入位置的前驱节点
        update_prev = [None] * self.max_level
        current = self.head
        # 从最高层级向下定位
        for i in range(self.current_max_level - 1, -1, -1):
            # 找到当前层级小于目标时间戳的最后一个节点
            while current.next[i] and current.next[i].data["time_stamp"] < data["time_stamp"]:
                current = current.next[i]
            update_prev[i] = current
        # 生成新节点层级
        new_level = self._random_level()
        # 如果新节点层级超过当前最大层级，更新前驱节点列表的高层级部分
        if new_level > self.current_max_level:
            for i in range(self.current_max_level, new_level):
                update_prev[i] = self.head
            self.current_max_level = new_level
        # 创建新节点并更新指针
        new_node = SkipNode(data, new_level)
        for i in range(new_level):
            new_node.prev[i] = update_prev[i]
            new_node.next[i] = update_prev[i].next[i]
            if update_prev[i].next[i]:
                update_prev[i].next[i].prev[i] = new_node
            update_prev[i].next[i] = new_node
        self.count += 1
    def search(self, target_time_stamp):
        """
        根据时间戳检索操作记录
        :param target_time_stamp: 目标时间戳
        :return: 匹配的操作记录字典，无匹配则返回None
        """
        current = self.head
        # 从最高层级向下定位
        for i in range(self.current_max_level - 1, -1, -1):
            while current.next[i] and current.next[i].data["time_stamp"] < target_time_stamp:
                current = current.next[i]
        # 定位到底层，判断是否存在匹配节点
        current = current.next[0]
        if current and current.data["time_stamp"] == target_time_stamp:
            return current.data
        return None
    def delete(self, target_time_stamp):
        """
        根据时间戳删除操作记录
        :param target_time_stamp: 目标时间戳
        :return: 成功删除返回True，无匹配节点返回False
        """
        update_prev = [None] * self.max_level
        current = self.head
        # 从最高层级向下定位
        for i in range(self.current_max_level - 1, -1, -1):
            while current.next[i] and current.next[i].data["time_stamp"] < target_time_stamp:
                current = current.next[i]
            update_prev[i] = current
        current = current.next[0]
        # 无匹配节点
        if not current or current.data["time_stamp"] != target_time_stamp:
            return False
        # 更新各层级指针
        for i in range(self.current_max_level):
            if update_prev[i].next[i] != current:
                break
            update_prev[i].next[i] = current.next[i]
            if current.next[i]:
                current.next[i].prev[i] = update_prev[i]
        # 更新跳表当前最大层级（若最高层级无节点）
        while self.current_max_level > 1 and not self.head.next[self.current_max_level - 1]:
            self.current_max_level -= 1
        self.count -= 1
        return True
    def range_query(self, start_time, end_time):
        """
        范围查询操作记录（根据时间戳区间）
        :param start_time: 起始时间戳
        :param end_time: 结束时间戳
        :return: 符合条件的操作记录列表，按时间戳升序排列
        """
        result = []
        current = self.head.next[0]
        # 遍历底层链表，提取时间戳在区间内的记录
        while current and current.data["time_stamp"] <= end_time:
            if current.data["time_stamp"] >= start_time:
                result.append(current.data)
            current = current.next[0]
        return result
    def get_count(self):
        """获取当前存储的操作记录总数"""
        return self.count
# 测试例程：模拟监控电脑操作记录软件的跳表应用场景
if __name__ == "__main__":
    # 初始化跳表
    op_skip_list = SkipList()
    # 模拟生成5条监控电脑操作记录
    test_operations = [
        {
            "time_stamp": 1740000000,
            "op_type": "FILE_WRITE",
            "op_content": "编辑文档 report.docx"
        },
        {
            "time_stamp": 1740000120,
            "op_type": "NETWORK_ACCESS",
            "op_content": "访问网址 https://company-intranet.com"
        },
        {
            "time_stamp": 1740000240,
            "op_type": "PROCESS_START",
            "op_content": "启动进程 Chrome.exe"
        },
        {
            "time_stamp": 1740000360,
            "op_type": "FILE_READ",
            "op_content": "读取文件 data.xlsx"
        },
        {
            "time_stamp": 1740000480,
            "op_type": "KEYBOARD_INPUT",
            "op_content": "输入文本 项目进度汇报"
        }
    ]
    # 插入操作记录
    for op in test_operations:
        op_skip_list.insert(op)
    print(f"跳表初始化完成，共存储 {op_skip_list.get_count()} 条操作记录")
    # 单条记录检索测试
    target_ts = 1740000240
    searched_op = op_skip_list.search(target_ts)
    print(f"\n检索时间戳 {target_ts} 的操作记录：")
    print(searched_op if searched_op else "未找到匹配记录")
    # 范围查询测试
    start_ts = 1740000100
    end_ts = 1740000400
    range_ops = op_skip_list.range_query(start_ts, end_ts)
    print(f"\n查询时间戳 {start_ts} 至 {end_ts} 的操作记录：")
    for op in range_ops:
        print(op)
    # 删除记录测试
    delete_ts = 1740000360
    delete_result = op_skip_list.delete(delete_ts)
    print(f"\n删除时间戳 {delete_ts} 的操作记录：{'成功' if delete_result else '失败'}")
    print(f"删除后剩余操作记录数：{op_skip_list.get_count()}")