<强> C语言数据结构之判断循环链表空与满
<强>前言:
何时队列为空?何时为满?
由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等。因此,我们无法通过前方=后方来判断队列还“空”是“满”。
注:先进入的为“头”,后进入的为“尾”。
解决此问题的方法至少有三种:
其一是另设一个布尔变量以匹别队列的空和满;
其二是少用一个元素的空间,约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:后所指的单元始终为空),
其三是使用一个计数器记录队列中元素的总数(实际上是队列长度)。
第一种方法没有实现,下面实现第二种和第三种:
<强>一,少用一个元素空间,约定以“队列头指针前在队尾指针后的下一个位置上”作为队列“满”状态的标志。即:
,队空时:前=后
,队满时(后+ 1):%最大尺寸=前面
,指前向队首元素,后指向队尾元素的下一个元素。
/////////////////////////////////////////////作者:kangquan2008@csdn///////////////////////////////////////////# include & lt; stdio.h>
# include & lt; stdlib.h>
# include & lt; stdbool.h>
#定义QUEUE_SIZE 10
#定义EN_QUEUE 1
#定义DE_QUEUE 2
#定义退出3
typedef int项目;
typedef struct队列{
项*项;
int面前;
int泪;
}队列;
int init_queue(队列*队列)
{
队列→项=malloc (QUEUE_SIZE * sizeof(项);
如果(!队列→项)
{
printf (" % s \ n”、“Alloc失败了,没有足够的内存”);
退出(EXIT_FAILURE);
}
队列→=队列前面→泪=0;
返回1;
}
int en_queue(队列*队列项条目)
{
如果((队列→泪+ 1)% QUEUE_SIZE==队列→前)
{
printf (" % s \ n ",“队列已满”);
返回1;
}
队列→项目[队列→撕裂]=项目;
队列→泪=(队列→泪+ 1)% QUEUE_SIZE;
返回1;
}
int de_queue(队列*队列项*项)
{
如果队列→==队列前面→泪)
{
printf (" % s \ n ",“队列是空的”);
返回1;
}
(*项)=队列→项目(队列→前);
队列→前=(队列→前+ 1)% QUEUE_SIZE;
返回1;
}
int destroy_queue(队列*队列)
{自由(队列→项);
}
int main ()
{
队列是;
init_queue (,,);
int elem;
bool国旗=true;
而(国旗)
{
int选择;
printf (" de_queue en_queue 1, 2, 3退出\ r \ nplease输入:”);
scanf (“% d”,和选择);
选择开关(())
{
案例EN_QUEUE:
printf (" num输入:");
scanf (“% d”,和elem);
en_queue(和,elem);
打破;
案例DE_QUEUE:
如果(de_queue (,,, elem)==1)
printf("前面的项目是:% d \ n”, elem);
打破;
退出:
国旗=false;
打破;
默认值:
printf("错误输入\ n”);
打破;
}
}
destroy_queue (,,);
返回0;
}
之前
<强>二,实例代码:
# include & lt; stdio.h>
# include & lt; assert.h>
#定义QueueSize 100
typedef char数据类型;//队列的数据元素
类型定义结构体
{
int面前;
int后方;
int数;//计数器,用来记录元素个数
数据类型数据(QueueSize);//数据内容
}cirqueue;//置空队
空白InitQueue (cirqueue *问)
{
问→前=问→后方=0;
问→数=0;
}//判断队满
int QueueFull (cirqueue *问)
{
返回(q→数==QueueSize);
}//判断队空
int QueueEmpty (cirqueue *问)
{
返回(问→数==0);
}//入队
空队列(cirqueue * q,数据类型x)
{
断言(QueueFull (q)==0);//q满,终止程序
问→计数+ +;
问→数据(q→后方)=x;
问→后方=(q→后+ 1)% QueueSize;//循环队列设计,防止内存浪费
}//出队
数据类型出列(cirqueue *问)
{
数据类型温度;
断言(QueueEmpty (q)==0);//q空,则终止程序,打印错误信息
temp=问→数据(q→前);
问→计数,
问→前=(q→前+ 1)% QueueSize;
返回临时;
}
