鏈表的隊列，無端環

我使用嵌套結構來定義鏈表的隊列：鏈表的隊列，無端環

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; 
    }

，但是當我在主程序中使用它，那麼它跳轉到無盡的循環，回溯後，我知道p roblem是：

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

，但它似乎是正確的，但我可以讓我的兩個嵌套結構的初始化一些錯誤！

P.S.我沒有列出「免費（）」。

來源

2013-11-09 hyaocuk

相關：一個隊列通常有一個前/頭和尾/後。理想情況下，它也有一個長度，以消除計算長度的O（n）操作的需要（這是您的主要bug的核心，順便說一下）。 – WhozCraig

尾指針會使插入O（1）而不是O（n）。如果這個隊列比幾個條目長，這將是主要的瓶頸。 –

你的代碼的一個問題是你的迭代通過隊列是破壞性的：而不是使用臨時變量迭代你的鏈表，你使用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; 
}

你決定預分配創建隊列時，一個節點也值得懷疑：它似乎頭節點未被使用，也被排除在計數之外。這使編寫插入和刪除節點的代碼變得更容易，但是可以通過額外的間接級別（即指向指針的指針）完成相同的操作。

來源

2013-11-09 09:25:02 dasblinkenlight

現在它可以正確地遍歷，但計數將會減少一個...... –

@JoeZ不是真的 - 它看起來像是該節點故意插入，並且不應該計數。 – dasblinkenlight

啊，是的，我現在明白了。很多關於原創的非慣用的東西。 –

該循環修改了列表在遍歷時的列表。具體來說，它用q->q_node->next代替q->q_node，如果沒有其他東西會丟棄整個循環。

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 */

來源

2013-11-09 09:26:05

鏈表的隊列，無端環

回答

相關問題