目录
一，关于链式队列程序编写的简要说明
二，linkqueue.h头文件
三，关键函数代码与详解
1.创建空的链式队列
2.入队
3.出队
4.销毁链式队列
四，linkqueue.c文件详细代码
一，关于链式队列程序编写的简要说明
学习链式队列之前，我们已经详细了解了链式表和顺序队列，链式队列的程序编写方式正好是结合了链式表和顺序队列的特点；
由“链式”我们可知队列中的每一个节点一定有一个数据域data和一个指针域next，队列中节点和节点之间通过指针域进行连接，并且还包含一个数据域为空的头节点；
由“队列”可知，队列中包含一个头指针front和一个尾指针rear，分别指向头节点和尾节点；除此之外，还需要一个长度变量len，用来计算队列的长度。
以上就是链式队列中的结构体内需要定义的成员变量。
二，linkqueue.h头文件
头文件中需要定义两个结构体，一个是包含了节点中数据域和指针域的结构体"link_t"，一个是包含了头指针front，尾指针rear和队列长度len的结构体"queue_t"。
头指针和尾指针的数据类型必须和节点的数据类型相同，这样才能指向节点。
#ifndef _LINKQUEUE_H_
#define _LINKQUEUE_H_
//队列节点结构体
typedef int datatype;
typedef struct link_mode
{
datatype data;
struct link_node *next;
}link_t;
//描述队列节点信息的结构体
typedef struct
{
link_t *front;
link_t *rear;
int len;
}queue_t;
//1.创建一个空的链式队列
queue_t *CreateQueue(void);
//2.入队
int IntoQueue(queue_t *p,datatype data);
//3.出队
datatype OutQueue(queue_t *p);
//4.判断是否为空
int isEpQueue(queue_t *p);
//5.计算队列长度
int LengthQueue(queue_t *p);
//6.清空队列
int ClearQueue(queue_t *p);
//7.销毁队列
void DestoryQueue(queue_t **p);
#endif
三，关键函数代码与详解
1.创建空的链式队列
首先需要先开辟包含头指针和尾指针的堆区空间，后面我们才能让它们指向创建的空的头节点，
创建头节点后，将头节点的指针域指向NULL，表示队列为空，最后将队列长度赋值为0。
//1.创建一个空的链式队列
queue_t *CreateQueue(void)
{
//1.创建头尾指针的内存空间
queue_t *p = (queue_t *)malloc(sizeof(queue_t));
if(NULL == p)
{
printf("CreateQueue fail\n");
return NULL;
}
//2.创建头节点，并让头尾指针指向它
p->front=p->rear=(link_t *)malloc(sizeof(link_t));
if(p->front == NULL)
{
printf("malloc head node fail\n");
return NULL;
}
//3.初始化头节点，指针域指向空
p->front->next = NULL;
//4.初始化长度
p->len = 0;
return p;
}
2.入队
入队时，也就是向队尾插入数据时，我们要新开辟一个节点空间，并对其进行初始化(赋指定值，指向NULL)，每插入一个数据，尾指针的指向就要发生变化，在新节点插入之前，当前尾节点的指针域要指向新节点，然后再将尾指针指向新节点。
//2.入队
int IntoQueue(queue_t *p,datatype data)
{
//1.开辟新节点内存空间
link_t *pnew = (link_t *)malloc(sizeof(link_t));
if(NULL == pnew)
{
printf("malloc pnew fail\n");
return -1;
}
//2.初始化新节点
pnew->data = data;
pnew->next = NULL;
//3.当前尾节点指向的节点指针域指向新节点
p->rear->next = pnew;
//4.尾节点向后移动，移动到新节点的位置，队列长度加一
p->rear = pnew;
p->len++;
return 0;
}
3.出队
链式队列的数据出队，就是将队首节点(不是头节点)的数据输出，并将当前的头节点释放；
首先需要定义一个保存头节点的指针pdel，将该指针pdel指向队列当前的头节点A；然后将头指针指向头节点的下一个节点B，我们要输出的就是头指针现在指向的节点B的数据，要释放的就是头节点A；
为什么要释放头节点A？为什么释放了头节点A下一个节点B就是新的头节点了呢，因为头指针指向的是要输出数据的节点B，头节点A被释放后，我们还需要找一个节点作为头节点，循环上述操作，很容易就可以看出节点B就是新的头节点，下一个数据输出时，要释放的就是节点B了。
//3.出队
datatype OutQueue(queue_t *p)
{
//1.判断队列是否为空
if(isEpQueue(p))
{
printf("out fail\n");
return -1;
}
//2,定义一个临时的指向删除节点的指针
link_t *pdel = NULL;
//3.pdel指向头指针指向的节点
pdel = p->front;
//4.头指针指向下一个节点，将下一个节点作为头节点
p->front = pdel->next;
//5.释放临时指针指向的节点，队列长度减一
free(pdel);
pdel = NULL;
p->len--;
//6.最后返回的是头指针指向的节点的数据
return p->front->data;
}
4.销毁链式队列
销毁队列，就是对队列的内存进行操作，所以需要地址传递，对主函数中的队列的内容进行修改；
首先需要将队列中的数据全部出队，只留下一个头节点；
然后将头节点中的节点内存空间进行释放；
然后再将保存了头指针，尾指针和队列长度的内存空间进行释放。
//7.销毁队列
void DestoryQueue(queue_t **p)
{
ClearQueue(*p);
free((*p)->front);
free(*p);
*p = NULL;
}
四，linkqueue.c文件详细代码
#include <stdio.h>
#include <stdlib.h>
#include "linkqueue.h"
//1.创建一个空的链式队列
queue_t *CreateQueue(void)
{
//1.创建头尾指针的内存空间
queue_t *p = (queue_t *)malloc(sizeof(queue_t));
if(NULL == p)
{
printf("CreateQueue fail\n");
return NULL;
}
//2.创建头节点，并让头尾指针指向它
p->front=p->rear=(link_t *)malloc(sizeof(link_t));
if(p->front == NULL)
{
printf("malloc head node fail\n");
return NULL;
}
//3.初始化头节点，指针域指向空
p->front->next = NULL;
//4.初始化长度
p->len = 0;
return p;
}
//2.入队
int IntoQueue(queue_t *p,datatype data)
{
//1.开辟新节点内存空间
link_t *pnew = (link_t *)malloc(sizeof(link_t));
if(NULL == pnew)
{
printf("malloc pnew fail\n");
return -1;
}
//2.初始化新节点
pnew->data = data;
pnew->next = NULL;
//3.当前尾节点指向的节点指针域指向新节点
p->rear->next = pnew;
//4.尾节点向后移动，移动到新节点的位置，队列长度加一
p->rear = pnew;
p->len++;
return 0;
}
//3.出队
datatype OutQueue(queue_t *p)
{
//1.判断队列是否为空
if(isEpQueue(p))
{
printf("out fail\n");
return -1;
}
//2,定义一个临时的指向删除节点的指针
link_t *pdel = NULL;
//3.pdel指向头指针指向的节点
pdel = p->front;
//4.头指针指向下一个节点，将下一个节点作为头节点
p->front = pdel->next;
//5.释放临时指针指向的节点，队列长度减一
free(pdel);
pdel = NULL;
p->len--;
//6.最后返回的是头指针指向的节点的数据
return p->front->data;
}
//4.判断是否为空
int isEpQueue(queue_t *p)
{
return p->front == p->rear;
}
//5.计算队列长度
int LengthQueue(queue_t *p)
{
printf("当前队列长度为%d\n",p->len);
return 0;
}
//6.清空队列
int ClearQueue(queue_t *p)
{
while(!isEpQueue(p))
{
for(int i = 0;i < p->len;i++)
{
OutQueue(p);
}
}
return 0;
}
//7.销毁队列
void DestoryQueue(queue_t **p)
{
ClearQueue(*p);
free((*p)->front);
free(*p);
*p = NULL;
}
如果本文中存在代码逻辑，代码完善，解释不通或不清楚的错误，还请批评指正。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
