数据结构课程实验报告 实验4

HUNAN UNIVERSITY

课程实习报告

题 目： 杨辉三角显示

学生姓名 康小雪

学生学号 20090810310

专业班级 计科三班 指导老师 李晓鸿 完 成 日 期 2010-10-18

－ 1 －

数据结构课程实验指导书

一、 需求分析

1程序以用户和计算机对话方式得到n, n是大于等于0 小于等于20 的整数 2 由计算机通过公式计算出n行杨辉三角每一行的数值，并将计算的结果输出在屏幕上 3

输入输出举例 输入 n＝ 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

二、 概要设计 算法的基本思想

杨辉三角是一个由数字排列成的三角形数表，一般形式如下： 1 1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

1 6 15 20 15 6 1

...................................................... 杨辉三角最本质的特征是，它的两条斜边都是由数字1组成的，而其余的数则是等于它肩上的两个数之和。

于是先建立空的队列，将1入列，再把队列的最后一个元素出列，如果当前出列元素为1，则直接将其插入队尾，并保存其值，计算当前出列出列元素与下一个出列元素之和，插入队尾，并在队尾插入1.，若当前出列元素不为1，则计算当前出列出列元素与下一个出列元素之和，插入队尾，并在队尾插入1.，每一次出列时都将出列元素打印在屏幕上，在这个思想中，用到了先进先出，后进后出的思想，所以，利用队列来解决此问题，又由于整个运算结果是连续的，并且开销不大，故选择用数组来实现队列。

－ 2 －

数据结构课程实验指导书

抽象数据类型

ADT Queue{

数据对象：D={ai|ai∈ElemType,i=1,2,…,n,n>=0} 数据关系：R1={ai1，ai|ai1，ai∈D,i=2,…,n}

约定a1端为队列头，an端为队列尾。 基本操作： InitQueue (&Q)

操作结果：构造一个空队列S

Destroy Queue（& Q） 初始条件：队列Q已存在 操作结果：队列Q被销毁 ClearQueue（& Q）

初始条件：队列Q已存在 操作结果：队列Q清为空队列 QueueEmpty（Q）

初始条件：队列Q已存在

操作结果：若Q为空队列，则返回TRUE,否则FALSE QueueLength（Q）

初始条件：队列Q已存在

操作结果：返回Q元素的个数，即队列的长度 GetHead（Q &e）

初始条件：队列S已存在且非空 操作结果：用e返回Q的队头元素 EnQueue（& Q，e）

初始条件：队列Q已存在

操作结果：插入元素e为新的队尾元素 DeQueue（& Q,&e）

初始条件：队列Q已存在且非空

操作结果：删除Q的队头元素，并返回e QueueTraverse（Q,visit()）

初始条件：队列Q已存在且非空

操作结果：从队头到队尾依次对Q的每个元素调用函数visit()，一旦visit()失败，则操作失败

}ADT Stack 程序的流程

程序由两个个模块组成： （1） 主函数模块；

while(scanf(“%d”,&n),n<=20,n>=0)

YHTriangle(n);

（2） 处理并计算模块；实现计算输入的杨辉三角各行各项的值，并打印在屏幕上 模块调用关系：

－ 3 －

数据结构课程实验指导书

主函数模块

处理并计算模块

三、详细设计

物理数据类型

根据题目要求和堆栈的基本操作的特点，采用堆栈来实现。 //部分基本操作的函数原型 #define MAXQSIZE 100

#define STACKINCREMENT 10 #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OVERFLOW -2

typedef float QElemtype; typedef int Status;

typedef struct { QElemtype * base;

int front; int rear;

} SqQueue;

Status IniQueue (SqQueue &Q) {

//构造一个空队列Q }

int QueueLength(SqQueue Q) {

//返回Q的元素个数，即队列的长度

return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;

}

－ 4 －

Q.base = (QElemtype *)malloc(MAXSIZE*sizeof(QElemtype)); if (! S.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK;

数据结构课程实验指导书

Status EnQueue (SqQueue &Q, QElemtype e) {

//插入元素e为新的队尾元素

If((Q.rear+1)%MAXSIZE==Q.front) return ERROR;

*(Q.base+Q.rear*sizeof(QElemtype))=e; Q.rear=(Q.rear+1)%MAXSIZE;

return OK; }

Status DeQueue (SqQueue &Q, QElemtype &e) {

//若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK //否则返回ERROR

if(Q.front==Q.rear) return ERROR ;

e= *(Q.base+Q.rear*sizeof(QElemtype));

Q.front=(Q.front+1)%MAXSIZE; return OK; }

算法的时空分析

当输入为n时，出队列及入队列及计算的次数为n(n-1)/2,故复杂度为O（n^2） 输入和输出的格式

请输入n。//输出 等待输入

//输出结果的位置

四、调试分析

1．独立完成预习报告，在老师讲解实验报告之后才发现自己的算法错了，在写代码时及时更改自己的算法，写出相应代码。

2．编译通过之后，运行还是有问题，开始是运行错误，调试后发现不能用Q.base[Q.rear]=e，而必须改用*(Q.base+Q.rear*sizeof(QElemtype))=e;才能使运行不出错，但是我至今也不知为何啊。

3．最后在同学的帮助下，修改了代码，终于得出了正确的结果。 五、测试结果 请输入n： 5 1 1 1 1 2 1 1 3 3 1

1 4 6 4 1

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

1、本程序的运行环境为DOS操作系统，执行文件为gcd.exe 2、运行程序时 请输入n：//

－ 5 －

数据结构课程实验指导书

//

七、实验心得（可选）

通过本次试验，我明白了，自己在审题方面存在很大的不足，代码实现依然是头疼的问题。以后要努力。 八、附录（可选） Gcd.c 主程序 #include #include #define MAXSIZE 100 #define STACKINCREMENT 10 #define OK 1 #define TRUE 1 #define FALSE 0 #define ERROR 0 #define OVERFLOW -2 typedef int QElemtype; typedef int Status; typedef struct { QElemtype * base; int front; int rear; } SqQueue; Status IniQueue (SqQueue &Q) { //构造一个空队列Q Q.base = (QElemtype *)malloc(MAXSIZE*sizeof(QElemtype)); if (! Q.base) exit(OVERFLOW); Q.front=Q.rear=0; return OK; } int QueueLength(SqQueue Q) { //返回Q的元素个数，即队列的长度 return (Q.rear-Q.front+MAXSIZE)%MAXSIZE; } Status EnQueue (SqQueue &Q, QElemtype e) － 6 －

数据结构课程实验指导书

{ //插入元素e为新的队尾元素 if((Q.rear+1)%MAXSIZE==Q.front) return ERROR; *(Q.base+Q.rear*sizeof(QElemtype))=e; Q.rear=(Q.rear+1)%MAXSIZE; return OK; } Status DeQueue (SqQueue &Q, QElemtype &e) { //若队列不为空，则删除Q的队头元素，用e返回其值，并返回OK //否则返回ERROR if(Q.front==Q.rear) return ERROR ; e=*(Q.base+Q.front*sizeof(QElemtype)); Q.front=(Q.front+1)%MAXSIZE; return OK; } void YangHuiTriangle(int n) { SqQueue Queue; QElemtype e1,e2; e1=1; IniQueue(Queue); EnQueue(Queue,e1); for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { } if(j==1) { DeQueue(Queue,e1); printf(\"%d \EnQueue(Queue,e1); } else { } DeQueue(Queue,e2); printf(\"%d \EnQueue(Queue,e1+e2); e1=e2; //printf(\"%d\\n\－ 7 －

数据结构课程实验指导书

} } printf(\"\\n\"); EnQueue(Queue,1); int main() { }

int n; printf(\"请输入n：\\n\"); while(scanf(\"%d\ YangHuiTriangle(n); return 0; － 8 －