Untitled

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

bool firstInsert =true;
bool removeBeforeInsert = false;

// 定义节点类型
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) // 要注意
{   
    Node *node = L->head[L->level]; // 从最高层开始
    
    if (data > L->head[0]->next->data ) {
        printf("%d\n",-1);
        return NULL ;
    }

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

    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; }

    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) {
    // 使用位移运算替代pow
    return IsOdd(k >> (i - 1));
}


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

        Node* firstNode  =CreateNode(data);

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

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

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

                newHead->down = L->head[currentLevel-1];
                copyFirstNode->down = L->head[currentLevel-1]->next;

                L->head[currentLevel] = newHead;
                newHead->next = copyFirstNode;
                L->level++;
            }
            currentLevel++;
        }
        removeBeforeInsert = true ; 
        firstInsert =false;
        return;
    }

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

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

    int SearchLevel = L->level ;

    while (node->down != NULL ) {
        while (node->next != NULL && data <= node->next->data) { 
            node = node->next; 
        }
        insertPositions[SearchLevel] = node; // 在该层保存插入位置
        node = node->down;
        SearchLevel--;
    }

    while (node->next != NULL && data <= node->next->data){
        node = node->next ;
    }

    // 检查数据是否已存在
    if (node != NULL && node->data == data) { return;}
    
    insertPositions[0] = node;

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

    // 从第二层开始决定是否插入新节点
    int currentLevel = 1;

    while (CoinFlip(data, currentLevel)) {
        // 如果当前层级超出跳表现有层级，则增加一层

        if (currentLevel > L->level) {
            Node *newHead = CreateNode(-1); // 创建新的头节点
            newHead->down = L->head[L->level];

            L->level++;

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

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

        currentLevel++;
        newNode = newNodeHigher;
    }
}

void Remove(SkipList *L, long long int data) {
    if (!removeBeforeInsert) { return; }

    Node *BeforeNode[L->level+1];

    for (int i = 0; i < L->level; ++i) {
        BeforeNode[i] = NULL;
    }

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

    int SearchLevel = L->level ;

    while (node->down != NULL ) {
        while (node->next != NULL && data < node->next->data) { 
            node = node->next; 
        }
        BeforeNode[SearchLevel] = node; // 在该层保存插入位置
        node = node->down;
        SearchLevel--;
    }

    while (node->next != NULL && data < node->next->data){
        node = node->next ;
    }

    for (int i = L->level; i >=0; i--) {
        node = BeforeNode[i]->next;

        if (node == NULL || node->data != data) { break; }

        node = BeforeNode[i]->next;
        BeforeNode[i]->next = node->next;
        free(node);

        if (L->head[i]->next == NULL && i>0){

            L->head[i]->down = NULL;
            free(L->head[i]);
            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();
    L->level=0;

    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;
        }
    }
    // printf("%d\n",L->head[0]->next->data);

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

    return 0;
}