# Untitled

unknown
plain_text
a month ago
8.5 kB
3
Indexable
Never
```#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;
free(list); // 释放已分配的内存
return NULL; // 内存分配失败处理
}

for (int i = 0; i < MAX_LEVEL; i++) {
}
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->down != NULL ) {
while (node->next != NULL && data <= node->next->data) {
node = node->next;
printf("%d ",node->data);
}
node = node->down;
}

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) {
return IsOdd(floor(k / pow(2, i - 1)));
}

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

if (newHead == NULL) { return; }

// 将新头节点放置在跳表的第一层
L->level = 1;

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

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

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

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

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

int currentLevel = 2;

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

L->level++;
}

// 为当前层级创建新节点并连接
Node *newNodeHigher = CreateNode(data);
newNodeHigher->down = newNode;
newNodeHigher->next = insertPositions[currentLevel-1]->next;
insertPositions[currentLevel-1]->next = 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) {
free(node);
L->level--;
}
}
}

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

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

```