Попытка вернуть строку из очереди в C/бесплатные проблемы

Question

Я некоторое время работал над лабораторией для класса CSC, и, к сожалению, я немного ржав с C (как вы, вероятно, заметите из код). Я сталкиваюсь с двумя конкретными проблемами, связанными с управлением памятью.

1) В операции dequeue я пытаюсь вернуть строковое значение из узла в конце очереди. Поскольку я также пытаюсь использовать free() и убивать этот узел после получения данных, мне нужно использовать метод strcpy() для захвата данных. Программа segfaults всякий раз, когда я пытаюсь использовать strcpy, и Valgrind утверждает недопустимый r/w.

2) dequeue также неправильно обновляет структуру stringQueue по причинам, которые я не могу понять. У меня есть аналогичный код для стеков, где изменения сохраняются, но я могу продолжать выполнять деактивацию весь день, и он фактически не удалит конечный узел.

Соответствующий код:

typedef struct node { 
    char data [strMax]; 
    struct node * next; 
} queueNode; 

typedef struct { 
    queueNode * head; 
    queueNode * tail; 
} stringQueue; 

char * dequeue(stringQueue *queue) { 
    char * data = malloc(strMax * sizeof(char)); 
    if(empty(*queue)) { 
    return "Null list!"; 
    } 
    else if(!(queue->head)->next) { // One item in the queue. 
    data = (queue->head)->data; 
    //free(queue->head); 
    queue->head = NULL; 
    queue->tail = NULL; 
    } 
    else { // Multiple items in the queue. 
    data = (queue->tail)->data; 
    free(queue->tail); 
    queueNode * trace = queue->head; 
    while(trace->next) // Seek the last node in the queue. 
     trace = trace->next; 
    queue->tail = trace; 
    } 
    return data; 
} 

Answer 1

Вы, вероятно, хотите, чтобы объявить data как char * = NULL на первом. Затем, когда вы хотите вернуть его, используйте data = asprintf("%s", (queue->tail)->data);. Это будет делать только распределение строк и копирование, когда это необходимо, и только необходимый размер. Тогда ваш код звонка должен взять на себя ответственность за освобождение этих данных.

В настоящее время у вас есть char[] в структуре узла в памяти кучи. Позже вы устанавливаете указатель на элемент структуры data, а затем освобождаете структуру в памяти. У вас остался «оборванный указатель», указывающий на то, где была структура. Попытка использовать этот указатель закончится почти определенной гибельностью (или, что еще хуже, непредсказуемым поведением).

Answer 2

Ваша основная проблема в таких строках, как data = (queue->head)->data;. Вы не можете назначить такой массив. вы должны memcpy. (strcpy для нулевых строк, и я думаю, что это не так)

Редактировать: вы также можете использовать strncpy, чтобы избежать переполнения буфера.

Answer 3

Я вижу несколько проблем с вашим кодом ...

Сначала вы не проверить, что ваш queue аргумент не NULL. Тогда вы не указали свое определение empty(), но, вероятно, тестирование того, что queue-> head равно NULL, должно сказать вам, что список пуст. Здесь вы разыгрываете его перед тестированием, это действительный указатель, очень опасный.

Во-вторых, вы mallocing некоторые данные, которые не используются должным образом. Когда вы делаете привязанность data = (queue->head)->next;, вы теряете указатель на выделенную память, вы, вероятно, захотите сделать strncpy() здесь, как strncpy(data, queue->head->data, strMax). После этого вы можете раскомментировать свой free(). Функция, вызывающая ваш dequeue, будет иметь значение free(), что строка позже, когда она больше не используется. Почему бы не выделить data только в том случае, если вы уверены, что список не пуст? Если вы не хотите этого делать, тогда вам нужно будет free(), что неосведомленная память malloc'ed.

См. Приведенный ниже код.

queueNode* find_before_tail(stringQueue* queue) 
{ 
    queueNode* node = NULL; 

    if (!queue || !queue->head) 
     return NULL; 

    node = queue->head; 
    while (node->next != queue->tail && node->next) 
     node = node->next; 

    return node; 
} 

char * dequeue(stringQueue *queue) { 
    char *data = NULL; 
    queueNode* to_queue = NULL; 

    if(!queue || !queue->head) { 
    /* Nothing to dequeue here... */ 
    return NULL; 
    } 

    data = malloc(strMax * sizeof(char)); 
    if (!data) { 
    printf("Error with malloc()...\n"); 
    return NULL; 
    } 

    /* Only one element */ 
    if(!(queue->head)->next == queue->head) { 
    strncpy(data, queue->head->data, strMax); 

    free(queue->head); 

    queue->head = NULL; 
    queue->tail = NULL; 
    } 
    else { 
    strncpy(data, queue->tail->data, strMax); 

    to_dequeue = queue->tail; 

    queue->head = queue->head->next; 

    queue->tail = find_before_tail(queue); 
    if (!queue->tail) 
     return NULL; 
    queue->tail->next = NULL; 

    free(to_dequeue); 
    } 

    data[strMax - 1] = 0; 

    return data; 
} 

Есть, вероятно, некоторые другие вопросы, с остальной частью кода, судя по этой одной, но, надеюсь, это дает некоторое основание.

EDIT С ВАШИМ ОЧЕРЕДИ КОД

Здесь вы снова не испытывая возвращаемое значение malloc(). Вот версия с нециклическим связанным списком (я также обновил функцию dequeue() выше, чтобы работать с этим).

int enqueue(stringQueue *queue, char *item) 
{ 
    queueNode * newNode = NULL; 

    if (!queue || !item) 
     return EINVAL; 

    newNode = malloc(sizeof(queueNode)); 
    if (!newNode) { 
     perror("malloc()"); 
     return errno; 
    } 

    strncpy(newNode->data, item, strMax); 
    newNode->data[strMax - 1] = 0; 

    if (!queue->head) { 
     /* Element is queue and tail */ 
     queue->tail = newNode; 
    } 

    newNode->next = queue->head; 
    queue->head = newNode; 

    return 0; /* Everything was fine */ 
} 

Я не тестировал код, но он должен быть очень похож на этот. В этом случае, когда у вас есть только один элемент, this_element->next - NULL и не указывая на себя.