数据结构实验报告四—基于队列的操作来实现杨辉三角

杨辉三角显示问题描述：编写程序，根据输入的行数，屏幕显示杨辉三角。一、需求分析：1、行数不大于20行。2、基于队列的操作来实现杨辉三角的不断生成过程。（注：不要用其它的公式计算的方法或者二维数组来实现）3、基于数组实现队列的物理数据结构。输入形式：输入一个整数n(行数不大于20)输出形式：打印出来前(n+1)行的杨辉三角数列功能实现：输出前20层的杨辉三角序列样例输入输出形式：输入：6输出：1n=011n=1121n=21331n=314641n=415101051n=51615201561n=65、效率分析：O(n)二、概要设计：抽象数据类型voidQueue::EnQueue(intitem)//将元素item入列{QueueValue[++iLast]=item;}//入列intQueue::OutQueue()//第一个元素出列返回此元素{returnQueueValue[++iFront];}算法的基本思想：下面为主要实现生成杨辉三角的算法：Q.EnQueue(1);//第一行和第二行的生成Q.EnQueue(1);Q.EnQueue(1);coutQ.OutQueue()n=0\n;for(i=3;i=n+1;i++)//n行杨辉三角数的生成与输出{Q.EnQueue(1);t1=Q.OutQueue();for(j=2;ji;j++)//利用第n-1行的杨辉三角生成第n行的中间杨辉三角数{t2=t1;t1=Q.OutQueue();//第n-1行第j个元素出列Q.EnQueue(t1+t2);//第n行的第j个元素入列coutt2;}Q.EnQueue(1);//第n行最后一个元素为1coutt1n=i-2endl;}//输出第n-1行最后1个元素Q.EnQueue(0);//以防队列为空while(--i)//输出最后一行coutQ.OutQueue();coutn=nendl;}程序的流程程序由三个模块组成：输入模块：输入一个整数n计算模块：栈和杨辉三角的算法输出模块：在屏幕上打印出来前(n+1)行的杨辉三角数列三、详细设计算法的具体步骤：算法思想已经在概要设计中提到了，现在通过基于队列基本操作的函数以及程序的模块化思想来实现杨辉三角的打印输出问题。算法函数描述：实现杨辉三角的算法，代码在算法的基本思想中已经提出，算法的时空分析：由上可得该算法的时间复杂度O(n);输入和输出的格式：输入请输入n://输入一个数，这里输入6回车输出在屏幕上现实n+1行杨辉三角数列四、调试分析在编写过程中出现了部分错误，但最后经过讨论和调试都得到了解决。五、测试结果六、用户使用说明（可选）本程序的运行环境为windows操作系统，执行文件为yanghui.exe。七、实验心得（可选）此次实验没有通过什么公式，二维数组来实现杨辉三角，而是基于队列的操作来实现杨辉三角的不断生成过程。一方面了队列的应用与算法，而且也了解到了新的方法实现杨辉三角。在实验过程中遇到了部分问题，但通过与同学讨论得到了解决，挺有收获的，然需要再接再厉！附录（实验代码）：#includeiostream#includecstdlibusingnamespacestd;constintMaxSize=200;classQueue{friendvoidYangHuiSanJiao(intn);//生成杨辉三角的函数private:intQueueValue[MaxSize];//用一个数组实现队列intiFront,iLast;public:Queue(){iFront=iLast=-1;}voidEnQueue(intitem);//将元素item入列intOutQueue();};//第一个元素出列返回此元素voidQueue::EnQueue(intitem)//将元素item入列{QueueValue[++iLast]=item;}//入列intQueue::OutQueue()//第一个元素出列返回此元素{returnQueueValue[++iFront];}voidYangHuiSanJiao(intn)//生成杨辉三角的函数{QueueQ;intt1,t2;inti,j;//下面为主要实现生成杨辉三角的算法Q.EnQueue(1);//第一行和第二行的生成Q.EnQueue(1);Q.EnQueue(1);coutQ.OutQueue()n=0\n;for(i=3;i=n+1;i++)//n行杨辉三角数的生成与输出{Q.EnQueue(1);t1=Q.OutQueue();for(j=2;ji;j++)//利用第n-1行的杨辉三角生成第n行的中间杨辉三角数{t2=t1;t1=Q.OutQueue();//第n-1行第j个元素出列Q.EnQueue(t1+t2);//第n行的第j个元素入列coutt2;}Q.EnQueue(1);//第n行最后一个元素为1coutt1n=i-2endl;//输出第n-1行最后1个元素}Q.EnQueue(0);//以防队列为空while(--i)//输出最后一行coutQ.OutQueue();coutn=nendl;}intmain(){intn;cout请输入n:\n;cinn;//输入nYangHuiSanJiao(n);//生成杨辉三角并输出system(pause);return0;}