c - 指针不会显示到队列中的下一个条目

Question

我正在尝试构建一个简单的队列，但我陷入困境。我会用数据结构来解释它

typedef struct location_tag {
    int x;
    int y;
} Location;

typedef struct QueueNode{
    struct QueueNode *next;
    Location location;
}QueueNode;

typedef struct Queue{
    struct QueueNode *begin;
    struct QueueNode *end;
    int size;
}Queue;

队列将保存一个指向其中第一个和最后一个元素的指针。每个节点都知道它是下一个。现在我实现了入队/出队操作:

void enqueue(Location l, Queue *q) {
    printf("--------ENQUEUE--------\n");
    QueueNode newEntry = { NULL, l };

    if (q->size == 0) {
        q->end = &newEntry;
        q->begin = &newEntry;
    } else {
        newEntry.next = q->begin;
        q->begin = &newEntry;
    }

    q->size++;
    printQueue(q);
}

QueueNode* dequeue(Queue *q) {
    printf("--------DEQUEUE--------\n");
    QueueNode* node = q->end;
    q->size--;

    QueueNode *currentNode = q->begin;
    for (int z = 1; z < q->size; ++z) {
        currentNode = currentNode->next;
    }
    q->end = currentNode;
    printQueue(q);

    return node;
}

void printQueue(Queue* q) {
    QueueNode *currentNode = q->begin;

    for (int z = 0; z < q->size; ++z) {
        printf("Location(x=%d|y=%d) ==next==> ", currentNode->location.x,
                currentNode->location.y);
        currentNode = currentNode->next;
    }
    printf("\n\n");

}

这是一个 FIFO 队列。因此，当调用 dequeue 时，第一个条目将是第一个条目。这是一些主要的测试。

int main(void){
    Queue queue = { NULL, NULL, 0 };
    queuePtr = &queue;

    Location l1 = { 1, 0 };
    Location l2 = { 2, 0 };
    Location l3 = { 3, 0 };
    enqueue(l1, queuePtr);
    enqueue(l2, queuePtr);
    enqueue(l3, queuePtr);

    while (queue.size != 0) {
        nodePtr = dequeue(queuePtr);
    }
return 0;
}

问题是什么？当我将新条目放入队列时，指向下一个元素的指针将指向节点本身。下面是一个示例输出:

--------入队--------位置(x=1|y=0) ==下一个==>

--------入队--------位置(x=2|y=0) ==下一个==> 位置(x=2|y=0) ==下一个==>

--------入队--------位置(x=3|y=0) ==下一个==> 位置(x=3|y=0) ==下一个==> 位置(x=3|y=0) ==下一个==>

我不明白这种行为。我想这是错误的 newEntry.next = q->begin); ？也许你可以帮助我。谢谢。

Answer 1

主要问题是 newEntry 存在于堆栈中:

void enqueue(Location l, Queue *q) {
    printf("--------ENQUEUE--------\n");
    QueueNode newEntry = { NULL, l };

    if (q->size == 0) {
        q->end = &newEntry;
        ...

一旦 enqueue() 返回，newEntry 将不再存在，您将拥有 undefined behaviour当您尝试取消引用任何指向 newEntry 的指针时。