福州建网站哪家好,外贸网页制作公司,京东seo搜索优化,网上购物系统代码文章目录 2.链队列2.1初始化#xff08;带头结点#xff09;不带头结点 2.2入队#xff08;带头结点#xff09;2.3出队#xff08;带头结点#xff09;❗2.4链队列c实例 3.双端队列考点:输出序列合法性栈双端队列 队列的应用1.树的层次遍历2.图的广度优先遍历3.操作系统… 文章目录 2.链队列2.1初始化带头结点不带头结点 2.2入队带头结点2.3出队带头结点❗2.4链队列c实例 3.双端队列考点:输出序列合法性栈双端队列 队列的应用1.树的层次遍历2.图的广度优先遍历3.操作系统 - FCFS 补充释放内存 2.链队列
链队列的frontrear不能存在data的结构体里面如果那样每一个结点都有自己的front和raer。
//单链表的结构
typedef struct LinkNode{ //链式队列结点ElemType data;struct LinkNode *next;
}LinkNode;//链队列队头对尾结构
//因为队列只处理队头队尾所以后面只操作这个结构体
typdef struct{ //链式队列LinkNode *front,*rear; //队列的队头和队尾指针结点
}LinkQueue;2.1初始化带头结点
//初始化队列(带头结点)
void InitQueue(LinkQueue Q){//初始时 front、rear 都指向头结点Q.frontQ.rear(LinkNode*)malloc(sizeof(LinkNode));Q.front-nextNULL;
}判空
//判断队列是否为空
bool IsEmpty(LinkQueue Q){if(Q.frontQ.rear)return true;elsereturn false;
}不带头结点
//初始化队列(不带头结点
void InitQueue(LinkQueue Q){//初始时 front、rear 都指向NULLQ.frontNULL;Q.rearNULL;
}//判断队列是否为空不带头结点
bool IsEmpty(LinkQueue Q){if(Q.frontNULL)return true;elsereturn false;
}2.2入队带头结点
将元素x入队
创建新结点。判断内存是否分配成功。将元素x放入结点数据域、新节点next指针置空。队尾rear指向新结点、更新队尾结点。
//新元素入队带头结点
void EnQueue(LinkQueue Q, ElemType x){LinkNode *s(LinkNode *)malloc(sizeof(LinkNode));if(!s){ //创建结点分配内存要判断是否分配成功return false; //内存分配失败}s-datax;s-nextNULL;Q.rear-nexts;//新结点插入到rear之后Q.rears;//修改队尾指针
}2.3出队带头结点
步骤
判断链队列是否为空。创建temp指针指向要出栈的元素。用x返回该元素。删除该结点将头结点指向删除结点的后继结点更新队头。若删除的是队尾则队头队尾指针均指向队头结点。
//队头元素出队不带头结点
bool DeQueue(LinkQueue Q, ElemType x){ if(Q.front0.rear)return false; //空队LinkNode *temp Q.front-next;xtemp-data; //用变量x返回队头元素Q.front-nextp-next; //修改头结点的 next 指针if (Q.reartemp) //此次是最后一个结点出队Q.rearQ.front; //修改 rear 指针free(temp); //释放结点空间return true;
}❗2.4链队列c实例
#includeiostream
using namespace std;#define MaxSize 50 //最大队列长度
typedef int QElemType;// 链队列带头结点
// C//结点结构
typedef struct LinkNode
{QElemType data;struct LinkNode* next;
}LinkNode; //队列结点类型//链队列队头对尾结构
//因为队列只处理队头、队尾所以后面只操作这个结构体
typedef struct
{LinkNode *front; //队头指针LinkNode *rear; //队尾指针
}LinkQueue; //链式队列定义bool InitQueue(LinkQueue Q); //循环队列初始化
bool QueueEmpty(LinkQueue Q); //判断队列是否为空
int QueueLength(LinkQueue Q); //循环队列长度bool EnQueue(LinkQueue Q, QElemType value); //循环队列入队
bool DeQueue(LinkQueue Q, QElemType value); //循环队列出队QElemType GetHead(LinkQueue Q); //获取队头元素
bool QueuePrint(LinkQueue Q); //打印输出队列
void DestroyQueue(LinkQueue Q); //销毁链队列int main()
{LinkQueue Q;QElemType value;InitQueue(Q);int number 0; //入队的元素个数cout 请输入要入队的元素个数 ;cin number; int num 0; //入队的数据元素while ((number--) 0){EnQueue(Q, num); //将num入队num;}cout 队列输出顺序;QueuePrint(Q); //遍历输出队列元素cout 队头元素为 GetHead(Q) endl;cout 队列长度为 QueueLength(Q) endl;DeQueue(Q, value); //出队cout 出队元素为 valueendl;QueuePrint(Q); //遍历队列元素DestroyQueue(Q);//销毁链式队列释放内存空间return 0;
}//初始化链队列front与rear都指向队头结点队头结点next指针置空
bool InitQueue(LinkQueue Q) {// 将队列的头尾指针都指向同一个节点表示队列为空Q.front Q.rear new LinkNode; //Q.front Q.rear (LinkNode *)malloc(sizeof(LinkNode));if(!Q.front){return false; //内存分配失败}// 带头结点Q.front-next NULL; //将队列队头指针置空return true; //初始化完成
}//链队列判空
bool QueueEmpty(LinkQueue Q) {//队头队尾指针指向同一位置(队头结点)队列为空。return Q.front Q.rear;
}//入队
// 将元素value入队创建新结点将元素放入结点数据域、新节点next指针置空、队尾rear指向新结点、更新队尾结点。
bool EnQueue(LinkQueue Q, QElemType value) {// step1创建指针型LinkNode结点指针指向要插入的结点元素LinkNode* temp new LinkNode; // step2判断是否分配成功if (!temp) return false; //内存分配失败// step3构建新结点temp-data value; //将要插入的元素放入temp结点数据域temp-next NULL; //temp结点指针域置空// step4将新结点temp插入到队尾Q.rear-next temp; //将队尾指针接上temp结点Q.rear temp; //更新队尾结点return true;
}//出队删除队头结点的下一位头结点不存储数据元素。
// 判断链队列是否为空创建temp指针指向要出栈的元素、删除该结点将头结点指向删除结点的后继结点更新队头若删除的是队尾则队头队尾指针均指向队头结点。
bool DeQueue(LinkQueue Q, QElemType value) {// step1判断链队列是否为空if (!QueueEmpty(Q)) //若链队列不为空{// step2创建temp指针指向要出栈的元素LinkNode* temp Q.front-next;//temp指向队头结点下一位即第一位元素if (!temp) return false;// step3删除该结点将头结点指向删除结点的后继结点更新队头value temp-data; //将temp所指结点的数据保存到value中Q.front-next temp-next;//更新队头结点// step4若删除的是队尾则队头队尾指针均指向队头结点if (Q.rear temp)//如果删除的是最后一个结点(尾结点)尾结点回移{Q.rear Q.front;//rear、front均指向仅存的头结点Q.front-next NULL;}// step5释放出元素所占结点空间delete temp; //释放出栈元素所占结点空间return true; //出栈成功}return false; //队列为空
}//获取链队的队头元素
QElemType GetHead(LinkQueue Q) {if (!QueueEmpty(Q)){return Q.front-next-data;}return false;
}//链队列的长度/元素个数
// 这里Q不能用引用型传递否则下方队头指针front的移动会修改原队列front指针。不加引用就会创建一个副本执行操作故相比前者会多消耗些内存和时间。也可以创建一个临时指针temp对队列进行遍历这样即使Q加了, 也不会影响原链队列。
int QueueLength(LinkQueue Q) {if (!QueueEmpty(Q)){int count 0; //元素个数/队列长度while (Q.front ! Q.rear)//直到 队尾rear{Q.front Q.front-next;//队头指针后移一位count; //计数加一}return count; }return false; //队列为空或不存在
}//遍历输出链队元素
bool QueuePrint(LinkQueue Q) {if (!QueueEmpty(Q)){while (Q.front ! Q.rear){Q.front Q.front-next; //将链队头指针指向第一个元素结点cout Q.front-data ; //输出该结点所指的结点数据}cout endl;return true; }cout 队列为空或不存在;return false;
}//链队列销毁从队头结点开始一次释放所有结点
void DestroyQueue(LinkQueue Q) {LinkNode* temp; //创建临时指针while (Q.front){ //反正rear指针闲置无事此处可以不额外创建temp直接将下列temp替换成Q.rear效果一样。temp Q.front-next; //temp指向队头结点的下一个结点delete Q.front; //释放队头结点Q.front temp; //更新队头结点}Q.rear NULL;cout 队列销毁成功 endl;
}请输入要入队的元素个数 5 队列输出顺序0 1 2 3 4 队头元素为0 队列长度为5 出队元素为0 1 2 3 4 队列销毁成功 Press any key to continue . . . 3.双端队列
按照输出种类从少到多
队列只允许从一端插入、另一端删除的线性表。
栈只允许从一端插入和删除的线性表。
输入受限的双端队列只允许从一端插入、两端删除的线性表。 输出受限的双端队列只允许从两端插入、一端删除的线性表。
双端队列允许从两端插入、两端删除的线性表。
考点:输出序列合法性
若数据元素输入序列为1,2,3,4。则共有 A 4 4 ! 24 A^4_4! 24 A44!24种顺序。
栈
卡特兰Catalan数n个不同元素进栈出栈元素不同排列的个数为 1 n 1 C 2 n n \frac 1{n1}C_{2n}^n n11C2nn 所以有 1 4 1 C 8 4 1 5 ∗ 8 ∗ 7 ∗ 6 ∗ 5 4 ∗ 3 ∗ 2 ∗ 1 14 \frac 1{41}C_{8}^4\frac1{5}*\frac{8*7*6*5}{4*3*2*1}14 411C8451∗4∗3∗2∗18∗7∗6∗514 种出栈可能。
双端队列
栈中合法的序列双端队列中一定也合法。
输入受限的双端队列、输出受限的双端队列同样包含栈合法的序列。
队列的应用
1.树的层次遍历
在“树”章节会详细学习。 2.图的广度优先遍历
在“图”章节会详细学习。
3.操作系统 - FCFS
多个进程争抢着使用有限的系统资源时FCFSFirst Come First Service先来先服务是一种常用策略。
eg.: CPU的资源分配。
补充释放内存
在C语言中动态分配内存用 malloc() 函数释放内存用 free() 函数。如下所示
int *p (int*) malloc( sizeof(int) * 10 ); //分配10个int型的内存空间free(p); //释放内存
在C中这两个函数仍然可以使用但是C又新增了两个关键字new 和 deletenew 用来动态分配内存delete 用来释放内存。
用 new 和 delete 分配内存更加简单
int *p new int; //分配1个int型的内存空间delete p; //释放内存
new 操作符会根据后面的数据类型来推断所需空间的大小。
如果希望分配一组连续的数据可以使用 new[]
int *p new int[10]; //分配10个int型的内存空间delete[] p;
用 new[] 分配的内存需要用 delete[] 释放它们是一一对应的。
和 malloc() 一样new 也是在堆区分配内存必须手动释放否则只能等到程序运行结束由操作系统回收。为了避免内存泄露通常 new 和 delete、new[] 和 delete[] 操作符应该成对出现并且不要和C语言中 malloc()、free() 一起混用。
在C中建议使用 new 和 delete 来管理内存它们可以使用C的一些新特性最明显的是可以自动调用构造函数和析构函数。
