Освобождение узла в связанном списке

Question

Я выполняю какое-то упражнение со связанными списками на C. И столкнулся с проблемой указателя. Я пытаюсь реализовать функцию RemoveListByIndex (list, index). И пока я этот код. Функция

void RemoveNodeByIndex(struct node** head,int index) // NOT WORKING YET 
{ 
    // Remove node list 
    struct node* current = GetNodeByIndex(*(&head), index); 
    struct node* prev = GetNodeByIndex(*(&head), index-1); 

    // For debugging 
    PrintHRLine(); 
    printf("Deleting item %d from list.\n", index); 
    printf("Item %d data = %d\n", index, current->data); 
    PrintHRLine(); 
    // Change link from prev link node to the next 
    prev->link = current->link; 

    // Unlink node wished to delete 
    current->link = NULL; 
    current->data = 0; 

    // Free data 
    free((struct node*) current); 
} 

GetNodeByIndex:

struct node* GetNodeByIndex(struct node** list, int index) 
{ 
    // Return node by an index given 
    // if error it returns NULL 
    // for i < index 
    //  next_node <- node.link 
    //  node <- next.node 
    // return next_node 

    struct node* current = *list; 
    int counter = 0; 

    if (current) 
    { 
     while (current->link != NULL) 
    { 
     if (counter == index) 
     return current; 

     current = current->link; 
     counter++; 
    } 
    } 
    else 
    { 
     return NULL; 
    } 

    return NULL; 
} 

мой список структурирована следующим образом:

struct node 
{ 
    int data; 
    struct node* link; 
}; 

И я вызываю функцию из моего основного кода, как это:

int main() 
{ 
    struct node* head = NULL; 
    struct node* edit_node = NULL; 

    int i; 
    edit_node = (struct node*)malloc(sizeof(struct node)); 

    // Create a list of 10 elements 
    for (i = 0; i < SIZE_OF_LIST; i++) 
    { 
     struct node* item = (struct node*) malloc(sizeof(struct node)); 
     item->data = i; 
     if (i==0) 
     head = item; 
     printf("(item+%d)->data = %d\n",i,i); 
     if (i<SIZE_OF_LIST-1) 
    { 
     item->link = (item+i+1); 
     printf("(item+%d->link = (item+%d+1);\n", i, i); 
     printf("(item+%d adress = 0x%lx\n",i, (unsigned long int) &item+i); 
    } 
     else 
    { 
     item->link = NULL; 
     printf("(item+%d->link = NULL;\n", i); 
    } 
} 

    // RemoveNodeByIndex(head, 5); 
    // PrintListData(&head); 
    edit_node->data = 1001; 
    AddLastNode(&head, &edit_node); 
    SearchNode(&head, 101); 
    RemoveNodeByIndex(&head, 8); 
    PrintListData(&head); 

    // Free memory 
    free(item); 
    free(edit_node); 
    free(head); 

    return 0; 
} 

Кажется, все кажется f ine, за исключением того, что когда я получаю вызов free(). он не работает. выхода:

=================================== 
Deleting item 8 from list. Located : 0x7fffd20ecad0 
Item 8 data = 6 
=================================== 
*** Error in `./a.out': double free or corruption (out): 0x00000000011b2090 *** 
Aborted (core dumped) 

У меня есть подозрение, что я обработка моего указателя какие-то образом неправильно. Но что я делаю неправильно?

EDIT: Я включил весь мой исходный код в следующей ссылке: SOURCE CODE И я включил весь вывод, сгенерированный программой здесь: OUTPUT

Спасибо, на заранее.

Answer 1

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

как страница человека для free() говорит

бесплатно() освобождает пространство памяти, на которую указывает PTR, которая должна была быть возвращена предыдущим вызовом таНос(), calloc() или перераспределить() , Другой - мудрый, или если free (ptr) уже был вызван до этого, происходит неопределенное поведение. Если ptr равно NULL, операция не выполняется.

Я думаю, что в вашем рен, указатель на current не выделяются malloc() или calloc(). сделав (*(head)+index);, вы указываете куда-то еще.

---

EDIT:

в вашем коде, вместо того, чтобы использовать item = (struct node*)malloc(sizeof(struct node) * 10);, попытайтесь выделить каждый node отдельно. Кроме того, при удалении n-го узла подход должен идти на n-1-й узел, получить указатель next [или link] и free().

---

EDIT 2:

Каким

struct node* current = GetNodeByIndex(*(&head), index); 
    struct node* prev = GetNodeByIndex(*(&head), index); 

current и prev такие же? Как вы думаете?

Answer 2

Вы пытаетесь удалить последний узел.

struct node * current = ((head) + index); это указывает на индекс + 1 узел, а не на индексный узел struct node prev = (* (head) + index-1); это указывает на индексный узел, а не индекс - 1.

Друзья, вы пытаетесь удалить часть памяти, выделенную malloc. который я не думаю, что это разрешено.

Попробуйте таНос каждый узел separtely вместо объединения 10 узлов в один таНос,

Answer 3

в функции «RemoveNodeByIndex», пожалуйста, проверьте строку ниже.

struct node* current = GetNodeByIndex(*(&head), index); 
struct node* prev = GetNodeByIndex(*(&head), index); 

Оба будут иметь один и тот же узел, и вы делаете NULL текущий узел и нет никакой связи сохраняется, если текущий узел удаляются. Это может привести к неопределенному поведению.

Answer 4

Ваш код пытается реализовать связанный список, где узлы хранятся в отдельном пуле узлов, items. У вас есть какие-то неправильные представления об этой реализации:

• Если размер пула фиксирован, должен быть только один распределением, а именно, что из 10 узлов для бассейна. Все остальные указатели - головка списка, текущий узел итератора, ссылки в узлах и временные рабочие узлы - должны быть указателями в существующую память.

• Потому что есть только одно распределение, в конце должно быть только одно free, а именно free(items). Указатели, переданные в free, должны быть такими же, что когда-то были возвращены с malloc. Рабочий стол h'list может меняться в зависимости от рабочих указателей; вы явно не можете их освободить.

• Когда вы говорите о показателях, вы говорите о двух разных понятиях здесь: индекс пункта, который является индексом узла в массиве items и индекс списка, который является индексом в списке с листом списка по индексу 0.

• Потому что items - это массив узлов, вы можете получить узел в индексе элемента с помощью items + item_ix. Это не работает для связанного списка. Преимуществом связанного списка является быстрая вставка и удаление. (Ну, это действительно для двусвязных списков.) Недостатком является медленный поиск узлов по индексу: вы должны начинать подсчет с головы и итерации по списку.

• Вы передаете головку списка своим функциям в качестве указателя на указатель на головной узел. Это необходимо только в том случае, если функция меняет список, например, когда он удаляет или добавляет узлы. Это необязательно, когда вы просто проверяете список, то есть когда вы просматриваете узлы или когда вы печатаете их; здесь указывается указатель на узел.

• Когда вы добавляете или удаляете узел, выделенная память items остается неизменной. Например, если ваш список пуст, то items содержит 10 узлов (данные которых произвольны) независимо. Вам нужен механизм, чтобы определить, используется ли узел в списке или нет. Это может быть дополнительная запись в struct node или может быть вспомогательным массивом.

• Вы создаете список в цикле в main. Лучшей реализацией будет предоставление дополнительной функции, которая добавляет узлы в список. Конечно, такая функция должна знать о пуле узлов, потому что ей нужно взять свои узлы из пула.

• В это время вы должны инкапсулировать всю логику списка в структуру. Вместо указателя на голову вы передаете указатель на структуру списка и внесите туда все изменения.

Ниже приведен пример реализации ниже, который не использует распределение в куче, а пул фиксированного размера в стеке. Код использует РЗЭ структуры данных:

• В узел s являются такими же, как и в вашем коде.

• Пул пул представляет собой пул фиксированных размеров узлов, который может быть создан в стеке, и который должен быть инициализирован равным нулю, чтобы нормально работать. Пул отслеживает доступные узлы с дополнительным массивом, used. Размер фиксированного пула определяется константой времени компиляции.

• содержит ссылку на головной узел списка и ссылку на пул. (Несколько списков могут совместно использовать пул, но тогда фиксируется максимальное общее количество узлов для этих списков.) Он также отслеживает размер, это необязательно, но легко сделать.

Код клиента в main получает доступ к этим структурам только через функцию после инициализации структур. Обратите внимание, как пул не может переполняться и как освободить узлы снова и снова.

#include <stdio.h> 
#include <stdlib.h> 

#define POOL_SIZE 10 

struct node {      /* List node */ 
    int data; 
    struct node *next; 
}; 

struct pool {      /* Fixed-size node pool */ 
    char used[POOL_SIZE];   /* used/free markers */ 
    struct node data[POOL_SIZE]; /* associated nodes */ 
}; 

struct list {      /* List structure */ 
    struct pool *pool;    /* Node pool reference */ 
    struct node *head; 
    struct node *tail; 
    int size; 
}; 



/* 
*  Find an unused node and return it. If there are no unused 
*  nodes in the pool, return NULL: 
*/ 
struct node *pool_new_node(struct pool *pool) 
{ 
    int i; 

    for (i = 0; i < POOL_SIZE; i++) { 
     if (pool->used[i] == 0) { 
      pool->used[i] = 1; 
      return pool->data + i; 
     } 
    } 

    return NULL; 
} 

/* 
*  Mark a node in the pool as unused, effectively freeing it. 
*  Return 0 on success, -1 on error. 
*/ 
int pool_free_node(struct pool *pool, struct node *node) 
{ 
    int i = node - pool->data; 

    if (i < 0 || i >= POOL_SIZE) return -1; 
    if (pool->used[i] == 0) return -1; 

    pool->used[i] = 0; 
    return 0; 
} 

/* 
*  Append an item with value x at the tail. 
*/ 
struct node *list_append(struct list *list, int x) 
{ 
    struct node *node = pool_new_node(list->pool); 

    if (node == NULL) return NULL; 

    node->next = NULL; 
    node->data = x; 

    if (list->tail) { 
     list->tail->next = node; 
    } else { 
     list->head = node; 
    } 
    list->tail = node;  
    list->size++; 

    return node; 
} 

/* 
*  Return ix'th node in list or NULL. 
*/ 
struct node *list_find_by_index(const struct list *list, int ix) 
{ 
    struct node *node = list->head; 

    if (ix < 0 || ix >= list->size) return NULL; 

    while (node) { 
     if (ix-- == 0) return node; 
     node = node->next; 
    } 

    return NULL;  
} 

/* 
*  Return first node with given data or NULL. 
*/ 
struct node *list_find_by_data(const struct list *list, int data) 
{ 
    struct node *node = list->head; 

    while (node) { 
     if (node->data == data) return node; 
     node = node->next; 
    } 

    return NULL; 
} 

/* 
*  Delete given node from list. 
*/ 
void list_delete_node(struct list *list, struct node *node) 
{ 
    if (node) { 
     struct node **iter = &list->head; 

     while (*iter) { 
      if (*iter == node) { 
       *iter = node->next; 
       pool_free_node(list->pool, node); 
       list->size--; 
       return; 
      } 
      iter = &(*iter)->next; 
     } 
    } 
} 

/* 
*  Delete node at index from list. 
*/ 
void list_delete_by_index(struct list *list, int ix) 
{ 
    struct node *node = list_find_by_index(list, ix); 

    if (node) list_delete_node(list, node); 
} 


/* 
*  Print the list items 
*/ 
void list_print(const struct list *list) 
{ 
    struct node *node = list->head; 

    printf("%d items: [", list->size); 
    while (node) { 
     if (node != list->head) printf(", "); 
     printf("%d", node->data); 
     node = node->next; 
    } 
    printf("]\n"); 
} 



/* 
*  Example client code 
*/ 
int main() 
{ 
    struct pool pool = {{0}}; 
    struct list list = {&pool}; 
    struct node *node; 

    int i; 

    for (i = 0; i < 12; i++) { 
     list_append(&list, i); 
     list_print(&list); 
    } 

    node = list_find_by_index(&list, 9); 
    if (node) node->data = 1001; 

    node = list_find_by_index(&list, 10); 
    if (node) node->data = 1001; 

    list_print(&list); 

    node = list_find_by_data(&list, 7); 
    if (node) node->data = 999; 

    list_print(&list); 

    list_delete_by_index(&list, 0); 
    list_delete_by_index(&list, 0); 
    list_delete_by_index(&list, 0);  
    list_delete_by_index(&list, 5); 

    list_print(&list); 

    for (i = -10; i < 0; i++) { 
     list_append(&list, i); 
     list_print(&list); 
    } 

    list_print(&list); 

    return 0; 
}