指针数组与跳过列表混淆

Question

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

其次，为什么struct Node *next[1]中的[1]？以后 list->header->next[i] 需要吗？ next[i] 高于 1 可以吗？是不是因为每个节点的指针数量是可变的，所以你把它做成一个数组，然后单独增加它？

三、为什么一开始是list->header->next[i] = list->header而不是NULL？

任何 advice/comments 非常感谢，谢谢。

Answer 1

sizeof 数字是 16，因为 结构填充 。

许多体系结构要求或强烈希望它们的指针在特定边界上对齐（例如，4 字节边界，8 -byte 边界等）如果指针是 "misaligned"，它们要么失败，要么执行缓慢。您的 C 编译器可能会在您的结构中间插入 4 个未使用的字节，以便您的 8 字节指针在 8 字节边界上对齐，这会导致结构大小增加 4 个字节。

C FAQ 中提供了更多解释。

Answer 2

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

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

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

指针数组与跳过列表混淆

Array of pointers confusion with skip list

c

arrays

pointers

skip-lists