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; } 如有疑問請留言或者到本站社區交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
