数据结构（C语言） 队列的链式表示和实现

链队列

（a）空队列 （b）元素x入队列 （c）元素y入队列 （d）元素x出队列

队列的链式存储表示

//----单链队列----队列的链式存储结构 typedef struct QNode { QElemType data; struct QNode* next; }QNode, * QueuePtr; typedef struct { QueuePtr front;//队头指针 QueuePtr rear;//队尾指针 }LinkQueue;

基本操作的函数原型说明

//----基本操作的函数原型说明---- Status InitQueue(LinkQueue& Q); //构造一个空队列Q Status DestroyQueue(LinkQueue& Q); //销毁队列Q，Q不再存在 //将Q清为空队列 Status GetHead(LinkQueue Q, QElemType& e); //若队列不空，则用e返回Q的对头元素，并返回OK;否则返回ERROR Status EnQueue(LinkQueue& Q, QElemType e); //插入元素e为Q的新的队列元素 Status DeQueue(LinkQueue& Q, QElemType& e); //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK //否则返回ERROR void PrintQueue(LinkQueue Q); //打印队列

基本操作的实现

Status InitQueue(LinkQueue& Q) { //构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit(OVERFLOW);//分配存储失败 Q.front->next = NULL; return OK; }//InitQueue Status DestroyQueue(LinkQueue& Q) { //销毁队列Q while (Q.front) { Q.rear = Q.front->next; free(Q.front); Q.front = Q.rear; } return OK; } Status GetHead(LinkQueue Q, QElemType& e) { if (Q.front == Q.rear) return ERROR; e = Q.front->next->data; return OK; } Status EnQueue(LinkQueue& Q, QElemType e) { //插入元素e为Q的新的队尾元素 QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } Status DeQueue(LinkQueue& Q, QElemType& e) { //若队列不空，则删除Q的对头元素，用e返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR; QueuePtr p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free(p); return OK; } void PrintQueue(LinkQueue Q) { printf("队列值为："); QueuePtr p = Q.front; while (p->next != NULL) { printf("%d ",p->next->data); p = p->next; } printf("\n"); }

完整代码

#include<stdio.h> #include<stdlib.h> #define TRUE 1 #define FALSE 0 #define OK 1 #define ERROR 0 #define INFEASIBLE -1 #define OVERFLOW -2 //Status是函数的类型，其值是函数结果状态代码 typedef int Status; typedef int QElemType; //----单链队列----队列的链式存储结构 typedef struct QNode { QElemType data; struct QNode* next; }QNode, * QueuePtr; typedef struct { QueuePtr front;//队头指针 QueuePtr rear;//队尾指针 }LinkQueue; //----基本操作的函数原型说明---- Status InitQueue(LinkQueue& Q); //构造一个空队列Q Status DestroyQueue(LinkQueue& Q); //销毁队列Q，Q不再存在 //将Q清为空队列 Status GetHead(LinkQueue Q, QElemType& e); //若队列不空，则用e返回Q的对头元素，并返回OK;否则返回ERROR Status EnQueue(LinkQueue& Q, QElemType e); //插入元素e为Q的新的队列元素 Status DeQueue(LinkQueue& Q, QElemType& e); //若队列不空，则删除Q的队头元素，用e返回其值，并返回OK //否则返回ERROR void PrintQueue(LinkQueue Q); //打印队列 //----基本操作的算法描述---- Status InitQueue(LinkQueue& Q) { //构造一个空队列Q Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode)); if (!Q.front) exit(OVERFLOW);//分配存储失败 Q.front->next = NULL; return OK; }//InitQueue Status DestroyQueue(LinkQueue& Q) { //销毁队列Q while (Q.front) { Q.rear = Q.front->next; free(Q.front); Q.front = Q.rear; } return OK; } Status GetHead(LinkQueue Q, QElemType& e) { if (Q.front == Q.rear) return ERROR; e = Q.front->next->data; return OK; } Status EnQueue(LinkQueue& Q, QElemType e) { //插入元素e为Q的新的队尾元素 QueuePtr p = (QueuePtr)malloc(sizeof(QNode)); if (!p) exit(OVERFLOW); p->data = e; p->next = NULL; Q.rear->next = p; Q.rear = p; return OK; } Status DeQueue(LinkQueue& Q, QElemType& e) { //若队列不空，则删除Q的对头元素，用e返回其值，并返回OK；否则返回ERROR if (Q.front == Q.rear) return ERROR; QueuePtr p = Q.front->next; e = p->data; Q.front->next = p->next; if (Q.rear == p) Q.rear = Q.front; free(p); return OK; } void PrintQueue(LinkQueue Q) { printf("队列值为："); QueuePtr p = Q.front; while (p->next != NULL) { printf("%d ",p->next->data); p = p->next; } printf("\n"); } int main() { LinkQueue Q; InitQueue(Q); EnQueue(Q, 1); EnQueue(Q, 2); EnQueue(Q, 3); PrintQueue(Q); return 0; }