C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之判斷循環(huán)鏈表空與滿

更新時(shí)間：2017年10月20日 10:29:36 作者：yzs87

這篇文章主要介紹了C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之判斷循環(huán)鏈表空與滿的相關(guān)資料,希望通過(guò)本文能幫助到大家，讓大家掌握這部分內(nèi)容，需要的朋友可以參考下

C語(yǔ)言數(shù)據(jù)結(jié)構(gòu)之判斷循環(huán)鏈表空與滿

前言：

何時(shí)隊(duì)列為空？何時(shí)為滿？

由于入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此，我們無(wú)法通過(guò)front=rear來(lái)判斷隊(duì)列“空”還是“滿”。

注：先進(jìn)入的為‘頭'，后進(jìn)入的為‘尾'。

解決此問(wèn)題的方法至少有三種：

其一是另設(shè)一個(gè)布爾變量以匹別隊(duì)列的空和滿；

其二是少用一個(gè)元素的空間，約定入隊(duì)前，測(cè)試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿（注意：rear所指的單元始終為空）；

其三是使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)（實(shí)際上是隊(duì)列長(zhǎng)度）。

第一種方法沒(méi)有實(shí)現(xiàn)，下面實(shí)現(xiàn)第二種和第三種：

一、少用一個(gè)元素空間，約定以“隊(duì)列頭指針front在隊(duì)尾指針rear的下一個(gè)位置上”作為隊(duì)列“滿”狀態(tài)的標(biāo)志。即：

隊(duì)空時(shí)： front=rear
隊(duì)滿時(shí)： (rear+1)%maxsize=front
front指向隊(duì)首元素，rear指向隊(duì)尾元素的下一個(gè)元素。


 
///////////////////////////////////////// 
//  
// 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; 
}

二、實(shí)例代碼：

#include <stdio.h> 
#include <assert.h> 
#define QueueSize 100 
typedef char datatype; 
//隊(duì)列的數(shù)據(jù)元素 
typedef struct 
{ 
   int front; 
   int rear; 
   int count; //計(jì)數(shù)器，用來(lái)記錄元素個(gè)數(shù) 
   datatype data[QueueSize]; //數(shù)據(jù)內(nèi)容 
}cirqueue; 
//置空隊(duì) 
void InitQueue(cirqueue *q) 
{ 
   q->front = q->rear = 0; 
   q->count = 0; 
} 

//判斷隊(duì)滿 
int QueueFull(cirqueue *q) 
{ 
   return (q->count == QueueSize); 
} 

//判斷隊(duì)空 
int QueueEmpty(cirqueue *q) 
{ 
   return (q->count == 0); 
} 

//入隊(duì) 
void EnQueue(cirqueue *q, datatype x) 
{ 
   assert(QueueFull(q) == 0); //q滿，終止程序 
 
   q->count++; 
   q->data[q->rear] = x; 
   q->rear = (q->rear + 1)%QueueSize; //循環(huán)隊(duì)列設(shè)計(jì)，防止內(nèi)存浪費(fèi) 
} 

//出隊(duì) 
datatype DeQueue(cirqueue *q) 
{ 
   datatype temp; 
 
   assert(QueueEmpty(q) == 0);//q空，則終止程序，打印錯(cuò)誤信息 
 
   temp = q->data[q->front]; 
   q->count--; 
   q->front = (q->front + 1)%QueueSize; 
   return temp; 
}

如有疑問(wèn)請(qǐng)留言或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

您可能感興趣的文章: