0

我正在尝试制作一个基于我已经制作的链表库的队列库。具体来说，在将新节点添加到链表后，我无法更新队列结构中的尾指针。

链表结构：

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

2 回答 2

2 
void add(queue currentQueue, int data){

您将struct的副本传递给，因此只有副本的成员被更改。您需要将 a 传递给函数才能更改其自身的成员。queueaddqueue*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你有一个严重的问题。使用 assignment newNode = initNode(value, length);，您将丢失对刚刚malloc编辑的内存的引用。

如果initNode malloc一个新的内存块，它“只是”一个内存泄漏，那么你应该删除mallocin addTail。

否则，我担心initNode返回局部变量的地址，à la

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实现。

于 2012-10-07T19:06:25.240 回答
0

我想你从来没有初始化回来，所以 back->next 是一些随机指针？

于 2012-10-07T19:09:17.407 回答