论坛 › 数据结构与算法 › 跳表插入第5个数据时出错

小玉玉 发表于 2021-8-5 14:18:27

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

发在数据结构的板块比较合适{:5_109:}
C写的跳表测试代码，但是只要插入第5个数据就会不正常退出，看了一天了，着实看不出哪里有问题，有好心大大帮我看看吗？
skiplist.h
#include <stdio.h>
typedef struct Node{
    int key;
    int value;
    int max_level;
    struct Node* next;
}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) != NULL) && (tmp->key < key))
      {
            prev = tmp;
      }
      update = 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 = list->head;
      }
      list->level = max_level;
    }

    for(i = 0;i < list->level;i++)
    {
      newNode->next = update->next;
      update->next = 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 != NULL)
      {
            printf("%d-%d ", prev->next->key, prev->next->value);
            prev = prev->next;
      }
      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;
}

小玉玉 发表于 2021-8-5 16:33:50

找到问题了
for(i = 0;i < list->level;i++)
    {
      newNode->next = update->next;
      update->next = newNode;
    }
换成
    for(i = 0;i < max_level;i++)
    {
      newNode->next = update->next;
      update->next = newNode;
    }
这里如果下次插入节点的层级比上次的小，会访问到没有值的update->next

查看完整版本: 跳表插入第5个数据时出错