跳表实现出现Access Violation读取错误，求排查解决

问题描述 #

• 正在完成Stroustrup《PPP2》第18章练习11，实现跳表时抛出内存访问异常：

  Exception thrown at 0x00007FF61A3E656F in Skip List.exe: 0xC0000005: Access violation reading location 0x0000000000000020.
  

• 经排查，问题出在skipList::insert函数的嵌套while循环和if语句中对nullptr解引用，具体是访问(*current)->value > value或(*current)->value < value时出错。
• 移除该段代码后程序能运行但无输出，调试发现*current经常为nullptr，修改构造函数未解决问题。

核心排查步骤 #

1. 验证头节点初始化完整性 #

• 跳表的头节点需包含多层链表的表头结构，必须确保构造函数为头节点分配了内存，且每层的next指针都初始化为nullptr。如果头节点某层未初始化，会直接导致遍历指针current指向无效内存。
• 检查构造函数代码：是否创建了头节点对象，是否为每一层的指针成员完成初始化（比如用循环初始化所有层的next为nullptr）。

2. 修复遍历逻辑的边界判断 #

• 在insert函数的嵌套循环中，必须在访问(*current)->value前判断*current是否为nullptr，避免空指针解引用：

  // 错误写法
  while ((*current)->next != nullptr && (*current)->next->value < value)
  
  // 修正后写法
  while (*current != nullptr && (*current)->next != nullptr && (*current)->next->value < value)
  

• 当遍历到某一层的末尾时，停止该层的移动，切换到下一层继续遍历，避免越界访问。

3. 检查层数生成与管理逻辑 #

• 跳表的随机层数生成函数如果返回超过当前跳表最大层数的值，会导致访问未初始化的层结构，进而让current指向nullptr。
• 确保随机层数的上限不超过跳表初始化时设定的最大层数，且所有层的表头节点都已提前创建。

4. 确认current指针的初始赋值 #

• insert函数中current指针的初始值必须指向头节点的对应层指针，比如：

  // 假设头节点head有一个next数组，存储各层的指针
  Node** current = &head->next[max_level];
  

• 避免将current初始化为nullptr或指向未初始化的内存区域。

实用调试技巧 #

• 在insert函数开头，打印头节点各层next指针的地址，确认头节点是否正常初始化。
• 在每次访问(*current)前添加调试输出：

  if (*current == nullptr) {
      cout << "current is nullptr at level: " << current_level << endl;
      break;
  }
  

• 重点测试插入第一个元素的场景：此时所有层链表为空，需确保逻辑不会直接访问空指针的value成员。

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