C语言数据结构之判断循环链表空与满

C语言数据结构之判断循环链表空与满

前言:

何时队列为空?何时为满?

由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等。因此,我们无法通过front=rear来判断队列“空”还是“满”。

注:先进入的为‘头',后进入的为‘尾'。

解决此问题的方法至少有三种:

其一是另设一个布尔变量以匹别队列的空和满;

其二是少用一个元素的空间,约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始终为空);

其三是使用一个计数器记录队列中元素的总数(实际上是队列长度)。

第一种方法没有实现,下面实现第二种和第三种:

一、少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即:

队空时: front=rear
  队满时: (rear+1)%maxsize=front
  front指向队首元素,rear指向队尾元素的下一个元素。

/////////////////////////////////////////
//
// author: kangquan2008@csdn
//
/////////////////////////////////////////
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h> 

#define QUEUE_SIZE 10
#define EN_QUEUE 1
#define DE_QUEUE 2
#define EXIT   3 

typedef int  Item;
typedef struct QUEUE{ 

  Item * item;
  int front;
  int tear; 

}Queue; 

int init_queue(Queue * queue)
{
  queue->item = malloc(QUEUE_SIZE * sizeof(Item));
  if(!queue->item)
  {
    printf("%s\n","Alloc failed,not memory enough");
    exit(EXIT_FAILURE);
  } 

  queue->front = queue->tear = 0; 

  return 1;
} 

int en_queue(Queue * queue, Item item)
{
  if((queue->tear+1) % QUEUE_SIZE == queue->front)
  {
    printf("%s\n","The queue is full");
    return -1;
  } 

  queue->item[queue->tear] = item;
  queue->tear = (queue->tear + 1) % QUEUE_SIZE; 

  return 1;
} 

int de_queue(Queue * queue, Item * item)
{
  if(queue->front == queue->tear)
  {
    printf("%s\n","The queue is empty");
    return -1;
  } 

  (*item) = queue->item[queue->front];
  queue->front = (queue->front + 1) % QUEUE_SIZE; 

  return 1;
} 

int destroy_queue(Queue * queue)
{ free(queue->item);
} 

int main()
{
  Queue que;
  init_queue(&que);
  int elem;
  bool flag = true;
  while(flag)
  {
    int choice;
    printf("1 for en_queue,2 for de_queue,3 for exit\r\nplease input:");
    scanf("%d",&choice); 

    switch((choice))
    {
      case EN_QUEUE:
        printf("input a num:");
        scanf("%d",&elem);
        en_queue(&que,elem);
        break;
      case DE_QUEUE:
        if(de_queue(&que,&elem) == 1)
          printf("front item is:%d\n",elem);
        break;
      case EXIT:
        flag = false;
        break;
      default:
        printf("error input\n");
        break;
    }
  } 

  destroy_queue(&que);
  return 0;
}

二、 实例代码:

#include <stdio.h>
#include <assert.h>
#define QueueSize 100
typedef char datatype;
//队列的数据元素
typedef struct
{
   int front;
   int rear;
   int count; //计数器,用来记录元素个数
   datatype data[QueueSize]; //数据内容
}cirqueue;
//置空队
void InitQueue(cirqueue *q)
{
   q->front = q->rear = 0;
   q->count = 0;
} 

//判断队满
int QueueFull(cirqueue *q)
{
   return (q->count == QueueSize);
} 

//判断队空
int QueueEmpty(cirqueue *q)
{
   return (q->count == 0);
} 

//入队
void EnQueue(cirqueue *q, datatype x)
{
   assert(QueueFull(q) == 0); //q满,终止程序 

   q->count++;
   q->data[q->rear] = x;
   q->rear = (q->rear + 1)%QueueSize; //循环队列设计,防止内存浪费
} 

//出队
datatype DeQueue(cirqueue *q)
{
   datatype temp; 

   assert(QueueEmpty(q) == 0);//q空,则终止程序,打印错误信息 

   temp = q->data[q->front];
   q->count--;
   q->front = (q->front + 1)%QueueSize;
   return temp;
}

如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

(0)

相关推荐

  • C++数据结构之链表的创建

    C++数据结构之链表的创建 前言 1.链表在C/C++里使用非常频繁, 因为它非常使用, 可作为天然的可变数组. push到末尾时对前面的链表项不影响. 反观C数组和std::vector, 一个是静态大小, 一个是增加多了会对之前的元素进行复制改写(线程非常不安全). 2.通常创建链表都是有next这样的成员变量指向下一个项, 通过定义一个head,last来进行链表创建. 参考函数 TestLinkCreateStupid(). 说明 1.其实很早就知道另一种创建方式, 但是一直没总结. 没

  • C语言数据结构之串插入操作

    C语言数据结构之串插入操作 实例代码: /* 串的堆分配存储表示 */ #include<stdio.h> #include<string.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define OVERFLOW -2 typedef int Status; typedef struct { char *ch; //如果是非空串,则按串长分配存储区

  • C语言数据结构之二叉树的非递归后序遍历算法

    C语言数据结构之二叉树的非递归后序遍历算法 前言: 前序.中序.后序的非递归遍历中,要数后序最为麻烦,如果只在栈中保留指向结点的指针,那是不够的,必须有一些额外的信息存放在栈中. 方法有很多,这里只举一种,先定义栈结点的数据结构 typedef struct{Node * p; int rvisited;}SNode //Node 是二叉树的结点结构,rvisited==1代表p所指向的结点的右结点已被访问过. lastOrderTraverse(BiTree bt){ //首先,从根节点开始,

  • C语言数据结构递归之斐波那契数列

    C语言数据结构递归之斐波那契数列 因为自己对递归还是不太熟练,于是做POJ1753的时候就很吃力,就是翻棋子直到棋盘上所有棋子的颜色一样为止,求最少翻多少次,方法是枚举递归.然后就打算先做另一道递归的题(从数组中取出n个元素的组合),但是同样在递归的问题上不太理解.好吧,于是复习CPP,在第229页的时候,看到了斐波那契数列,回想起之前做过的一道题目,发现可以用递归的方法来做.于是决定优化一下之前的代码. 以下这段摘自<C primer plus> 斐波那契数列的定义如下:第一个和第二个数字都

  • C语言数据结构中定位函数Index的使用方法

    数据结构中定位函数Index的使用方法 实现代码: #include<stdio.h> #include<string.h> #include<stdlib.h> #define OK 1 #define ERROR 0 #define TRUE 1 #define FALSE 0 #define MAXSIZE 40 //最大字符串 typedef int Status; typedef char SString[MAXSIZE+1]; //此处声明的SString[

  • C语言数据结构之判断循环链表空与满

    C语言数据结构之判断循环链表空与满 前言: 何时队列为空?何时为满? 由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等.因此,我们无法通过front=rear来判断队列"空"还是"满". 注:先进入的为'头',后进入的为'尾'. 解决此问题的方法至少有三种: 其一是另设一个布尔变量以匹别队列的空和满: 其二是少用一个元素的空间,约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始

  • C语言数据结构之双向循环链表的实例

    数据结构之双向循环链表 实例代码: #include <stdlib.h> #include <stdio.h> #include <malloc.h> typedef struct Node{ struct Node *pNext; int data; struct Node *prior; } NODE,*PNODE; PNODE CreatList(); void TreNode(PNODE pHead); bool isEmpty(PNODE pHead); i

  • java数据结构循环队列的空满判断及长度计算

    目录 一.假溢出 二.循环队列判断是空是满 三.循环队列的长度计算 四.代码实现 在上一章中,使用了数组模拟了队列.但是留下的问题是,把数据取完后,再往里加数据就不行了. 一.假溢出 这是因为数组的末尾已经被占用了,入队会继续在数组后面增加,于是产生数组越界.但是实际上,数组里是有空闲位置的,这种也可以叫“假溢出”. 为了解决“假溢出”的问题,于是乎有了循环队列. 既然数组后面满了,头部有空,那继续加进来的元素从头开始放即可. 接着上图,这时候有a6入队,于是rear的下标指向a6的下一个元素位

  • C语言数据结构之循环链表的简单实例

     C语言数据结构之循环链表的简单实例 实例代码: # include <stdio.h> # include <stdlib.h> typedef struct node //定义链表中结点的结构 { int code; struct node *next; }NODE,*LinkList; /*错误信息输出函数*/ void Error(char *message) { fprintf(stderr,"Error:%s/n",message); exit(1)

  • C语言编程数据结构带头双向循环链表全面详解

    目录 前言 一.什么是带头循环双向链表 二.链表初始化 三.链表接口函数 1.尾插 2.头插 3.头删 4.尾删 5.任意位置插入数据 6.任意位置删除数据 四.打印链表 总结 前言 上一篇数据结构专栏:C语言数据结构单链表接口函数全面讲解教程 我们介绍了单链表的各个接口函数,大家可能会发现单链表存在一些缺陷:比如它一个节点要存储数据+下一个节点地址,占用的空间要远多于顺序表:并且由于单链表是无法从后往前找的,如果你想进行尾删这样的操作,你必须从第一个节点往后找,你的时间复杂度一定是O(n).

  • C语言实现带头双向循环链表

    目录 前言 1. 创建结构体 2.malloc新节点 3.创建哨兵位节点 4.尾插 5.打印 6.尾删 7.头插 8.在指定位置pos的前面进行插入 9. 删除指定位置pos节点 10.销毁链表 前言 在实际生活中最常用的就是这两种链表.无头单向非循环链表.和带头双向循环链表.无头单向非循环链表:结构简单,一般不会单独用来存数据.实际中更多是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.另外这种结构在笔试面试中出现很多.带头双向循环链表:结构最复杂,一般用在单独存储数据.实际中使用的链表数

  • C语言中带头双向循环链表基本操作的实现详解

    目录 一.概念与结构 二.基本操作的实现 1.创建结点 2.初始化链表 3.打印链表 4.尾插 5.尾删 6.头插 7.头删 8.查找某个数并返回其指针 9.在某个位置之前插入 10.删除某个位置 11.判断链表是否为空 12.计算链表中有效值的个数 13.销毁链表 三.测试代码 一.概念与结构 无头单向非循环链表结构简单,一般不会单独用来存数据.实际中更多的是作为其他数据结构的子结构,如哈希桶.图的邻接表等等.而带头双向循环链表的结构较为复杂,一般用在单独存储数据.实际中使用的链表数据结构,都

  • C语言数据结构链表队列的实现

    C语言数据结构链表队列的实现 1.写在前面 队列是一种和栈相反的,遵循先进先出原则的线性表. 本代码是严蔚敏教授的数据结构书上面的伪代码的C语言实现代码. 分解代码没有包含在内的代码如下: #include <stdio.h> #include <stdlib.h> #define OK 1 #define ERROR 0 typedef int QElemtype; typedef int status; 2.代码分解 2.1对队列和节点的结构定义 typedef struct

  • C语言 数据结构之连续存储数组的算法

    数据结构之数组定义及基本操作 数据结构中最基本的一个结构就是线性结构,而线性结构又分为连续存储结构和离散存储结构.所谓的连续存储结构其实就是数组. 数组本质其实也是数据的一种存储方式,既然有了数据的存储,就会涉及到如何对数据进行寻址的问题.首先,先说一下在数组中数据是如何存储的,在内存中,数组中的数据是以一组连续的数据集合的形式存在于内存中.当我们访问存在于内存中的数组时,我们应该找到其在内存中的地址,当我们找到数据的地址后我们就可以找到对应的数据.了解了以上知识后,我们就可以进行数组的设计了(

  • C语言 数据结构之中序二叉树实例详解

    C语言数据结构 中序二叉树 前言: 线索二叉树主要是为了解决查找结点的线性前驱与后继不方便的难题.它只增加了两个标志性域,就可以充分利用没有左或右孩子的结点的左右孩子的存储空间来存放该结点的线性前驱结点与线性后继结点.两个标志性域所占用的空间是极少的,所有充分利用了二叉链表中空闲存的储空间. 要实现线索二叉树,就必须定义二叉链表结点数据结构如下(定义请看代码): left leftTag data rightTag right 说明: 1.       leftTag=false时,表示left

随机推荐