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 回答