我是一名 CS 学生，我的万圣节周末刚刚被我无法调试的编程作业毁了。这可能是这里为数不多的不会立即被标记为“重复”的问题之一。
分配是一个“跳过列表”或单链表（用 C 编程），其中每个节点都有一个可变大小的指针数组，由随机的“硬币”投掷决定。3 次成功的投掷导致高度为 3，依此类推。然后，每个数组都链接到具有相似高度的其他数组 - 第七层链接到下一个第七层，第六层到下一个第六层，一直到第一个或数组元素0，它自然地链接到列表中的下一个项目。
由于大多数项目没有更高的级别，因此这是在 log(n) 时间内搜索的好方法，而不是简单的 n。插入、删除和搜索的速度要快得多，但代价是内存成本更高。这只是理论 - 这是一张图片：跳过列表
你们中的许多人已经知道这些东西，但我只是想稍微解释一下，并表明我确实了解这里发生的事情的基础知识。
问题是一个随机的段错误，它用“CODE 6 - ABORT”消息搞砸了所有提供的测试。当我运行我的主文件时，我会在代码中的指定位置随机出现段错误（<-----Segfaults）——它发生在大约一半的时间，并且可以在任何一行。测试还给了我很多“错误指针”和“minmap 块错误”消息。
我对此束手无策。我在课堂上得了 93 分，但如果我不能完成这件可恶的事情，那分数就会下降到 87 分。
任何帮助表示赞赏，这是代码：
定义
typedef int data_t;
typedef struct skip_node {
data_t data;
size_t height;
struct skip_node **next;
} skip_node_t;
typedef struct skip_set {
skip_node_t *head;
size_t max_height;
size_t size;
} skip_set_t;
造成随机故障的主要方法
skip_set_t set;
skip_set_init(&set);
skip_set_add(&set, 4);
skip_set_add(&set, 3);
skip_set_clear(&set);
skip_set_t set2;
skip_set_init(&set2);
skip_set_add(&set2, 1); //faults here
...最后，魔鬼的数据结构：
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include "skip_set.h"
/***********************
PART 1
***********************/
//Initialize
void skip_set_init(skip_set_t *set)
{
//Set
set->size = 0;
set->max_height = 1;
set->head = malloc(sizeof(skip_node_t));
//Sentinel
set->head->data = 0;
set->head->height = set->max_height;
set->head->next = malloc(sizeof(skip_node_t*) * set->max_height);
}
//Clear
void skip_set_clear(skip_set_t *set)
{
if (set->head == NULL)
return;
skip_node_t* this;
skip_node_t* nex;
this = set->head->next[0];
while(this != NULL)
{
nex = this->next[0];
free(this->next);
this->next = NULL;
free(this);
this = nex;
}
set->size = 0;
for (int ii = 0; ii < set->max_height; ii++)
set->head->next[ii] = NULL;
}
//Size
size_t skip_set_size(skip_set_t *set)
{
return set->size;
}
//Free
void skip_set_free(skip_set_t *set)
{
skip_set_clear(set);
free(set->head->next);
set->head->next = NULL;
free(set->head);
set->head = NULL;
}
//Add
void skip_set_add(skip_set_t *set, data_t value)
{
printf("Add Start\n");
if (skip_set_contains(set, value))
return;
int new_height = 1;
while(rand() % 2 == 0)
{
new_height++;
}
printf("Add One\n");
if (set->max_height < new_height)
{
skip_node_t** arr = malloc(sizeof(skip_node_t*) * new_height);
for (int ii = 0; ii < set->max_height; ii++)
arr[ii] = set->head->next[ii];
for (int jj = set->max_height; jj < new_height; jj++)
arr[jj] = NULL;
printf("Add Two\n");
free(set->head->next);
set->head->next = NULL;
set->head->next = arr;
set->max_height = new_height;
set->head->height = new_height;
printf("Add Three\n");
}
skip_node_t* new_node = (skip_node_t*)malloc(sizeof(skip_node_t));
skip_node_t** arr = calloc(new_height, sizeof(skip_node_t*));
new_node->next = arr;
new_node->height = new_height;
new_node->data = value;
skip_node_t* cur_node = set->head;
int cur_level = set->max_height - 1;
printf("Add Four\n");
while (cur_level >= 0)
{
printf("ABreak 1\n");
while ((cur_node->next[cur_level] != NULL) && (cur_node->next[cur_level]->data < value))//<-----Segfaults
{
printf("ABreak 2\n");
cur_node = cur_node->next[cur_level];
printf("ABreak 3\n");
}
printf("ABreak 4\n");
if (cur_level < new_height)
{
printf("ABreak 5\n");
new_node->next[cur_level] = cur_node->next[cur_level];
cur_node->next[cur_level] = new_node;
printf("ABreak 6\n");
}
printf("ABreak 7\n");
cur_level--;
}
set->size++;
printf("Add End\n");
}
//Remove
void skip_set_remove(skip_set_t *set, data_t value)
{
printf("Remove Start\n");
if (!skip_set_contains(set, value))
return;
skip_node_t* tbf;
skip_node_t* cur_node = set->head;
int cur_level = set->max_height - 1;
printf("Remove 1\n");
while (cur_level >= 0)
{
while ((cur_node->next[cur_level] != NULL) && (cur_node->next[cur_level]->data < value))
{
cur_node = cur_node->next[cur_level];
}
if ((cur_node->next[cur_level] != NULL) && (cur_node->next[cur_level]->data == value))
{
tbf = cur_node->next[0];
cur_node->next[cur_level] = cur_node->next[cur_level]->next[cur_level];
if (cur_node == NULL && cur_node->next[cur_level] == NULL)
set->max_height--;
}
cur_level--;
}
printf("Remove 2\n");
free(tbf->next);
printf("Remove 3\n");
free(tbf);
set->size--;
printf("Remove End\n");
}
//Pop
data_t skip_set_pop(skip_set_t *set)
{
printf("Pop Start\n");
data_t lazyCSstudent = set->head->next[0]->data;
skip_set_remove(set, lazyCSstudent);
printf("Pop End\n");
return lazyCSstudent;
}
//Contains
bool skip_set_contains(skip_set_t *set, data_t value)
{
printf("Contains Start\n");
skip_node_t* this = set->head;
int i = set->max_height - 1;
printf("Contains Mid\n");
while(i >= 0)
{
printf("CBreak One\n");
while((this->next[i] != NULL) && (this->next[i]->data < value)) ///<-----Segfaults
{
printf("CBreak Two\n");
this = this->next[i];
printf("CBreak Three\n");
}
i--;
printf("CBreak Four\n");
}
printf("Contains End\n");
return (this->next[0] != NULL) && (this->next[0]->data == value);
}
包含和添加是问题所在，尽管可能还有其他问题。奇怪的是，这通常发生在我释放另一个列表之后，但我在我的代码中找不到任何工件。
如果你帮我解决这个问题，我会寄 20 美元和一盘饼干到你选择的地址。