C语言数据结构之判断循环链表空与满
C语言数据结构之判断循环链表空与满
前言：
何时队列为空？何时为满？
由于入队时尾指针向前追赶头指针，出队时头指针向前追赶尾指针，故队空和队满时头尾指针均相等。因此，我们无法通过front=rear来判断队列“空”还是“满”。
注：先进入的为‘头'，后进入的为‘尾'。
解决此问题的方法至少有三种：
其一是另设一个布尔变量以匹别队列的空和满；
其二是少用一个元素的空间，约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满（注意：rear所指的单元始终为空）；
其三是使用一个计数器记录队列中元素的总数（实际上是队列长度）。
第一种方法没有实现，下面实现第二种和第三种：
一、少用一个元素空间，约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即：
队空时：front=rear
队满时：(rear+1)%maxsize=front
front指向队首元素，rear指向队尾元素的下一个元素。
///////////////////////////////////////// // //author:kangquan2008@csdn // ///////////////////////////////////////// #include#include #include #defineQUEUE_SIZE10 #defineEN_QUEUE1 #defineDE_QUEUE2 #defineEXIT3 typedefintItem; typedefstructQUEUE{ Item*item; intfront; inttear; }Queue; intinit_queue(Queue*queue) { queue->item=malloc(QUEUE_SIZE*sizeof(Item)); if(!queue->item) { printf("%s\n","Allocfailed,notmemoryenough"); exit(EXIT_FAILURE); } queue->front=queue->tear=0; return1; } inten_queue(Queue*queue,Itemitem) { if((queue->tear+1)%QUEUE_SIZE==queue->front) { printf("%s\n","Thequeueisfull"); return-1; } queue->item[queue->tear]=item; queue->tear=(queue->tear+1)%QUEUE_SIZE; return1; } intde_queue(Queue*queue,Item*item) { if(queue->front==queue->tear) { printf("%s\n","Thequeueisempty"); return-1; } (*item)=queue->item[queue->front]; queue->front=(queue->front+1)%QUEUE_SIZE; return1; } intdestroy_queue(Queue*queue) {free(queue->item); } intmain() { Queueque; init_queue(&que); intelem; boolflag=true; while(flag) { intchoice; printf("1foren_queue,2forde_queue,3forexit\r\npleaseinput:"); scanf("%d",&choice); switch((choice)) { caseEN_QUEUE: printf("inputanum:"); scanf("%d",&elem); en_queue(&que,elem); break; caseDE_QUEUE: if(de_queue(&que,&elem)==1) printf("frontitemis:%d\n",elem); break; caseEXIT: flag=false; break; default: printf("errorinput\n"); break; } } destroy_queue(&que); return0; }
二、 实例代码：
#include#include #defineQueueSize100 typedefchardatatype; //队列的数据元素 typedefstruct { intfront; intrear; intcount;//计数器，用来记录元素个数 datatypedata[QueueSize];//数据内容 }cirqueue; //置空队 voidInitQueue(cirqueue*q) { q->front=q->rear=0; q->count=0; } //判断队满 intQueueFull(cirqueue*q) { return(q->count==QueueSize); } //判断队空 intQueueEmpty(cirqueue*q) { return(q->count==0); } //入队 voidEnQueue(cirqueue*q,datatypex) { assert(QueueFull(q)==0);//q满，终止程序 q->count++; q->data[q->rear]=x; q->rear=(q->rear+1)%QueueSize;//循环队列设计，防止内存浪费 } //出队 datatypeDeQueue(cirqueue*q) { datatypetemp; assert(QueueEmpty(q)==0);//q空，则终止程序，打印错误信息 temp=q->data[q->front]; q->count--; q->front=(q->front+1)%QueueSize; returntemp; }
如有疑问请留言或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！