跳表插入第5个数据时出错

小玉玉

发在数据结构的板块比较合适
C写的跳表测试代码，但是只要插入第5个数据就会不正常退出，看了一天了，着实看不出哪里有问题，有好心大大帮我看看吗？
skiplist.h

#include <stdio.h>
typedef struct Node{
    int key;
    int value;
    int max_level;
    struct Node* next[0];
}Node;

typedef struct SkipList{
    int count;
    int level;
    struct Node* head;
}SkipList;

main.c

#include <stdio.h>
#include "./skiplist.h"
#include<stdlib.h>
#include<string.h>

Node* CreateNode(int key, int value, int level)
{
    printf("key:%d,value:%d\n", key, value);
    Node* tmp = (Node*)malloc(sizeof(Node) + sizeof(Node*)*level);
    memset(tmp, 0, sizeof(Node) + sizeof(Node*)*level);
    tmp->key = key;
    tmp->value = value;
    tmp->max_level = level;
    return tmp;
}

SkipList* CreateSkipList(int max_level)
{
    printf("创建表头\n");
    SkipList* list = (SkipList*)malloc(sizeof(SkipList));
    list->level = 1;
    list->count = 0;
    list->head = CreateNode(0, 0, max_level);
    if(list->head == NULL)
    {
        printf("表头为空\n");
        free(list);
        return NULL;
    }
    printf("表头创建完毕\n");
    return list;
}

int SkipListLevel(SkipList * list)
{
        int i = 0;
        int level = 1;
        for (i = 1; i < list->head->max_level; i++)
        {
                if ((rand()%2) == 1)
                {
                        level++;
                }
        }

        return level;
}

void Insert(SkipList* list, int key, int value)
{
    printf("开始插入key:%d\n", key);
    printf("max_level:%d\n", list->head->max_level);
    Node** update = (Node**)malloc(sizeof(Node*)*list->head->max_level);
    Node* prev = list->head;
    Node* tmp = (Node*)malloc(sizeof(Node*));

    int i = 0;
    for(i = list->level - 1;i >= 0;i--)
    {
        while(((tmp = prev->next[i]) != NULL) && (tmp->key < key))
        {
            prev = tmp;
        }
        update[i] = prev;
    }

    if((tmp != NULL) && (tmp->key == key))
    {
        printf("%d已经存在\n");
        return;
    }

    int max_level = SkipListLevel(list);

    Node* newNode = CreateNode(key, value, max_level);
    printf("创建了一个节点key:%d,value:%d\n", newNode->key, newNode->value);
    if(max_level > list->level)
    {
        for(i = list->level;i < max_level;i++)
        {
            update[i] = list->head;
        }
        list->level = max_level;
    }

    for(i = 0;i < list->level;i++)
    {
        newNode->next[i] = update[i]->next[i];
        update[i]->next[i] = newNode;
    }

    list->count ++;
}


void PrintSkipList(SkipList* list)
{
    Node* prev = list->head;
    int i = 0;
    for(i = list->level - 1;i >= 0;i--)
    {
        prev = list->head;
        printf("level[%d]:", i);
        while(prev->next[i] != NULL)
        {
            printf("%d-%d ", prev->next[i]->key, prev->next[i]->value);
            prev = prev->next[i];
        }
        printf("\n");
    }
    printf("\n");
}

int main()
{
    SkipList* list = CreateSkipList(5);

    Insert(list, 1, 1);
    Insert(list, 2, 2);
    Insert(list, 3, 3);
    Insert(list, 4, 4);
//    Insert(list, 5, 5);
    PrintSkipList(list);
    return 0;
}

小玉玉

找到问题了

for(i = 0;i < list->level;i++)
    {
        newNode->next[i] = update[i]->next[i];
        update[i]->next[i] = newNode;
    }

换成

    for(i = 0;i < max_level;i++)
    {
        newNode->next[i] = update[i]->next[i];
        update[i]->next[i] = newNode;
    }

这里如果下次插入节点的层级比上次的小，会访问到没有值的update[i]->next[i]