Функция для вставки узла в связанный список - PullRequest
Новая
       17

Функция для вставки узла в связанный список

0 голосов
/ 26 января 2020

Я читаю слова из словаря, а затем добавляю их в связанные списки в таблице ha sh. Это прекрасно работает, когда я пытаюсь вставить узлы для каждого слова в то время как l oop. 

// 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 с точно таким же кодом, но это не так t и узлы, кажется, теряются и вызывают утечку памяти. Я предполагаю, что это как-то связано с тем, как аргументы передаются в функцию, но поскольку 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;
}

, поэтому пока l oop в load просто вызовет функцию (которая определена ранее) 

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++;
}

1 Ответ

1 голос
/ 26 января 2020

Поскольку переменная 'head' является указателем, вы можете просто передать значение 'head' этим указателем, а не самим указателем, и в этом случае вы попытаетесь переопределить локальный указатель внутри функции.

Хорошо посмотрите на этот пример, чтобы присвоить / изменить значение указателю: 

#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;
}
...