基于void指针的跳表实现异常：compare函数无法执行

实现基于void指针的跳表时，insertSkipList函数执行到list->compare(I, actual_node->next[k]->item)语句时直接停止，后续代码无法执行，怀疑问题出在actual_node->next[k]->item，但无法定位原因。

问题代码片段 #

void insertSkipList(SkipList* list, void* I){
  Node* new_node=createNode(I, randomLevel(list->max_level));
  if (new_node->size > list->max_level)   

  Node* actual_node=list->head;
  unsigned int k;
  for (k = list->max_level;k>=1;k--){                          
    if (actual_node->next[k] == NULL || list->compare(I, actual_node->next[k]->item)<0){
      if (k < new_node->size) {                                
        new_node->next[k] = actual_node->next[k];
        actual_node->next[k]=new_node;
      }
    else{                                                    
        actual_node->next = &actual_node->next[k];
        k=k+1;                                                
    }
  }
  }
}

结构体定义 #

typedef struct _SkipList SkipList;
typedef struct _Node Node;

struct _SkipList {
  Node *head;
  unsigned int max_level;
  int (*compare)(void*, void*);
};

struct _Node {
  Node **next;
  unsigned int size;
  void *item;
};

完整可复现代码 #

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_LENGTH 20
#define MAX_HEIGHT 5

typedef struct _SkipList SkipList;
typedef struct _Node Node;

struct _SkipList {
  Node *head;
  unsigned int max_level;
  int (*compare)(void*, void*);
};

struct _Node {
  Node **next;
  unsigned int size;
  void *item;
};


unsigned int randomLevel(unsigned int height);

static int compare_int(void* x_void,void* y_void){
  int x=(int)x_void;
  int y=(int)y_void;
  return x-y;
}

static Node* createNode(void* item, unsigned int lvl) {
  Node* n = (Node*) malloc(sizeof(Node));
  if(n == NULL) {
    printf("\nError! Node memory not allocated.");
    exit(0);
  }
  n->item = item;
  n->next = NULL;
  n->size = lvl;
  return n;
}

SkipList* createSkipList(unsigned int height, int (*compare)(void*, void*)){
  SkipList* skiplist = (SkipList*) malloc(sizeof(SkipList));
  if(skiplist == NULL) {
    printf("\nError! Skiplist memory not allocated.");
    exit(0);
  }
  skiplist->head=createNode(NULL,height);
  skiplist->max_level=1;
  skiplist->compare=(*compare);
  return skiplist;
}

void insertSkipList(SkipList* list, void* I){
  Node* new_node=createNode(I, randomLevel(list->max_level));
  if (new_node->size > list->max_level)   
    list->max_level = new_node->size;
  Node* actual_node=list->head;
  unsigned int k;
  printf("here it's before the loop\n");
  for (k = list->max_level;k>=1;k--){                          
    if (actual_node->next[k] == NULL || list->compare(I, actual_node->next[k]->item)<0){     //here the code stops completely
      if (k < new_node->size) {                                
        new_node->next[k] = actual_node->next[k];
        actual_node->next[k]=new_node;
      }
    }
    else{                                                    
        actual_node->next = &actual_node->next[k];
        k=k+1;                                                
    }
  }
  printf("here it's after the loop (and actually this wont get printed idk why\n");
}

unsigned int randomLevel(unsigned int height){
  unsigned int lvl = 1;
  time_t t;
  srand((unsigned) time(&t));
  while (rand() < 0.5 && lvl < height)
    lvl = lvl + 1;
  return lvl;
}

int main()          //creates a skiplist that goes from 0 to MAX_LENGTH
{
      skiplist=createSkipList(MAX_HEIGHT,(*compare_int));
      int found[MAX_LENGTH];
      int expected[MAX_LENGTH];
      for(int i=0;i<MAX_LENGTH;i++){
        insertSkipList(skiplist,(void*) i);
      }
      return 0;
}

问题分析与修复 #

1. 核心崩溃原因：Node->next未分配内存 #

createNode函数中直接将n->next设为NULL，但跳表节点的next是指针数组，需要为其分配对应层级数的内存。访问actual_node->next[k]时，next为NULL会触发空指针访问崩溃。

修复createNode：

static Node* createNode(void* item, unsigned int lvl) {
  Node* n = (Node*) malloc(sizeof(Node));
  if(n == NULL) {
    printf("\nError! Node memory not allocated.");
    exit(0);
  }
  // 为next数组分配内存，层级从1到lvl，预留额外位置避免越界
  n->next = (Node**)calloc(lvl + 1, sizeof(Node*));
  if(n->next == NULL) {
    printf("\nError! Node next array memory not allocated.");
    free(n);
    exit(0);
  }
  n->item = item;
  n->size = lvl;
  return n;
}

2. randomLevel函数逻辑错误 #

• 每次调用都重置随机数生成器srand((unsigned) time(&t))，导致随机数重复甚至完全一致。
• rand()返回整数（范围0~RAND_MAX），和浮点数0.5比较永远为假，导致randomLevel永远返回1，跳表退化为普通链表。

修复randomLevel：

// 仅初始化一次随机数生成器
static int rand_inited = 0;

unsigned int randomLevel(unsigned int height){
  if(!rand_inited) {
    srand((unsigned)time(NULL));
    rand_inited = 1;
  }
  unsigned int lvl = 1;
  // 用rand()%2模拟50%概率
  while ((rand() % 2 == 0) && lvl < height) {
    lvl++;
  }
  return lvl;
}

3. insertSkipList中的指针操作错误 #

else分支中actual_node->next = &actual_node->next[k];完全错误，会把节点的next指针数组替换为指向自身数组元素的指针，导致后续访问混乱。正确逻辑是移动到当前节点的next[k]，并通过k++抵消for循环的k--以保持当前层级。

修复insertSkipList的else分支：

else {
  // 移动到下一个节点
  actual_node = actual_node->next[k];
  // 保持当前k值，抵消for循环的k--
  k++;
}

4. 其他次要问题 #

• createSkipList中skiplist->max_level初始值错误，应设为传入的height（head节点的层级为height）：

  skiplist->max_level = height;
  

• main函数中skiplist未声明类型，添加：

  SkipList* skiplist;
  

• compare_int的类型转换存在64位平台兼容性问题，若要安全存储整数，应分配内存存储int值再传入指针：

  // 插入时
  int* val = malloc(sizeof(int));
  *val = i;
  insertSkipList(skiplist, val);
  // compare函数修改为
  static int compare_int(void* x_void,void* y_void){
    int x=*(int*)x_void;
    int y=*(int*)y_void;
    return x-y;
  }
  

修复后的完整代码 #

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX_LENGTH 20
#define MAX_HEIGHT 5

typedef struct _SkipList SkipList;
typedef struct _Node Node;

struct _SkipList {
  Node *head;
  unsigned int max_level;
  int (*compare)(void*, void*);
};

struct _Node {
  Node **next;
  unsigned int size;
  void *item;
};


unsigned int randomLevel(unsigned int height);

static int compare_int(void* x_void,void* y_void){
  // 若使用内存分配存储整数，启用下面两行
  // int x=*(int*)x_void;
  // int y=*(int*)y_void;
  // 原代码的转换方式（仅32位系统安全）
  int x=(int)x_void;
  int y=(int)y_void;
  return x-y;
}

static Node* createNode(void* item, unsigned int lvl) {
  Node* n = (Node*) malloc(sizeof(Node));
  if(n == NULL) {
    printf("\nError! Node memory not allocated.");
    exit(0);
  }
  // 为next数组分配内存，层级从1到lvl
  n->next = (Node**)calloc(lvl + 1, sizeof(Node*));
  if(n->next == NULL) {
    printf("\nError! Node next array memory not allocated.");
    free(n);
    exit(0);
  }
  n->item = item;
  n->size = lvl;
  return n;
}

SkipList* createSkipList(unsigned int height, int (*compare)(void*, void*)){
  SkipList* skiplist = (SkipList*) malloc(sizeof(SkipList));
  if(skiplist == NULL) {
    printf("\nError! Skiplist memory not allocated.");
    exit(0);
  }
  skiplist->head=createNode(NULL,height);
  skiplist->max_level=height;
  skiplist->compare=compare;
  return skiplist;
}

void insertSkipList(SkipList* list, void* I){
  Node* new_node=createNode(I, randomLevel(list->max_level));
  if (new_node->size > list->max_level)   
    list->max_level = new_node->size;
  Node* actual_node=list->head;
  unsigned int k;
  printf("here it's before the loop\n");
  for (k = list->max_level;k>=1;k--){                          
    if (actual_node->next[k] == NULL || list->compare(I, actual_node->next[k]->item)<0){
      if (k <= new_node->size) {                                
        new_node->next[k] = actual_node->next[k];
        actual_node->next[k]=new_node;
      }
    }
    else{                                                    
        actual_node = actual_node->next[k];
        k++;                                                
    }
  }
  printf("here it's after the loop\n");
}

static int rand_inited = 0;
unsigned int randomLevel(unsigned int height){
  if(!rand_inited) {
    srand((unsigned)time(NULL));
    rand_inited = 1;
  }
  unsigned int lvl = 1;
  while ((rand() % 2 == 0) && lvl < height) {
    lvl++;
  }
  return lvl;
}

int main()          
{
  SkipList* skiplist=createSkipList(MAX_HEIGHT, compare_int);
  int found[MAX_LENGTH];
  int expected[MAX_LENGTH];
  for(int i=0;i<MAX_LENGTH;i++){
    // 若使用内存分配存储整数，替换为下面两行
    // int* val = malloc(sizeof(int));
    // *val = i;
    // insertSkipList(skiplist, val);
    insertSkipList(skiplist,(void*) i);
  }
  return 0;
}

内容的提问来源于stack exchange，提问作者ramaswag