C语言数据结构之判断循环链表空与满

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

如有疑问请留言或者到本站社区交流讨论,感谢阅读,希望能帮助到大家,谢谢大家对本站的支持!

声明:本文内容来源于网络,版权归原作者所有,内容由互联网用户自发贡献自行上传,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任。如果您发现有涉嫌版权的内容,欢迎发送邮件至:notice#cainiaojc.com(发邮件时,请将#更换为@)进行举报,并提供相关证据,一经查实,本站将立刻删除涉嫌侵权内容。