我用谷歌搜索了跳过列表,找到了一本书“算法导论” 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;到 list.hdr->forward[15] = NIL;并查看 nodeType 结构,它具有 forward var struct nodeTag *forward[1]; , 不是 struct nodeTag *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;
或者我错过了什么?
最佳答案
我认为原文是正确的。
仔细看这个malloc:
list.hdr = malloc(sizeof(nodeType) + MAXLEVEL*sizeof(nodeType *)));
注意表达式中的 MAXLEVEL*sizeof(nodeType *)。这是在做分配 单个 malloc 中的 nodeType AND MAXLEVEL * nodeType*。所以它正在分配 节点和 nodeType* 数组。这是有效的,因为数组是最后一个 结构中的字段。所以节点和数组是一个连续的片段 的内存。
可以说更正确的是 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 在下面的评论中提出了两个非常好的观点。
关于c - 书中的跳过列表源代码,一个结构让我困惑,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/18754239/