跳表C语言

【C语言】算法学习·跳表_c语言跳表-CSDN博客

leetcode原题，代码如下

#define MAX(a, b) ((a) > (b) ? (a) : (b))
const int MAX_LEVEL = 32;
const int P_FACTOR = RAND_MAX >> 2;typedef struct SkiplistNode {int val;int maxLevel;struct SkiplistNode **forward;
} SkiplistNode;typedef struct {SkiplistNode *head;int level;
} Skiplist;SkiplistNode *skiplistNodeCreat(int val, int maxLevel) {SkiplistNode *obj = (SkiplistNode *)malloc(sizeof(SkiplistNode));obj->val = val;obj->maxLevel = maxLevel;obj->forward = (SkiplistNode **)malloc(sizeof(SkiplistNode *) * maxLevel);for (int i = 0; i < maxLevel; i++) {obj->forward[i] = NULL;}return obj;
}void skiplistNodeFree(SkiplistNode* obj) {if (obj->forward) {free(obj->forward);obj->forward = NULL;obj->maxLevel = 0;}free(obj);
}Skiplist* skiplistCreate() {Skiplist *obj = (Skiplist *)malloc(sizeof(Skiplist));obj->head = skiplistNodeCreat(-1, MAX_LEVEL);obj->level = 0;srand(time(NULL));return obj;
}static inline int randomLevel() {int lv = 1;/* 随机生成 lv */while (rand() < P_FACTOR && lv < MAX_LEVEL) {lv++;}return lv;
}bool skiplistSearch(Skiplist* obj, int target) {SkiplistNode *curr = obj->head;for (int i = obj->level - 1; i >= 0; i--) {/* 找到第 i 层小于且最接近 target 的元素*/while (curr->forward[i] && curr->forward[i]->val < target) {curr = curr->forward[i];}}curr = curr->forward[0];/* 检测当前元素的值是否等于 target */if (curr && curr->val == target) {return true;} return false;
}void skiplistAdd(Skiplist* obj, int num) {SkiplistNode *update[MAX_LEVEL];SkiplistNode *curr = obj->head;for (int i = obj->level - 1; i >= 0; i--) {/* 找到第 i 层小于且最接近 num 的元素*/while (curr->forward[i] && curr->forward[i]->val < num) {curr = curr->forward[i];}update[i] = curr;}int lv = randomLevel();if (lv > obj->level) {for (int i = obj->level; i < lv; i++) {update[i] = obj->head;}obj->level = lv;}SkiplistNode *newNode = skiplistNodeCreat(num, lv);for (int i = 0; i < lv; i++) {/* 对第 i 层的状态进行更新，将当前元素的 forward 指向新的节点 */newNode->forward[i] = update[i]->forward[i];update[i]->forward[i] = newNode;}
}bool skiplistErase(Skiplist* obj, int num) {SkiplistNode *update[MAX_LEVEL];SkiplistNode *curr = obj->head;for (int i = obj->level - 1; i >= 0; i--) {/* 找到第 i 层小于且最接近 num 的元素*/while (curr->forward[i] && curr->forward[i]->val < num) {curr = curr->forward[i];}update[i] = curr;}curr = curr->forward[0];/* 如果值不存在则返回 false */if (!curr || curr->val != num) {return false;}for (int i = 0; i < obj->level; i++) {if (update[i]->forward[i] != curr) {break;} /* 对第 i 层的状态进行更新，将 forward 指向被删除节点的下一跳 */update[i]->forward[i] = curr->forward[i];}skiplistNodeFree(curr);/* 更新当前的 level */while (obj->level > 1 && obj->head->forward[obj->level - 1] == NULL) {obj->level--;}return true;
}void skiplistFree(Skiplist* obj) {for (SkiplistNode * curr = obj->head; curr; ) {SkiplistNode *prev = curr;curr = curr->forward[0];skiplistNodeFree(prev);}free(obj);
}/*** Your Skiplist struct will be instantiated and called as such:* Skiplist* obj = skiplistCreate();* bool param_1 = skiplistSearch(obj, target);* skiplistAdd(obj, num);* bool param_3 = skiplistErase(obj, num);* skiplistFree(obj);
*/