使用單鏈表更新隊列adt中的尾指針時遇到問題

Question

我正在嘗試創建一個基於已經創建的鏈表庫的隊列庫。特別是我有麻煩更新隊列結構中的尾指針後，我添加一個新的節點到鏈接列表。

鏈表結構：

struct listNode { 
    int nodeLength; 
    int nodeValue; 
    struct listNode *next; 
}; 

typedef struct listNode node; 

隊列結構：

struct QueueRecord { 
    node *list; 
    node *front; 
    node *back; 
    int maxLen; 
}; 
typedef struct QueueRecord queue; 

所以這裏是在隊列庫

void add(queue currentQueue, int data){ 
    addTail(currentQueue.list, data, data+5); 
    currentQueue.back = currentQueue.back->next; 

} 

和addTail功能從鏈表我的附加功能圖書館

void addTail (node *head, int value, int length) { 
    node *current = head; 
    node *newNode = (struct listNode *)malloc(sizeof(node)); 
    newNode = initNode(value, length); 

    while (current->next != NULL) 
     current = current->next; 

    newNode->next = NULL; 
    current->next = newNode; 
} 

所以我的問題是再次我的問題是尾巴指針沒有被設置到列表中的最後一個節點。它與頭指針保持在相同的位置。我一直在研究這個好幾個小時，試圖看看我是否僅僅缺少一些小東西，但是我無法找到它。如果需要更多的代碼或解釋來理解我可以提供的問題。

如何創建隊列：

queue createQueue(int maxLen){ 
    queue newQueue; 
    newQueue.list = createList(); 
    newQueue.front = newQueue.list; 
    newQueue.back = newQueue.list; 
    newQueue.maxLen = maxLen; 
    return newQueue; 
}  

node *createList(){ 
    node *head = NULL; 
    head = (struct listNode *)malloc(sizeof(node)); 
    head->next = NULL; 
    return head; 
} 

node *initNode (int value, int length){ 
    node *newNode = NULL; 
    newNode = (struct listNode *)malloc(sizeof(node)); 
    newNode->nodeValue = value; 
    newNode->nodeLength = length; 
    newNode->next = NULL; 
    return newNode; 
} 

Answer 1

void add(queue currentQueue, int data){ 

您傳遞queue結構的副本到add，所以只有副本的成員都改變了。您需要將queue*傳遞給函數以便能夠更改queue本身的成員。

void add(queue *currentQueue, int data){ 
    if (currentQueue == NULL) { 
     exit(EXIT_FAILURE); 
    } 
    addTail(currentQueue->list, data, data+5); 
    currentQueue->back = currentQueue->back->next; 
} 

，並把它作爲add(&your_queue);

在你addTail功能，你應該檢查head是否NULL了。

而且隨着

node *newNode = (struct listNode *)malloc(sizeof(node)); 
newNode = initNode(value, length); 

在 addTail

，你有一個嚴重的問題。在分配newNode = initNode(value, length);時，您正在失去對只有malloc ed內存的引用。

如果initNodemalloc S的內存新的塊體，它的「公正」的內存泄漏，那麼你應該在addTail刪除malloc。

否則，我擔心initNode返回一個局部變量的地址，點菜

node * initNode(int val, int len) { 
    node new; 
    new.nodeValue = val; 
    new.nodeLength = len; 
    new.next = NULL; 
    return &new; 
} 

如果initNode看起來相似，因爲地址只要在函數返回失效會導致一個問題。但是如果initNode看起來像這樣，你的編譯器應該已經警告過你。

無論如何，沒有看到initNode的代碼，我無法診斷原因。

但是，如果你改變你的addTail到

void addTail (node *head, int value, int length) { 
    if (head == NULL) { // violation of contract, die loud 
     exit(EXIT_FAILURE); 
    } 
    node *current = head; 
    node *newNode = malloc(sizeof(node)); 
    if (newNode == NULL) { 
     exit(EXIT_FAILURE); // or handle gracefully if possible 
    } 
    newNode->nodeValue = value; 
    newNode->nodeLength = length; 
    newNode->next = NULL; 

    while (current->next != NULL) 
     current = current->next; 

    current->next = newNode; 
} 

它應該工作。

不過，既然你有一個指針到第一，並在列表中的最後一個節點，那將是更有效地使用了back指針追加一個新的節點，

void add(queue *currentQueue, int data){ 
    node *newNode = malloc(sizeof *newNode); 
    if (newNode == NULL) { 
     exit(EXIT_FAILURE); // or handle gracefully if possible 
    } 
    newNode->nodeValue = data; 
    newNode->nodeLength = data+5; 
    newNode->next = NULL; 
    currentQueue->back->next = newNode; 
    currentQueue->back = newNode; 
} 

，因爲你不必遍歷整個列表找到結尾。

---

一個簡單的示例程序

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

struct listNode { 
    int nodeLength; 
    int nodeValue; 
    struct listNode *next; 
}; 

typedef struct listNode node; 

struct QueueRecord { 
    node *list; 
    node *front; 
    node *back; 
    int maxLen; 
}; 
typedef struct QueueRecord queue; 

node *createList(){ 
    node *head = NULL; 
    head = (struct listNode *)malloc(sizeof(node)); 
    head->next = NULL; 
    return head; 
} 

void addTail (node *head, int value, int length) { 
    if (head == NULL) { // violation of contract, die loud 
     exit(EXIT_FAILURE); 
    } 
    node *current = head; 
    node *newNode = malloc(sizeof(node)); 
    if (newNode == NULL) { 
     exit(EXIT_FAILURE); // or handle gracefully if possible 
    } 
    newNode->nodeValue = value; 
    newNode->nodeLength = length; 
    newNode->next = NULL; 

    while (current->next != NULL) 
     current = current->next; 

    current->next = newNode; 
} 

queue createQueue(int maxLen){ 
    queue newQueue; 
    newQueue.list = createList(); 
    newQueue.front = newQueue.list; 
    newQueue.back = newQueue.list; 
    newQueue.maxLen = maxLen; 
    return newQueue; 
} 

void add(queue *currentQueue, int data){ 
    if (currentQueue == NULL) { 
     exit(EXIT_FAILURE); 
    } 
    addTail(currentQueue->list, data, data+5); 
    currentQueue->back = currentQueue->back->next; 
} 

int main(void) { 
    queue myQ = createQueue(10); 
    for(int i = 1; i < 6; ++i) { 
     add(&myQ, i); 
     printf("list: %p\nfront: %p\nback: %p\n", 
       (void*)myQ.list, (void*)myQ.front, (void*)myQ.back); 
    } 
    node *curr = myQ.front->next; 
    while(curr) { 
     printf("Node %d %d, Back %d %d\n", curr->nodeValue, 
       curr->nodeLength, myQ.back->nodeValue, myQ.back->nodeLength); 
     curr = curr->next; 
    } 
    while(myQ.list) { 
     myQ.front = myQ.front->next; 
     free(myQ.list); 
     myQ.list = myQ.front; 
    } 
    return 0; 
} 

作品如預期，也與替代add實施。

Answer 2

我想你從來沒有初始化回來，所以back-> next是一些隨機指針？