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

问题描述：

编写程序，根据输入的行数，屏幕显示杨辉三角。

一、需求分析：

1、行数不大于20行。

2、基于队列的操作来实现杨辉三角的不断生成过程。（注：不要用其它的公式计算的方法或者二维数组来实现） 3、基于数组实现队列的物理数据结构。

输入形式：输入一个整数n (行数不大于20) 输出形式：打印出来前(n+1)行的杨辉三角数列 功能实现：输出前20层的杨辉三角序列 样例输入输出形式： 输入：6 输出：

1 n=0 1 1 n=1 1 2 1 n=2 1 3 3 1 n=3 1 4 6 4 1 n=4 1 5 10 10 5 1 n=5 1 6 15 20 15 6 1 n=6

5、效率分析：O(n)

二、概要设计 ：

抽象数据类型

void Queue::EnQueue(int item) //将元素

item入列

{QueueValue[++iLast]=item; } //入列

int Queue::OutQueue() //第一个元素出列 返回此元素 { return QueueValue[++iFront];}

算法的基本思想 ：

下面为主要实现生成杨辉三角的算法：

Q.EnQueue(1); //第一行和第二行的生成 Q.EnQueue(1); Q.EnQueue(1);

cout<for(i=3;i<=n+1;i++) //n行杨辉三角数的生成 与输出 {Q.EnQueue(1); t1=Q.OutQueue();

for(j=2;jt1=Q.OutQueue(); //第n-1行第j个元素出列 Q.EnQueue(t1+t2); //第n行的第j个元素入列 cout<Q.EnQueue(1); //第n行最后一个元素为1 cout<程序的流程

程序由三个模块组成：

输入模块：输入一个整数n 计算模块：栈和杨辉三角的算法

输出模块：在屏幕上打印出来前(n+1)行的杨辉三角数列

三、详细设计

算法的具体步骤：

算法思想已经在概要设计中提到了，现在通过基于队列基本操作的函数以及程序的模块化思想来实现杨辉三角的打印输出问题。

算法函数描述：实现杨辉三角的算法，代码在算法的基本思想中已经提出，

算法的时空分析：

由上可得该算法的时间复杂度O(n); 输入和输出的格式： 输入

请输入n: //输入一个数，这里输入6 回车 输出

在屏幕上现实n+1行杨辉三角数列

四、调试分析

在编写过程中出现了部分错误，但最后经过讨论和调试都得到了解决。

五、测试结果

六、用户使用说明（可选）

本程序的运行环境为windows 操作系统，执行文件为yanghui.exe 。

七、实验心得（可选）

此次实验没有通过什么公式，二维数组来实现杨辉三角，而是基于队列的操作来实现杨辉三角的不断生成过程。一方面了队列的应用与算法，而且也了解到了新的方法实现杨辉三角。在实验过程中遇到了部分问题，但通过与同学讨论得到了解决，挺有收获的，然需要再接再厉！

附录（实验代码）： #include #include

using namespace std; const int MaxSize=200;

class Queue

{friend void YangHuiSanJiao(int n); //生成杨辉三角的函数 private:

int QueueValue[MaxSize]; //用一个数组实现队列 int iFront,iLast; public:

Queue(){iFront=iLast=-1;}

void EnQueue(int item); //将元素item入列 int OutQueue(); }; //第一个元素出列 返回此元素 void Queue::EnQueue(int item) //将元素item入列 { QueueValue[++iLast]=item; } //入列

int Queue::OutQueue() //第一个元素出列 返回此元素 { return QueueValue[++iFront];}

void YangHuiSanJiao(int n) //生成杨辉三角的函数 {Queue Q; int t1,t2; int i,j;

//下面为主要实现生成杨辉三角的算法 Q.EnQueue(1); //第一行和第二行的生成

Q.EnQueue(1); Q.EnQueue(1);

cout<for(i=3;i<=n+1;i++) //n行杨辉三角数的生成 与输出 { Q.EnQueue(1);

t1=Q.OutQueue();

for(j=2;jt1=Q.OutQueue(); //第n-1行第j个元素出列 Q.EnQueue(t1+t2); //第n行的第j个元素入列 cout<Q.EnQueue(1); //第n行最后一个元素为1 cout<Q.EnQueue(0); //以防队列为空 while(--i) //输出最后一行 cout<int main() {int n;

cout<<\"请输入n:\\n\"; cin>>n; //输入n

YangHuiSanJiao(n); //生成杨辉三角并输出 system(\"pause\"); return 0; }