队列的存储与操作

1、成绩评阅人重庆邮电大学课程设计实验报告班级：1301416姓名：陈昊学号：2014214156指导老师：夏晨洋课程名称：数据结构实验时间：2015年10月26日-2015年日月2日实验地点：数字图书馆负一楼 b132可编辑范本实验四 队列的存储与操作一、实验目的1理解队列是限定只能在队头进行删除操作在队尾进行插入操作的线性表；2理解队列的存储结构特点，掌握队列的存储分配要点；3掌握队列的基本操作及实现，深刻领会队列操作的先进先出特征，并能正确分析其时间复杂度，知道队列性能优于普通线性表，以及队列的常用情形。、主要数据结构描述class cirqueuepublic :cirqueue( );

2、cirqueue( );void enqueue(t x);t dequeue( );t getqueue( );bool empty( );private :t dataqueuesize;int front, rear;/ 构造函数，置空队/ 析构函数/将元素x入队/ 将队头元素出队/ 取队头元素（并不删除）/ 判断队列是否为空/ 存放队列元素的数组/ 队头和队尾指针，分别指向队头元素的前一个位置和队尾元素的位置;在循环队列这个数据结构中， 需要一个构造函数， 来创建一个空的队列； 需要一个析构函数来删除队列；需要一个 enqueue （）函数来插入一个数据；需要一个 dequeue （）

3、函数来将队头的元素出队；需要一个dequeue （）函数来输出队头的值；需要一个布尔型的函数来判断队列是否为空。三、算法的基本思想描述1 .构造函数：令头指针和尾指针均为零。2 .析构函数：空的析构函数。3 .入队函数：函数的形参为将存入队列的数据的值。因为判空和判满都需要用到rear=front,所以在判满的操作中，对rear+1取模，在循环的意义下进行判断。如果（ rear+1） %queuesize=front ，那么队满。如果没有队满，那么就在循环+1下标的位置存入当前数据。4 . 出队操作： 这里的出队不是删除相应的数据， 而是将队头指针 +1。 首先判断队是否为空，如果不为空就将队

4、头指针在循环意义上+1。5 . 取队头元素：将队头元素的值取出。6 . 判空：如果rear=front 则为空，否则不为空。因为不涉及循环，所以所有函数的时间复杂度都为 o（ 1）。运 行的结果截图请按任意键继续五、实验体会和收获经过本次试验。我对循环队列有了更深的理解。了解了队列先进先出的特点 知道了如何运用队列解决相应的问题。六、程序清单。cirqueue.h/cirqueue. hcir3ueue_hsdefuie cir3ueue_hconst工nt (ieuesize=lco ;定义存储ea列元素的数组的最大长度template class cirueue fpublic:cirqu

5、eue ():cirqueue(): void enqueue (t x).t dequeue()；t getqueue(): bool einpty (); private;t datafueuesise: int front k rear;)；7定义模板类c i rqueue“构造函翱，置空以析构函数将元需k入队耨队头元素出队取队头元素（并不删除）判斯队列是否为空存放队列元春的数组“队头和跳尾指针，分别指向队头元素的前一个位置和队尾元素的位置aendifzzl/cirqu&ue. cpp#i_ncluide cirqueue. h.17t&mplate -ci-rqueuet ： :cii

6、52uetie ()(fronts ear=0:-cirqueuep ： ： cirqueue()template v&id cirueue： :enqueue(t k) if ccrsar+1) % qusussiie =f rorrt) ,threw 上溢；rear=(rear+g % queuesize . m尾指料在循环意义下加1 dart a re ar在队屋处底入元素t&mplatt -t cirqu&ue;：dequeue()(“队头指针在循环意义下加1/读我并返回出队前的队头元素，注意队头指针if (rear=trorrt) throw 下益”； f rent- (front+

7、l % q-ueuesize: return data front:teiplaize -cclass t3-|t cirqueue： iequefue()iint i.;i (rea.r=front) ,throv 下溢；i= (fcont+1)将qu取号siew;注意不要给从头指针瞰值+1声明itenplate zjbaol cirqueue! :empty()：if ront=rear)veturri ：elsereturn 0 ：cirqueuemain.cpp可编辑范本j /./c i r(jue u emain. cpp“即用输入输出流引丸成员区1数文件创建模版类的实例#inclu

8、de using najnespace st d ;t include “c1rquene.cpp”-dvcid iitaih ()(cirqueuea：if (a-empty ( ) (cotrtc 环队列空，对i0执行入队操作：ysndl ：t ry(a, enqueue(lo):入队操作)cat ch (char# uirong)(ccut cwonj;)corrtd读勘队头元素i*endl ：c(xita. get queue ( ) endl:“读队头元素cout对lb执行入队操作上白力壮1 ：t ry(a. enqueue(15)：)cat ch (chart wrong)(cou

9、t wong;)coutv读的队头元素：endl.c ant a. qetqueue ( ) cendl:cout执行出队操作a即dl：”出队操作a. dequeue (),cout读取他头元素：tendl; coll! ai get queue ( ) endl;else (环网列不空17 endl.六、链队列链队列与顺序队列大致相同，只是用链表来表示而已。链队列的队头指针 指向头结点，队尾指针指向终端节点。基本数据结构：class linkqueue public :linkqueue( );/构造函数，初始化一个空的链队列linkqueue( );/析构函数，释放链队列中各结点的存储空间

10、void enqueue(t x);/ 将元素 x入队t dequeue( );/将队头元素出队t getqueue( );/取链队列的队头元素bool empty( );/判断链队列是否为空private :node *front, *rear; /队头和队尾指针，分别指向头结点和终端结点 ;思想与顺序队列一致。需要注意的是对节点的增加和删除。在enqueue() 中，将新申请的节点接在rear后，再让 伯2二新节点。在dequeue ()中, 要暂存队头元素，用来返回，再摘链。运行结果和程序：可编辑范本空看15看?队杳1q对查10执查1ss/linkqueue. h-.#ifndef li

11、nkqutue,h#define liwkqoeue_htemplate el struct node7 data;日代号仃*n=t; 此处 (工也可以省够匕template ,-.class linkqueuepublic;linkqueust );构造的数，初始化一个空的锚队列linkqueue ()： 祈梅函数，獐的链队列中各结点的存储空间void enqueuect x)： 将元素空入队i dequeue():牌队头元素出队i get queue (); “取链队列的队头元素tool empty ():判断镇吼列是否为空private:nade *front *rear；”队头和队.尾

12、指科，分别指向头结卓和翁端结点#endif;-1 /l iriltqtietife. cppsirclude “ litlhqueue. hteijilate hlinl:queue: linkdueue ()ii-iods 找q ： s=ylsw jtod*： s-next 二 mill; front=rtar=s:)+1声明t cuplate 3 l inltqiieiie: : tintequ.eue ()iwhile(f r ont)inode学p；p= r oiftztieqs t ； d&lei*? f rent ;f ron,t=p ,+ mltplate class t? vo

13、id link queue i :erqueue (t k)inode +s：erue mr ljcde;s-da.t 3fx ;申请一个数据域为芯的结点早s-nex+=null;rear- next=s ：将结点莒插入到队尾rearms;士|声明t emplate 71 linkqu&ue:;dequcue 0node #p: int x:if (rear=fron.t) th匚口下溢: p=front-nekt;“皆存队头元素将队头元素所在结点摘第判断出队前双列长度是否为1x=p-dala:f r ont-rext =p-,if (p-nekt-null) r&ar=f ront;dele

14、te p: return s:.)国|声明template t linkqusus: g-etqusus c)(.f (front 1-rea.r)return ron-t-nekt-data;templat e -bool lirjueui: rjnpty () if(frent=rear)return 1.elsereturn 0;ll/linkqujeujemain. cpp#include /弓 i 用输入输出 ij usinff naxespaca std;flincludelinkqueue. cpp”引入成员函数文件-vcid ntain 0l ink queue s;创建模版舞的实例rf (a. enpt/() cout队上4对1 0执行入队操作！ nj t rya enqueue(ia):入队操作) cat ch (chai* wrong) (cout wrong:)cout直看队头元寮! endl ：c out a. get queue ( ) endl; 读队头元安cmt对lb执行入队操作！久endkt ry (a, knqueti