在网站上使用特殊字体,关于《大学物理》网站资源建设的思路,外贸网站公司,wordpress怎么屏蔽蜘蛛目录
1. 队列的概念和结构
2. 队列的应用
3. 队列的实现
3.1 队列实现的底层结构选择
3.2 结构体设计
3.2.1 仅为链表结点设计结构体
3.2.2 为链表再设计一个结构体
3.3 Queue.h
3.4 Queue.c
3.5 Test_Queue.c
注#xff1a;部分方法实现细节 1. 队列的概念和结构 …目录
1. 队列的概念和结构
2. 队列的应用
3. 队列的实现
3.1 队列实现的底层结构选择
3.2 结构体设计
3.2.1 仅为链表结点设计结构体
3.2.2 为链表再设计一个结构体
3.3 Queue.h
3.4 Queue.c
3.5 Test_Queue.c
注部分方法实现细节 1. 队列的概念和结构
队列只允许在一端进行数据的插入操作在另一端进行数据的删除操作的特殊线性表队列具有先进先出FIFOFirst In First Out的特点。
入队列进行插入操作的一端称为队尾
出队列进行删除操作的一端称为队头尾进头出
2. 队列的应用
队列的最大特点是保持公平性。其主要应用场景有以下两个
1设置排队器实现先进先出
2实现二叉树的广度优先遍历
3. 队列的实现
3.1 队列实现的底层结构选择
1、若采用数组实现
若将数组头视为队头数组尾视为队尾则插入对应尾插实现方便但删除对应头删实现麻烦
若将数组头视为队尾数组尾视为队头则删除对应尾删实现方便但插入对应头插实现麻烦
选数组实现队列则不便实现。
2、若采用单链表实现采用此种结构
相较于双链表单链表更节省空间
将链表尾视为队尾链表头视为队头
则插入对应尾插实现方便记录尾结点可避免遍历删除对应头删也实现方便。
3.2 结构体设计
采用单链表结构实现队列则结点包括数据域val和后继指针域next两个成员。
且队列的插入通过链表尾插实现为了避免每次插入都需遍历链表采取插入传参尾结点的方式
3.2.1 仅为链表结点设计结构体
以插入和删除操作为例都有可能造成第一个结点指针和尾结点指针的变化故需传二级指针
typedef int QDataType;
typedef struct QueueNode {QDataType val;struct QueueNode* next;
}QNode;
// 队尾插入
void QueuePush(QNode** pphead, QNode** pptail, QDataType x);
// 队头删除
void QueuePop(QNode** pphead, QNode** pptail);注若采取设有头结点的单链表可传一级指针但仍然需传队尾结点指针仍需要传递两个参数总体而言依然较为麻烦。
3.2.2 为链表再设计一个结构体
由于插入删除操作均需队头指针与队尾指针可为其再设置一个结构体。
同时考虑由于需要提供返回队列元素个数的方法若在该方法内部对单链表进行遍历则该方法时间复杂度为O(N)可以在Queue结构体内再设置一个变量size以计算队列元素个数
typedef int QDataType;
typedef struct QueueNode {QDataType val;struct QueueNode* next;
}QNode;
typedef struct Queue {QNode* phead;QNode* ptail;int size;
}Queue;
// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);采取这种方式队头队尾指针作为Queue结构体变量改变队头队尾指针只需传递该结构体的一级指针即可。
既避免了使用二级指针可能导致的的接口不一致问题也使得插入删除方法大的参数减少。
3.3 Queue.h
#pragma once
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.h
typedef int QDataType;
typedef struct QueueNode {QDataType val;struct QueueNode* next;
}QNode;
typedef struct Queue {QNode* phead;QNode* ptail;int size;
}Queue;
// 初始化
void QueueInit(Queue* pq);
// 销毁
void QueueDestory(Queue* pq);
// 队尾插入
void QueuePush(Queue* pq, QDataType x);
// 队头删除
void QueuePop(Queue* pq);
// 计算列表元素个数
int QueueSize(Queue* pq);
// 取队头/队尾数据
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
// 判空
bool QueueEmpty(Queue* pq);
3.4 Queue.c
#includeQueue.h
// 初始化
void QueueInit(Queue* pq) {assert(pq);pq-phead NULL;pq-ptail NULL;pq-size 0;
}
// 队尾插入
void QueuePush(Queue* pq, QDataType x) {assert(pq);QNode* newNode (QNode*)malloc(sizeof(QNode));if (newNode NULL) {perror(malloc fail);return;}newNode-val x;newNode-next NULL;// 情况1队列为空if (pq-ptail NULL) {pq-phead pq-ptail newNode;}// 情况2队列不为空队尾插入else {pq-ptail-next newNode;pq-ptail newNode;}pq-size;
}
// 队头删除
void QueuePop(Queue* pq) {assert(pq);assert(QueueSize(pq)!0);// 情况1队列仅一个结点if (pq-phead-next NULL) {free(pq-phead);pq-phead pq-ptail NULL;}// 情况2队列有多个结点else {QNode* pheadNext pq-phead-next;free(pq-phead);pq-phead NULL;pq-phead pheadNext;}pq-size--;
}
// 计算列表元素个数
int QueueSize(Queue* pq) {return pq-size;
}
// 取队头/队尾数据
QDataType QueueFront(Queue* pq) {assert(pq);assert(pq-phead);return pq-phead-val;
}
QDataType QueueBack(Queue* pq) {assert(pq);assert(pq-phead);return pq-ptail-val;
}
// 判空
bool QueueEmpty(Queue* pq) {assert(pq);return pq-size 0;
}
// 销毁
void QueueDestory(Queue* pq) {assert(pq);QNode* cur pq-phead;while (cur) {QNode* curNext cur-next;free(cur);cur NULL;cur curNext;}pq-phead pq-ptail NULL;
}3.5 Test_Queue.c
#includeQueue.h
int main() {Queue q;QueueInit(q);QueuePush(q, 1);QueuePush(q, 2);QueuePush(q, 3);QueuePush(q, 4);while (!QueueEmpty(q)) {printf(%d , QueueFront(q));QueuePop(q);}QueueDestory(q);return 0;
}
注部分方法实现细节
对于队头的删除操作按照方法完善思路首先应该是考虑多个结点的无特殊情况而后考虑对于删除结点的特殊操作进行补充
1需保证队列当中有结点可删即队列数据个数不为0可直接使用assert实现
2若队列仅剩一个元素按当前无特殊情况处理的方法实现则pq-ptail未置空使得其成为野指针故需对其进行单独处理。
综合以上两点方法实现如下
// 队头删除
void QueuePop(Queue* pq) {assert(pq);assert(QueueSize(pq)!0);QNode* pheadNext pq-phead-next;free(pq-phead);pq-phead NULL;pq-phead pheadNext;pq-size--;// 特殊情况单独处理队列仅有一个结点if (pq-phead NULL) {pq-ptail NULL;}
}
这种方法框架可以正确实现功能但程序结构并不清晰可以在此基础上进行结构的优化即使用分支处理① 队列仅有一个结点 ② 队列有≥2个结点。具体实现见3.4部分程序此处不再重复。
