学习记录——day17 数据结构队列链式队列

27 阅读 0 评论 0 点赞

队列介绍

1、队列也是操作受限的线性表:所有操作只能在端点处进行，其删除和插入必须在不同端进行

2、允许插入操作的一端称为队尾，允许删除操作的一端称为队头

3、特点:先进先出(FIFO)

4、分类：

顺序存储的栈称为顺序栈

链式存储的队列，称为链式队列

顺序队列

1、使用一片连续存储的空间存储队列，并且给定两个变量，分别记录队头和队尾下标

2、普通顺序队列使用中，存在“假溢满”现象

假溢满:队列中明明还有存储空间，但是由于队尾已经达到了数组的最大下标，不能在继续入队元素了

3、为了解决“假溢满”现象，我们引入了循环顺序队列

循环顺序队列

循环顺序队列:通过相关操作，当对头或队尾达到数组最大下标时，可以返回到下标为0的位置

注：以下均使用人为浪费一个空间的方法判满

1、创建

头节点类型定义

//类型重定义
typedef int datatype;


//队列类型结构体
typedef struct Queue
{
    datatype data[MAX];
    int head;
    int tail;

}SeqQueue, *SeqQueuePtr;

创建队列

SeqQueuePtr queue_create()
{
    SeqQueuePtr Q = (SeqQueuePtr)malloc(sizeof(SeqQueue));
    if(NULL == Q)
    {
        return NULL;
    }

    bzero(Q->data,sizeof(Q->data));
    Q->front = Q->tail = 0;

    printf("创建成功 \n");

    return Q;
}

2、判空判满

int queue_empty(SeqQueuePtr Q)
{
    return Q->tail == Q->front;
}

int queue_full(SeqQueuePtr Q)
{
    return (Q->tail+1)%MAX == Q->front;
}

3、插入

void queue_push(SeqQueuePtr Q ,datatype e)
{
    if (NULL == Q || queue_full(Q))
    {
        return;
    }
    
    Q->data[Q->tail] = e;

    Q->tail = (Q->tail+1)%MAX;

    return;
}

4、遍历

void queue_show(SeqQueuePtr Q)
{
    if (NULL == Q)
    {
        return;
    }

    printf("遍历结果:");
    for (int i = Q->front; i !=Q->tail; i=(i+1)%MAX)
    {
        printf("%d\t",Q->data[i]);
    }
    putchar(10);
    return;
}

5、出队

void queue_pop(SeqQueuePtr Q)
{
    if (NULL == Q || queue_empty(Q))
    {
        return;
    }
    
    printf("%d 出队\n",Q->data[Q->front]);

    Q->front = (Q->front+1)%MAX;
}

6、求实际大小

int queue_size(SeqQueuePtr Q)
{
    if (NULL == Q)
    {
        return -1;
    }

    //不使用循环求大小

    int size = ((Q->tail-Q->front)+MAX)%MAX;

    return size;
}

7、销毁

void queue_destroy(SeqQueuePtr Q)
{
    if (NULL != Q)
    {
        free(Q);
        Q = NULL;
    }
    
    printf("boom!!\n");

    return;
}

8、完整代码

dui_lie.h

#ifndef DUI_LEI
#define DUI_LEI

#include <myhead.h>

#define MAX 8
typedef int datatype;

typedef struct 
{
    datatype data[MAX];
    int front;
    int tail;
}SeqQueue,*SeqQueuePtr;

SeqQueuePtr queue_create();

int queue_empty(SeqQueuePtr Q);

int queue_full(SeqQueuePtr Q);

void queue_push(SeqQueuePtr Q ,datatype e);

void queue_show(SeqQueuePtr Q);

void queue_pop(SeqQueuePtr Q);

int queue_size(SeqQueuePtr Q);

void queue_destroy(SeqQueuePtr Q);


#endif // !DUI_LEI.H

dui_lie.c

#include "dui_lie.h"
#include <myhead.h>

SeqQueuePtr queue_create()
{
    SeqQueuePtr Q = (SeqQueuePtr)malloc(sizeof(SeqQueue)*MAX);
    if(NULL == Q)
    {
        return NULL;
    }

    bzero(Q->data,sizeof(Q->data));
    Q->front = Q->tail = 0;

    printf("创建成功 \n");

    return Q;
}

int queue_empty(SeqQueuePtr Q)
{
    return Q->tail == Q->front;
}

int queue_full(SeqQueuePtr Q)
{
    return (Q->tail+1)%MAX == Q->front;
}

void queue_push(SeqQueuePtr Q ,datatype e)
{
    if (NULL == Q || queue_full(Q))
    {
        return;
    }
    
    Q->data[Q->tail] = e;

    Q->tail = (Q->tail+1)%MAX;

    return;
}

void queue_show(SeqQueuePtr Q)
{
    if (NULL == Q)
    {
        return;
    }

    printf("遍历结果:");
    for (int i = Q->front; i !=Q->tail; i=(i+1)%MAX)
    {
        printf("%d\t",Q->data[i]);
    }
    putchar(10);
    return;
}

void queue_pop(SeqQueuePtr Q)
{
    if (NULL == Q || queue_empty(Q))
    {
        return;
    }
    
    printf("%d 出队\n",Q->data[Q->front]);

    Q->front = (Q->front+1)%MAX;
}

int queue_size(SeqQueuePtr Q)
{
    if (NULL == Q)
    {
        return -1;
    }

    //不使用循环求大小

    int size = ((Q->tail-Q->front)+MAX)%MAX;

    return size;
}

void queue_destroy(SeqQueuePtr Q)
{
    if (NULL != Q)
    {
        free(Q);
        Q = NULL;
    }
    
    printf("boom!!\n");

    return;
}

main.c

#include "dui_lie.h"
int main(int argc, char const *argv[])
{
    SeqQueuePtr Q = queue_create();
    if (NULL == Q)
    {
        return -1;
    }

    queue_push(Q,90);
    queue_push(Q,80);
    queue_push(Q,100);
    queue_push(Q,20);
    queue_show(Q);

    queue_pop(Q);
    queue_pop(Q);
    queue_show(Q);

    printf("数组实际大小为%d:\n",queue_size(Q));

    queue_destroy(Q);
    return 0;
}

链式队列

链式存储的队列称为链式队列

实现原理:
单向链表头插尾删实现:链表的头部就是队尾，链表的尾部就是队头

单向链表头删尾插实现:链表的头部就是队头，链表的尾部就是队尾

但是，上述操作中，都要用到链表尾部节点，都需要遍历整个链表完成，于是专门使用一个指针指向队尾，称为尾指针

00.h

#ifndef DAY17_1
#define DAY17_1

#include <myhead.h>

//类型重定义
typedef int datatype;

//节点结构体
typedef struct Node
{
    union 
    {
        datatype data;
        int len;
    };
    
    struct Node *next;
    
}Node, *NodePtr;

//头节点结构体
typedef struct Queue
{
    NodePtr head;
    NodePtr tail;

}Queue, *QueuePtr;

//队列创建
QueuePtr queue_create();

//判空
int queue_empty(QueuePtr Q);

//头插
int queue_push(QueuePtr Q,datatype);

//遍历
int queue_show(QueuePtr Q);

//出队
int queue_pop(QueuePtr Q);

//输出实际大小
int queue_size(QueuePtr Q);

//销毁
void queue_destroy(QueuePtr Q);

#endif // DAY17_1

00.c

#include "00.h"

//先创建队列 然后创建链表，将队列的两个指针指向链表
QueuePtr queue_create()
{
    //申请队列的空间
    QueuePtr Q = (QueuePtr)malloc(sizeof(Queue));
    if (NULL == Q)
    {
        printf("创建失败\n");
        return NULL;
    }

    //创建链表
    Q->head = (NodePtr)malloc(sizeof(Node));

    if (Q->head == NULL)
    {
        printf("创建失败\n");
        free(Q);
        return NULL;
    }

    Q->head->len = 0;
    Q->head->next = NULL;
    
    Q->tail = Q->head;

    return Q;
}


int queue_empty(QueuePtr Q)
{
    return Q->head->len == 0;
}

int queue_push(QueuePtr Q,datatype e)
{
    if (NULL == Q)
    {
       return -1;
    }

    NodePtr p = (NodePtr)malloc(sizeof(Node));
    if (NULL == p)
    {
        return -1;
    }
    
    p->data = e;
    p->next = NULL;

    Q->tail->next = p;

    Q->tail = p;

    Q->head->len++;
    
}

int queue_show(QueuePtr Q)
{
    if (NULL == Q || queue_empty(Q))
    {
        return -1;
    }
    NodePtr q = Q->head->next;

    while (q)
    {
        printf("%d\t",q->data);

        q = q->next;
    }
    putchar(10);
}

int queue_pop(QueuePtr Q)
{
    if (NULL == Q)
    {
        return -1;
    }
    

    NodePtr p = Q->head->next;
    Q->head->next = p->next;
    printf("%d 出队\n",p->data);
    free(p);
    p = NULL;

    //如果所有节点都出列成功，将尾节点重新指向头节点
    if (Q->tail == NULL)//Q->head->next == NULL
    {
        Q->tail = Q->head;
    }
    

    Q->head->len--;
}

int queue_size(QueuePtr Q)
{
    if (NULL == Q)
    {
        return -1;
    }
    
    return Q->head->len;
}

void queue_destroy(QueuePtr Q)
{
    if (NULL == Q)
    {
        return;
    }
    
    //释放所有节点
    while (!queue_empty(Q))
    {
        queue_pop(Q);
    }
    
    //释放头结点
    free(Q->head);
    Q->head = Q->tail = NULL;

    //释放队列空间
    free(Q);
    Q = NULL;
}

main.c

#include "00.h"

int main(int argc, char const *argv[])
{
    QueuePtr Q = queue_create();
    if (NULL == Q)
    {
        return -1;
    }
    queue_push(Q,233);
    queue_push(Q,1314);
    queue_push(Q,520);

    queue_show(Q);

    queue_pop(Q);
    queue_pop(Q);
    queue_pop(Q);
    
    queue_destroy(Q);

    return 0;
}

本站资源均来自互联网，仅供研究学习，禁止违法使用和商用，产生法律纠纷本站概不负责！如果侵犯了您的权益请与我们联系！

转载请注明出处：免费源码网-免费的源码资源网站 » 学习记录——day17 数据结构队列链式队列

点赞(0) 打赏

本文分类：文章资讯
本文标签：学习记录——day17 数据结构队列链式队列
浏览次数：27 次浏览
本文链接：https://freeymw.com/article/19450.html

上一篇 > 机器学习 - 决策树
下一篇 > 【Python机器学习】决策树的构造——递归构建决策树

评论列表共有 0 条评论

暂无评论

学习记录——day17 数据结构 队列 链式队列

队列介绍

顺序队列

循环顺序队列

1、创建

2、判空判满

3、插入

4、遍历

5、出队

6、求实际大小

7、销毁

8、完整代码

链式队列

00.h

00.c

main.c

评论列表 共有 0 条评论

发表评论 取消回复

学习记录——day17 数据结构队列链式队列

评论列表共有 0 条评论

发表评论取消回复