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;
}
如有疑問請留言或者到本站社區交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
