数据结构-----对列
前言
Hello, 小伙伴们,你们的作者菌又来了,前不久,我们学习了一种数据结构----栈,他特殊的性质使得他在一些数据管理的问题上被广泛的使用,那今天,我们就来学习另一种十分重要的数据结构--对列。
在开始之间,还是按例求三,如果你喜欢我的内容,就请不要忘记,点赞、评论和收藏,你们的支持就是我更新的动力,万分感谢!!
好,我们先在开始。
1.队列的介绍
基本概念:
只允许在⼀端进⾏插⼊数据操作,在另⼀端进⾏删除数据操作的特殊线性表,队列具有先进先出FIFO(First In First Out)
入队列:进行插入操作的一段为队尾;
出队列:进行删除操作的一端称为对头。
队列的底层结构选型:
队列也可以用数组和链表的方式链实现,使用链表的结构实现会更加的优秀,因为如果使用数组的结构,出队列在数组的头部进行,效率会十分底下!!
2.队列的实现
我门还是先创建三个文件(就向实现其他数据结构一样):
2.1队列结构的定义:
typedef int QDataType;
typedef struct QueueNode
{
QDataType x;
struct Queue* next;
}QueueNode;
typedef struct Queue
{
QueueNode* phead;
QueueNode* ptail;
}Queue;
怎样来理解这样的定义呢?
队列的定义底层使用的确实是单链表的结构,但是特殊的就是,他只能在头部出数据,只能在为部插入数据,所以,我们可以使用两个结构体,来实现队列:
phead用于出数据;
ptail用于输入数据。
2.2队列的初始化(QueueIit函数的实现)
2.2.1函数的定义
//初始化队列
void QueueInit(Queue* ps);
2.2.2函数的实现
//初始化队列
void QueueInit(Queue* ps)
{
assert(ps);
ps->phead = ps->ptail = NULL;
}
初始化的操作与单链表相似。
代码测试:
2.3队列的数据插入(QueuePush函数的实现)
2.3.1 函数的定义
//入队列
void QueuePush(Queue* ps, QDataType x);
这个也和单链表的结构相似,但是要注意几点,我们先来看函数的是实现代码:
2.3.2函数的实现
QueueNode* BuyNode(QDataType x)
{
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc Fail!!");
exit(1);
}
newnode->x = x;
newnode->next = NULL;
return newnode;
}
//队列的销毁
void QueuePush(Queue* ps, QDataType x)
{
assert(ps);
QueueNode* New = BuyNode(x);
if (ps->phead == NULL)
{
ps->phead = ps->ptail = New;
}
else
{
ps->ptail->next = New;
ps->ptail = ps->ptail->next;
}
}
1.我们注意不要将QueueNode 和Queue的结构混淆;
2.一定要记得,将新节点的next指针置位NULL;
3.要考虑到ps->phead 和 ps->ptail都为NULL的情况!!
代码测试:
入队列的操作就完成了!!
2.4队列的出数据
原文地址:https://blog.csdn.net/2302_79964175/article/details/140725810
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!