杨辉三角队列实现.doc

杨辉三角显示问题描述：编写程序，根据输入的行数，屏幕显示杨辉三角。基本要求：(1) 行数不大于20行。(2) 基于队列的操作来实现杨辉三角的不断生成过程。（注：不要用其它的公式计算的方法或者二维数组来实现） （3）基于数组实现队列的物理数据结构需求分析： 1、输入形式：输入一个整数n ，0=n=20 2、输出形式：打印出来前(n+1)行的杨辉三角数列 3、功能实现：输出前20层的杨辉三角序列 4、样例输入输出：（数据加强版） 输入：10 输出： 1 n=1 1 1 n=2 1 2 1 n=3 1 3 3 1 n=4 1 4 6 4 1 n=5 1 5 10 10 5 1 n=6 1 6 15 20 15 6 1 n=7 1 7 21 35 35 21 7 1 n=8 1 8 28 56 70 56 28 8 1 n=9 1 9 36 84 126 126 84 36 9 1 n=10 5、效率分析：O(n)抽象数据类型（ ADT）: 抽象数据结构描述： Typedef struct Int qMaxSize;/存放队列中的元素 Int front,rear;/front和rear分别是指向队头和队尾的指针 Queue; 队列的基本操作： Void InitQueue(Queue Q) function:构造一个空队列 Void EnQueue(Queue Q,int x) :function:将元素x入队 Void DeQueue(Queue Q,int x):function:删除队头元素，并用x返回其值 Bool QueueEmpty(Queue Q) function:判断队列是否为空概要设计：既然要用到队列来打印杨辉三角，那么肯定会利用到队列FILO的性质（First In Lase Out），由于是要打印一个数列，那么肯定要利用已经进队的元素在其出队之前完成杨辉三角的递归性-即利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，我们来构造杨辉三角的第N+1行，从而实现打印杨辉三角的目的。详细设计： 算法思想已经在概要设计中提到了，现在通过基于队列基本操作的函数以及程序的模块化思想来实现杨辉三角的打印输出问题。算法函数描述： void EnterQueue(Queue &Q,int x)/入队 int DeleteQueue(Queue &Q, int &x) /出队 void GetHead(Queue &Q,int &x) /得到队首元素 void YangHuiTriangle(int n) /打印杨辉三角数表通过在void YangHuiTriangle(int n)中反复的调用void GetHead(Queue &Q,int &x)、int DeleteQueue(Queue &Q, int &x)、void EnterQueue(Queue &Q,int x)来实现打印.调试分析： 调试了很久很久啊，小的错误总是那么的多，主要遇到的问题有：typedef用法不很清楚，刚开始用指针实现的时候出现了问题；没有在基本操作中采用“传引用”的方式传参，导致很长的时间内，根本就没有相应的输出；刚开始在每一行中总是没有出现最后一个1，导致问题的结果是没有相应的入队操作导致后面的杨辉三角很是紊乱！测试结果：用户使用说明：该程序只支持1-20以内输入规模的操作C+代码实现：#includeusing namespace std;# define MaxSize 1001typedef struct double stMaxSize; int top;Stack;int main() int t; cint; getchar(); while(t-) Stack S; S.top=-1; char ch; bool f=1; while(cinch,ch!=#) if(ch= ) continue; if(f) / coutch=0 & ch=9) S.st+S.top=ch-0; else if(S.top1) f=0; if(f) if(ch=+) S.stS.top-1+=S.stS.top;S.top-; else if(ch=-) S.stS.top-1-=S.stS.top;S.top-; else if(ch=*) S.stS.top-1*=S.stS.top;S.top-; else if(ch=/) if(S.stS.top=0)f=0;continue; S.stS.top-1-=S.stS.top;S.top-; if(f & S.top=0) printf(%.2lfn,S