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

HUNAN  UNIVERSITY

课程实习报告

题    目：    杨辉三角显示                       

    学生姓名     康小雪                       

      学生学号     20090810310                   

    专业班级      计科三班                        

    指导老师       李晓鸿                         

    完 成 日  期              2010-10-18                                         

一、需求分析

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.，每一次出列时都将出列元素打印在屏幕上，在这个思想中，用到了先进先出，后进后出的思想，所以，利用队列来解决此问题，又由于整个运算结果是连续的，并且开销不大，故选择用数组来实现队列。

抽象数据类型

ADT Queue{

数据对象：D={∈ElemType,i=1,2,…,n,n>=0}

数据关系：R1={∈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）处理并计算模块；实现计算输入的杨辉三角各行各项的值，并打印在屏幕上

模块调用关系：

                   主函数模块

处理并计算模块

三、详细设计

物理数据类型

根据题目要求和堆栈的基本操作的特点，采用堆栈来实现。

//部分基本操作的函数原型

#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

    Q.base = (QElemtype *)malloc(MAXSIZE*sizeof(QElemtype));

    if (! S.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)

{

//插入元素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操作系统，执行文件为.exe

2、运行程序时

请输入n：//

//

七、实验心得（可选）

通过本次试验，我明白了，自己在审题方面存在很大的不足，代码实现依然是头疼的问题。以后要努力。

八、附录（可选）

    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)

{

//插入元素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 ",e1);

            EnQueue(Queue,e1);

        }

        else 

        {

            DeQueue(Queue,e2);

            printf("%d ",e2);

            EnQueue(Queue,e1+e2);

            e1=e2;

        }

    }    

    //printf("%d\\n",1);

    printf("\\n");

    EnQueue(Queue,1);

}

}

int main()

{

    int n;

    printf("请输入n：\\n");

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

        YangHuiTriangle(n);

    return 0;