0

我想我对跳过列表的工作原理有了基本的了解,但是除了作为 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?

非常感谢任何建议/意见,谢谢。

4

2 回答 2

1

由于结构填充,该sizeof数字为 16 。

许多架构要么要求强烈希望它们的指针在某个边界上对齐(例如,4 字节边界、8 字节边界等)。如果指针“未对齐”,它们要么失败,要么执行缓慢。您的 C 编译器可能会在结构中间插入 4 个未使用的字节,以便您的 8 字节指针在 8 字节边界上对齐,这会导致结构大小增加 4 个字节。

C FAQ提供了更多解释。

于 2016-07-19T21:41:53.860 回答
1

对于您的第一个问题 - 为什么struct其成员的大小不是大小?- 这是由于struct padding,编译器通常出于对齐原因,可能会在 astruct的成员之间或之后添加额外的空白空间,以使大小达到某个基本大小(通常为 8 或 16)的好倍数. 没有可移植的方法来强制结构的大小与其成员的大小完全相同,尽管大多数编译器都有一些自定义开关,您可以翻转来执行此操作。

对于你的第二个问题 - 为什么[1]?- 这里的想法是,当您实际分配节点之一时struct,您将过度分配空间,以便可以将末尾的内存struct用于指针。通过创建一个长度为 1 的数组,然后过度分配空间,您可以在语法上方便地访问这个过度分配的空间,就好像它是一直以来的一部分struct一样。较新版本的 C 有一个称为灵活数组成员的概念,它取代了这种技术。我建议用谷歌搜索它,看看是否有帮助。

对于您的最后一个问题-为什么list->header->next[i]最初指向list->header而不是NULL?- 没有看到更多的代码很难说。链表结构的许多实现都使用类似这样的技巧来避免在NULL实现中使用特殊情况,并且完全有可能在这里也使用这种技巧。

于 2016-07-19T21:42:34.340 回答