c - 关于 struct 内存分配机制的一些困惑？

Question

在我的项目中，我遇到了 C 程序。

如下图，htmp是一个结构指针。我们首先为它分配内存。但是我们为什么要为其元素分配内存 word再次？

如果必须为结构的每个元素分配内存，为什么不为其他元素分配内存，id和 next ?

#define HASHREC bitewisehash  


typedef struct hashrec {
    char    *word;
    long long id;
    struct hashrec *next;
} HASHREC;

/* Move-to-front hashing and hash function from Hugh Williams, http://www.seg.rmit.edu.au/code/zwh-ipl/ */

/* Simple bitwise hash function */
unsigned int bitwisehash(char *word, int tsize, unsigned int seed) {
    char c;
    unsigned int h;
    h = seed;
    for (; (c =* word) != '\0'; word++) h ^= ((h << 5) + c + (h >> 2));
    return((unsigned int)((h&0x7fffffff) % tsize));
}

/* Insert string in hash table, check for duplicates which should be absent */
void hashinsert(HASHREC **ht, char *w, long long id) {
    HASHREC *htmp, *hprv;
    unsigned int hval = HASHFN(w, TSIZE, SEED);
    for (hprv = NULL, htmp = ht[hval]; htmp != NULL && scmp(htmp->word, w) != 0; hprv = htmp, htmp = htmp->next);
    if (htmp == NULL) {
        htmp = (HASHREC *) malloc(sizeof(HASHREC)); # allocate memory for htmp
        htmp->word = (char *) malloc(strlen(w) + 1); # why allocate memory again ?
        strcpy(htmp->word, w);    # 
        htmp->id = id;            # why not allocate memory for htmp->id ?
        htmp->next = NULL;        # why nor allocate memory for htmp->next?
        if (hprv == NULL) ht[hval] = htmp;
        else hprv->next = htmp;
    }
    else fprintf(stderr, "Error, duplicate entry located: %s.\n",htmp->word);
    return;
}

Answer 1

您需要在脑海中区分两件事(1)我要存储的东西存储在什么内存中？ (2) 什么变量(指针)将地址保存到它的存储位置，以便我可以再次找到它。

首先声明两个指向 struct hashrec 的指针:

HASHREC *htmp, *hprv;

指针只不过是一个变量，它将指向其他东西的地址作为其值。当你第一次声明这两个指针时，它们是未初始化的并且没有地址。然后，您以一种相当笨拙的方式初始化 for 中的两个指针。循环声明，例如 hprv = NULL, htmp = ht[hval]及以后 hprv = htmp, htmp = htmp->next所以大概两个指针现在都持有一个地址并指向某个地方。

在循环之后(带有空主体)，您测试 if (htmp == NULL) , 表示 htmp不指向地址(如果您发现感兴趣的哈希索引为空，则可能是这种情况)。

然后为了给一个 HASHREC 提供存储空间(例如 struct hashrec )您需要分配存储空间，以便您有一 block 内存来存储您想要存储的东西。所以你分配一个 block 来保存一个结构。 (见: Do I cast the result of malloc?)

现在，看看你为什么分配了内存:

typedef struct hashrec {
    char    *word;
    long long id;
    struct hashrec *next;
} HASHREC;

您已为包含 (1) char *word; 的结构分配存储空间。 (指向 char 的指针 - 8 字节(x86 上为 4 字节))； (2) 一个 long long id; (两者均为 8 字节)和 (3) 一个指针，用于保存下一个 HASHREC 的地址在序列中。

毫无疑问 id可以持有 long long值，但是 word 呢？和 next ?它们都是指针。指针有什么作用？可以找到他们指向的东西的地址。哪里可以 word被发现？ w当前指向你想要的东西, 但不能保证 w将继续保留您想要的单词，因此您将制作一个副本并将其存储为 HASHREC 的一部分.所以你看:

htmp->word = malloc(strlen(w) + 1);    /* useless cast removed */

现在 malloc 是什么意思？返回？它将地址返回到新内存块的开头， strlen(w) + 1字节长。由于指针保存其他东西的值作为它的值， htmp->word现在将地址存储到新内存块的开头作为其值。所以 htmp->word “指向”新的内存块，您可以使用 htmp->word作为引用该内存块的引用。

接下来发生的事情很重要:

    strcpy(htmp->word, w);    # 
    htmp->id = id;            # why not allocate memory for htmp->id ?
    htmp->next = NULL;        # why nor allocate memory for htmp->next?

strcpy(htmp->word, w);副本 w进入那个新的内存块。 htmp->id = id;赋值 id至 htmp->id和 无需分配因为当你分配:

htmp = malloc(sizeof(HASHREC));  /* useless cast removed */

您为 (1) char * 分配存储空间指针，(2) 一个 long long id; (3) 一个 struct hashrec*指针——你已经为 long long 分配了所以 htmp->id可以存储 id的值在 long long 的内存中.

htmp->next = NULL;        # why nor allocate memory for htmp->next?

您尝试存储的内容是什么，需要为 htmp->next 重新分配? (提示:目前没有)它将指向下一个 struct hashrec .目前初始化为 NULL以便下次您迭代到所有 struct hashrec next 的末尾指针，当你到达 NULL 时，你就知道你已经走到了尽头.

另一种思考方式是前面的 struct hashrec next现在可以指向你刚刚分配的这个节点。同样不需要额外分配，前一个节点 ->next指针只是指向顺序的下一个节点，不需要分配任何特定的新内存。它仅用作引用(或指向)链中下一个节点的引用。

这里有很多信息，但是当您通过确定(1)我要存储的东西存储在哪个内存中的思考过程时？和(2)什么变量(指针)将地址保存到它的存储位置，以便我可以再次找到它...... - 事情开始到位。希望这可以帮助。