软件开发|编程技术|编程代码|编程入门先学什么—程序设计语言

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

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