/************************************链队列的主要知识点************************************** 链队列其实是线性表的单链表,只不过只能尾进头出。 队头指针front指向链表的头结点,队尾指针rear指向链表的终端结点。 空队列是,队尾指针和队头指针都指向头结点。 ***********************************************************************************************/ #include "declear.h" #include <stdio.h> #include <stdlib.h> #include "math.h" typedef struct QNode { QElemType data; struct QNode *next; }QNode, *QueuePtr; typedef struct { QueuePtr front; QueuePtr rear; }LinkQueue; Status InitQueue(LinkQueue *Q) { Q->front = Q->rear = (QueuePtr)malloc(sizeof(QNode)); if(!Q->front) { exit(OVERFLOW); } Q->rear = NULL; return OK; } int LengthQue(LinkQueue Q) { int len = 0; QueuePtr tem; tem = Q.front; while(tem != Q.rear) { tem = tem->next; ++len; } return len; } Status DestroyQue(LinkQueue *Q) { QueuePtr tem; while (Q->front) { tem = Q->front; Q->front = Q->front->next; free(tem); } return OK; } Status ClearQueue(LinkQueue *Q) { QueuePtr tem; tem = Q->front->next; while (!(Q->front->next)) { tem = Q->front->next; Q->front->next = Q->front->next->next; free(tem); } Q->rear = Q->front; Q->front->next = NULL; return OK; } Status InsertQueue(LinkQueue *Q, QElemType elem) { QueuePtr tem; tem = (QueuePtr)malloc(sizeof (QNode)); if(!tem) //分配内存失败退出。 { exit(OVERFLOW); } tem->data = elem; tem->next = NULL; Q->rear->next = tem; //在尾部插入元素 Q->rear = Q->rear->next; //更新尾部指针 return OK; } Status DeleteQueue(LinkQueue *Q) { QueuePtr p; if(Q->rear == Q->front) { return ERROR; } p = Q->front->next; Q->front->next = p->next; //修改front指向,使其指示Q->front->next->next if (p->next == Q->rear) //如果*Q只有一个结点,即Q->front->next == Q->rear,则给Q->rear赋值 { Q->rear = Q->front; } free(p); return OK; } int main () { LinkQueue linkQue; Status s; s = InitQueue (&linkQue); if(s) { printf("成功地构造了一个空队列!\n"); printf("是否成功清除队列?%d(1:是 0:否) \n",ClearQueue(&linkQue)); printf("队列的长度为%d\n",LengthQue(linkQue)); InsertQueue(&linkQue, 22); InsertQueue(&linkQue, 3); InsertQueue(&linkQue, 3); InsertQueue(&linkQue, 3); InsertQueue(&linkQue, 3); DeleteQueue(&linkQue); printf("队列的长度为%d\n",LengthQue(linkQue)); } return 0; }