网站三要素关键词 描述怎么做,seo网站关键词快速排名,专做脚本的网站,html5做手机网站建设第三部分、栈(Stack)和队列(Queue)详解 栈和队列#xff0c;严格意义上来说#xff0c;也属于线性表#xff0c;因为它们也都用于存储逻辑关系为 一对一 的数据#xff0c;但由于它们比较特殊#xff0c;因此将其单独作为一章#xff0c;做重点讲解。
使用栈… 第三部分、栈(Stack)和队列(Queue)详解 栈和队列严格意义上来说也属于线性表因为它们也都用于存储逻辑关系为 一对一 的数据但由于它们比较特殊因此将其单独作为一章做重点讲解。
使用栈结构存储数据讲究“先进后出”即最先进栈的数据最后出栈使用队列存储数据讲究 先进先出即最先进队列的数据也最先出队列。
既然栈和队列都属于线性表根据线性表分为顺序表和链表的特点栈也可分为顺序栈和链表队列也分为顺序队列和链队列这些内容都会在本章做详细讲解。
九、链式队列及基本操作C语言实现
链式队列简称链队列即使用链表实现的队列存储结构。 链式队列的实现思想同顺序队列类似只需创建两个指针命名为 top 和 rear分别指向链表中队列的队头元素和队尾元素如图 1 所示: 图 1 链式队列的初始状态
图 1 所示为链式队列的初始状态此时队列中没有存储任何数据元素因此 top 和 rear 指针都同时指向头节点。 在创建链式队列时强烈建议初学者创建一个带有头节点的链表这样实现链式队列会更简单。 由此我们可以编写出创建链式队列的 C 语言实现代码为: //链表中的节点结构 typedef struct QNode{ int data; struct QNode * next; }QNode; //创建链式队列的函数 QNode * initQueue(){ //创建一个头节点 QNode * queue(QNode*)malloc(sizeof(QNode)); //对头节点进行初始化 queue-nextNULL; return queue; } 1、链式队列数据入队
链队队列中当有新的数据元素入队只需进行以下 3 步操作
将该数据元素用节点包裹例如新节点名称为 elem与 rear 指针指向的节点建立逻辑关系即执行 rear-nextelem最后移动 rear 指针指向该新节点即 rearelem
由此新节点就入队成功了。 例如在图 1 的基础上我们依次将 {1,2,3} 依次入队各个数据元素入队的过程如图 2 所示: 图 2 {1,2,3} 入链式队列
数据元素入链式队列的 C 语言实现代码为 QNode* enQueue(QNode * rear,int data){ //1、用节点包裹入队元素 QNode * enElem(QNode*)malloc(sizeof(QNode)); enElem-datadata; enElem-nextNULL; //2、新节点与rear节点建立逻辑关系 rear-nextenElem; //3、rear指向新节点 rearenElem; //返回新的rear为后续新元素入队做准备 return rear; } 2、链式队列数据出队
当链式队列中有数据元素需要出队时按照 先进先出 的原则只需将存储该数据的节点以及它之前入队的元素节点按照原则依次出队即可。这里我们先学习如何将队头元素出队。 链式队列中队头元素出队需要做以下 3 步操作
通过 top 指针直接找到队头节点创建一个新指针 p 指向此即将出队的节点将 p 节点即要出队的队头节点从链表中摘除释放节点 p回收其所占的内存空间
例如在图 2b) 的基础上我们将元素 1 和 2 出队则操作过程如图 3 所示 图 3 链式队列中数据元素出队
链式队列中队头元素出队的 C 语言实现代码为 void DeQueue(QNode * top,QNode * rear){ if (top-nextNULL) { printf(队列为空); return ; } // 1、 QNode * ptop-next; printf(%d,p-data); top-nextp-next; if (rearp) { reartop; } free(p); } 注意将队头元素做出队操作时需提前判断队列中是否还有元素如果没有要提示用户无法做出队操作保证程序的健壮性。
3、总结
通过学习链式队列最基本的数据入队和出队操作我们可以就实际问题对以上代码做适当的修改。 前面在学习顺序队列时由于顺序表的局限性我们在顺序队列中实现数据入队和出队的基础上又对实现代码做了改进令其能够充分利用数组中的空间。链式队列就不需要考虑空间利用的问题因为链式队列本身就是实时申请空间。因此这可以算作是链式队列相比顺序队列的一个优势。 这里给出链式队列入队和出队的完整 C 语言代码为 #include stdio.h #include stdlib.h typedef struct QNode{ int data; struct QNode * next; }QNode; QNode * initQueue(){ QNode * queue(QNode*)malloc(sizeof(QNode)); queue-nextNULL; return queue; } QNode* enQueue(QNode * rear,int data){ QNode * enElem(QNode*)malloc(sizeof(QNode)); enElem-datadata; enElem-nextNULL; //使用尾插法向链队列中添加数据元素 rear-nextenElem; rearenElem; return rear; } QNode* DeQueue(QNode * top,QNode * rear){ if (top-nextNULL) { printf(\n队列为空); return rear; } QNode * ptop-next; printf(%d ,p-data); top-nextp-next; if (rearp) { reartop; } free(p); return rear; } int main() { QNode * queue,*top,*rear; queuetoprearinitQueue();//创建头结点 //向链队列中添加结点使用尾插法添加的同时队尾指针需要指向链表的最后一个元素 rearenQueue(rear, 1); rearenQueue(rear, 2); rearenQueue(rear, 3); rearenQueue(rear, 4); //入队完成所有数据元素开始出队列 rearDeQueue(top, rear); rearDeQueue(top, rear); rearDeQueue(top, rear); rearDeQueue(top, rear); rearDeQueue(top, rear); return 0; } 程序运行结果为 1 2 3 4 队列为空 十、[数据结构实践项目]变态的停车场管理系统
实践是检验真理的唯一标准学习也是如此。本章对栈和队列做了详细的讲解为了让大家能够学以致用特推出一个项目供大家练习包含了本章所有的重要知识点。 本项目比较烧脑要求对栈和队列有一定深度的了解虽有完整代码供大家参考但是建议先自行完成然后参照本节给出的完整代码。 1、项目简介
设停车场是一个可以停放 n 辆汽车的南北方向的狭长通道且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序依次由北向南排列大门在最南端最先到达的第一辆车停放在车场的最北端。 若车场内已停满 n 辆车那么后来的车只能在门外的便道上等候一旦有车开走则排在便道上的第一辆车即可开入当停车场内某辆车要离开时在它之后进入的车辆必须先退出车场为它让路待该辆车开出大门外其它车辆再按原次序进入车场每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。项目要求试为停车场编制按上述要求进行管理的模拟程序。要求程序输出每辆车到达后的停车位置停车场或便道上以及某辆车离开停车场时应缴纳的费用和它在停车场内停留的时间。
2、设计思路
停车场的管理流程如下
当车辆要进入停车场时检查停车场是否已满如果未满则车辆进入停车场如果停车场已满则车辆进入便道等候。当车辆要求出栈时先让在它之后进入停车场的车辆退出停车场为它让路再让该车退出停车场让路的所有车辆再按其原来进入停车场的次序进入停车场。之后再检查在便道上是否有车等候有车则让最先等待的那辆车进入停车场。
3、项目中涉及到的数据结构
由于停车场只有一个大门当停车场内某辆车要离开时在它之后进入的车辆必须先退出车场为它让路先进停车场的后退出后进车场的先退出符合栈的“后进先出先进后出”的操作特点因此可以用一个栈来模拟停车场。而当停车场满后继续来到的其它车辆只能停在便道上根据便道停车的特点先排队的车辆先离开便道进入停车场符合队列的“先进先出后进后出”的操作特点因此可以用一个队列来模拟便道。排在停车场中间的车辆可以提出离开停车场并且停车场内在要离开的车辆之后到达的车辆都必须先离开停车场为它让路然后这些车辆依原来到达停车场的次序进入停车场因此在前面已设的一个栈和一个队列的基础上还需要有一个地方保存为了让路离开停车场的车辆由于先退出停车场的后进入停车场所以很显然保存让路车辆的场地也应该用一个栈来模拟。
因此本题求解过程中需用到两个栈和一个队列。栈和队列都既可以用顺序结构实现也可以用链式结构实现。
4、程序清单
以栈模拟停车场以队列模拟车场外的便道按照从终端读入的输入数据序列进行模拟管理。 每一组输入数据包括三个数据项汽车“到达”或“离去”信息、汽车牌照号码以及到达或离去的时刻。对每一组输入数据进行操作后的输出信息为若是车辆到达则输出汽车在停车场内或便道上的停车位置若是车辆离去则输出汽车在停车场内停留的时间和应交纳的费用在便道上停留的时间不收费停车场费用按照 1 小时 1.5元。
5、实现代码 #include stdio.h #define MAX 3//模拟停车场最多可停的车辆数 //车的必要信息的结构体 typedef struct{ int number; int arrive_time; }zanInode; //进入停车场的处理函数 int push(zanInode * park,int *parktop,zanInode car){ //如果停车场已满该车需进入便道等待先返回 -1 在主程序中处理 if ((*parktop)MAX) { printf(停车场已停满需停到便道上.\n); return -1; }else{//否则将该车入栈同时进行输出 park[(*parktop)]car; printf(该车在停车场的第 %d 的位置上\n,(*parktop)1); (*parktop); return 1; } } //车从停车场中退出的处理函数 zanInode pop(zanInode *park,int *parktop,int carnumber,zanInode * location,int *locationtop){ int i; //由于函数本身的返回值需要返回一辆车所以需要先初始化一个 zanInode thecar; thecar.number-1; thecar.arrive_time-1; //在停车场中找到要出去的车 for (i-1; i(*parktop); i) { if (park[i].numbercarnumber) { break; } } //如果遍历至最后一辆车还没有找到证明停车场中没有这辆车 if (i(*parktop)) { printf(停车场中没有该车\n); }else{//就将该车移出停车场 //首先将在该车后进入停车场的车全部挪至另一个栈中 while ((*parktop)i1) { (*parktop)--; location[*locationtop]park[*parktop]; (*locationtop); } //通过以上的循环可以上该车后的左右车辆全部移开但是由于该车也要出栈所以栈顶指针需要下移一个位置当车进栈时就直接覆盖掉了 (*parktop)--; thecarpark[*parktop]; //该车出栈后还要将之前出栈的所有车在全部进栈 while ((*locationtop)0) { (*locationtop)--; park[*parktop]location[*locationtop]; (*parktop); } } return thecar; } int main(int argc, const char * argv[]) { //停车场的栈 zanInode park[MAX]; int parktop0;//栈顶指针 //辅助停车场进行挪车的栈 zanInode location[MAX]; int locationtop0;//栈顶指针 //模拟便道的队列 zanInode accessroad[100]; int front,rear;//队头和队尾指针 frontrear0; char order;//进出停车场的输入命令 int carNumber;//车牌号 int arriveTime;//到停车场的时间 int leaveTime;//离开停车场的时间 int time;//车在停车场中逗留的时间 zanInode car; printf(有车辆进入停车场A;有车辆出停车场(D);程序停止#:\n); while (scanf(%c,order)) { if (order#) { break; } switch (order) { case A: printf(登记车牌号(车牌号不能为 -1)及车辆到达时间按小时为准\n); scanf(%d %d,carNumber,arriveTime); car.numbercarNumber; car.arrive_timearriveTime; //当有车想要进入停车场时首先试图将该车进入停车场 int resultpush(park, parktop, car); //如果返回值为 -1 证明停车场已满需要停在便道中 if (result-1) {//停在便道上 accessroad[rear]car; printf(该车在便道的第 %d 的位置上\n,rear1-front); rear; } break; case D: printf(出停车场的车的车牌号以及离开的时间\n); scanf(%d %d,carNumber,leaveTime); //当有车需要出停车场时调用出栈函数 carpop(park, parktop, carNumber, location, locationtop); //如果返回的车的车牌号为-1 表明在停车场中没有查找到要查找的车 if (car.number!-1) { //停留时间等于进停车场的时间- timeleaveTime-car.arrive_time; printf(该车停留的时间为%d 小时,应缴费用为%f 元\n,time,time*1.5); //一旦有车离开停车场则在便道中先等待的车就可以进入进入时需设定车进入的时间 if (front!rear) { caraccessroad[front]; printf(在便道上第1的位置上车牌号为%d 的车进停车场的时间为\n,car.number); scanf(%d,car.arrive_time); park[parktop]car; front; parktop; }else{ printf(便道上没有等待车辆停车场不满\n); } } break; default: break; } printf(\n有车辆进入停车场A;有车辆出停车场(D);程序停止#:\n); scanf(%*[^\n]); scanf(%*c);//清空缓冲区 } return 0; } 运行结果: 有车辆进入停车场A;有车辆出停车场(D);程序停止#: A 登记车牌号(车牌号不能为 -1)及车辆到达时间按小时为准 633 6 该车在停车场的第 1 的位置上 有车辆进入停车场A;有车辆出停车场(D);程序停止#: A 登记车牌号(车牌号不能为 -1)及车辆到达时间按小时为准 634 7 该车在停车场的第 2 的位置上 有车辆进入停车场A;有车辆出停车场(D);程序停止#: A 登记车牌号(车牌号不能为 -1)及车辆到达时间按小时为准 635 8 该车在停车场的第 3 的位置上 有车辆进入停车场A;有车辆出停车场(D);程序停止#: A 登记车牌号(车牌号不能为 -1)及车辆到达时间按小时为准 636 9 停车场已停满需停到便道上. 该车在便道的第 1 的位置上 有车辆进入停车场A;有车辆出停车场(D);程序停止#: D 出停车场的车的车牌号以及离开的时间 633 10 该车停留的时间为4 小时,应缴费用为6.000000 元 在便道上第1的位置上车牌号为636 的车进停车场的时间为 10 有车辆进入停车场A;有车辆出停车场(D);程序停止#: D 出停车场的车的车牌号以及离开的时间 634 10 该车停留的时间为3 小时,应缴费用为4.500000 元 便道上没有等待车辆停车场不满 有车辆进入停车场A;有车辆出停车场(D);程序停止#: A 登记车牌号(车牌号不能为 -1)及车辆到达时间按小时为准 637 11 该车在停车场的第 3 的位置上 有车辆进入停车场A;有车辆出停车场(D);程序停止#: #
