数据结构 - 链队列的实行（C语言）
2024-08-28 09:49:11
一、什么是链队列？
队列的链式存储结构，其实就是线性表的单链表，只不过它只能尾进头出而已，我们把它简称为链队列。为了操作上的方便，我们将队头指针指向链队列的头结点，而队尾指针指向尾结点，如下图所示：
空队列时，front和rear都指向头结点，如下图所示。
链队列的结构为：
typedef int QElemType; /* QElemType类型根据实际情况而定，这里假设为int */
/* 结点结构 */
typedef struct QNode
{
ElemType data;
struct QNode *next;
}QNode;
/* 队列的链表结构 */
typedef struct
{
QNode *front; // 队头指针
QNode *rear; // 队尾指针
}LinkQueue;
二、基本操作
2.1 初始化操作
实现代码如下：
// 初始化链队列操作
Status initQueue(LinkQueue *Q)
{
Q->front = Q->rear = (Node *)malloc(sizeof(Node));
if (!Q->front)
return FALSE;
Q->front->next = NULL;
return TRUE;
}
2.1 入队操作
人队操作时，其实就是在链表尾部插入结点，如下图所示：
实现代码如下：
// 入队操作
Status enQueue(LinkQueue *Q, ElemType e)
{
Node *s = (Node *)malloc(sizeof(Node));
if (!s)
return FALSE;
s->data = e;
s->next = NULL;
Q->rear->next = s; // 把拥有元素e的新结点s赋值给原队尾结点的后继
Q->rear = s; // 把当前的s设置为队尾结点，rear指向s
return TRUE;
}
2.3 出队操作
出队操作时，就是头结点的后继结点出队，将头结点的后继改为它后面的结点，若链表除头结点外只剩一个元素时，则需将rear指向头结点，如下图所示：
实现代码如下：
// 出队操作
Status deQueue(LinkQueue *Q, ElemType *e)
{
Node *p;
if (Q->front == Q->rear)
return FALSE;
p = Q->front->next; // 将欲删除的队头结点暂存给p，见图中①
*e = p->data; // 将欲删除的队头结点的值赋值给e
Q->front->next = p->next; // 将原队头结点的后继p->next赋值给头结点后继，见图中②
if (Q->rear == p) // 若队头就是队尾，则删除后将rear指向头结点，见图中③
Q->rear = Q->front;
free(p);
return TRUE;
}
2.4 遍历操作
实现代码如下：
// 遍历队列操作
Status tarverseQueue(const LinkQueue Q)
{
Node *p;
p = Q.front->next;
while (p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return TRUE;
}
三、完整程序
#include <stdio.h>
#include <stdlib.h>
#define TRUE 1
#define FALSE 0
#define MAXSIZE 20 /* 存储空间初始分配量 */
typedef int Status;
typedef int ElemType; /* ElemType类型根据实际情况而定，这里假设为int */
/* 结点结构 */
typedef struct Node
{
ElemType data;
struct Node *next;
}Node;
/* 队列的链表结构 */
typedef struct
{
Node *front; // 队头指针
Node *rear; // 队尾指针
}LinkQueue;
Status initQueue(LinkQueue *Q); // 初始化链队列操作
Status enQueue(LinkQueue *Q, ElemType e); // 入队操作
Status deQueue(LinkQueue *Q, ElemType *e); // 出队操作
Status tarverseQueue(const LinkQueue Q); // 遍历队列操作
Status destroyQueue(LinkQueue *Q); // 销毁队列操作
Status clearQueue(LinkQueue *Q); // 清空队列操作
Status isEmpty(const LinkQueue Q); // 判断是否为空队列
Status getHead(const LinkQueue Q, ElemType *e); // 获得队头元素
int getLength(const LinkQueue Q); // 获得队列的长度
// 初始化链队列操作
Status initQueue(LinkQueue *Q)
{
Q->front = Q->rear = (Node *)malloc(sizeof(Node));
if (!Q->front)
return FALSE;
Q->front->next = NULL;
return TRUE;
}
// 入队操作
Status enQueue(LinkQueue *Q, ElemType e)
{
Node *s = (Node *)malloc(sizeof(Node));
if (!s)
return FALSE;
s->data = e;
s->next = NULL;
Q->rear->next = s; // 把拥有元素e的新结点s赋值给原队尾结点的后继，见图中①
Q->rear = s; // 把当前的s设置为队尾结点，rear指向s，见图中②
return TRUE;
}
// 出队操作
Status deQueue(LinkQueue *Q, ElemType *e)
{
Node *p;
if (Q->front == Q->rear)
return FALSE;
p = Q->front->next; // 将欲删除的队头结点暂存给p，见图中①
*e = p->data; // 将欲删除的队头结点的值赋值给e
Q->front->next = p->next; // 将原队头结点的后继p->next赋值给头结点后继，见图中②
if (Q->rear == p) // 若队头就是队尾，则删除后将rear指向头结点，见图中③
Q->rear = Q->front;
free(p);
return TRUE;
}
// 遍历队列操作
Status tarverseQueue(const LinkQueue Q)
{
Node *p;
p = Q.front->next;
while (p)
{
printf("%d ", p->data);
p = p->next;
}
printf("\n");
return TRUE;
}
// 销毁队列操作
Status destroyQueue(LinkQueue *Q)
{
while (Q->front)
{
Q->rear = Q->front->next;
free(Q->front);
Q->front = Q->rear;
}
return TRUE;
}
// 清空队列操作
Status clearQueue(LinkQueue *Q)
{
Node *p;
Node *q;
Q->rear = Q->front;
p = Q->front->next;
Q->front->next = NULL;
while (p)
{
q = p;
p = p->next;
free(q);
}
return TRUE;
}
// 判断是否为空队列
Status isEmpty(const LinkQueue Q)
{
return Q.front == Q.rear ? TRUE : FALSE;
}
// 获得队头元素
Status getHead(const LinkQueue Q, ElemType *e)
{
Node *p;
if (Q.front == Q.rear)
return FALSE;
p = Q.front->next;
*e = p->data;
return TRUE;
}
// 获得队列的长度
int getLength(const LinkQueue Q)
{
int i = 0;
Node *p;
p = Q.front;
while (Q.rear != p)
{
i++;
p = p->next;
}
return i;
}
int main()
{
LinkQueue Q;
// 初始化队列
initQueue(&Q);
// 入队操作
for (int i = 0; i < 4; i++)
enQueue(&Q, i);
printf("入队操作（0、1、2、3）! \n\n");
// 出队操作
ElemType d;
deQueue(&Q, &d);
printf("删除的元素是%d \n\n", d);
// 遍历队列
printf("遍历队列: ");
tarverseQueue(Q);
printf("\n");
// 判断是否为空队列
printf("现在队列空否？ %u (1:空 0:否)\n\n", isEmpty(Q));
// 获得队列的长度
printf("队列长度为: %d \n\n", getLength(Q));
// 获得队头元素
getHead(Q, &d);
printf("队头元素是%d \n\n", d);
return 0;
}
输出结果如下图所示：
参考：
《大话数据结构 - 第4章》 栈与队列
最新文章
- jQuery插件开发精品教程，让你的jQuery提升一个台阶
- vs2012安装Microsoft.AspNet.WebApi.WebHost
- 跟我一起学WCF(11)——WCF中队列服务详解
- android:windowSoftInputMode及其他部分属性用法
- Redis中的批量删除数据库中的Key
- 关于ADMM的研究（一）
- 模板类之间的友元关系实现Blob和BlobPtr
- MySQL数据库中日期中包涵零值的问题
- javascript设计模式——Publish/Subscribe
- 翻纸牌游戏（dfs回溯）
- poj 2480 （欧拉函数应用）
- 安卓ADB学习笔记
- javase的网络编程（InetAddress,UDP,TCP,URL,Socket,DatagramSocket）
- python第九十一天----第十六周作业
- 将浏览器的内容复制到Linux的文件里面
- nyoj Registration system
- 执行sh脚本报“/usr/bin/env: "sh\r": 没有那个文件或目录”错误
- [JS] selector 背景选择器
- 使用click报错
- linux关闭地址空间随机化(ASLR)