Untitled
unknown
plain_text
a year ago
8.4 kB
7
Indexable
#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; }
Editor is loading...
Leave a Comment