# Untitled

unknown
plain_text
a month ago
8.4 kB
1
Indexable
Never
```#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;
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) // 要注意
{
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* firstNode  =CreateNode(data);

// 将新头节点放置在跳表的第一层

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

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

L->level++;
}
currentLevel++;
}
removeBeforeInsert = true ;
firstInsert =false;
return;
}

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

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); // 创建新的头节点

L->level++;

}

// 为当前层级创建新节点并连接
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;
}

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