Связанный список в C (проблемы с памятью)

Question

Я создаю простой связанный список в C, чтобы привыкнуть к некоторому управлению памятью.Я определил структуру узла, которая содержит ключ char *, char * value и узел * next.

void newnode(node *n, int x, int y)
{
    n->key = malloc(x*sizeof(char));
    n->value = malloc(y*sizeof(char)); 
}

//This how i create a new node given a key and value to make sure that I have allocated the proper amount of space. x and y are the strlengths of the key and value being added.

// In the add function I use the following two lines (when it is valid to add a new key value pair)

current->next = malloc(sizeof(node));
node_newnode(current->next,strlen(key),strlen(value));

// My remove function then searches for a key and if that key exists in the structure it removes that node. I use a delete point to keep track of the node needing deletion.

void remove(dict *d, const char *key)
{
    node* delete;
    node* current;
    current = d->head;

    while(current->next != NULL){

        if(strcmp(current->next->key,key)==0){
            delete = current->next;
            if(current->next->next != NULL)
                current = current->next->next;
            else
                current->next = NULL;
            node_destroy(delete);
            break;
        }

        current = current->next;
    }
}

// Here is the node_destroy function I used in remove. 

void node_destroy(node* delete)
{ 
    free(delete->key); 
    free(delete->value); 
    free(delete); 
} 

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

Есть предложения?

PS Функция уничтожения моего узла не освобождает память должным образом?

Answer 1

Сразу можно сказать, что если ваши ключи и значения являются строками (и, согласно вашему коду), то для хранения строки длины N в памяти вам нужно выделить N + 1 байт, а не Nбайт.Дополнительный байт требуется для нулевого символа-терминатора.В своем коде вы передаете strlen s соответствующих строк в виде x и y параметров в функцию распределения, а затем выделяете точно x и y символов для ключа и значения.Это уже неправильно.

Вы не показываете, как вы заполняете выделенную память ключей и значений (вероятно, на strcpy), но она наверняка будет заполнять выделенную память на 1 байт все время с катастрофическими последствиями.

На языке C память можно получить с помощью функций malloc() и calloc().для более подробной информации посетите http://scanftree.com/Data_Structure/linked-list

Answer 2

Вы никогда не удаляете удаленный узел из связанного списка.Это должно быть что-то вроде (проверка на крайние случаи):

current->next = current->next->next;

Например, если у вас есть:

{foo: bar} => {bar: baz} => {goo: gai}

и вы удаляете {bar: baz}, вам нужно установить следующий указатель foo, чтобы он указывал на goo.Вы не устанавливаете current->next, если только после удаления current не станет последним элементом.

Из-за этого освобожденная память все еще присутствовала в вашем списке, и вы прочитаете ее позже.Это неопределенное поведение, но, как вы видели, память может быть использована не сразу.

Answer 3

current->next = malloc(sizeof(node));

должно быть текущим-> следующее = calloc (1, sizeof (узел));/ * потому что безопасный тест NULL для -> следующий!* /

void newnode(node *n, int x, int y)
{
    n->key = malloc(x*sizeof(char));
    n->value = malloc(y*sizeof(char)); 
}

должно быть

void newnode(node *n, int x, int y)
{
    n->key = malloc(x+1); /* because x comes from strlen() and sizeof(char)==1 */
    n->value = malloc(y+1); /* because x comes from strlen() and sizeof(char)==1 */ 
}

Answer 4

Во-первых, вы не выделяете место для нуля в конце строк ...

Другая возможная проблема заключается в том, что вы должны убедиться, что вы инициализировали n->next = NULL;

И, наконец,

current = current->next->next;

должно быть

current->next = ...

Answer 5

current-> next = malloc (sizeof (node));

Я полагаю, вы имеете в виду sizeof (узел *)? Кроме того, я могу увидеть структуру, которую вы используете для определения узла? Или, может быть, вся программа?