­

【自考】数据结构第三章，队列，期末不挂科指南，第4篇

  • 2020 年 1 月 26 日
  • 筆記

队列

这篇博客主要介绍一下队列的概念，并且采用C语言，编写两种存储实现方式：顺序存储和链式存储，当然还有常规的队列基本操作的实现算法

队列基本概念

标准解释：队列（Queue）是有限个同类型数据元素的线性序列，是一种先进先出（First In First Out FIFO）的线性表，新键入的数据元素插在队列尾端，出队列的数据元素在队列首部被删除。

教材中给了一个示意图，不错

顺序队列结构类型中有三个域：data、front、rear。

data:一维数组，存储队列中的数据元素 font：指向队列首元素的前一个单元 rear：指向实际的队列尾元素单元

参考示意图

入队列操作可以用两条赋值语句

SQ.rear = SQ.rear+1;  SQ.data[SQ.rear] = x;

出队列操作可以用一条语句完成

SQ.front = SQ.front+1

但是，会出现一些问题，通过示意图说明一下

当然还有一种情况，一边入队列，一边出队列 注意下图，SQ.front下面还有空间

所以为了解决这种假溢出问题，聪明的开发人员，想出来新的解决办法了，造一个环儿~

循环队列

下面看一个图，重点看一下SQ.rear与SQ.front的对应位置

如果上述图翻译成C语言代码，入队核心逻辑为

SQ.rear = (SQ.rear+1) % maxsize ;  SQ.data[SQ.rear] = x;

出队列的核心逻辑为

SQ.front = (SQ.front+1)%maxsize;

你在学习的时候，肯定对SQ.rear+1和SQ.front+1有疑问

我们举例来说明一下吧

顺序队列的C语言实现

接下来难度指数上升，开始用C语言编写代码吧

一顿操作之后，还是比较简单的，总之不写链式存储，顺序的还是比较简单的

#include <stdio.h>  #include <stdlib.h>    //循环队列最大数据元素个数  const int maxsize = 8;    //循环队列的结构体  typedef struct cycqueue{      int *data;      int front,rear;  } CycQue;      //队列初始化  void init(CycQue *CQ){      CQ->data = (int *)malloc(maxsize*sizeof(int));      CQ->front = 0;      CQ->rear = 0;  }      //判断队列是否为空  int empty(CycQue *CQ){      if(CQ->rear==CQ->front) return 1;      else return 0;  }      //入队列  int EnQueue(CycQue *CQ,int x){      if((CQ->rear+1)%maxsize==CQ->front){          printf("队列满");          return 0;      }      else{          CQ->rear =(CQ->rear+1) % maxsize;          CQ->data[CQ->rear] = x;          return 1;      }    }    //出队列  int OutQueue(CycQue *CQ){      if(empty(CQ)){          printf("队列为空");          return 0;      }      else{          CQ->front = (CQ->front+1) % maxsize;          return 1;        }    }    int main()  {      CycQue CQ;      init(&CQ);        EnQueue(&CQ,2);      EnQueue(&CQ,4);      printf("%d",CQ.rear);      OutQueue(&CQ);      printf("%d",CQ.front);      return 0;  }

链式队列的C语言实现

链式队列其实有之前的经验之后，写起来难度系数也不会太高，接下来我们编写一个核心的部分代码

队列的链接实现实际上是用一个带有头结点的单链表来表示队列，成为链队列 头指针指向链表的头结点 单链表的头结点的next域指向队列首结点 尾指针指向队列尾结点，即单链表的最后一个结点

初始化

#include <stdio.h>  #include <stdlib.h>  typedef struct LinkQueueNode{      int *data;      struct LinkQueueNode *next;  } LkQueNode;    typedef struct LkQueue{      LkQueNode *front,*rear;  } LkQue;      void init(LkQue *LQ){      LkQueNode *temp;      temp = (LkQueNode *)malloc(sizeof(LkQueNode)); //生成队列的头结点      LQ->front = temp;    //队列头指针指向队列头结点      LQ->rear = temp;     //队列尾指针指向队列尾结点      (LQ->front)->next = NULL;    }

核心两个操作入队列和出队列

入队列代码如下

//入队列  void EnQueue(LkQue *LQ,int x){        LkQueNode *temp;      temp = (LkQueNode *)malloc(sizeof(LkQueNode));      temp->data = x;      temp-next = NULL;      (LQ->rear)->next = temp;      LQ->rear = temp;  }

出队列这个事情就交给你自己吧，好好理解一下，就可以写出来了

VirMach 便宜 VPS

QNews

QNews