杨辉三角形实验报告.docx
《杨辉三角形实验报告.docx》由会员分享，可在线阅读，更多相关《杨辉三角形实验报告.docx（9页珍藏版）》请在冰点文库上搜索。
杨辉三角形实验报告
课内实验报告
题目：
编写程序，根据输入的行数，屏幕显示杨辉三角形（Pascal’striangle）
班级：
自动化05姓名:
刘丽丽
学号：
10054107完成日期：
2011.12.20
一．需求分析
1、本演示程序中，利用顺序队列打印杨辉三角。
杨辉三角的特点是两个腰上的数字都为1，其它位置上的数字是其上一行中与之相邻的两个整数之和，故在打印过程中，第i行上的元素要由第i-1行中的元素来生成。
这是一个基于队列的操作来实现杨辉三角不断生成的过程。
2、此次输出的杨辉三角不需要只有一个1的第一行，但只需对输出实际杨辉三角的程序稍作修改即可；
3、在计算机终端上显示"提示信息"之后，由用户在键盘上输入演示程序中需要输入的数据，以“回车符”为结束标志。
相应的输入数据和运算结果显示在其后。
4、程序执行的命令包括：
1）构造顺序队列；
2）分析第i行元素与第i+1行元素的关系
目的是从前一行的数据可以计算下一行的数据
从第i行数据计算并存放第i+1行数据
5、测试数据
输入行数n=3；
输出结果为：
11
121
1331
二．概要设计
链队列的抽象数据类型定义为：
ADTQueue{
数据对象：
D={ai|ai∈Elemset，i=1,2,3，···n，n＞=0}
数据关系：
R={＜ai-1,ai＞|ai-1,ai∈D,i=1,2,···n}（约定其中ai端为队列头，an端为队列尾）
基本操作：
InitQueue（&Q）
操作结果：
构造一个空队列
DestroyQueue（&Q）
初始条件：
队列已存在
操作结果：
队列被销毁
ClearQueue（&Q）
初始条件：
队列已存在
操作结果：
将Q清空
QueueEmpty（Q）
若队为空，则返回为TRUE，否则返回为FALSE。
Queuelength（Q）
初始条件：
队列已存在
操作结果：
返回Q的元素个数
Gethead（Q，&e）
初始条件：
队列非空
操作结果：
用e返回Q的队首元素
Enqueue（&Q，&e）
初始条件：
队列已存在
操作结果：
插入的元素e为Q的新队首元素
Dequeue（&Q，&e）
初始条件：
Q为非空
操作结果：
删除Q的队首元素，并用e返回其值
QueueTraverse（Q，visit（））
初始条件：
Q存在且非空
操作结果：
从队头到队尾，依次对Q的每个元素用函数visit（），一旦visit（）失败则操作失败
}ADTQueue
2、程序包含两个模块：
1）主程序模块：
voidmain（）
{
初始化；
Do
{
接受命令；
处理命令；
}while（“命令”！
=“退出“）；
}
2）顺序队列单元模块
各模块之间的调用关系如下：
主程序模块
顺序队列模块
三、详细设计
1、元素类型、结点类型和指针类型。
typedefstructsqQueue
{
int*base;
intfront;
intrear;
}SqQueue;、
2、基于程序的模块化思想，通过以下初始化队列、入队、取得队头元素等三个基本操作来实现程序，具体如下：
intInitQueue（SqQueue&Q）
{
Q.base=（int*）malloc（100*sizeof（int））;
//分配队列的存储空间;
if（!
Q.base）exit（0）;
Q.front=Q.rear=0;
return0;
}
intEnQueue（SqQueue&Q,inte）
{
if（（（Q.rear+1）%100）==Q.front）
return（0）;
Q.base[Q.rear]=e;
Q.rear=（（Q.rear+1）%100）;
return1;
}//EnQueue;
intDeQueue（SqQueue&Q,int&e）
{
if（Q.rear==Q.front）
return（0）;
e=Q.base[Q.front];
Q.front=（Q.front+1）%100;
return1;
}//DeQueue;
3、主函数
voidYangHui（intn）//n为需要输出的杨辉三角形的行数
{
SqQueueq;
ints=0,t,i,j,k;
InitQueue（q）;
EnQueue（q,1）;
EnQueue（q,1）;
for（i=1;i<=n;i++）//逐行计算
{
EnQueue（q,0）;
for（k=2*i;k<=n*（n+1）/2;k++）
printf（""）;
for（j=1;j<=i+2;j++）//根据上行系数求下行系数
{DeQueue（q,t）;
EnQueue（q,s+t）;
s=t;
if（j!
=i+2）
printf（"%4d",s）;//不输出每行结尾的0
}
printf（"\n"）;
}
}
voidmain（）
{
intn;
printf（"pleaseinputanumber:
\n"）;
scanf（"%d",&n）;
YangHui（n）;
}
四、调试分析
1、由于对队列的算法不熟，在早期调试的过程中出现了很多问题。
2、打印输出的数据是对的，但由于空格的输出没控制好，到后面由于有些数字位数较多，导致输出效果很不美观，而后通过根据数字位数多少来更改输出空格的语句，从而解决了这一问题；
3、本程序的模块设置比较合理
4、算法的时空分析
1）本算法的时间复杂度为：
O（i*（n-2））
2）本算法的空间复杂度为：
O（n*（n+5）/2）
5、本次实习作业采用数据抽象的程序设计方法，设计时思路清晰，实现调试时较为顺利，尤其是对杨辉三角的队列实现算法具有较好的可重复利用性，确实得到了一次良好的程序设计训练
五、用户手册
1、本程序的运行环境为Win7操作系统，MicrosoftVisualc++6.0，执行文件为：
YangHuiTriangle.exe；
2、进入演示程序后的用户界面为：
3、得到“pleaseinputanumber:
”的命令后，即提示键入杨辉三角形的行数，结束符为“回车符”；
4、输入数字即为杨辉三角形的行数，之后即输出要打印的杨辉三角形；
5、接受其他命令后即执行相应运算和显示相应的结果。
六、测试结果
1、执行命令n=1：
键入Enter键后结果为
2、执行命令n=2:
键入Enter键后结果为
3、执行命令n=6:
键入Enter键后结果为
七、附录
源程序文件名清单：
YangHuiTriangle.c//主程序
SqQueue//顺序队列类型
升级会员 