Untitled

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h> // For using the floor function 
#define MAX_LEVEL 64 // 定义最大层数为 64

// 定义节点类型
typedef struct Node {
    int data;
    struct Node *next;
    struct Node *down; // 添加一个指向下层的指针
} Node;

// 定义跳表类型
typedef struct SkipList {
    Node **head; // An array of pointers to the head of each level.
    int level;   // The number of levels in the skip list.
} SkipList;

// Function to create a new skip list node
Node* CreateNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    node->down = NULL;
    return node;
}

SkipList* NewSkipList() {
    SkipList* list = (SkipList*)malloc(sizeof(SkipList));
    if (list == NULL) {
        return NULL; // 内存分配失败处理
    }

    list->level = 0;
    list->head = (Node**)malloc(MAX_LEVEL * sizeof(Node*));
    if (list->head == NULL) {
        free(list); // 释放已分配的内存
        return NULL; // 内存分配失败处理
    }

    for (int i = 0; i < MAX_LEVEL; i++) {
        list->head[i] = NULL;
    }
    return list;
}

Node* SlowGet(SkipList *L, int data) {
    Node *node = L->head[0]; // 从底层链表的头节点开始

    if (data > node->next->data ) {
        printf("%d",-1);
        return NULL ;
    }

    while (node->next != NULL && data <= node->next->data) {
        node = node->next; // 移动到下一个节点
        printf("%d ", node->data); // 打印当前节点数据
    }
    printf("\n");
    if (node != NULL && node->data == data) {
        return node;
    } else {
        return NULL;
    }
}

Node* FastGet(SkipList *L, int data) {
    
    if (L->level > 1) {
        Node *node = L->head[L->level - 1]; // 从最高层开始
        
        if (data > node->next->data ) {
            printf("%d",-1);
            return NULL;
        }

        while (node != NULL) {
            // 横向搜索直到下一个节点的数据小于目标数据
            while (node->next != NULL && data < node->next->data) {
                printf("%d ", node->data); // 打印当前节点数据
                node = node->next;
            }

            // 向下一层跳转，如果已经在底层则退出循环
            if (node->down != NULL) {
                node = node->down;
            } else {
                break;
            }
        }

        // 检查是否找到目标数据
        if (node != NULL && node->data == data) {
            // 找到目标数据，返回节点（不打印目标节点）
            printf("\n");
            return node;
        } else {
            return NULL;
        }
    }
    return NULL; 
}

// Helper function to determine if the least significant bit is set (which indicates odd).
bool IsOdd(int number) {
    return number & 1;
}

bool CoinFlip(int k, int i) {
    return IsOdd(floor(k / pow(2, i - 1)));
}

void Insert(SkipList *L, int data) //注意相同節點?
{
    // 检查跳表是否还没有任何层级
    if (L->level == 0) {
        // 为第一层创建一个新的头节点
        Node* newHead = CreateNode(0);
        Node* firstNode  =CreateNode(data);

        if (newHead == NULL) { return; }

        // 将新头节点放置在跳表的第一层
        L->head[0] = newHead;
        newHead->next = firstNode; 
        L->level = 1;

        int currentLevel = 2 ; 
        while (CoinFlip(data, currentLevel)) {

            // 如果当前层级超出跳表现有层级，则增加一层
            if (currentLevel >= L->level) {
                Node *newHead = CreateNode(data); // 创建新的头节点
                newHead->down = L->head[currentLevel-2];

                L->head[currentLevel-1] = newHead;
                L->level++;
            }
            currentLevel++;
        }


        return;
    }

    Node *insertPositions[MAX_LEVEL];
    for (int i = 0; i < MAX_LEVEL; ++i) {
        insertPositions[i] = NULL;
    }

    Node *node = L->head[L->level - 1];
    int SearchLevel = L->level ;

    // 从最高层开始向下查找插入位置
    while (SearchLevel >= 1) {
        while (node->next != NULL && data < node->next->data) { node = node->next; }

        insertPositions[SearchLevel-1] = node; // 在该层保存插入位置
        node = node->down;
        SearchLevel--;
    }

    // 在底层插入新节点
    Node *newNode = CreateNode(data);
    newNode->next = insertPositions[0]->next;
    insertPositions[0]->next = newNode;

    // 从第二层开始决定是否插入新节点

    //level = 1 , head[0]

    int currentLevel = 2;
    Node *lowerNode = newNode;
    while (CoinFlip(data, currentLevel)) {
        // 如果当前层级超出跳表现有层级，则增加一层
        if (currentLevel >= L->level) {
            Node *newHead = CreateNode(data); // 创建新的头节点
            newHead->down = L->head[L->level-1];
            L->head = realloc(L->head, sizeof(Node*) * (L->level + 1));
            L->head[L->level] = newHead;
            L->level++;

            insertPositions[L->level-1] = newHead;
        }

        // 为当前层级创建新节点并连接
        Node *newNodeHigher = CreateNode(data);
        newNodeHigher->down = lowerNode;
        newNodeHigher->next = insertPositions[currentLevel-1]->next;
        insertPositions[currentLevel-1]->next = newNodeHigher;

        lowerNode = newNodeHigher;
        currentLevel++;
    }
}

void Remove(SkipList *L, long long int data) {
    if (L == NULL || L->level == 0) {
        return; // 确保跳表非空且有至少一层
    }

    Node *update[L->level];
    Node *node = L->head[L->level - 1];

    // 初始化 update 数组
    for (int i = 0; i < L->level; ++i) {
        update[i] = NULL;
    }

    // 寻找每一层的前驱节点
    for (int i = L->level - 1; i >= 0; --i) {
        while (node->next != NULL && data < node->next->data) {
            node = node->next;
        }
        update[i] = node;
        node = node->down;
    }

    // 检查并删除底层节点
    node = update[0]->next;
    if (node != NULL && node->data == data) {
        update[0]->next = node->next;
        free(node);

        // 从底层向上删除节点
        for (int i = 1; i < L->level; ++i) {
            if (update[i]->next == NULL || update[i]->next->data != data) {
                break;
            }
            node = update[i]->next;
            update[i]->next = node->next;
            free(node);
        }

        // 移除空的顶层
        while (L->level > 1 && L->head[L->level - 1]->next == NULL) {
            node = L->head[L->level - 1];
            L->head[L->level - 1] = node->down;
            free(node);
            L->level--;
        }
    }
}

void FreeSkipList(SkipList* L) {
    if (L == NULL) return;

    // 遍历每一层
    for (int i = 0; i < L->level; ++i) {
        Node *node = L->head[i];
        // 遍历并释放当前层的所有节点
        while (node != NULL) {
            Node *temp = node;
            node = node->next;
            free(temp);
        }
    }
    // 释放头指针数组和跳表结构
    free(L->head);
    free(L);
}

int main() {
    int operation_nums;
    scanf("%d", &operation_nums);

    SkipList* L = NewSkipList();

    for (int i = 0; i < operation_nums; i++) {
        int operation_type, target;
        scanf("%d", &operation_type);

        Node *result;
        switch (operation_type) {
            case 1: // SlowGet
                scanf("%d", &target);
                result = SlowGet(L, target);
                break;
            case 2: // FastGet
                scanf("%d", &target);
                result = FastGet(L, target);
                break;
            case 3: // Insert
                scanf("%d", &target);
                Insert(L, target);
                break;
            case 4: // Remove
                scanf("%d", &target);
                Remove(L, target);
                break;
        }
    }

    // 释放跳表占用的内存
    FreeSkipList(L);

    return 0;
}