c-从书中跳过列表源代码，一个结构让我感到困惑

Question

我在谷歌上搜索了跳过列表，找到了一本书"算法入门"http://epaperpress.com/sortsearch/index.html 并从以下位置获取跳过列表教程示例http://epaperpress.com/sortsearch/skl.html

有一个运行良好的skl.c，但是当我研究代码时，我发现了一些东西让我感到困惑的是，显示为以下内容：

typedef int keyType;            /* type of key */
/* user data stored in tree */
typedef struct {
    int stuff;                  /* optional related data */
} recType;

/* levels range from (0 .. MAXLEVEL) */
#define MAXLEVEL 15
typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[1]; /* skip list forward pointer */
} nodeType;
/* implementation independent declarations */
typedef struct {
    nodeType *hdr;              /* list Header */
    int listLevel;              /* current level of list */
} SkipList;
SkipList list;                  /* skip list information */

让我感到困惑的功能如下：

void initList() {
    int i;
   /**************************
    *  initialize skip list  *
    **************************/
    if ((list.hdr = malloc(
        sizeof(nodeType) + MAXLEVEL*sizeof(nodeType *))) == 0) {
        printf ("insufficient memory (initList)n");
        exit(1);
    }
    for (i = 0; i <= MAXLEVEL; i++)
        list.hdr->forward[i] = NIL;
    list.listLevel = 0;
}

在这个测试中似乎 MAXLEVEL = 15 ，所以在 initList（） 中，它会做 list.hdr->forward[0] = NIL; to list.hdr->forward[15] = NIL; 看看nodeType结构，它有前向var结构节点标签*forward[1]; ，而不是结构节点标签 *forward[MAXLEVEL];

我认为正确的结构应该是：

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[MAXLEVEL]; /* skip list forward pointer */
} nodeType;

不

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[1]; /* skip list forward pointer */
} nodeType;

还是我错过了什么？

Answer 1

我认为原文是正确的。

仔细看看这个马洛克：

list.hdr = malloc(sizeof(nodeType) + MAXLEVEL*sizeof(nodeType *)));

请注意表达式中的 MAXLEVEL*sizeof（nodeType *）。这是在做的是分配一个 nodeType 和 MAXLEVEL * nodeType* 在一个 malloc 中。所以它正在分配节点和节点类型* 数组。这是有效的，因为数组是最后一个结构中的字段。所以节点和数组是一个连续的部分的记忆。

可以说更正确的应该是typedef

typedef struct nodeTag {
    keyType key;                /* key used for searching */
    recType rec;                /* user data */
    struct nodeTag *forward[0]; /* skip list forward pointer */
} nodeType;

请注意零数组大小。

当与上面的 malloc 表达式一起使用时，这是一个常见的 C 习语。它允许你在运行时而不是编译时决定数组大小。但请记住数组必须是结构中的最后一个字段。

Rici在下面的评论中提出了两个非常好的观点。