4.1、链式队列实现
4.1.1、链式队列说明
- 和单链表类似。链式队列即用一组任意的存储单元存储栈的数据元素。每个结点包括存放数据元素的数据域,和指示下一个队列结点的指针域。
- 对于队尾元素而言,由于其没有下一个结点,故队尾结点的指针域始终为 NULL ,其数据域存放最后一个入队的数据元素(头出尾入),由于元素通过队尾入队,附设一个队尾指针( rear )。
- 为了操作方便,这里给链队列添加一个头结点,并令头指针( front )指向头结点。链队列示意图如下图所示。
注:可将链式队列结构看成带头结点的单链表,将队头指针看成头指针,将单链表的头删看作出队,尾插看作入队。这样易于理解。
4.3.2、链队列的优缺点与适用场合
敬请期待
4.3.3、存储结构的定义与头文件声明
(1)存储结构的定义
- 根据上述分析,链队列结点包括数据域、指针域,以及一个存放队头指针、队尾指针的链队列类型。故,定义如下。
typedefstruct QNode//队列结点定义{
ElemType data;struct QNode*next;} QNode,*QueuePtr;//QueuePtr 为队列结点型指针typedefstruct{
QueuePtr front;//队头指针,指向头结点
QueuePtr rear;//队尾指针} LinkQueue;//链队列类型
(2)头文件声明
- 头文件声明包括函数结果状态代码 OK、ERROR,数据元素类型 ElemType ,栈的基本操作的函数原型声明,以及需要的库。
注:由于C语言不存在引用,需用传址。这里 LinkQueue 是普通结构体类型,对链队列的操作就是对 LinkQueue 类型中两个结点指针的操作,故当需要改变链队列内容时,就是要改变 LinkQueue 类型中的变量,所以此时要传递 LinkQueue 类型的地址。
#ifndef LINKQUEUE_H#define LINKQUEUE_H#define OK 1#define ERROR 0typedefint Status;//自定义函数类型,其值是函数结果的状态代码typedefint ElemType;//自定义数据类型#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefstruct QNode//队列结点定义{
ElemType data;struct QNode*next;} QNode,*QueuePtr;//QueuePtr 为队列结点型指针typedefstruct{
QueuePtr front;//队头指针,指向头结点
QueuePtr rear;//队尾指针} LinkQueue;//链队列基本操作的函数原型说明
StatusInitQueue(LinkQueue*Q);//构造一个空队列
StatusDestoryQueue(LinkQueue*Q);//销毁队列 Q
StatusClearQueue(LinkQueue*Q);//置空队列 Q
boolQueueEmpty(LinkQueue Q);//判断队列是否为空intQueueLength(LinkQueue Q);//返回队列 Q 的元素个数,即队列长度
StatusGetHead(LinkQueue Q, ElemType*e);//若队列不为空,则用 e 获取 Q 的队头元素,并返回OK;否则返回ERROR
StatusEnQueue(LinkQueue*Q, ElemType e);//插入元素 e 为队列 Q 的新队尾元素
StatusDeQueue(LinkQueue*Q, ElemType*e);//若队列不为空,则删除 Q 的队头元素,用 e 获取其值,并返回OK;否则返回ERROR
StatusQueueTraverse(LinkQueue Q/*,visit()*/);//从队头到队尾依次调用函数 visit(),这里简化为输出#endif
4.3.4、主要操作实现与思路
(1)初始化 InitQueue()
- 由于该链队列存在头结点,故其初始化就是开辟一个头结点,并给 front、rear 赋初值。
- 该函数要更改队列的内容,故形参要传递地址。初始化效果如下图。
StatusInitQueue(LinkQueue*Q){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));//头结点,头结点不存数据,仅有指针assert(p!=NULL);
Q->front= Q->rear= p;//初始化队头指针与队尾指针
Q->rear->next=NULL;//由队尾进元素,队尾结点的指针域总为空return OK;}
(2)置空 ClearQueue()
- 对于链队列而言,置空操作要回收每一个队列结点。在循环中,由于队尾结点的 next 域始终为 NULL ,故结点的指针域是否为 NULL 可以作为循环的终止条件。
- 首先考虑当前队列是否为空,若为空,则直接返回。
- 由于该链队列存在头结点,故操作指针 p 应该从头结点的下一个结点开始(即队头结点),在 p != NULL 的情况下(),先下移队头结点,再释放原队头结点,最后重置队尾指针(由于置空完后,仅剩一个头结点,队头指针与队尾指针均指向该结点)。
StatusClearQueue(LinkQueue*Q){if(QueueEmpty(*Q))return ERROR;
QueuePtr p= Q->front->next;//初始指向头结点之后的一个元素while(p!=NULL){
Q->front->next= p->next;//连接p结点的后一个与前一个结点free(p);
p= Q->front->next;//p结点下移,队尾rear所指结点的指针域为NULL}
Q->rear= Q->front;//此时队列为空,要重置尾结点return OK;}
(3)销毁 DestoryQueue()
- 区别与置空操作,销毁还要释放链式队列的的头结点,而置空不是。
- 释放头结点后,注意队头指针与队尾指针的赋 NULL 操作(避免随机指针的存在,这是大忌)。
StatusDestoryQueue(LinkQueue*Q){ClearQueue(Q);free(Q->front);//释放头结点
Q->front= Q->rear=NULL;//头指针与尾指针相当于全局变量,预防迷指针return OK;}
(4)判空、求长 QueueEmpty()、 QueueLength()
- 当 front == rear 表明当前链队列为空。
- 求长就像遍历链队列一样,但要增加一个计数器 count ,操作指针 p 的初始值指向队头结点(即头结点的下一个结点),终止条件为 p == NULL (由于队尾结点的 next 始终为 NULL)。
boolQueueEmpty(LinkQueue Q){return(Q.front== Q.rear? true: false);}intQueueLength(LinkQueue Q){int count=0;
QueuePtr p= Q.front->next;//长度不计无数据的头结点while(p!=NULL){
count++;
p= p->next;}return count;}
(5)入队 EnQueue()
- 队列的入队即像单链表的尾插操作,队尾( rear ) 指针是始终指向队尾结点的,操作简单。
StatusEnQueue(LinkQueue*Q,ElemType e){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));assert(p!=NULL);//新结点初始化
p->data= e;
p->next=NULL;
Q->rear->next= p;//先接在原队尾结点后
Q->rear= p;//队尾结点更新return OK;}
(6)出队 DeQueue()
链队列的出队就像单链表的头删操作一样。
即,首先操作指针 p 先获得队头结点,再更新队头结点,最后释放原队头结点。
StatusDeQueue(LinkQueue*Q,ElemType*e){if(QueueEmpty(*Q))return ERROR;
QueuePtr p= Q->front->next;
Q->front->next= p->next;//连接p结点的后一个与前一个结点*e= p->data;if(p== Q->rear)//如果p指向尾指针,直接释放p时,队尾指针会丢失
Q->rear= Q->front;//此时表明队列删除完毕,仅剩无数据的头结点,故头尾结点都应指向头结点free(p);return OK;}
(7)获取队头元素 GetHead()
- 队列不为空时,操作指针 p 直接直线队头结点即可。
- 该函数内不需要更改队列的内容,故形参不需传递地址。
StatusGetHead(LinkQueue Q, ElemType*e){if(QueueEmpty(Q))return ERROR;
QueuePtr p= Q.front->next;*e= p->data;return OK;}
(8)遍历 QueueTraverse()
- 首先判断当前链队列是否为空,或已销毁。
- 其次像遍历链表那样,易于实现。
StatusQueueTraverse(LinkQueue Q){if(Q.front==NULL){printf("The Queue is Destoried!\n");return ERROR;}if(QueueEmpty(Q)){printf("The Queue is empty\n");return ERROR;}
QueuePtr p= Q.front->next;//由于Q->front指向头结点,头结点无数据printf("front:< ");while(p!=NULL){printf("%d ", p->data);
p= p->next;}printf("<:rear.\n");return OK;}
4.3.5、完整代码
(1)头文件 linkQueue_ADT.h
//linkQueue_ADT.h#ifndef LINKQUEUE_H#define LINKQUEUE_H#define OK 1#define ERROR 0typedefint Status;//自定义函数类型,其值是函数结果的状态代码typedefint ElemType;//自定义数据类型#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>typedefstruct QNode//队列结点定义{
ElemType data;struct QNode*next;} QNode,*QueuePtr;//QueuePtr 为队列结点型指针typedefstruct{
QueuePtr front;//队头指针,指向头结点
QueuePtr rear;//队尾指针} LinkQueue;//链队列基本操作的函数原型说明
StatusInitQueue(LinkQueue*Q);//构造一个空队列
StatusDestoryQueue(LinkQueue*Q);//销毁队列 Q
StatusClearQueue(LinkQueue*Q);//置空队列 Q
boolQueueEmpty(LinkQueue Q);//判断队列是否为空intQueueLength(LinkQueue Q);//返回队列 Q 的元素个数,即队列长度
StatusGetHead(LinkQueue Q, ElemType*e);//若队列不为空,则用 e 获取 Q 的队头元素,并返回OK;否则返回ERROR
StatusEnQueue(LinkQueue*Q, ElemType e);//插入元素 e 为队列 Q 的新队尾元素
StatusDeQueue(LinkQueue*Q, ElemType*e);//若队列不为空,则删除 Q 的队头元素,用 e 获取其值,并返回OK;否则返回ERROR
StatusQueueTraverse(LinkQueue Q/*,visit()*/);//从队头到队尾依次调用函数 visit(),这里简化为输出#endif
(2)函数实现代码 linkQueue_ADT.c
#include"linkQueue_ADT.h"//链队列基本操作的算法实现
StatusInitQueue(LinkQueue*Q){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));//头结点,头结点不存数据,仅有指针assert(p!=NULL);
Q->front= Q->rear= p;//初始化队头指针与队尾指针
Q->rear->next=NULL;//由队尾进元素,队尾结点的指针域总为空return OK;}
StatusClearQueue(LinkQueue*Q){if(QueueEmpty(*Q))return ERROR;
QueuePtr p= Q->front->next;//初始指向头结点之后的一个元素while(p!=NULL){
Q->front->next= p->next;//连接p结点的后一个与前一个结点free(p);
p= Q->front->next;//p结点下移,队尾rear所指结点的指针域为NULL}
Q->rear= Q->front;//此时队列为空,要重置尾结点return OK;}
StatusDestoryQueue(LinkQueue*Q){ClearQueue(Q);free(Q->front);//释放头结点
Q->front= Q->rear=NULL;//头指针与尾指针相当于全局变量,预防迷指针return OK;}
boolQueueEmpty(LinkQueue Q){return(Q.front== Q.rear? true: false);}intQueueLength(LinkQueue Q){int count=0;
QueuePtr p= Q.front->next;//长度不计无数据的头结点while(p!=NULL){
count++;
p= p->next;}return count;}
StatusGetHead(LinkQueue Q, ElemType*e){if(QueueEmpty(Q))return ERROR;
QueuePtr p= Q.front->next;*e= p->data;return OK;}
StatusEnQueue(LinkQueue*Q, ElemType e){
QueuePtr p=(QueuePtr)malloc(sizeof(QNode));assert(p!=NULL);//新结点初始化
p->data= e;
p->next=NULL;
Q->rear->next= p;//先接在原队尾结点后
Q->rear= p;//队尾结点更新return OK;}
StatusDeQueue(LinkQueue*Q, ElemType*e){if(QueueEmpty(*Q))return ERROR;
QueuePtr p= Q->front->next;
Q->front->next= p->next;//连接p结点的后一个与前一个结点*e= p->data;if(p== Q->rear)//如果p指向尾指针,直接释放p时,队尾指针会丢失
Q->rear= Q->front;//此时表明队列删除完毕,仅剩无数据的头结点,故头尾结点都应指向头结点free(p);return OK;}
StatusQueueTraverse(LinkQueue Q){if(Q.front==NULL){printf("The Queue is Destoried!\n");return ERROR;}if(QueueEmpty(Q)){printf("The Queue is empty\n");return ERROR;}
QueuePtr p= Q.front->next;//由于Q->front指向头结点,头结点无数据printf("front:< ");while(p!=NULL){printf("%d ", p->data);
p= p->next;}printf("<:rear.\n");return OK;}
(3)测试代码 linkQueue_test.c
#include"linkQueue_ADT.c"//测试 linkQueue_ADTvoidmenu();intmain(){
LinkQueue Q;
ElemType e;char choice;int n;menu();while(1){printf("输入你的选择:\n");scanf("%c",&choice);getchar();//每输入一个数据,缓存区还存在一个回车符,要取走,防止switch语句误判switch(choice){case'1':InitQueue(&Q);printf("空队列创建成功!\n开始创建队列,输入队列的长度\n");scanf("%d",&n);getchar();printf("输入%d个队列元素\n",n);for(int i=0; i< n; i++){scanf("%d",&e);getchar();EnQueue(&Q, e);}printf("该队列为:");QueueTraverse(Q);break;case'2':printf("队列长为:%d\n",QueueLength(Q));break;case'3':if(GetHead(Q,&e)== ERROR)printf("队列已空!\n");elseprintf("队列顶元素为:%d\n", e);break;case'4':if(!DeQueue(&Q,&e))printf("队列已空!\n");else{printf("出队列的元素为:%d\n", e);printf("出队列后,新队列为:");QueueTraverse(Q);}break;case'5':printf("输入压队列元素!\n");scanf("%d",&e);getchar();EnQueue(&Q, e);printf("新队列为:");QueueTraverse(Q);break;case'6':if(!QueueEmpty(Q))printf("非空队列!\n");elseprintf("空队列!\n");break;case'7':printf("当前队列为:");QueueTraverse(Q);break;case'8':ClearQueue(&Q);printf("队列已置空!\n");printf("该队列为:");QueueTraverse(Q);break;case'9':DestoryQueue(&Q);printf("队列已销毁!\n");printf("该队列为:");QueueTraverse(Q);break;default:exit(0);break;}}return0;}voidmenu(){printf("--------linkQueue_ADT_test-------\n"