c - 带指针的结构的 malloc(重新访问)

Question

如果这看起来像是一个重复的问题，我深表歉意，但我想对 a previous question I found here 做一些澄清。关于使用 malloc 为包含指针的结构分配堆内存。我发现了关于 malloc 和结构的各种其他问题，但出于某种原因，它们似乎都涉及在定义结构时使用 typedef 的人，我不知道这是否会改变问题的上下文，所以我想通过询问来避免混淆新问题。

所以 answers to this question似乎暗示着这样的结构:

struct Vector {
    double *data;
    size_t size;
};

创建实例时，我们应该为结构本身分配内存空间:

struct Vector *retVal = malloc (sizeof (struct Vector));

AND 指向结构内数据的指针:

retVal->data = malloc (sz * sizeof (double));

问题是我一直在阅读 Brian Kernighan 和 Dannis Ritchie 合着的 “The ANSI C Programming Language”(第二版)，这是一本相当古老的书，但我认为它是好东西。不幸的是，它没有详细介绍 malloc。然后我在第 119 页看到了以下代码，它说明了符号表管理(例如预处理器)如何工作的示例。它为符号和替换符号的文本定义了一个结构(nlist)。 nlists存储在一个静态数组(hashtab)中，使用一个简单的散列函数，然后使用散列的模数数组大小来计算数组索引，因此如果发生冲突，则有一个指向下一个nlist的指针:

struct nlist { /* table entry: */
     struct nlist *next; /* next entry in chain */
     char *name; /* defined name */
     char *defn; /* replacement text */
 };

然后有一个安装函数，用于将新的 nlist 添加到 hashtab:

struct nlist *lookup(char *);
char *strdup(char *);

/* install: put (name, defn) in hashtab */
 struct nlist *install(char *name, char *defn)
 {
     struct nlist *np;
     unsigned hashval;
     if ((np = lookup(name)) == NULL) { /* not found */
            np = (struct nlist *) malloc(sizeof(*np));
         if (np == NULL || (np->name = strdup(name)) == NULL)
            return NULL;
         hashval = hash(name);
         np->next = hashtab[hashval];
         hashtab[hashval] = np;
     } else /* already there */
        free((void *) np->defn); /*free previous defn */
    if ((np->defn = strdup(defn)) == NULL)
        return NULL;
     return np;
 }

这是我开始哭泣和前后摇晃的时刻，当我的大脑从耳朵里融化时流口水。对于指向 next、name 或 defn 的指针，似乎没有发生任何 malloc 操作nlist 结构。这是对还是错？

谢谢。

PS 查找函数是:

/* lookup: look for s in hashtab */
 struct nlist *lookup(char *s)
 {
     struct nlist *np;
     for (np = hashtab[hash(s)]; np != NULL; np = np->next)
        if (strcmp(s, np->name) == 0)
            return np; /* found */
     return NULL; /* not found */
 }

Answer 1

您的问题有几个部分:

There doesn't appear to be any malloc action going on for the pointers to next, name or defn in the nlist struct. Is this right or wrong?

你已经从评论中看到，name 和 defn 都分配了空间来保存关联的字符串，这是由于 strdup 为你分配的. (因此，当不再需要时，您可以free name 和 defn。)

问题的症结所在，似乎是您混淆的根源，是链表的 next 指针。正如 Ahmad 正确指出的那样，pointer 是一种数据类型，与 int 或 char 相同。 (存储大小因操作系统而异，但通常您会在 x86 上找到 4 字节 指针，在 x86_64 上找到 8 字节 指针。有一些极端情况嵌入式系统等)

正如 int 可以保存一个整数，char 可以保存一个字符而无需进一步分配，pointer 可以保存一个内存地址无需进一步分配。如果您查看链表，特别是 next 指针的使用方式以及 next 指针包含的内容，您将看到 next用于保存以下节点的地址:

    +----+      +----+      +----+
    |1st |      |2nd |      |3rd |
    |node|  +-->|node|  +-->|node|
    |    |  |   |    |  |   |    |
    |next|--+   |next|--+   |next|-->...
    +----+      +----+      +----+

节点本身被分配:

np = (struct nlist *) malloc(sizeof(*np));    [see: footnote 1]

当分配每个节点时，next 指针的空间也被分配。不需要进一步分配next。它可以愉快地自己保存下一个节点的地址。您只需要为指针指向的内容分配一 block 内存，而不是指针本身。

你分配的东西在很多情况下可能是指针，例如:

#define NUMPTRS 10

char **list;
list = malloc (NUMPTRS * sizeof *list);

但如果你仔细观察，它符合规则。您没有分配空间来保存 list 的地址，而是分配了 10 指针来保存其他内容的地址。

希望这对 Ahmad 试图解释的内容有所补充，并使您的头脑更加清晰。如果您有任何问题，请告诉我。

脚注:

1. There is no need to cast the return of malloc.

    np = malloc (sizeof *np);

is fine by itself. see Do I cast the result of malloc?