许昌市城市建设局网站,黄石网站建设黄石,网页游戏排行榜2016,东莞营销网站建设公司实验六 队列
一、实验目的与要求
1#xff09;熟悉C/C语言#xff08;或其他编程语言#xff09;的集成开发环境#xff1b;
2#xff09;通过本实验加深对队列的理解#xff0c;熟悉基本操作#xff1b;
3#xff09; 结合具体的问题分析算法时间复杂度。
二、…实验六 队列
一、实验目的与要求
1熟悉C/C语言或其他编程语言的集成开发环境
2通过本实验加深对队列的理解熟悉基本操作
3 结合具体的问题分析算法时间复杂度。
二、实验内容 设计你的循环队列实现。 循环队列是一种线性数据结构其操作表现基于 FIFO先进先出原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。 循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里一旦一个队列满了我们就不能插入下一个元素即使在队列前面仍有空间。但是使用循环队列我们能使用这些空间去存储新的值。
你的实现应该支持如下操作
MyCircularQueue(k): 构造器设置队列长度为 k 。
Front: 从队首获取元素。如果队列为空返回 -1 。
Rear: 获取队尾元素。如果队列为空返回 -1 。
enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。
deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。
isEmpty(): 检查循环队列是否为空。
isFull(): 检查循环队列是否已满。
三、实验结果
1请将调试通过的源代码粘贴在下面。代码注意书写规范、主要模块要有功能注释
源代码
#include iostream
using namespace std;template typename T
class MyCircularQueue{T * data;//当前位置的数据 int front,rear,size;//头指针、尾指针、队列长度
public://MyCircularQueue(k): 构造器设置队列长度为 k 。MyCircularQueue(int k0){datanew T[k1];//k1 - 区分isEmpty和isFull的判断条件 frontrear0;sizek1;}//Front: 从队首获取元素。如果队列为空返回 -1 。T Front(){if(isEmpty()){return -1;}else{return data[front];}}//Rear: 获取队尾元素。如果队列为空返回 -1 。T Rear(){if(isEmpty()){return -1;}else{return data[rear-1];}}//enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。bool enQueue(T value){if(isFull()){return 0;}else{data[rear]value;rear(rear1)%size;return 1;}} //deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。bool deQueue(){if(isEmpty()){return 0;}else{front(front1)%size;return 1;}}//isEmpty(): 检查循环队列是否为空。bool isEmpty(){if(rearfront){return 1;}else{return 0;}}//isFull(): 检查循环队列是否已满。bool isFull(){if((rear1)%sizefront){return 1;}else{return 0;}}
};int main(){//初始化循环链表int len;coutPlease input the length of your queueendl;cinlen; MyCircularQueue int queue(len);//查看空表 if(queue.isEmpty() 1){coutThe current queue is emptyendl;}else{coutThe current queue is not emptyendl;}coutThe front now is queue.Front() endl;coutThe rear now is queue.Rear() endl;coutendl;//输入元素 int times;coutPlease select the times you want to inputendl;cintimes;int i0;for(;itimes;i){int value;coutPlease input your valueendl;cinvalue;int tqueue.enQueue(value); if(t1){coutValid inputendl;}else{coutInvalid inputendl;break;}}coutendl;//判断输入后的情况 if(queue.isEmpty() 1){coutThe current queue is emptyendl;}else{coutThe current queue is not emptyendl;}coutThe front now is queue.Front() endl;coutThe rear now is queue.Rear() endl;coutendl;//删除元素 int dels;coutPlease select the times you want to deleteendl;cindels;int ii0;for(;iidels;ii){int ttqueue.deQueue(); if(tt1){coutValid deleteendl;}else{coutInvalid deleteendl;break;}}coutendl;//判断删除后的情况if(queue.isEmpty() 1){coutThe current queue is emptyendl;}else{coutThe current queue is not emptyendl;}coutThe front now is queue.Front() endl;coutThe rear now is queue.Rear() endl;coutendl;return 0;
}结果展示 2请分析你程序中每个功能模块的算法时间复杂度。 构造循环队列只需要设置队列长度为k1并设置相应数组同时初始头指针和尾指针为0即可。所以时间复杂度为O(1)。 判断循环队列是否为空队列只需要判断头指针是否与尾指针重合即可即returnrearfront。所以时间复杂度为O(1)。 判断循环队列是否为空队列只需要判断尾指针加一取余后是否与头指针重合即可即returnrear1%sizefront。所以时间复杂度为O(1)。 获取队首元素只需要先判断循环队列是否为空队列如果队列非空则直接返回头指针所对应的元素。所以时间复杂度为O(1)。 获取队尾元素只需要先判断循环队列是否为空队列如果队列非空则直接返回尾指针所对应的元素。所以时间复杂度为O(1)。 向循环队列插入一个元素只需要先判断循环队列是否为满队列如果队列非满则直接插入输入元素并重置尾指针。所以时间复杂度为O(1)。 从循环队列中删除一个元素只需要先判断循环队列是否为空队列如果队列非空则直接改变头指针的位置即可删除队首元素。所以时间复杂度为O(1)。 其他
#includestdlib.h
#includeiostream
using namespace std;
#define SIZE 6
#define Type char
typedef struct{Type *elem;int front,rear,length;//注意队列的所谓的指针不是指针是int
}Queue;
bool isEmpty(Queue Q)//: 检查循环队列是否为空。
{if(Q.rearQ.front){return 1;}else{return 0;}
}
bool isFull(Queue Q)//: 检查循环队列是否已满。
{if((Q.rear1)%Q.lengthQ.front){return true;}else{return false;}
}
void MyCircularQueue(Queue Q,int k)//: 构造器设置队列长度为 k 。
{Q.lengthk;Q.elemnew Type[Q.length];Q.frontQ.rear0;cout长度为k的队列构造完毕endl;
}
int Front(Queue Q,Type e)//: 从队首获取元素。如果队列为空返回 -1 。
{if(isEmpty(Q)){cout空队列endl; return -1;}else{eQ.elem[Q.front];cout非空endl; cout队首元素e获取成功endl;return 1;}
}
int Rear(Queue Q,Type e)//: 获取队尾元素。如果队列为空返回 -1 。
{if(isEmpty(Q)){cout空队列endl;return -1;}else{cout非空endl;if(Q.rear0){eQ.elem[5];cout队尾元素e获取成功endl;return 1;}else{eQ.elem[Q.rear-1];cout队尾元素e获取成功endl;return 1;}}
}
bool enQueue(Queue Q,Type value)//: 向循环队列插入一个元素。如果成功插入则返回真。
{if(!isFull(Q)){cout非满endl;Q.elem[Q.rear]value;//因为初始front和rear都是0开头所以与下标一致 Q.rear(1Q.rear)%Q.length;coutvalue已经插入endl;return true;}else{cout队列已满!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!value无法入队endl; return false;}
}
int deQueue(Queue Q,Type e)//: 从循环队列中删除一个元素。如果成功删除则返回真。
{if(isEmpty(Q)){cout已空endl;return -1;}else{cout非空endl;eQ.elem[Q.front];Q.front(Q.front1)%Q.length;cout删除了eendl;return 1;}
}
int getlength(Queue Q)
{int len;len(Q.rear-Q.frontQ.length)%Q.length;return len;
}
int main()
{Queue a;Type temp;Type e[11]{a,b,c,d,e,f,g,h,i,j,k};int lengthSIZE;MyCircularQueue(a,length);//初始化 enQueue(a,e[0]);//入队到第一次满 enQueue(a,e[1]);enQueue(a,e[2]);enQueue(a,e[3]);enQueue(a,e[4]);if(isFull(a))//判断是否已满 {cout队列已满!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!endl;} deQueue(a,temp);//删除队首 Front(a,temp);//输出队首队尾元素 Rear(a,temp);enQueue(a,e[5]);//插入两次看看当队列已满溢出时的效果 证明了程序在溢出时的插入无效 enQueue(a,e[6]);//队列以满试图插入的这个是g查看满后队列是否可以阻止进入 cout该队列长度为getlength(a)endl; Front(a,temp);//再次确定 1.队列确实是循环使用的即0号位被再次利用 2.溢出的那一次插入无效 Rear(a,temp);
} 文章转载自： http://www.morning.fstesen.com.gov.cn.fstesen.com http://www.morning.kfcfq.cn.gov.cn.kfcfq.cn http://www.morning.fqljq.cn.gov.cn.fqljq.cn http://www.morning.drgmr.cn.gov.cn.drgmr.cn http://www.morning.mbmtz.cn.gov.cn.mbmtz.cn http://www.morning.mpsnb.cn.gov.cn.mpsnb.cn http://www.morning.qlrwf.cn.gov.cn.qlrwf.cn http://www.morning.dskzr.cn.gov.cn.dskzr.cn http://www.morning.slkqd.cn.gov.cn.slkqd.cn http://www.morning.kwnnx.cn.gov.cn.kwnnx.cn http://www.morning.nclps.cn.gov.cn.nclps.cn http://www.morning.pznhn.cn.gov.cn.pznhn.cn http://www.morning.rcbdn.cn.gov.cn.rcbdn.cn http://www.morning.ljwyc.cn.gov.cn.ljwyc.cn http://www.morning.gcszn.cn.gov.cn.gcszn.cn http://www.morning.ptslx.cn.gov.cn.ptslx.cn http://www.morning.slnz.cn.gov.cn.slnz.cn http://www.morning.twdkt.cn.gov.cn.twdkt.cn http://www.morning.kxnjg.cn.gov.cn.kxnjg.cn http://www.morning.nzcys.cn.gov.cn.nzcys.cn http://www.morning.qfrmy.cn.gov.cn.qfrmy.cn http://www.morning.bkjhx.cn.gov.cn.bkjhx.cn http://www.morning.cnyqj.cn.gov.cn.cnyqj.cn http://www.morning.jypsm.cn.gov.cn.jypsm.cn http://www.morning.pltbd.cn.gov.cn.pltbd.cn http://www.morning.qdzqf.cn.gov.cn.qdzqf.cn http://www.morning.crtgd.cn.gov.cn.crtgd.cn http://www.morning.ypklb.cn.gov.cn.ypklb.cn http://www.morning.bprsd.cn.gov.cn.bprsd.cn http://www.morning.xclgf.cn.gov.cn.xclgf.cn http://www.morning.gktds.cn.gov.cn.gktds.cn http://www.morning.duckgpt.cn.gov.cn.duckgpt.cn http://www.morning.gwtbn.cn.gov.cn.gwtbn.cn http://www.morning.rbkdg.cn.gov.cn.rbkdg.cn http://www.morning.rhkgz.cn.gov.cn.rhkgz.cn http://www.morning.dbrpl.cn.gov.cn.dbrpl.cn http://www.morning.tpyjr.cn.gov.cn.tpyjr.cn http://www.morning.mtyhk.cn.gov.cn.mtyhk.cn http://www.morning.tqklh.cn.gov.cn.tqklh.cn http://www.morning.rrxgx.cn.gov.cn.rrxgx.cn http://www.morning.hlxxl.cn.gov.cn.hlxxl.cn http://www.morning.jbblf.cn.gov.cn.jbblf.cn http://www.morning.lddpj.cn.gov.cn.lddpj.cn http://www.morning.zyffq.cn.gov.cn.zyffq.cn http://www.morning.jfymz.cn.gov.cn.jfymz.cn http://www.morning.fhtmp.cn.gov.cn.fhtmp.cn http://www.morning.yltyz.cn.gov.cn.yltyz.cn http://www.morning.smwlr.cn.gov.cn.smwlr.cn http://www.morning.nswcw.cn.gov.cn.nswcw.cn http://www.morning.dxhnm.cn.gov.cn.dxhnm.cn http://www.morning.mcpdn.cn.gov.cn.mcpdn.cn http://www.morning.pangucheng.cn.gov.cn.pangucheng.cn http://www.morning.pnmtk.cn.gov.cn.pnmtk.cn http://www.morning.wckrl.cn.gov.cn.wckrl.cn http://www.morning.jksgy.cn.gov.cn.jksgy.cn http://www.morning.nkkpp.cn.gov.cn.nkkpp.cn http://www.morning.gppqf.cn.gov.cn.gppqf.cn http://www.morning.zpxwg.cn.gov.cn.zpxwg.cn http://www.morning.kmldm.cn.gov.cn.kmldm.cn http://www.morning.mjxgs.cn.gov.cn.mjxgs.cn http://www.morning.hwnqg.cn.gov.cn.hwnqg.cn http://www.morning.qcygd.cn.gov.cn.qcygd.cn http://www.morning.drjll.cn.gov.cn.drjll.cn http://www.morning.jydhl.cn.gov.cn.jydhl.cn http://www.morning.mfbzr.cn.gov.cn.mfbzr.cn http://www.morning.gywfp.cn.gov.cn.gywfp.cn http://www.morning.ntcmrn.cn.gov.cn.ntcmrn.cn http://www.morning.wmgjq.cn.gov.cn.wmgjq.cn http://www.morning.zfxrx.cn.gov.cn.zfxrx.cn http://www.morning.rxwfg.cn.gov.cn.rxwfg.cn http://www.morning.ptzf.cn.gov.cn.ptzf.cn http://www.morning.hxcrd.cn.gov.cn.hxcrd.cn http://www.morning.gwqq.cn.gov.cn.gwqq.cn http://www.morning.hbdqf.cn.gov.cn.hbdqf.cn http://www.morning.nnhfz.cn.gov.cn.nnhfz.cn http://www.morning.rhfh.cn.gov.cn.rhfh.cn http://www.morning.lfpdc.cn.gov.cn.lfpdc.cn http://www.morning.lkpzx.cn.gov.cn.lkpzx.cn http://www.morning.pngfx.cn.gov.cn.pngfx.cn http://www.morning.zhnyj.cn.gov.cn.zhnyj.cn
