связанного списка очереди, бесконечный цикл

Question

Я использую вложенную структуру для определения очереди связного списка:

queue.h:

#define QUEUE_MAX_SIZE 4096 

struct QUEUE_NODE { 
    char *string; 
    struct QUEUE_NODE *next; 
}queue_node; 

struct COMMON_QUEUE { 
    struct QUEUE_NODE *q_node; 
}common_queue; 

============= ====================

queue.c:

/* here I define the operations */ 
struct COMMON_QUEUE *C_init_queue() { 
    struct QUEUE_NODE *head; 
    head = malloc(sizeof(struct QUEUE_NODE)); 
    if (head==NULL) { 
    fprintf(stderr, "Insufficient memory!!!"); 
    return NULL; 
    } 
    struct COMMON_QUEUE *new_queue; 
    new_queue = malloc(sizeof(struct COMMON_QUEUE)); 
    if (new_queue==NULL) { 
    fprintf(stderr, "Insufficient memory!!!"); 
    return NULL; 
    } 
    head->next = NULL; 
    head->string = NULL; 

    new_queue->q_node = head; 

    return new_queue; 
} 

int C_get_queue_length(struct COMMON_QUEUE *q) { 
    int count; 
    count = 0; 

    while (q->q_node->next!=NULL) { 
    count += 1; 
    q->q_node = q->q_node->next; 
    } 

    return count; 
} 

int C_enqueue(struct COMMON_QUEUE *q, char *in) { 
    if (C_get_queue_length(q)>=QUEUE_MAX_SIZE) { 
    fprintf(stderr, "Linked queue is full!!!"); 
    return ERROR; 
    } 
    struct QUEUE_NODE *new_node; 
    new_node = malloc(sizeof(struct QUEUE_NODE)); 
    if (new_node==NULL) { 
    return ERROR; 
    } 
    new_node->next = NULL; 
    new_node->string = NULL; 

    while (q->q_node->next!=NULL) { 
    q->q_node = q->q_node->next; 
    } 
    new_node->next = q->q_node->next; 
    q->q_node->next = q->q_node; 
    new_node->string = in; 

    return OK; 
    } 

, но когда я использую его в основной программе, то он прыгает в бесконечный цикл, после backtracing, и я знал, что p РОБЛЕМА находится по адресу:

while (q->q_node->next!=NULL) { 
    count += 1; 
    q->q_node = q->q_node->next; 
} 

но это кажется правильным, но я могу сделать некоторые ошибки в моей инициализации двух вложенной структуры!

P.S. я не перечислял «free()».

Answer 1

Одна из проблем с вашим кодом заключается в том, что ваши итерации через очередь являются деструктивными: вместо использования временной переменной для итерирования связанного списка вы выполняете итерацию, используя сам q_node. Это приводит к тому, что вызовы C_get_queue_length эффективно уничтожают очередь, не освобождая ее узлы (утечка памяти).

Вот пример того, как перебрать список неразрушающим, используя ваш «получить длину» метод:

int C_get_queue_length(struct COMMON_QUEUE *q) { 
    int count; 
    count = 0; 
    struct QUEUE_NODE node = q->q_node; 
    while (node->next != NULL) { 
     count++; 
     node = node->next; 
    } 

    return count; 
} 

Ваше решение предварительно выделить один узел при создании очереди также под вопросом: она что головной узел не используется, а также исключен из счета. Это упрощает запись кода для вставки и удаления узлов, но то же самое можно сделать с дополнительным уровнем косвенности (т. Е. Указателем на указатель).

Answer 2

Этот цикл изменяет список, пока он пересекает его. В частности, он заменяет q->q_nodeq->q_node->next, который, если ничто иное не отбросит весь цикл.

while (q->q_node->next!=NULL) { 
    count += 1; 
    q->q_node = q->q_node->next; 
} 

Если вы хотите, чтобы правильно пройти этот список, вам нужно объявить отдельный указатель, который используется для обхода. Что-то вроде этого:

int C_get_queue_length(struct COMMON_QUEUE *q) { 
    int count; 
    struct COMMON_QUEUE *p = q->q_node; 
    count = 0; 

    while (p->next != NULL) { 
     count += 1; 
     p = p->next; 
    } 

    return count; 
} 

Указатель p шагнет по списку, не изменяя q_node указатели вдоль пути.

Аналогичная ошибка с номером C_enqueue. Вы действительно хотите использовать отдельный указатель для просмотра списка и не назначать q->q_node во время обхода. Вы можете исправить свой C_enqueue аналогичным образом:

p = q->q_node; 
while (p->next != NULL) { 
    p = p->next; 
} 
p->next = new_node;  /* append the new node after where the list traversal stopped */ 
new_node->next = NULL; /* always NULL, because you always insert at the end */