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

小玉玉

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

1. #include <stdio.h>
   
2. typedef struct Node{
   
3.     int key;
   
4.     int value;
   
5.     int max_level;
   
6.     struct Node* next[0];
   
7. }Node;
   
8. 
   
9. typedef struct SkipList{
   
10.     int count;
    
11.     int level;
    
12.     struct Node* head;
    
13. }SkipList;
    

复制代码

main.c

1. #include <stdio.h>
   
2. #include "./skiplist.h"
   
3. #include<stdlib.h>
   
4. #include<string.h>
   
5. 
   
6. Node* CreateNode(int key, int value, int level)
   
7. {
   
8.     printf("key:%d,value:%d\n", key, value);
   
9.     Node* tmp = (Node*)malloc(sizeof(Node) + sizeof(Node*)*level);
   
10.     memset(tmp, 0, sizeof(Node) + sizeof(Node*)*level);
    
11.     tmp->key = key;
    
12.     tmp->value = value;
    
13.     tmp->max_level = level;
    
14.     return tmp;
    
15. }
    
16. 
    
17. SkipList* CreateSkipList(int max_level)
    
18. {
    
19.     printf("创建表头\n");
    
20.     SkipList* list = (SkipList*)malloc(sizeof(SkipList));
    
21.     list->level = 1;
    
22.     list->count = 0;
    
23.     list->head = CreateNode(0, 0, max_level);
    
24.     if(list->head == NULL)
    
25.     {
    
26.         printf("表头为空\n");
    
27.         free(list);
    
28.         return NULL;
    
29.     }
    
30.     printf("表头创建完毕\n");
    
31.     return list;
    
32. }
    
33. 
    
34. int SkipListLevel(SkipList * list)
    
35. {
    
36.         int i = 0;
    
37.         int level = 1;
    
38.         for (i = 1; i < list->head->max_level; i++)
    
39.         {
    
40.                 if ((rand()%2) == 1)
    
41.                 {
    
42.                         level++;
    
43.                 }
    
44.         }
    
45. 
    
46.         return level;
    
47. }
    
48. 
    
49. void Insert(SkipList* list, int key, int value)
    
50. {
    
51.     printf("开始插入key:%d\n", key);
    
52.     printf("max_level:%d\n", list->head->max_level);
    
53.     Node** update = (Node**)malloc(sizeof(Node*)*list->head->max_level);
    
54.     Node* prev = list->head;
    
55.     Node* tmp = (Node*)malloc(sizeof(Node*));
    
56. 
    
57.     int i = 0;
    
58.     for(i = list->level - 1;i >= 0;i--)
    
59.     {
    
60.         while(((tmp = prev->next[i]) != NULL) && (tmp->key < key))
    
61.         {
    
62.             prev = tmp;
    
63.         }
    
64.         update[i] = prev;
    
65.     }
    
66. 
    
67.     if((tmp != NULL) && (tmp->key == key))
    
68.     {
    
69.         printf("%d已经存在\n");
    
70.         return;
    
71.     }
    
72. 
    
73.     int max_level = SkipListLevel(list);
    
74. 
    
75.     Node* newNode = CreateNode(key, value, max_level);
    
76.     printf("创建了一个节点key:%d,value:%d\n", newNode->key, newNode->value);
    
77.     if(max_level > list->level)
    
78.     {
    
79.         for(i = list->level;i < max_level;i++)
    
80.         {
    
81.             update[i] = list->head;
    
82.         }
    
83.         list->level = max_level;
    
84.     }
    
85. 
    
86.     for(i = 0;i < list->level;i++)
    
87.     {
    
88.         newNode->next[i] = update[i]->next[i];
    
89.         update[i]->next[i] = newNode;
    
90.     }
    
91. 
    
92.     list->count ++;
    
93. }
    
94. 
    
95. 
    
96. void PrintSkipList(SkipList* list)
    
97. {
    
98.     Node* prev = list->head;
    
99.     int i = 0;
    
100.     for(i = list->level - 1;i >= 0;i--)
     
101.     {
     
102.         prev = list->head;
     
103.         printf("level[%d]:", i);
     
104.         while(prev->next[i] != NULL)
     
105.         {
     
106.             printf("%d-%d ", prev->next[i]->key, prev->next[i]->value);
     
107.             prev = prev->next[i];
     
108.         }
     
109.         printf("\n");
     
110.     }
     
111.     printf("\n");
     
112. }
     
113. 
     
114. int main()
     
115. {
     
116.     SkipList* list = CreateSkipList(5);
     
117. 
     
118.     Insert(list, 1, 1);
     
119.     Insert(list, 2, 2);
     
120.     Insert(list, 3, 3);
     
121.     Insert(list, 4, 4);
     
122. //    Insert(list, 5, 5);
     
123.     PrintSkipList(list);
     
124.     return 0;
     
125. }
     

复制代码

小玉玉

找到问题了

1. for(i = 0;i < list->level;i++)
   
2.     {
   
3.         newNode->next[i] = update[i]->next[i];
   
4.         update[i]->next[i] = newNode;
   
5.     }

复制代码

换成

1.     for(i = 0;i < max_level;i++)
   
2.     {
   
3.         newNode->next[i] = update[i]->next[i];
   
4.         update[i]->next[i] = newNode;
   
5.     }

复制代码

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