我想我对跳过列表的工作原理有了基本的了解,但是除了作为 C 初学者之外,对它们来说是新手让我在一些方面感到困惑,尤其是列表的初始化。这是我要遵循的代码:
#define MAXSKIPLEVEL 5
typedef struct Node {
int data;
struct Node *next[1];
} Node;
typedef struct SkipList {
Node *header;
int level;
} SkipList;
// Initialize skip list
SkipList* initList() {
SkipList *list = calloc(1, sizeof(SkipList));
if ((list->header = calloc(1, sizeof(Node) + MAXSKIPLEVEL*sizeof(Node*))) == 0) {
printf("Memory Error\n");
exit(1);
}
for (int i = 0; i < MAXSKIPLEVEL; i++)
list->header->next[i] = list->header;
return list;
}
我还没有在 C 语言中对指针数组做过任何事情,所以我想我有点了解它们是如何工作的。如果有人愿意帮助我,我有几个问题。
首先,我做sizeof(int)
了,得到了 4,sizeof(Node*)
得到了 8,所以我希望sizeof(Node)
等于 12,但结果是 16,这是为什么呢?SkipList
与其内容的大小相比,它的大小也有同样的混淆。我拿出typedef
来[1]
看看是否是其中任何一个原因,但尺寸仍然是 16。
其次,为什么[1]在struct Node *next[1]
?list->header->next[i]
后期需要吗?next[i]
高于 1 可以吗?是不是因为每个节点的指针数量是可变的,所以你把它变成一个数组,然后再单独增加它?
三、为什么list->header->next[i] = list->header
最初不是NULL
?
非常感谢任何建议/意见,谢谢。