c语言实现跳表(skiplist)

发布时间:2024年01月12日

概述:

跳表(Skip List)是一种数据结构,用于在有序的序列中进行快速查找、插入和删除操作。跳表的设计灵感来自平衡树,但相比于平衡树,跳表的实现更加简单,同时在实际应用中也能提供较好的性能。

以下是跳表的主要特点和概述:

  1. 层级结构: 跳表采用多层次的结构,每一层都是一个有序的链表。最底层包含所有的元素,而每一层都是前一层的一个子集。

  2. 索引: 每个节点都包含多个指针,指向同一层中的其他节点。这些指针被称为索引,通过索引可以在不必遍历整个链表的情况下,快速定位到目标节点。

  3. 随机性: 在跳表中,每个节点的升级或降级过程是随机的,这有助于保持跳表的平衡性。

  4. 平均时间复杂度: 在跳表中,查找、插入和删除的平均时间复杂度都是 O(log n),其中 n 是跳表中元素的数量。相比于平衡树的实现,跳表的实现更简单,但在一些情况下性能能够媲美平衡树。

  5. 空间复杂度: 跳表的空间复杂度相对较高,因为每个节点都包含多个指针。

  6. 实现简单: 相比于复杂的平衡树实现,跳表的实现相对简单,容易理解和调试。

跳表的设计使得它成为一种高效的数据结构,尤其适用于需要频繁插入和删除操作的情况。在某些场景下,跳表可以作为一种替代平衡树的选择。

第一步:定义跳表节点

// 定义跳表节点结构
typedef struct Node {
    int key;
    struct Node** forward; // 指向前方节点的指针数组
} Node;

注意:这里并没有定义下一层的指针,在插入节点时,需要手动更新每层的指针

第二步:定义跳表节点构造

// 定义跳表结构
typedef struct SkipList {
    int level; // 当前跳表的层数
    Node* header; // 头节点
} SkipList;

第三步:创建新节点

// 创建新节点
Node* createNode(int key, int level) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->forward = (Node**)malloc(sizeof(Node*) * (level + 1));
    return newNode;
}

第四步:创建跳表

// 创建跳表
SkipList* createSkipList() {
    SkipList* skipList = (SkipList*)malloc(sizeof(SkipList));
    skipList->level = 0;
    skipList->header = createNode(INT_MIN, MAX_LEVEL);
    for (int i = 0; i <= MAX_LEVEL; i++) {
        skipList->header->forward[i] = NULL;
    }
    return skipList;
}

第五步:生成一个随机层数算法

// 生成一个随机层数,控制跳表的平衡性
int randomLevel() {
    int level = 0;
    while (rand() % 2 == 0 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}
  1. int level = 0;: 首先,初始化一个变量 level 为 0,表示节点的层数。

  2. while (rand() % 2 == 0 && level < MAX_LEVEL) {: 进入一个循环,条件是当前随机数除以2的余数为0且 level 小于预设的最大层数 MAX_LEVEL

    • rand() % 2 == 0: 这部分通过 rand() 函数生成一个随机数,然后对2取余。由于 rand() 返回的值在一定范围内是随机的,因此这个条件的目的是使得随机数为偶数时循环继续,为奇数时循环结束。

    • level < MAX_LEVEL: 这个条件确保节点的层数不会超过预设的最大层数。

  3. level++;: 如果满足条件,增加 level 的值,表示节点的层数增加一层。

  4. 最终 return level;: 返回生成的随机层数。

第六步:编写插入节点

// 插入节点
void insertNode(SkipList* skipList, int key) {
    Node* update[MAX_LEVEL + 1];
    Node* current = skipList->header;

    // 初始化update数组
    for (int i = 0; i <= MAX_LEVEL; i++) {
        update[i] = NULL;
    }

    // 从最高层开始,找到每层的插入位置
    for (int i = skipList->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    // 生成一个随机层数,作为新节点的层数
    int newLevel = randomLevel();

    // 如果新节点的层数比当前跳表的层数大,更新update数组
    if (newLevel > skipList->level) {
        for (int i = skipList->level + 1; i <= newLevel; i++) {
            update[i] = skipList->header;
        }
        skipList->level = newLevel;
    }

    // 创建新节点
    Node* newNode = createNode(key, newLevel);

    // 更新每层的指针
    for (int i = 0; i <= newLevel; i++) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }
}
  1. Node* update[MAX_LEVEL + 1];: 定义一个数组 update 用于存储每层的插入位置。

  2. Node* current = skipList->header;: 初始化 current 指针为跳表的头节点,从头节点开始查找插入位置。

  3. 初始化 update 数组,将每个元素都设置为 NULL

  4. 进入一个循环,从跳表的最高层开始向下查找每层的插入位置。在每层中,通过 current->forward[i] 遍历节点,找到对应位置并更新 update[i]

  5. 生成一个随机层数 newLevel 作为新节点的层数。

  6. 如果新节点的层数比当前跳表的层数大,更新 update 数组。将新层数之后的位置都设置为跳表的头节点,并更新跳表的层数。

  7. 创建新节点,使用 createNode 函数生成一个具有指定键值和层数的节点。

  8. 最后,通过循环更新每层的指针,将新节点插入到跳表中。在每层中,将新节点的 forward[i] 指向 update[i]->forward[i],并将 update[i]->forward[i] 指向新节点,完成插入操作。

第七步:编写查找节点

// 查找节点
Node* searchNode(SkipList* skipList, int key) {
    Node* current = skipList->header;

    // 从最高层开始,找到每层的查找位置
    for (int i = skipList->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
    }

    // 在最底层找到节点后,检查是否为目标节点
    if (current->forward[0] != NULL && current->forward[0]->key == key) {
        return current->forward[0];
    }

    // 未找到目标节点
    return NULL;
}
  1. Node* current = skipList->header;: 初始化 current 指针为跳表的头节点,从头节点开始查找。

  2. 进入一个循环,从跳表的最高层开始向下查找每层的查找位置。在每层中,通过 current->forward[i] 遍历节点,找到对应位置。

  3. 在最底层找到节点后,通过?current->forward[0]?检查是否为目标节点。如果找到了目标节点,返回该节点的指针。
  4. 如果在最底层未找到目标节点,函数返回?NULL?表示未找到。

第八步:打印跳表

// 打印跳表
void printSkipList(SkipList* skipList) {
    printf("Skip List (level %d):\n", skipList->level);

    for (int i = skipList->level; i >= 0; i--) {
        Node* current = skipList->header->forward[i];
        printf("Level %d: ", i);
        while (current != NULL) {
            printf("%d ", current->key);
            current = current->forward[i];
        }
        printf("\n");
    }

    printf("\n");
}

第九步:释放

// 释放节点
void freeNode(Node* node) {
    free(node->forward);
    free(node);
}

// 释放跳表
void freeSkipList(SkipList* skipList) {
    Node* current = skipList->header->forward[0];
    Node* next;

    while (current != NULL) {
        next = current->forward[0];
        freeNode(current);
        current = next;
    }

    free(skipList->header->forward);
    free(skipList->header);
    free(skipList);
}

完整代码

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>

#define MAX_LEVEL 6 // 最大层数

// 定义跳表节点结构
typedef struct Node {
    int key;
    struct Node** forward; // 指向前方节点的指针数组
} Node;

// 定义跳表结构
typedef struct SkipList {
    int level; // 当前跳表的层数
    Node* header; // 头节点
} SkipList;

// 创建新节点
Node* createNode(int key, int level) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->key = key;
    newNode->forward = (Node**)malloc(sizeof(Node*) * (level + 1));
    return newNode;
}

// 创建跳表
SkipList* createSkipList() {
    SkipList* skipList = (SkipList*)malloc(sizeof(SkipList));
    skipList->level = 0;
    skipList->header = createNode(INT_MIN, MAX_LEVEL);
    for (int i = 0; i <= MAX_LEVEL; i++) {
        skipList->header->forward[i] = NULL;
    }
    return skipList;
}

// 生成一个随机层数,控制跳表的平衡性
int randomLevel() {
    int level = 0;
    while (rand() % 2 == 0 && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

// 插入节点
void insertNode(SkipList* skipList, int key) {
    Node* update[MAX_LEVEL + 1];
    Node* current = skipList->header;

    // 初始化update数组
    for (int i = 0; i <= MAX_LEVEL; i++) {
        update[i] = NULL;
    }

    // 从最高层开始,找到每层的插入位置
    for (int i = skipList->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
        update[i] = current;
    }

    // 生成一个随机层数,作为新节点的层数
    int newLevel = randomLevel();

    // 如果新节点的层数比当前跳表的层数大,更新update数组
    if (newLevel > skipList->level) {
        for (int i = skipList->level + 1; i <= newLevel; i++) {
            update[i] = skipList->header;
        }
        skipList->level = newLevel;
    }

    // 创建新节点
    Node* newNode = createNode(key, newLevel);

    // 更新每层的指针
    for (int i = 0; i <= newLevel; i++) {
        newNode->forward[i] = update[i]->forward[i];
        update[i]->forward[i] = newNode;
    }
}

// 查找节点
Node* searchNode(SkipList* skipList, int key) {
    Node* current = skipList->header;

    // 从最高层开始,找到每层的查找位置
    for (int i = skipList->level; i >= 0; i--) {
        while (current->forward[i] != NULL && current->forward[i]->key < key) {
            current = current->forward[i];
        }
    }

    // 在最底层找到节点后,检查是否为目标节点
    if (current->forward[0] != NULL && current->forward[0]->key == key) {
        return current->forward[0];
    }

    // 未找到目标节点
    return NULL;
}

// 打印跳表
void printSkipList(SkipList* skipList) {
    printf("Skip List (level %d):\n", skipList->level);

    for (int i = skipList->level; i >= 0; i--) {
        Node* current = skipList->header->forward[i];
        printf("Level %d: ", i);
        while (current != NULL) {
            printf("%d ", current->key);
            current = current->forward[i];
        }
        printf("\n");
    }

    printf("\n");
}

// 释放节点
void freeNode(Node* node) {
    free(node->forward);
    free(node);
}

// 释放跳表
void freeSkipList(SkipList* skipList) {
    Node* current = skipList->header->forward[0];
    Node* next;

    while (current != NULL) {
        next = current->forward[0];
        freeNode(current);
        current = next;
    }

    free(skipList->header->forward);
    free(skipList->header);
    free(skipList);
}

int main() {
    SkipList* skipList = createSkipList();

    insertNode(skipList, 3);
    insertNode(skipList, 6);
    insertNode(skipList, 7);
    insertNode(skipList, 9);
    insertNode(skipList, 12);
    insertNode(skipList, 19);
    insertNode(skipList, 21);
    insertNode(skipList, 25);

    printSkipList(skipList);

    int keyToSearch = 9;
    Node* result = searchNode(skipList, keyToSearch);

    if (result != NULL) {
        printf("Node with key %d found in the skip list.\n", keyToSearch);
    } else {
        printf("Node with key %d not found in the skip list.\n", keyToSearch);
    }

    freeSkipList(skipList);

    return 0;
}

文章来源:https://blog.csdn.net/m0_63251896/article/details/135552854
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。