Правописатель CS50: Unload выполняет 80 000 000 + освобождений - PullRequest
Новая
       6

Правописатель CS50: Unload выполняет 80 000 000 + освобождений

0 голосов
/ 30 апреля 2019

Это pset 5 в CS50 Гарварда. Он состоит в основном из загрузки словаря, проверки того, находится ли каждое слово в выбранном тексте в загруженном словаре, а затем выгрузки (освобождения всей выделенной памяти). Все остальные функции работают, но когда дело доходит до разгрузки, он просто выполняет, как указано, 80 000 000 + освобождает, в то время как в программе всего 143 094 malloc, я новичок, так что это для меня ошеломляет. Ниже приведены соответствующие функции для разгрузки.

Edit (1): Вот некоторый контекст относительно переменной hashtable . 

typedef struct node
{
    char word[LENGTH+2];
    struct node *next;
}
node;

node *hashtable[264636] = { NULL };

Я инициализирую каждый элемент в NULL, чтобы при выгрузке я мог легко пропустить значения индекса, для которых в хэш-функции не было сгенерировано ключа. 

//LOAD FUNCTION: Loads the dictionary into a hash table. Djb2 function used. 

bool load(const char *dictionary)
{
    head = malloc(sizeof(node));
    head->next = NULL;
    if (head == NULL)
    {
        unload();
        return false;
    }
    opntr = fopen(dictionary, "r");

    while (fscanf(opntr, "%s", WORD) != EOF)
    {
        wnode = malloc(sizeof(node));
        if (wnode == NULL)
        {
            unload();
            return false;
        }
        strcpy(wnode->word, WORD);
        wnode->next = head; 
        head = wnode; 
        unsigned long key = hash(wnode->word);
        hashtable[key] = wnode;
        wnode = wnode->next;
    }
    return true;
}

// Checks whether the input word is somewhere within the dictionary

bool check(const char *word)
{
    char dword[strlen(word) + 1];
    strcpy(dword, word);
    for (int c = 0; c < strlen(dword); c++)
    {
        dword[c] = tolower(dword[c]);
    }
    int key_w;
    key_w = hash(dword);
    node *cursor = hashtable[key_w];
    while (cursor != NULL)
    {
        if (strcmp(cursor->word, dword) == 0)
        {
            return true;
        }
        cursor = cursor->next; 
    }
    return false;
}


// Unloads memory allocated (?) to store the dictionary

bool unload(void)
{
    for (int in = 0; in < 264636; in++)
    {
        node *fhead = hashtable[in];             
        while (fhead != NULL)
        {
            node *fcursor = fhead->next;
            free(fhead);
            fhead = fcursor;
        }
    }
    return true;
}

1 Ответ

0 голосов
/ 01 мая 2019

В случае, если кто-то найдет это полезным, проблема была в функции загрузки.Неверные узлы были обновлены неправильно, так что элементы массива хеш-таблиц не были независимыми связанными списками, и я без необходимости использовал головной узел, чтобы указывать на первый элемент списка каждый раз, когда мы хотели добавить узел.Вместо этого, чтобы добавить новый узел к соответствующему элементу в массиве хеш-таблиц, мы используем сам элемент в качестве заголовка связанного списка и размещаем его так, чтобы он указывал на каждый добавленный узел, таким образом, успешно отслеживая началосвязанный список.Каждый элемент в хеш-таблице изначально указывает на NULL, чтобы мы могли найти конец каждого связанного списка. 

int null()
{
    for (int i = 0; i < 264636; i++)
    {
        hashtable[i]->next = NULL;
    }
    return 0;
}

bool load(const char *dictionary)
{

    opntr = fopen(dictionary, "r");
    while (fscanf(opntr, "%s", WORD) != EOF)
    {
        wnode = malloc(sizeof(node));
        if (wnode == NULL)
        {
            unload();
            return false;
        }
        strcpy(wnode->word, WORD);
        unsigned long key = hash(wnode->word);
        wnode->next = hashtable[key]; 
        hashtable[key] = wnode; 
    }
    return true;
}
...