menu 贺大礼(乱丶心)的博客
4.13队列的链式存储结构及实现(大话数据结构)
3348 浏览 | 2021-01-14 | 阅读时间: 约 2 分钟 | 分类: 数据结构,算法与数据结构,C/C++ | 标签: 数据结构
请注意,本文编写于 1424 天前,最后修改于 1424 天前,其中某些信息可能已经过时。

队列的链式存储结构,其实就是线性表的单链表,只不过它只能尾进头出而已,我们把它简称为链队列。
队头指针指向队列的头结点,队尾指针指向终端结点。

空队列时,front和rear都指向头结点

链队列的结构为:

typedef int QElemType; /* QElemType类型根据实际情况而定,这里假设为int */
typedef struct QNode   /* 结点结构 */
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct     /* 队列的链表结构 */
{
    QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

入队操作:
在链表尾部插入结点

整体代码:

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#define OK 1
#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OVERFLOW -1
typedef int Status;
typedef int QElemType; /* QElemType类型根据实际情况而定,这里假设为int */
typedef struct QNode   /* 结点结构 */
{
    QElemType data;
    struct QNode *next;
}QNode,*QueuePtr;
typedef struct     /* 队列的链表结构 */
{
    QueuePtr front,rear; /* 队头、队尾指针 */
}LinkQueue;

Status InitQueue(LinkQueue *Q);//初始化操作,建立一个空队列
Status Destroy(LinkQueue *Q);//若队列Q存在,则销毁它。
Status ClearQueue(LinkQueue *Q);//将队列Q清空
Status QueueEmpty(LinkQueue Q);//若队列Q为空,返回true,否则返回false
Status GetHead(LinkQueue Q, QNode *e);//若队列Q存在且非空,用e返回队列Q的队头元素。
Status EnQueue(LinkQueue *Q, QElemType e);//若队列Q存在,插入新元素e到队列Q中并成为队尾元素。
Status DeQueue(LinkQueue *Q, QElemType *e);//删除队列Q中队头元素,并用e返回其值
Status QueueLength(LinkQueue Q);//返回队列Q的元素个数

int main() {
    LinkQueue* Q = (LinkQueue*)malloc(sizeof(LinkQueue));
    QNode* e;
    QElemType ee;
    int status;
    InitQueue(Q);
    EnQueue(Q, 111);
    EnQueue(Q, 222);
    EnQueue(Q, 333);
    printf("结点数量:%d \n", QueueLength(*Q));
    GetHead(*Q, e);
    printf("首元素的值e->data = %d;\n", e->data);
    DeQueue(Q, &ee);
    printf("被删除的值e->data = %d;\n", ee);
    printf("结点数量:%d \n", QueueLength(*Q));
    printf("队列为空吗? : %d \n", QueueEmpty(*Q));
    GetHead(*Q, e);
    printf("首元素的值e->data = %d;\n", e->data);
    ClearQueue(Q);
    if (GetHead(*Q, e) == 1)
    printf("首元素的值e->data = %d;\n", e->data);
    printf("结点数量:%d \n", QueueLength(*Q));
    printf("队列为空吗? : %d \n", QueueEmpty(*Q));
    Destroy(Q);
    if (GetHead(*Q, e) == 1)
    printf("首元素的值e->data = %d;\n", e->data);
    printf("结点数量:%d \n", QueueLength(*Q));
    printf("队列为空吗? : %d \n", QueueEmpty(*Q));

    printf("执行完成\n");
    printf("\n");
    return 0;
}

//初始化操作,建立一个空队列
Status InitQueue(LinkQueue *Q)
{
    QueuePtr head = (QueuePtr)malloc(sizeof(QNode));
    head->data = 0;
    head->next=NULL;
    Q->front = head; // 首指针指向头结点
    printf("Q->front = head;成功\n");
    Q->rear = head; // 尾指针指向头结点
    printf("Q->rear = head;成功\n");
    return OK;
}
//若队列Q存在,则销毁它。
Status Destroy(LinkQueue *Q)
{
    if (Q->front)
    {
        ClearQueue(Q);
        QueuePtr q = Q->front;
        free(q);//释放头结点
        Q->front = NULL;
        Q->rear = NULL;
    }
    return OK;
}
//将队列Q清空
Status ClearQueue(LinkQueue *Q)
{
    QueuePtr p,q;
    p = Q->front->next; //p指向第一个数据结点
    while (p)
    {
        q = p->next;
        free(p);//free释放的是对内存空间的使用权,释放后内存值还在
        p = q;
    }
    Q->front->data = 0;//头结点数据清0
    Q->front->next = NULL; 
    Q->rear = Q->front;
    return OK;
}
//若队列Q为空,返回true,否则返回false
Status QueueEmpty(LinkQueue Q)
{
    if (!Q.front) 
    return OVERFLOW;
    if (Q.front == Q.rear)
    return TRUE;
    else
    return FALSE;
}

//若队列Q存在且非空,用e返回队列Q的队头元素。
Status GetHead(LinkQueue Q, QNode *e)
{
    if (!Q.front) 
    return OVERFLOW;
    if (Q.front == Q.rear)
    {
        return ERROR;
    }
    e->data = Q.front->next->data;
    e->next = Q.front->next->next;
    return OK;
}
// 插入元素e为Q的新的队尾元素
Status EnQueue (LinkQueue *Q, QElemType e)
{
    if (!Q) 
    return OVERFLOW;
    QueuePtr s = (QueuePtr)malloc(sizeof(QNode));
    if (!s) /* 存储分配失败 */
    {
        exit(OVERFLOW);
    }
    s->data=e;
    printf("s->data=%d;\n", s->data);
    s->next=NULL;
    Q->rear->next = s; // 把拥有元素e新结点s赋值给原队尾结点的后继
    Q->rear=s; // 把当前的s设置为队尾结点,rear指向s
    Q->front->data++;//结点数量加1
    return OK;
}
// 若队列不空,删除Q的队头元素,用e返回其值,并返回OK,否则返回ERROR
Status DeQueue(LinkQueue *Q, QElemType *e)
{
    if (!Q) 
    return OVERFLOW;
    QueuePtr p;
    if (Q->front == Q->rear)
        return ERROR;
    p=Q->front->next; //将欲删除的队头结点暂存给p
    *e=p->data;//将欲删除的队头结点的值赋值给e
    Q->front->next = p->next;//将原队头结点后继p->next赋值给头结点后继

    if(Q->rear==p) //若队头是队尾,则删除后将rear指向头结点
        Q->rear=Q->front;
    free(p);
    Q->front->data -= 1;//结点数量减1
    return OK;
}
//返回队列Q的元素个数
Status QueueLength(LinkQueue Q)
{
    if (Q.front != NULL)
    return Q.front->data;
    else 
    return 0;
}
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议

发表评论

email
web

全部评论 (共 1 条评论)

    飞飞
    2021-01-19 14:10
    写的不错!