数据结构队列的链式表示与实现

Question

#include<stdio.h>
#include<stdlib.h>
#define OK 1
#define ERROR 0
#define N 100
typedef int Status;
typedef int ElemType;
typedef struct QNode{
    ElemType data;
    struct QNode *next;
}QNode,* QueuePtr;
typedef struct{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;
Status Init_Sq(LinkQueue &Q){
    Q.front=Q.rear=(QNode *)malloc(sizeof(QNode));
    Q.front->next=NULL;
    return OK;
}
Status Inser_Sq(LinkQueue &Q,ElemType e){
    QNode *p;
    p=new QNode;
    p->data=e;
    p->next=NULL;
    Q.rear->next=p;
    Q.rear=p;
    return OK;
}
ElemType Pop_Sq(LinkQueue &Q){
    if(Q.front==Q.rear) return ERROR;
    ElemType e=Q.front->next->data; 
    Q.front->next=Q.front->next->next;
    if(Q.rear==Q.front->next) Q.rear=Q.front;
    return e;
}
int main(){
    LinkQueue Q;
    Init_Sq(Q);
    Inser_Sq(Q,4);
    Inser_Sq(Q,1);
    Inser_Sq(Q,2);
    ElemType e=Pop_Sq(Q);
    printf("%d\n",e);
        ElemType e1=Pop_Sq(Q);
    printf("%d\n",e1);
        ElemType e2=Pop_Sq(Q);
    printf("%d\n",e2);
}

为什么这样不对，输出是4（换行）1（换行）0

Answer 1

在你的代码中，问题出现在 Pop_Sq 函数的实现上。具体来说，这里的条件判断可能导致错误：

if(Q.front==Q.rear) return ERROR;

在你的实现中，Q.front 指向头结点，而 Q.rear 指向最后一个元素，当队列为空时，它们指向同一个结点。因此，这个条件判断在空队列时可能不正确。

为了解决这个问题，你可以修改条件判断，以检查 Q.front->next 是否为空来判断队列是否为空。请修改 Pop_Sq 函数如下：

ElemType Pop_Sq(LinkQueue &Q){
    if(Q.front->next == NULL) return ERROR; // 判断队列是否为空
    ElemType e = Q.front->next->data; 
    Q.front->next = Q.front->next->next;
    if(Q.rear == Q.front->next) Q.rear = Q.front;
    return e;
}

这样修改后，再运行你的程序，应该可以得到正确的输出。