奎屯市住房和城乡建设局网站,做面料那几个网站,已备案网站更换域名,做网站设计管理的专业代码参考《妙趣横生的算法.C语言实现》 文章目录前言1、队列定义2、创建一个队列3、入队列4、出队列5、销毁一个队列6、循环队列的概念7、循环队列的实现8、实例分析前言
本章总结#xff1a;链队列定义#xff0c;创建#xff0c;出队入队操作#xff0c;销毁操作#x…代码参考《妙趣横生的算法.C语言实现》 文章目录前言1、队列定义2、创建一个队列3、入队列4、出队列5、销毁一个队列6、循环队列的概念7、循环队列的实现8、实例分析前言
本章总结链队列定义创建出队入队操作销毁操作循环队列的定义以及循环队列的一些基本操作 1、队列定义
队列是一种先进先出的线性表(FIFO),它要求所有的数据从队列的一端进入从队列的另一端离开。 在队列中允许插入数据的一端角队尾允许数据离开的一端叫做队头。 队列是一个线性表既可以是一个顺序表也可以是一个链表。这里重点介绍用链表实现一个队列。
typedef char ElemType ;
//队列元素类队列中的每个元素都是QNode类
typedef struct QNode{ElemType data; //队列结点的数据域struct QNode* next; //队列结点的指针域
}QNode, *QueuePtr;typedef struct {QueuePtr front; //队头指针用来存放队头元素的地址QueuePtr rear; //队尾指针用来存放队尾元素的地址
}LinkQueue;
//这里定义得队列是一个链队列队列之间的元素由指针相连所以只要掌握了队列的队头指针和队尾指针就可以对队列进行各种2、创建一个队列
创建一个队列要完成两步 1、在内存中创建一个头结点但该头结点不是用来存放数据的而是为了操作方便人为添加的。 2、将队列的头指针和尾指针都指向这个生成的头结点此时队列中没有任何队列元素该队列为空队列。 这样判断队列为空的条件就是头指针front和尾指针rear都同时指向头结点。
//创建一个空队列
void InitQueue(LinkQueue* q)
{q-front q-rear (QueuePtr)malloc(sizeof(QNode)); //初始化一个队列指针大小的空间并将地址传给头指针和尾指针if (!q-front){printf(内存分配失败);exit(0);}q-front-next NULL; //头结点指针域指向空
}此时空队列的状态如下
3、入队列
入队列就是讲一个QNode类型的结点从队列尾部进入队列。 每当一个队列元素插入队列队列的尾指针都要进行修改。 队头的指针不改变。
//入队列
void EnQueue(LinkQueue* q,ElemType elem)
{QueuePtr p;p (QueuePtr)malloc(sizeof(QNode)); //创建一个队列元素结点并将地址传给指针pif (p NULL){printf(分配内存失败);exit(0);}p-data elem; //将数据elem放到队列结点data域中p-next NULL;q-rear-next p; //从队尾插入元素q-rear p; //修改队尾指针注意此时队尾指针指向空(q-rear-next p-next NULL)
}入队列操作流程
4、出队列
出队列操作就是将队列中的元素从队列的头部移除。每次从队列中一出数据时队头指针front不改变但是头结点的next指针要发生改变。队尾指针rear只有在(队头即队尾)的情况下才会改变否则也不改变。
//出队列
void DeQueue(LinkQueue* q, ElemType *elem)
{QueuePtr p;//如果队列不为空删除q的队头元素用e返回其值if (q-front q-rear) return; //队列为空返回p q-front-next; //p指向队列的第一个元素*elem p-data; //将队首元素数据传给eq-front-next p-next; //删除当前头结点if (q-rear p) q-rear q-front; //如果此时队列为空则修改队尾指针free(p); //将原本队头结点销毁
}效果如下 1、当队伍中存在超过1个元素 2、当队伍中只有一个元素时
5、销毁一个队列
由于队列建立在内存动态区(堆内存)因此当一个队列不再有用时应当把它及时销毁掉以免占用内存空间得不到释放导致内存泄漏。 释放一块内存要做两点1.释放指向它的指针。2.将该指针指向空
void DestroyQueue(LinkQueue* q)
{while (q-front) //如果队列头指针还存在{q-rear q-front-next; //q-rear指向q-front的后继结点free(q-front); //释放q-front,此时q-rear应该指向NULLq-front q-rear;}
}6、循环队列的概念
用顺序表实现的队列称为循环队列此队列的空间是可以循环使用的。
循环队列一般来说有固定的容量。
如果不断地有元素入队列同时又不断地有元素出队列那么对于一般的链队列只要队列不为空头指针front和尾指针rear都不会改变只有头指针的next指针和尾指针的前一个结点的next指针会发生变化而且链队列的长度也会随着入出度列元素而不断变化。
循环队列容量固定队头指针和队尾指针都可以随着元素的入出队列而发生改变这样循环队列逻辑上就是一个环形的存储空间只要队列中有空单元未使用就可以向队列中存放元素
所以循环队列可以作为缓冲池存储结构来存放数据。 该队列总容量为8B实际长度为5B。这里规定循环队列头指针front始终指向队头元素尾指针rear始终指向队尾元素的下一个空间。 这里队头元素:f,队尾元素:b该队列实际可用空间为7B。 将队首元素f出队列在队尾加入元素a形成上面队列。
所以入队列操作就是想rear指向的空间赋值rear再指向队尾元素的下一个空间。
出队列就是将队头指针front向上移一个单元。整个循环队列逻辑上就是一个首尾相接的环形缓冲区。
7、循环队列的实现
现实中只有线性的存储单元不存在环形存储单元。
只需要注意rear不断加1后超过循环队列的地址范围采用取模运算处理的结果。
因此无论是入队列的rear1操作还是出队列的front1操作实际都是模加运算即
(rear1)%len 和(front1)%len
/*****************************循环队列******************************************/
//定义一个循环队列
#define MAXQSIZE 100
typedef struct {ElemType* base; //循环队列内存分配基地址int front; //队头int rear; //队尾
}cycleQueue; //循环队列类cycleQueue//初始化一个循环队列
void InitcycleQueue(cycleQueue *q)
{q-base (ElemType*)malloc(MAXQSIZE*sizeof(ElemType));//开辟MAXQSIZE个单元的顺序表作为循环队列的存储空间if (!q-base){printf(循环队列分配内存失败);exit(0);}q-front q-rear 0; //空队列front和rear都指向0号单元}
//入队列操作
void EncycleQueue(cycleQueue* q, ElemType elem)
{if ((q-rear 1) % MAXQSIZE q-front) return; //循环队列已满q-base[q-rear] elem; //将元素elem入队列q-base为顺序表的额首地址q-rear (q-rear 1) % MAXQSIZE; //队尾指针1注意这里的全部都是模加运算
}
//出队列操作
void DecycleQueue(cycleQueue* q, ElemType* elem)
{if (q-front q-rear) return; //循环队列为空*elem q-base[q-front]; //取出队头元素q-front (q-front 1) % MAXQSIZE; //队头指针1
}
8、实例分析
实现一个链队列任意输入一串字符以为结束标志然后将队列中的元素逐一取出打印出来
#include stdio.h
#include malloc.h
#include conio.h
#include stdlib.h
#include math.h
typedef char ElemType ;
/*****************************链队列******************************************/
//队列元素类队列中的每个元素都是QNode类
typedef struct QNode{ElemType data; //队列结点的数据域struct QNode* next; //队列结点的指针域
}QNode, *QueuePtr;typedef struct {QueuePtr front; //队头指针用来存放队头元素的地址QueuePtr rear; //队尾指针用来存放队尾元素的地址
}LinkQueue;
//这里定义得队列是一个链队列队列之间的元素由指针相连所以只要掌握了队列的队头指针和队尾指针就可以对队列进行各种操作。、//创建一个空队列
void InitQueue(LinkQueue* q)
{q-front q-rear (QueuePtr)malloc(sizeof(QNode)); //初始化一个队列指针大小的空间并将地址传给头指针和尾指针if (!q-front){printf(内存分配失败);exit(0);}q-front-next NULL; //头结点指针域指向空
}
//入队列
void EnQueue(LinkQueue* q,ElemType elem)
{QueuePtr p;p (QueuePtr)malloc(sizeof(QNode)); //创建一个队列元素结点并将地址传给指针pif (p NULL){printf(分配内存失败);exit(0);}p-data elem; //将数据elem放到队列结点data域中p-next NULL;q-rear-next p; //从队尾插入元素q-rear p; //修改队尾指针注意此时队尾指针指向空(q-rear-next p-next NULL)
}
//出队列
void DeQueue(LinkQueue* q, ElemType *elem)
{QueuePtr p;//如果队列不为空删除q的队头元素用e返回其值if (q-front q-rear) return; //队列为空返回p q-front-next; //p指向队列的第一个元素*elem p-data; //将队首元素数据传给eq-front-next p-next; //删除当前头结点if (q-rear p) q-rear q-front; //如果此时队列为空则修改队尾指针free(p); //将原本队头结点销毁
}//销毁一个队列
//释放一块内存要做两点1.释放指向它的指针。2.将该指针指向空
void DestroyQueue(LinkQueue* q)
{while (q-front) //如果队列头指针还存在{q-rear q-front-next; //q-rear指向q-front的后继结点free(q-front); //释放q-front,此时q-rear应该指向NULLq-front q-rear;}
}/*****************************循环队列******************************************/
//定义一个循环队列
#define MAXQSIZE 100
typedef struct {ElemType* base; //循环队列内存分配基地址int front; //队头int rear; //队尾
}cycleQueue; //循环队列类cycleQueue//初始化一个循环队列
void InitcycleQueue(cycleQueue *q)
{q-base (ElemType*)malloc(MAXQSIZE*sizeof(ElemType));//开辟MAXQSIZE个单元的顺序表作为循环队列的存储空间if (!q-base){printf(循环队列分配内存失败);exit(0);}q-front q-rear 0; //空队列front和rear都指向0号单元}
//入队列操作
void EncycleQueue(cycleQueue* q, ElemType elem)
{if ((q-rear 1) % MAXQSIZE q-front) return; //循环队列已满q-base[q-rear] elem; //将元素elem入队列q-base为顺序表的额首地址q-rear (q-rear 1) % MAXQSIZE; //队尾指针1注意这里的全部都是模加运算
}
//出队列操作
void DecycleQueue(cycleQueue* q, ElemType* elem)
{if (q-front q-rear) return; //循环队列为空*elem q-base[q-front]; //取出队头元素q-front (q-front 1) % MAXQSIZE; //队头指针1
}//测试函数
int main()
{ElemType e;LinkQueue q;InitQueue(q); //初始化一个队列qprintf(请输入一串字符到队列中\n);scanf(%c,e);while (e ! ){EnQueue(q,e);scanf(%c, e);}printf(队列为\n);while (q.front ! q.rear){DeQueue(q, e);printf(%c,e);}printf(\n);DestroyQueue(q); //销毁队列q_getche();return 0;
}
效果
