首页天道酬勤简要叙述循环队列的数据结构,排序数据结构

简要叙述循环队列的数据结构,排序数据结构

张世龙 05-06 11:41 119次浏览

队列分为顺序队列和循环队列。 有多种方法可以实现顺序队列,包括数组和链表。 数组实现包括团队领导的前端、rear实现和使用变量size统计实现队列元素大小。 然后,对于size实现的序列队列(同时实现了数组和链表),已经实现了以前的数据结构文章。

排队可以通过排队买票来理解。

在谈论排队前,先谈谈排队的假溢出吧。

1序列队列的假溢出

1 :初始化空队列,假设q - front=q - rear=0。

2 )进入小组a1、a2、a3,q - front=0,q - rear=3。

3 )退出队伍a1、a2、q - front=2、q - rear=3。

4 )进入小组a4、a5、a6、q - front=2、q - rear=6。

但是,执行4操作后,队列的“末尾指针”超出了队列的最大范围,然后无法入队操作,队列的实际空间未满,导致了假溢出。

解决上述溢出的方法是将团队中的元素按顺序移动到团队的开头。 队列空间是指如果分配给队列的m个存储器单元可以重用且rear指定MAXSIZE,则如果队列开头为空闲,则可以从开头使用空闲空间的循环表。 前端为MAXSIZE时也是如此。 我们采用了第二种方法,所以下一步如下。

5 )入队a7,q - front=2,q - rear=0。

2环路队列根据上述说明,为了解决顺序队列的假溢出,需要引入环路队列进行解决。循环队列概念:

无论是插入还是删除,如果rear增加1,或者前端增加1,超过分配的空间,则指向该空间的起始地址。实现方法: 利用 模或者称为取余(mod,C语言中:%)运算。

2.1 插入元素

//队友q - base[q - rear]=data; //团队指针q-rear=(q-rear1) % MAXSIZE;2.2 删除元素

无论是插入还是删除,都要加1来去除剩下的。

//团队领导者data=q - base[q - front]; //小组头指针q-front=(q-front1) % MAXSIZE; 3熟悉解决循环队列空判决、满判决冲突的循环队列的人都知道,如果循环队列空或满,前端都等于rear。 例如,在上面的示例中,如果最初为空,则front=rear=0,如果满足六个元素,则返回rear=5 1%6=0。

解决方案:

1 )为区分队伍空缺、满员,另设标致位。 2 )设置其他变量,记录要素个数。 3 )不使用一个元素空间。 本文实现的方法是第三种,但个人在实际使用时倾向于使用第二种。 那是因为容易理解。

下图显示了在队列中减少一个空间时,如果队列已满,则始终为(q-rear 1) %MAXSIZE=q-front。 另一方面,空的情况下front=rear,区分循环队列满的情况和空的情况。

3.1 循环队列常规操作

/**************循环队列的正常操作* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *。 //循环队列为int QueueEmpty (); //循环队列为空的int QueueLength (); //循环队列长度(元素数) int EnQueue ); //循环队列入队int DeQueue (; //循环退出void QueueStatus (); //打印团队已满,团队已空,队长状态/* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *。

# include ' stdio.h ' # include ' malloc.h ' # define true1# define false0# define maxsize 10 typedefintelemtype; //循环队列结构类型结构队列{ int * base; //队列的起始地址int front; //队列头下int rear; //队列尾号}QueObj,*Queue; //结构对象和

结构体指针的形式。

3.3 初始化循环队列

/* * 初始化循环队列*/Queue InitQueue() {Queue q;q = malloc(sizeof(QueObj));// 分配循环队列空间q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);q->front = q->rear = 0;return q;}

3.4 释放循环队列

/** 释放队列结构体*/void FreeQueue(Queue q) {if (NULL != q) {if (NULL != q->base) {free(q->base);q->base = NULL;}free(q);q = NULL;}}

3.5 循环队列判满
注意,循环队列判满是我们上述说的少用一个元素空间的关键,因为它预先进行了+1操作,这样就能保证当rear指向队列尾部时,若再加1取余为0,说明队列为满。例如上述,当rear=5时,由于此时还没存进元素,所以下一次插入元素时,rear=(5+1)%6==q->front,即等于0,所以此时队列为满,即6个空间存进了5个元素。
具体看下面的例子。

/* * 循环队列判满 * q 循环队列*/int QueueFull(Queue q) {if (q == NULL) {return FALSE;}return (q->rear + 1) % MAXSIZE == q->front;}

3.6 循环队列判空

/* * 循环队列判空 * q 循环队列*/int QueueEmpty(Queue q) {if (q == NULL) {return FALSE;}return q->front == q->rear;}

3.7 计算循环队列的长度
按照正常逻辑,计算队列长度只需要队尾减去队头即可,但是由于是循环队列,可能存在front大,rear小运算得出负数的情况,所以必须通过加上MAXSIZE再取余保证队列的大小为正数。

/* * 计算循环队列长度 * q 循环队列*/int QueueLength(Queue q) {if (q == NULL) {return FALSE;}return (q->rear - q->front + MAXSIZE) % MAXSIZE;}

3.8 循环队列入队(EnQueue)
下面可以看到,每次入队前都会判断循环队列是否为满,QueueFull与EnQueue是保证队列少一元素的关键。

/* * 循环队列 入队 * q 循环队列 * data 入队元素*/int EnQueue(Queue q, ElemType data) {if (QueueFull(q)) {return FALSE;}// 队尾入队q->base[q->rear] = data;// 更新队尾指针q->rear = (q->rear + 1) % MAXSIZE;return TRUE;}

3.9 循环队列出队(DeQueue)

/* * 循环队列 出队 * q 循环队列 * *val 用来存出队元素的数据*/int DeQueue(Queue q, ElemType *val) {if (QueueEmpty(q)) {return FALSE;}// 队头元素出队*val = q->base[q->front];// 更新队头指针q->front = (q->front + 1) % MAXSIZE;return TRUE;}

3.10 打印队满、队空、队长状态

/* * 打印队满、队空、队长状态 * q 顺序队列*/void QueueStatus(Queue q) {printf("QueueFull():%d\n", QueueFull(q));printf("QueueEmpty():%d\n", QueueEmpty(q));printf("QueueLength():%d\n", QueueLength(q));}

3.11 打印队列中的元素

/* * 打印队列中的元素*/void PrintQueue(Queue q) {if (NULL == q || NULL == q->base) {return;}if (QueueEmpty(q)) {printf("Current element of array is NULL\n");return;}//注意,由于我们判断队列满的时侯是进行+1判断的(看QueueFull函数),所以这里必须-1打印元素//若不减1,则队列尾部的元素为很大的负数for (int i = 0; i < MAXSIZE - 1; i++) {printf("%d ", q->base[i]);}printf("\n");} 4 循环队列的测试 #include "stdio.h"#include "malloc.h"#define TRUE 1#define FALSE 0#define MAXSIZE 10typedef int ElemType;// 定义循环队列结构体typedef struct Queue {int *base;// 队列首地址int front;// 队列头下标int rear;// 队列尾下标}QueObj,*Queue;/* * 初始化循环队列*/Queue InitQueue() {Queue q;q = malloc(sizeof(QueObj));// 分配循环队列空间q->base = (ElemType *)malloc(sizeof(ElemType) * MAXSIZE);q->front = q->rear = 0;return q;}/** 释放队列结构体*/void FreeQueue(Queue q) {if (NULL != q) {if (NULL != q->base) {free(q->base);q->base = NULL;}free(q);q = NULL;}}/* * 循环队列判满 * q 循环队列*/int QueueFull(Queue q) {if (q == NULL) {return FALSE;}return (q->rear + 1) % MAXSIZE == q->front;}/* * 循环队列判空 * q 循环队列*/int QueueEmpty(Queue q) {if (q == NULL) {return FALSE;}return q->front == q->rear;}/* * 计算循环队列长度 * q 循环队列*/int QueueLength(Queue q) {if (q == NULL) {return FALSE;}return (q->rear - q->front + MAXSIZE) % MAXSIZE;}/* * 循环队列 入队 * q 循环队列 * data 入队元素*/int EnQueue(Queue q, ElemType data) {if (QueueFull(q)) {return FALSE;}// 队尾入队q->base[q->rear] = data;// 更新队尾指针q->rear = (q->rear + 1) % MAXSIZE;return TRUE;}/* * 循环队列 出队 * q 循环队列 * *val 用来存出队元素的数据*/int DeQueue(Queue q, ElemType *val) {if (QueueEmpty(q)) {return FALSE;}// 队头元素出队*val = q->base[q->front];// 更新队头指针q->front = (q->front + 1) % MAXSIZE;return TRUE;}/* * 打印队满、队空、队长状态 * q 顺序队列*/void QueueStatus(Queue q) {printf("QueueFull():%d\n", QueueFull(q));printf("QueueEmpty():%d\n", QueueEmpty(q));printf("QueueLength():%d\n", QueueLength(q));}/* * 打印队列中的元素*/void PrintQueue(Queue q) {if (NULL == q || NULL == q->base) {return;}if (QueueEmpty(q)) {printf("Current element of array is NULL\n");return;}//注意,由于我们判断队列满的时侯是进行+1判断的(看QueueFull函数),所以这里必须-1打印元素//若不减1,则队列尾部的元素为很大的负数for (int i = 0; i < MAXSIZE - 1; i++) {printf("%d ", q->base[i]);}printf("\n");}int main(int argc, char const *argv[]){Queue q = InitQueue();printf("QueueMaxSize: %d\n", MAXSIZE);QueueStatus(q); // 打印队满、队空、队长状态PrintQueue(q);printf("\n\n");// 入队printf("EnQueue():");for (int i = 1; i < MAXSIZE * 2; i += 2) {EnQueue(q, i);}printf("\n");QueueStatus(q);PrintQueue(q);printf("\n\n");// 出队int val;printf("DeQueue():");while (!QueueEmpty(q)) {DeQueue(q, &val);}printf("\n");QueueStatus(q);PrintQueue(q);printf("\n\n");// 测试循环队列是否会假溢出//结果不会,因为此时rear=front=9,当执行(q->rear + 1) % MAXSIZE == q->front;会返回0//所以EnQueue可以往队列中插入元素返回1。然后更新rear=1,也就说rear不会由9变成10造成假溢出。int num = 20;printf("EnQueue(%d): %d\t(0 mean Failed, 1 mean Success)\n", num, EnQueue(q, num));QueueStatus(q);//释放FreeQueue(q);return 0;}

程序结果如下:

5 总结循环队列 1)关于循环队列的原理和实现我们已经熟悉,但是个人认为在实现循环队列时更建议使用变量区分判满和判空,优点有队列能保证有多大就存多大的元素,并且更容易理解。2)而使用少一个元素空间,其关键在于判断满时预先+1取余判断,虽然可以少一个变量区分判满判空,但是不习惯的可能不易于理解。

参考文章:
C语言实现循环队列

数据结构循环队列删除所有奇数,串数据结构