数据结构实验报告—队列

1、算法与数据结构课程教师评阅意见：签名：年月日实验成绩：一、实验目的掌握队列的存储结构及进队/出队等操作的实现。二、实验内容及要求1. 实现队列的一种存储结构。2. 实现队列的相关操作。3. 利用队列的操作特点，借助进队与出队操作完成打印二项式系数的任务。三、系统分析(1) 数据方面：该队列数据元素类型采用整型，在此基础上进行队列的一些基本操作，应用体现在打印二项式系数即打印杨辉三角形。(2) 功能方面：1. 进队操作：若队列不满，则将元素x进入队列。2. 出队操作：若队列不空，则退出队头元素x并由函数返回true,否则返回false。3. 获取队头元素：若队列不为空，贝U函数返回true及队头

2、元素的值，否则返回false。4. 判断队列是否为空、判断队列是否满。5. 计算队列中元素个数：直接返回队列中元素个数。6. 活空队列内容：队头指针和队尾指针置0。7. 打印杨辉三角形前n行数字。四、系统设计(1)设计的主要思路队列得基丁数组得存储表示亦称为顺序队列，是利用一个一维数组作为队列元素的存储结构，并且设置两个指针front和rear,分别指示队歹U的队头和队尾位置。每当添加一个新元素时，先将新元素添加到rear所指位置，再让队尾指针rear进1。每当退出队头元素，应当先把front所指位置元素记录下来，再让队头指针进1,指示下一队头元素位置，最后把记录下来的元素值返回。但当队头指针

3、front=rear,队歹0为空；而当rear=maxSize时，队歹U满，如果再加入新元素，就会产生“溢出”。但这种“溢出”可能时假溢出，因为在数组的前端可能还有空位置。为了能够充分地使用数组中的存储空间，把数组的前端和后端连接起来，形成一个环形表，即把存储队歹0兀素的表从逻辑上看成一个环，成为循环队列。循环队列的首尾相接，当队头指针front和队尾指针rear进到maxSize-1后，再前进一个位置就自动到0.这可以利用除法取余的运算实现。(2)数据结构的设计队列的定义是一种限定存取位置的线性表。它只允许在表的一端插入，在另一端删除。允许插入的一端叫做队尾，允许删除的一端叫做队头。最先进入

4、队列的元素最先退出队列，队列这种特性叫做先进先出。对头指针进1：front=(front+1)%maxSize;队尾指针进1:rear=(rear+1)%maxSize;队歹0初始化：front=rear=0;循环队歹0的队头指针和队尾指针初始化时都设置为0:front=rear=0.在队尾插入新元素和删除队头元素时，两个指针都按顺时针方向进1.当它们进到maxSize-1时，并不表示表的终结，只要有需要，利用运算可以前进到数组的0号位置。五、编程环境与实验步骤(1) 编程环境操作系统：Windows操作系统；编程工具软件：VisualStudio2017(2) 实验步骤无文件操作。(3) 编

5、译参数无特殊的编译参数设置。六、实现代码主要功能的实现代码杨辉三角函数：voidYANGVI(intn)(Queue<int>q(n+2);inti=1;intj=0;ints=0,k=0;intt,u;q.EnQueue(i);q.EnQueue(i);for(i=1;i<=n;i+)(q.EnQueue(k);for(j=1;j<=i+2;j+)(q.DeQueue(t);u=s+t;q.EnQueue(u);s=t;a0=1;if(j!=i+2)(ao=s;o+;杨辉三角形输出显示函数：voidShow(int*a,intn)(inti,j;intsum=0;in

6、tk=0;for(i=0;i<n;i+)(for(j=0;j<n-i-1;j+)cout<<setw(3)<<""/前导空格，为单个数据的一半宽度for(j=0;j<=i;j+)(cout<<setw(6)<<asum+j;k+;sum=k;cout<<endl;SeqQueueffi环队歹U棋板：template<classT>classQueue(public:Queue(intsz=100);Queue()(deleteelements;boolEnQueue(T&x);

7、boolDeQueue(T&x);boolgetFront(T&x);voidmakeEmpty()(front=rear=0;boolIsEmpty();boolIsFull();intgetSize();friendostream&operator<<(ostream&os,Queue<T>&Q);private:intrear,front;T*elements;intmaxSize;template<classT>Queue<T>:Queue(intsz)(rear=0;front=0;maxSize

8、=sz;elements=newTmaxSize;assert(elements!=NULL);/断f：动态存储分配成功与否template<classT>boolQueue<T>:EnQueue(T&x)if(IsFull()=true)returnfalse;elementsrear=x;rear=(rear+1)%maxSize;returntrue;template<classT>boolQueue<T>:DeQueue(T&x)if(IsEmpty()=true)returnfalse;x=elementsfront;f

9、ront=(front+1)%maxSize;returntrue;template<classT>boolQueue<T>:getFront(T&x)if(IsEmpty()=true)returnfalse;x=elementsfront;returntrue;template<classT>boolQueue<T>:IsEmpty()return(front=rear)?true:false;template<classT>boolQueue<T>:IsFull()return(rear+1)%maxSize

10、=front)?true:false;template<classT>intQueue<T>:getSize()return(rear-front+maxSize)%maxSize;template<classT>ostream&operator<<(ostream&os,Queue<T>&Q)os<<"front="<<Q.front<<",rear="<<Q.rear<<endl;for(inti=Q.fro

11、nt;i!=Q.rear;i=(i+1)%Q.maxSize)os<<i<<":"<<Q.elementsi<<endl;returnos;七、测试结果与说明n为4时杨辉三角输出为：VS2017W.51JProject1OebugPro作:如什康；41I11211331清按任.意键继续一一n为10时杨辉三角输出为:F:jmVS2017?!jProject1DebugProject1,exe输入行数：10111121133114641151010511615201561172135352171182856705628811936

12、84126126843691请按任意键继续.-.n为20时杨辉三角输出为:20111121133114641510105116152015611721353521711S385&70562B811936E413612684369111045120210252210120451011.115516533042462獭1655511112通2204957929247924前22066121113732E57U12B71716171612S77152867313114933jM1D012W300334323003200210013649114111510545515653003&00

13、5M35643550O&30031365455105151116120560183C4368灿811412S7011440S008436818205的1.2016111713&6802380们槌123761M48243W243101944812376618823606801361711131535163060日豌1856431824437534S62D43753318241S164855330WB16153IS11191719刖3876116282713250388755S2923789237B755825D38827132116283S76日的17119请按任意健催探八、实验

14、分析(1) 算法的性能分析打印杨辉三角：从三角形的形状可知，除第一行以外，在打印第i行时，用到上一行(第i-1行)的数据，在打印第i+1行时，乂用到第i行的数据。队列的操作的时间复杂度都是O(1)。循环队列和链队列的空间性能的比较与顺序栈和链栈的空间性能比较类似，只是循环队列不能像顺序栈那样共享空间，通常不能在一个数组中存储两个循环队歹0。(2) 数据结构的分析队列是另一种限定存取位置的线性表。它只允许在表的一端插入，在另一端删除。队列所具有的这种特性就叫做先进先出。为了能够充分地使用数组中的空问，把数组的前端和后端连接起来，形成一个环形的表，即把存储队列元素的表从逻辑上看成一个环，成为循环队

15、列。适用场景：当储存数据比较大的时候适合用队列。九、实验总结经过几天的努力，完成了数据结构的队列的实验内容，能够熟练掌握队列的基本操作并且对丁队列的应用有所了解，掌握了队列的特点即先进先出，以及进队、出队等基本操作。并实现了队列的应用即打印二项展开式的系数。在程序的整个分析、设计、实现、测试等环节都有所收获。由丁前面几次实验积累的经验，加上课堂上老师的相应讲解，在程序的分析阶段花费的时间主要在确定队列存储方式上，在确定使用循环队列存储元素后，乂对循环队列的基本操作进行了学习,在掌握循环队列的实现后将代码编写完成后，这次实验也变得没那么困难了。本次实验的难点就在丁使用队列输出二项式系数，由丁需要用队列实现所以就必须要熟练掌握循环队列的实现代码，最开始写的时候由丁忽略了循环队列最多只能存储maxSize-1个元素，所以导致二项式系数输出的最后一行始终有问题，反复逐步调试了几次代码才发现了问题所在，这个过程让我印象比较深刻，对