Освобождение памяти в C: Очередь

Question

void insert_queue (queue *this, queue_item_t item) { 

    //Inserts a new item at the end of queue. 
    queue_node *temp = malloc(sizeof (struct queue_node)); 
    temp->item = item; 

    if (isempty_queue(this)) this->front = temp; 
    else this->rear->link = temp; 
    this->rear = temp; 
    //free(temp); 
} 

queue_item_t remove_queue (queue *this) { 
    assert (! isempty_queue (this)); 
    //This removes the first item from queue. 
    queue_item_t temp = this->front->item; 
    this->front = this->front->link; 
    return temp; 
} 

У меня возникает ошибка сбоя seg, когда я пытаюсь освободить «temp». Я должен освободить узел после его использования, не так ли? Итак, как я могу предотвратить утечку памяти в этой ситуации? Есть идеи? Спасибо.

Когда я удаляю бесплатный (темп), все работает нормально, но я получаю утечки памяти. Я не уверен, куда положить бесплатно, если он не принадлежит этой функции. Я также добавил функцию удаления. Должен ли свободен войти сюда?

EDIT EDIT: Спасибо всем, вот мой обновленный код.

queue_item_t remove_queue (queue *this) { 
    assert (! isempty_queue (this)); 

    queue_node *temp = this->front; 
    queue_item_t rVal = temp->item; 

    //Moves on to the next one. 
    this->front = this->front->link; 
    //Free the unlinked node. 
    //free(temp->item); <<<<---- This causes program to fail. 
    free(temp); 
    return rVal; 
} 

Утечки памяти все еще встречаются.

Answer 1

Вы не закончили работу с узлом, когда insert_queue отделки. В методе insert_queue используется temp, чтобы удерживать указатель на узел, а insert_queue выполняется с использованием temp, когда он возвращается, но сам узел является частью связанного списка, поэтому он используется.

Вы завершаете использование узла, когда remove_queue удаляет его из списка. remove_queue должен передать указатель на узел до free, чтобы освободить его память.

Не думайте о temp как о узле. Это только объект, который временно удерживает указатель на узел. Сам узел - это отдельная вещь.

Answer 2

Ну, если вы создаете и вставляете новую очередь, зачем вы хотите ее удалить? Помните, что при использовании malloc() вы резервируете некоторые данные независимо от того блока, в котором находитесь. Free() - это то, что вы используете для уничтожения этой памяти, созданной с помощью malloc(). Все локально локализованные (не созданные с malloc) данные/переменные автоматически будут уничтожены в конце их уважаемых блоков. Данные, созданные с помощью malloc(), будут (в большинстве случаев) не такими.

void insert_queue (queue *this, queue_item_t item) 
{ 
    //Inserts a new item at the end of queue. 
    queue_node *temp = malloc(sizeof (struct queue_node)); 
    temp->item = item; 

    if (isempty_queue(this)) 
     this->front = temp; 
    else 
     this->rear->link = temp; 
    this->rear = temp; 
    //free(temp); // remember tmp is still referring to 
           // the node, so you will be erasing the 
           // node you just put inside the queue. 

}  // end of code block. Variable *temp will be 
     // automatically freed from memory, but 
     // its malloc'd data will not. This is good 
     // because its data is being used inside our 
     // queue, until it is removed with remove_queue(). 

Позже внутри функции Удалить можно удалить «Темп» (на самом деле его памяти, выделенной с помощью таНос()) с использованием бесплатно. Или вы можете использовать free (remove_queue (& myq)), и это даст тот же результат, потому что мы имеем дело с указателями.

Answer 3

Прежде всего, «это» означает ключевое слово в C++. Вы не должны использовать его в c-контексте, если вы спросите меня - просто чтобы избежать недоразумений.

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

Следующий элемент queue_item_t выделяется в стеке здесь как копия исходного значения, так как я не вижу, что это указатель, отправленный в выделенной для него памяти, будет удален при закрытии}.

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

Последний комментарий, выбор возврата и переход по значению без параметра ok, или вы столкнетесь с проблемами, когда вы не можете вернуть копию (см. Мой пример для размера == 0), и нет никакого способа сообщить пользователю функции, что-то пошло не так (очередь пуста, в данном случае)

Вот мой (быстро изготовлен и испытан) минимальное решение для вашей проблемы:

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

struct queue_item_t 
{ 
    int exampleItemData; 
}; 

struct queue_node 
{ 
    struct queue_item_t *item; 
    struct queue_node *next; 
}; 

struct queue 
{ 
    struct queue_node *firstItem; 
    struct queue_node *lastItem; 
    int size; 
}; 


struct queue* createQueue() 
{ 
    struct queue *queuePtr = (struct queue *)malloc(sizeof (struct queue)); 
    queuePtr->firstItem = NULL; 
    queuePtr->lastItem = NULL; 
    queuePtr->size = 0; 
    return queuePtr; 
} 

void queue(struct queue* queueData, struct queue_item_t itemToQueue) 
{ 
    // Create new node 
    struct queue_node* newNode = (struct queue_node*)malloc(sizeof(struct queue_node)); 

    // Create new item 
    newNode->item = (struct queue_item_t*)malloc(sizeof(struct queue_item_t)); 

    // Copy the item data from itemToQueue that will be deleted on the end of this function 
    newNode->item->exampleItemData = itemToQueue.exampleItemData; 

    // Insert the item into the queue 
    if(0 == queueData->size) 
    { 
     queueData->firstItem = newNode; 
     queueData->lastItem = newNode; 
     newNode->next = newNode; 
    } 
    else 
    { 
     queueData->lastItem->next = newNode; 
     queueData->lastItem = newNode; 
    } 

    queueData->size += 1; 

    // ! itemToQueue will deleted here we must have a copy of the data in the queue } 
} 

struct queue_item_t dequeue(struct queue* queueData) 
{ 
    struct queue_item_t item; 

    if (1 > queueData->size) 
    { 
     // !!! Serious problem if this happens: 
     // What will you return, an initialized queue_item_t? 
     // You can not return a null pointer ... 
     // Better you write ok to a boolean comming in ass parameter or something 
    } 
    else if(1 == queueData->size) 
    { 
     item.exampleItemData = queueData->firstItem->item->exampleItemData; 

     free(queueData->firstItem->item); 
     free(queueData->firstItem); 
     queueData->firstItem = NULL; 
     queueData->lastItem = NULL; 
    } 
    else if(2 == queueData->size) 
    { 
     item.exampleItemData = queueData->firstItem->item->exampleItemData; 

     struct queue_node* dequeuedNode = queueData->firstItem; 
     queueData->firstItem = dequeuedNode->next; 
     queueData->lastItem = dequeuedNode->next; 
     free(dequeuedNode->item); 
     free(dequeuedNode); 
    } 
    else if (1 < queueData->size) 
    { 
     item.exampleItemData = queueData->firstItem->item->exampleItemData; 

     struct queue_node* dequeuedNode = queueData->firstItem; 
     queueData->firstItem = dequeuedNode->next; 
     free(dequeuedNode->item); 
     free(dequeuedNode); 
    } 

    queueData->size -= 1; 

    return item; 
} 


int main() { 
    struct queue* myQueue = createQueue(); 
    struct queue_item_t item; 
    item.exampleItemData = 665; 
    queue(myQueue, item); 

    item.exampleItemData = 666; 
    queue(myQueue, item); 

    item.exampleItemData = 667; 
    queue(myQueue, item); 

    for(int i = myQueue->size; i > 0; --i) 
    { 
     struct queue_item_t dequeuedItem = dequeue(myQueue); 
     printf("Dequed ITem data = %i\n", dequeuedItem.exampleItemData); 
    } 

    // Now the next shows an undefined state if someone dequeues with size 0 or smaller: 
    struct queue_item_t dequeuedItem = dequeue(myQueue); 
    printf("Dequed ITem data = %i\n", dequeuedItem.exampleItemData); 

    // I recommend using a boolean like mentioned above 

    return 0; 
}