在链表中插入节点的函数

Question

我正在从字典中读入单词，然后将它们添加到哈希链接列表中 table。当我尝试在 while 循环中为每个单词插入节点时，这很好用。

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        return false;
    }

    // Set all next pointers to NULL in hash table
    for (int i = 0; i < N; i++)
    {
        table[i] = NULL;
    }

    char word[LENGTH + 1];
    while(fscanf(dict, "%s", word) != EOF)
    {
        // Get key from hash function
        unsigned int key = hash(word);

        node *pNode = getNode(word);

        if (table[key] != NULL)
        {
            pNode->next = table[key];
        }

        table[key] = pNode;

        words++;
    }
    fclose(dict);
    return true;
}

我试过用完全相同的代码将其重构为一个函数 insertNode，但它不起作用，节点似乎丢失并导致内存泄漏。我假设它与参数如何传递给函数有关，但由于 head 是一个指针，我认为它可以正常工作。

void insertNode(node *head, const char *key)
{
    // Create node
    node *pNode = getNode(key);

    // Insert node into linked list
    if (head != NULL)
    {
         // Make new node point to first item in linked list (a.k.a head)
         pNode->next = head;

    }
    // Now point head to new node
    head = pNode;
}

所以 load 中的 while 循环将只调用函数（之前定义）

char word[LENGTH + 1];
while(fscanf(dict, "%s", word) != EOF)
{
    // Get key from hash function
    unsigned int key = hash(word);

    // Add value to Hash table with head of linked list
    insertNode(table[key], word);

    words++;
}

Answer 1

因为'head'变量是一个指针，你可以只通过这个指针传递'head'的值而不是指针本身，在这种情况下你试图覆盖功能。

好吧看这个例子把assign/change值给指针：

#include <stdio.h>

class A {
public:
    int x;
};

// pass pointer by copy
void initialize(A* obj) {

    obj = new A(); // obj not null here
    obj->x = 2;

    printf("x: %d\n", obj->x);
}

int main() {

    A *a = nullptr;

    initialize(a);

    // a is still null here (pointer passed by copy)

    printf("x: %d\n", a->x); // seg fault here, read on null

    return 0;
}

如您所见，以下代码不正确。要修复此示例，您必须更改函数原型，并逐个传递指针，因此它应该像这样：

#include <stdio.h>

class A {
public:
    int x;
};

// pass pointer by pointer
void initialize(A** obj) {

    *obj = new A(); // obj not null here
    (*obj)->x = 2;

    printf("x: %d\n", (*obj)->x);
}

int main() {

    A *a = nullptr;

    initialize(&a); // get the pointer address

    // a is valid object here

    printf("x: %d\n", a->x); // no error, x == 2

    return 0;
}

所以在你的情况下应该是：

insertNode(&table[key], word);

和

void insertNode(node **head, const char *key)
{
    // Create node
    node *pNode = getNode(key);

    // Insert node into linked list
    if (*head != NULL)
    {
         // Make new node point to first item in linked list (a.k.a head)
         pNode->next = *head;

    }
    // Now point head to new node
    *head = pNode;
}

在链表中插入节点的函数

Function to insert node in linked list

c

hashtable

linked-list