0

我正在尝试建立一个简单的队列，但我被卡住了。我将用数据结构解释它

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");

}

这是一个先进先出队列。所以当 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;
}

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

--------ENQUEUE-------- Location(x=1|y=0) ==next==>

--------ENQUEUE-------- Location(x=2|y=0) ==next==> Location(x=2|y=0) ==next==>

--------ENQUEUE-------- Location(x=3|y=0) ==next==> Location(x=3|y=0) ==next==> Location (x=3|y=0) ==下一个==>

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

4

1 回答 1

1

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

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

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

一旦enqueue()返回，newEntry就不再存在，并且当您尝试取消引用任何指向newEntry.

于 2013-06-29T19:25:51.077 回答