devbox
IT小白
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

队列的链式存储实现_实现一个链接存储的队列

作者：IT小白 | 2024-05-08 00:17:57

赞

踩

实现一个链接存储的队列

文章目录

队列的链式存储实现

链式队列 ： 用链表形式实现的队列。链表结点为队列数据存储区，链表结点包括两部分数据存储

区和指针存储区。

数据存储区 ：存放真实有效数据的区域。

指针存储区 ：存放下一个链表结点的地址。

二、实现过程

1.链式队列概念图(有头结点)：

在这里插入图片描述

2.链式队列结构体：

头指针执行头结点，尾指针指向尾结点

//线性表存储结构
typedef struct LNode
{
        ElemType data;                  //存储队列中的元素。
        struct LNode* next;             //next指针

}LNode;

//队列的指针头和尾
typedef struct
{
  LNode *front,*rear;     // 队列的头指针和尾指针。
}LinkQueue,*PLinkQueue;


  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

3.队列的基本操作

在这里插入图片描述

4.代码实现：

/*
        程序名:linkqueue.cpp 此程序演示队列的链表实现（带头结点）。
*/


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

typedef int ElemType;                   //自定义队列的数据元素为整数。

//线性表存储结构
typedef struct LNode
{
        ElemType data;                  //存储队列中的元素。
        struct LNode* next;             //next指针

}LNode;

//队列的指针头和尾
typedef struct
{
  LNode *front,*rear;     // 队列的头指针和尾指针。
}LinkQueue,*PLinkQueue;


//队列QQ的初始化操作。
int InitQueue(PLinkQueue QQ);

// 销毁队列QQ。
void DestroyQueue(PLinkQueue QQ);

// 清空队列。
void Clear(PLinkQueue QQ);

// 元素入队，返回值：0-失败；1-成功。
int InQueue(PLinkQueue QQ, ElemType *ee);

// 打印队列中全部的元素。
void PrintQueue(PLinkQueue QQ);

// 求队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PLinkQueue QQ);

// 判断队列是否已满，链式队列不存在队满的说法。
int IsFull(PLinkQueue QQ);

// 判断队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PLinkQueue QQ);

// 元素出队，返回值：0-失败；1-成功。
int OutQueue(PLinkQueue QQ, ElemType *ee);

// 获取队头元素，返回值：0-失败；1-成功。
// 只查看队头元素的值，元素不出队。
int GetHead(PLinkQueue QQ, ElemType *ee);


int main()
{
        LinkQueue QQ;     // 创建队列。

        memset(&QQ,0,sizeof(LinkQueue));

        InitQueue(&QQ);  // 初始化队列。

        ElemType ee;     // 创建一个数据元素。

        printf("元素（1、2、3、4、5、6、7、8、9、10）入队。\n");
        ee=1;  InQueue(&QQ, &ee);
        ee=2;  InQueue(&QQ, &ee);
        ee=3;  InQueue(&QQ, &ee);
        ee=4;  InQueue(&QQ, &ee);
        ee=5;  InQueue(&QQ, &ee);
        ee=6;  InQueue(&QQ, &ee);
        ee=7;  InQueue(&QQ, &ee);
        ee=8;  InQueue(&QQ, &ee);
        ee=9;  InQueue(&QQ, &ee);
        ee=10; InQueue(&QQ, &ee);

        printf("队列的长度是%d\n",Length(&QQ));

        printf("打印队列元素:\n");
        PrintQueue(&QQ);

        if (OutQueue(&QQ,&ee)==1)  printf("出队的元素值为%d\n",ee);
        if (OutQueue(&QQ,&ee)==1)  printf("出队的元素值为%d\n",ee);
        if (OutQueue(&QQ,&ee)==1)  printf("出队的元素值为%d\n",ee);
        if (OutQueue(&QQ,&ee)==1)  printf("出队的元素值为%d\n",ee);
        if (OutQueue(&QQ,&ee)==1)  printf("出队的元素值为%d\n",ee);
        if (OutQueue(&QQ,&ee)==1)  printf("出队的元素值为%d\n",ee);
        if (OutQueue(&QQ,&ee)==1)  printf("出队的元素值为%d\n",ee);

        printf("队列的长度是%d\n",Length(&QQ));
        PrintQueue(&QQ);

        printf("元素（11、12、13、14、15）入队。\n");
        ee=11;  InQueue(&QQ, &ee);
        ee=12;  InQueue(&QQ, &ee);
        ee=13;  InQueue(&QQ, &ee);
        ee=14;  InQueue(&QQ, &ee);
        ee=15;  InQueue(&QQ, &ee);

        printf("队列的长度是%d\n",Length(&QQ));


        PrintQueue(&QQ);
        // 只查看队头元素的值，元素不出队。
        if (GetHead(&QQ,&ee)==1)  printf("队头的元素值为%d\n",ee);


//      printf("清除前front=%p,rear=%p\n",QQ.front,QQ.rear);
        Clear(&QQ); // 销毁队列QQ。     
//      printf("清除后front=%p,rear=%p\n",QQ.front,QQ.rear);

//      printf("销毁前front=%p,rear=%p\n",QQ.front,QQ.rear);
        DestroyQueue(&QQ); // 销毁队列QQ。      
//      printf("销毁后front=%p,rear=%p\n",QQ.front,QQ.rear);
        return 0;
}

//队列QQ的初始化操作。
int InitQueue(PLinkQueue QQ)
{
        if(QQ == NULL){ printf("队列不存在\n"); return 0; }

        //创建头结点
        LNode* head=(LNode*)malloc(sizeof(LNode));
        if(head==NULL){ printf("内存不足，分配结点失败。\n");return 0; }

        head->next=NULL;

        QQ->front=QQ->rear=head;
        return 1;
}

// 销毁队列QQ。删除所有结点
void DestroyQueue(PLinkQueue QQ)
{
        //队列指针不存在 
        if(QQ==NULL){ printf("队列不存在\n"); return ; }

        // 未初始化 即头尾指针没有指向头结点
        if(QQ->front==NULL){
                printf("队列未初始化。\n");
                return ;
        }


        LNode* tmp=QQ->front;

        //逐个结点删除
        while(tmp != QQ->rear->next)
        {
                tmp=tmp->next;          //下个结点地址
                free(QQ->front);        //释放本结点地址
                QQ->front=tmp;          //指针指向下一个结点
        }

        QQ->front=QQ->rear=NULL;
        return ;
}

// 清空队列。删除了除头结点以外的所有结点
void Clear(PLinkQueue QQ)
{

        //队列指针不存在 
        if(QQ==NULL){ printf("队列不存在\n"); return ; }

        // 未初始化 即头尾指针没有指向头结点
        if(QQ->front==NULL){
                printf("队列未初始化。\n");
                return ;
        }

        LNode *head=QQ->front;          //保存头结点

        LNode* tmp=QQ->front->next;     //从首节点开始删除

        //逐个结点删除
        while(tmp != QQ->rear->next)
        {
                tmp=tmp->next;          //下个结点地址
                free(QQ->front);        //释放本结点地址
                QQ->front=tmp;          //指针指向下一个结点
        }

        QQ->front=QQ->rear=head;
        QQ->front->next=QQ->rear->next=NULL;
}

// 元素入队，返回值：0-失败；1-成功。
int InQueue(PLinkQueue QQ, ElemType *ee)
{
        //队列指针不存在
        if(QQ==NULL){ printf("队列不存在\n"); return 0; }

        //未初始化 即头尾指针没有指向头结点
        if(QQ->front==NULL){
                printf("队列未初始化。\n");
                return 0;
        }

        //新建一个结点
        LNode *newnode=(LNode*)malloc(sizeof(LNode));
        if(newnode==NULL)return 0;
        //将元素值赋值给新结点
        memcpy(&newnode->data,ee,sizeof(ElemType));


        newnode->next=NULL;
        QQ->rear->next=newnode;
        QQ->rear=newnode;

        return 1;
}

// 打印队列中全部的元素。
void PrintQueue(PLinkQueue QQ)
{
        //队列指针不存在
        if(QQ==NULL){ printf("队列不存在\n"); return ; }

        //未初始化 即头尾指针没有指向头结点
        if(QQ->front==NULL){
                printf("队列未初始化。\n");
                return ;
        }


        LNode* tmp=QQ->front->next;             //从首节点开始输出


        //当指针没查询到尾指针的next域，一直查询
        while(tmp!=QQ->rear->next){
                printf("%3d ",tmp->data);
                tmp=tmp->next;
        }

        printf("\n");
}

// 求队列的长度，返回值：>=0-队列QQ元素的个数。
int  Length(PLinkQueue QQ)
{
        //队列指针不存在
            if(QQ==NULL){ printf("队列不存在\n"); return 0; }

        //未初始化 即头尾指针没有指向头结点
        if(QQ->front==NULL){
                printf("队列未初始化。\n");
                return 0;
        }

        LNode* tmp=QQ->front->next;     //从首节点开始计数
        if(tmp==NULL)return 0;

        int length=1;                   //头结点序号为1 

        while(tmp!=QQ->rear)
        {
                length++;
                tmp=tmp->next;
        }

        return length;
}

// 判断队列是否已满，链式队列不存在队满的说法。
int IsFull(PLinkQueue QQ)
{
        //队列指针不存在
        if(QQ==NULL){ printf("队列不存在\n"); return 0; }
        return 1;
}

// 判断队列是否为空，返回值：1-空，0-非空或失败。
int  IsEmpty(PLinkQueue QQ)
{
        //队列指针不存在
        if(QQ==NULL){ printf("队列不存在\n"); return 0; }

        //首尾相等为空
        if(QQ->front==QQ->rear)return 1;
        return 0;

}
// 元素出队，返回值：0-失败；1-成功。
int OutQueue(PLinkQueue QQ, ElemType *ee)
{
        //队列指针不存在
        if(QQ==NULL){ printf("队列不存在\n"); return 0; }

        if(QQ->front==NULL){printf("队列未初始化");return 0;}

        if(IsEmpty(QQ)){ printf("队空,无元素可以出队。\n"); return 0; }          
        //队头元素出队
        LNode* tmp=QQ->front->next;

        //队尾
        memcpy(ee,&tmp->data,sizeof(ElemType));

        QQ->front->next=tmp->next;

        // 如果出队的是最后一个结点。
        if (QQ->rear==tmp) QQ->rear=QQ->front;
        free(tmp);

        return 1;
}
// 获取队头元素，返回值：0-失败；1-成功。
// 只查看队头元素的值，元素不出队。
int GetHead(PLinkQueue QQ, ElemType *ee)
{
        if(QQ==NULL){ printf("队列不存在\n"); return 0; }

        if(QQ->front==NULL){printf("队列未初始化");return 0;}

        if(IsEmpty(QQ)){ printf("队空,无元素可以出队。\n"); return 0; }

        //取队头元素
        memcpy(ee,&QQ->front->next->data,sizeof(ElemType));

        return 1;
}         
                

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
  • 92
  • 93
  • 94
  • 95
  • 96
  • 97
  • 98
  • 99
  • 100
  • 101
  • 102
  • 103
  • 104
  • 105
  • 106
  • 107
  • 108
  • 109
  • 110
  • 111
  • 112
  • 113
  • 114
  • 115
  • 116
  • 117
  • 118
  • 119
  • 120
  • 121
  • 122
  • 123
  • 124
  • 125
  • 126
  • 127
  • 128
  • 129
  • 130
  • 131
  • 132
  • 133
  • 134
  • 135
  • 136
  • 137
  • 138
  • 139
  • 140
  • 141
  • 142
  • 143
  • 144
  • 145
  • 146
  • 147
  • 148
  • 149
  • 150
  • 151
  • 152
  • 153
  • 154
  • 155
  • 156
  • 157
  • 158
  • 159
  • 160
  • 161
  • 162
  • 163
  • 164
  • 165
  • 166
  • 167
  • 168
  • 169
  • 170
  • 171
  • 172
  • 173
  • 174
  • 175
  • 176
  • 177
  • 178
  • 179
  • 180
  • 181
  • 182
  • 183
  • 184
  • 185
  • 186
  • 187
  • 188
  • 189
  • 190
  • 191
  • 192
  • 193
  • 194
  • 195
  • 196
  • 197
  • 198
  • 199
  • 200
  • 201
  • 202
  • 203
  • 204
  • 205
  • 206
  • 207
  • 208
  • 209
  • 210
  • 211
  • 212
  • 213
  • 214
  • 215
  • 216
  • 217
  • 218
  • 219
  • 220
  • 221
  • 222
  • 223
  • 224
  • 225
  • 226
  • 227
  • 228
  • 229
  • 230
  • 231
  • 232
  • 233
  • 234
  • 235
  • 236
  • 237
  • 238
  • 239
  • 240
  • 241
  • 242
  • 243
  • 244
  • 245
  • 246
  • 247
  • 248
  • 249
  • 250
  • 251
  • 252
  • 253
  • 254
  • 255
  • 256
  • 257
  • 258
  • 259
  • 260
  • 261
  • 262
  • 263
  • 264
  • 265
  • 266
  • 267
  • 268
  • 269
  • 270
  • 271
  • 272
  • 273
  • 274
  • 275
  • 276
  • 277
  • 278
  • 279
  • 280
  • 281
  • 282
  • 283
  • 284
  • 285
  • 286
  • 287
  • 288
  • 289
  • 290
  • 291
  • 292
  • 293
  • 294
  • 295
  • 296
  • 297
  • 298
  • 299
  • 300
  • 301
  • 302
  • 303
  • 304
  • 305
  • 306
  • 307
  • 308
  • 309
  • 310
  • 311
  • 312
  • 313
  • 314
  • 315
  • 316
  • 317
  • 318
  • 319
  • 320
  • 321
  • 322
  • 323
  • 324
  • 325
  • 326
  • 327
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/551915
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号