数据结构(C语言版)——4.3、链式队列实现

2022-10-28 11:57:52

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"
  • 作者:C++的忠实粉丝
  • 原文链接:https://blog.csdn.net/weixin_41600504/article/details/108943381
    更新时间:2022-10-28 11:57:52