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

时间:2021-09-13 08:14:07

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

前言:

何时队列为空?何时为满?

由于入队时尾指针向前追赶头指针,出队时头指针向前追赶尾指针,故队空和队满时头尾指针均相等。因此,我们无法通过front=rear来判断队列“空”还是“满”。

注:先进入的为‘头',后进入的为‘尾'。

解决此问题的方法至少有三种:

其一是另设一个布尔变量以匹别队列的空和满;

其二是少用一个元素的空间,约定入队前,测试尾指针在循环意义下加1后是否等于头指针,若相等则认为队满(注意:rear所指的单元始终为空);

其三是使用一个计数器记录队列中元素的总数(实际上是队列长度)。

第一种方法没有实现,下面实现第二种和第三种:

一、少用一个元素空间,约定以“队列头指针front在队尾指针rear的下一个位置上”作为队列“满”状态的标志。即:

  队空时: front=rear
  队满时: (rear+1)%maxsize=front
  front指向队首元素,rear指向队尾元素的下一个元素。

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
/////////////////////////////////////////
// 
// 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;
}

二、 实例代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#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;
}

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

原文链接:http://blog.csdn.net/yanzongshuai/article/details/11883625