资料结构-跳表实现问题

Question

大家好 这次想问这个跳表错哪了 我感觉自己写的挺合理啊 但一开始insert就出问题了

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

#define MAX_LEVEL 32

typedef struct Node 
{
    long long value;
    struct Node *next;
    struct Node *below;
} Node;

typedef struct List
{
    int fast_layers;
    Node *heads[MAX_LEVEL];
} List;

Node* create(long long value) 
{
    Node* node = (Node*)malloc(sizeof(Node));
    if (node != NULL) 
    {
        node->value = value;
        node->next = NULL;
        node->below = NULL;
    }
    return node;
}

void initList(List *list) 
{
    list->fast_layers = 0;
    for (int i = 0; i < MAX_LEVEL; ++i) 
    {
        list->heads[i] = NULL;
    }
}

long long Power(long long times)
{
    long long answer = 1;
    for(int i = 0; i < times - 1; ++i)
    {
        answer *= 2;
    }
    return answer;
}

bool coinFlip(long long k, long long i) 
{
    return (k / Power(i)) % 2;
}

Node* slowGet(List* list, long long data) 
{
    Node* node = list->heads[0];
    while (node != NULL && data < node->value) 
    {
        node = node->next;
    }
    return node;
}

Node* fastGet(List* list, long long data) 
{
    Node* node = list->heads[list->fast_layers - 1];
    while (node != NULL) 
    {
        while (node->next != NULL && data <= node->next->value) 
        {
            node = node->next;
        }
        if (node->below != NULL) 
        {
            node = node->below;
        } 
        else 
        {
            break;
        }
    }
    return node;
}

void insert(List *list, long long data) 
{
    Node *prev[MAX_LEVEL];
    Node *node = fastGet(list, data);
    int layer = 0;

    while (node != NULL && node->value >= data) 
    {
        prev[layer] = node;
        if (node->below != NULL) 
        {
            node = node->below;
        } 
        else 
        {
            break;
        }
        ++layer;
    }

    Node *newNode = create(data);
    if (newNode == NULL) 
    {
        return;
    }

    for (int i = 0; i <= layer; ++i) 
    {
        newNode->next = prev[i]->next;
        prev[i]->next = newNode;

        if (i > 0) 
        {
            newNode->below = prev[i]->below; 
        }
    }

    for (int i = layer + 1; i < list->fast_layers; ++i) 
    {
        if(coinFlip(data, i)) 
        {
            Node *newLevelNode = create(data);
            newLevelNode->below = list->heads[i - 1];
            list->heads[i] = newLevelNode;
        } 
        else 
        {
            break;
        }
    }

    if (coinFlip(data, list->fast_layers)) 
    {
        ++(list->fast_layers);
        newNode = create(data);
        newNode->below = list->heads[list->fast_layers - 2];
        list->heads[list->fast_layers - 1] = newNode;
    }
}

void removeNode(List *list, long long data) 
{
    Node *node = fastGet(list, data);
    Node *prev = NULL;

    while (node != NULL && node->value == data) 
    {
        if (prev != NULL) 
        {
            prev->next = node->next;
        }
        Node *temp = node;
        node = node->below;
        free(temp);
        if (prev == NULL) 
        {
            break;
        }
        prev = prev->below;
    }

    while (list->heads[list->fast_layers - 1] == NULL) 
    {
        --(list->fast_layers);
    }
}

int main() 
{
    List list;
    initList(&list);

    int M;
    scanf("%d", &M);

    for (int i = 0; i < M; ++i) 
    {
        int op;
        long long k;
        scanf("%d %lld", &op, &k);
        switch (op) 
        {
            case 1: 
            {
                Node *result = slowGet(&list, k);
                if (result != NULL) 
                {
                    while (result != NULL) 
                    {
                        printf("%lld", result->value);
                        result = result->next;
                    }
                    printf("\n");
                } 
                else 
                {
                    printf("-1\n");
                }
                break;
            }
            case 2: 
            {
                Node *result = fastGet(&list, k);
                if (result != NULL) 
                {
                    while (result != NULL) 
                    {
                        printf("%lld ", result->value);
                        result = result->next;
                    }
                    printf("\n");
                } 
                else 
                {
                    printf("-1\n");
                }
                break;
            }
            case 3: 
            {
                insert(&list, k);
                break;
            }
            case 4: 
            {
                removeNode(&list, k);
                break;
            }
            default:
                break;
        }
    }

    return 0;
}

Answer 1

【相关推荐】

• 这个问题的回答你可以参考下: https://ask.csdn.net/questions/7424852

如果你已经解决了该问题, 非常希望你能够分享一下解决方案, 写成博客, 将相关链接放在评论区, 以帮助更多的人 ^-^