杨辉三角实验报告

西安交通大学数据结构实验报告!循环链表,C算法!

---《杨辉三角》

专 业：自动化

班 级：自动化05

姓 名：陈绍清

学 号：10054112

指导教师：蔡忠闵 刘美兰

2011.12.20

西安交通大学数据结构实验报告!循环链表,C算法!

实验目的：逐行打印二项展开式 (a + b)i 的系数

杨辉三角形 (Pascal’s triangle)

1 1 i = 1

1 2 1 2

1 3 3 1 3 1 4 6 4 1 4 1 5 10 10 5 1 5 1 6 15 20 15 6 1 6 问题描述：

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

基本要求：

(1)

(2) 行数不大于20行。 基于队列的操作来实现杨辉三角的不断生成过程。（注：不要用其它的公式计算的方法或者二维数组来实现）

（3）基于数组实现队列的物理数据结构

需求分析：

1、输入形式：输入一个整数n ，0<=n<=20

2、输出形式：打印出来前(n+1)行的杨辉三角数列

3、功能实现：输出前20层的杨辉三角序列

实验内容：

1. 采用类c语言定义相关的数据类型

ADT Queue {

数据对象：D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 }

西安交通大学数据结构实验报告!循环链表,C算法!

数据关系：R1＝{ <ai-1 ,ai >| ai-1, ai ∈D, i=2,...,n } 约定an端为对列尾，a1端为对列头

基本操作：

{

InitQueue (&Q) //构造一个空对列

DestroyQueue (& Q) //销毁对列

ClearQueue (& Q) //将S清为空对列

QueueEmpty(Q) //判断是否为空对列，是则返回True QueueLength(Q) //返回对列的长度

GetHead (Q, &e) // 返回队头元素

EnQueue (& Q, e) //插入元素e为新的队尾元素 DeQueue (& Q, &e) // 删除队头元素，并用e返回

QueueTraverse(Q, visit()) //对每个元素都调用visit函数，如调用失败，则操作失效

}2.

各模块的流程图及伪码算法

Status InitQueue (SqQueue &Q )

{

Q.base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));

// 分配队列的存储空间;

if ( !Q.base ) exit( OVERFLOW ) ;

Q.front = Q.rear = 0; // 队头、尾指针清0

西安交通大学数据结构实验报告!循环链表,C算法!

return OK;

}

Status EnQueue (SqQueue &Q, QElemType e )

{

if ((( Q.rear + 1) % MAXQSIZE )

return( ERROR ) ;

Q.base [ Q.rear ] = e;

Q.rear = (( Q.rear + 1) % MAXQSIZE );

return OK;

} // EnQueue ;

typedef struct Qnode {

QElemType data;

struct Qnode *next;

} Qnode;

typedef struct {

Qnode *front;

Qnode *rear;

} LinkQueue;

== Q. front )

西安交通大学数据结构实验报告!循环链表,C算法!

void YangHui ( int n ) // n为需要输出的杨辉三角形的行数 { SqQueue q; int s=0, t;

InitQueue(q); EnQueue (q, 1);

EnQueue (q, 1);

for( int i=1; i<=n; i++ ) // 逐行计算

{ printf(“\n”); EnQueue (q, 0);

for ( int j=1; j<=i+2; j++ ) // 根据上行系数求下行系数 { DeQueue (q, t);

EnQueue (q, s+t);

s = t;

if ( j != i+2 ) printf(“%3d”, s); // 不输出每行结尾的0

}

}

}

3.算法思路：

西安交通大学数据结构实验报告!循环链表,C算法!

概要设计：

既然要用到队列来打印杨辉三角，那么肯定会利用到队列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) //得到队首元素

西安交通大学数据结构实验报告!循环链表,C算法!

void YangHui (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，导致问题的结果是没有相应的入队操作导致后面的杨辉三角很是紊乱！

实验结果调试：

设 计 总 结

西安交通大学数据结构实验报告!循环链表,C算法!

我的这次数据结构课程设计的题目是:《杨辉三角》,通过对该题目的设计,我加深了对数据结构及存储结构的理解,进一步地理解和掌握了课本中所学的各种数据结构，尤其是对单循环链表上基本运算的实现,学会了如何把学到的知识用于解决实际问题,锻炼了自己动手的能力。

在此过程我深深地意识到自己知识的严重不足！不断地充实自己才是目前的当务之急！三周的课程设计很短暂，但其间的内容是很充实的，在其中我学习到了很多平时书本中无法学到的东西，积累了经验，锻炼了自己分析问题，解决问题的能力，并学会了如何将所学的各课知识融会，组织起来进行学习，总而言之这三周中我学到很多，收益匪浅同时一定程度上提高了自己程序设计和阅读程序的能力。本次课程设计提高了我们的专业知识，使自己所学的内容运用到实际中来，也增强了实际操作能力，为以后的工作学习提供了一个良好的铺垫。

通过本次课程设计的实践学习，我认识到了学好计算机要重视实践操作，所以在以后的学习过程中，我会更加注重实践操作，使自己更好地学好计算机。

参考文献

西安交通大学数据结构实验报告!循环链表,C算法!

1 严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.

2 严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.

3 谭浩强.《c语言程序设计》. 清华大学出版社.

4.李春葆编著 《数据结构教程（上机实验指导）》 清华大学出版社

5.叶核亚主编 《数据结构（C++版）》 机械工业出版社

致 谢

西安交通大学数据结构实验报告!循环链表,C算法!

课程设计完成之际，除了感到一种轻松以外，马上想到的就是对老师以及在课程设计过程中帮助我的同学们，因为他们的指导和鞭策，才使我下定决心，集中精力投入到课程设计的建设。

首先感谢我的指导老师刘美兰老师，他在我的课程设计过程中提出了指导性的方案和架构，比如让我把密码设计成自动和手动两种方式，使我在不熟悉的领域中仍能迅速掌握新的技术。

感谢我的数据结构老师蔡忠闵老师在以往的基础课学习中为我打下良好的基础，这是我这次课程设计能够顺利完成的前提。

我的同学在这次课设中也给予了我一些好的建议！在此，也谢谢他们！

西安交通大学数据结构实验报告!循环链表,C算法!

附录一：C程序：

#define MAXSIZE 50

#include<stdio.h>

typedef int datatype;

typedef struct

{ int data[MAXSIZE];

int front;

int rear;

}SeqQueue;

SeqQueue*InitQueue()

{SeqQueue *q;

q=(SeqQueue* )malloc(sizeof(SeqQueue)); q->front=q->rear=0;

return q;

}

void EnQueue(SeqQueue*q,datatype x) {

if((q->rear+1)%MAXSIZE==q->front) {

printf("ERROR");exit(1);

}

q->data[q->rear]=x;

西安交通大学数据结构实验报告!循环链表,C算法!

q->rear=(q->rear+1)%MAXSIZE; }

datatype DeQueue (SeqQueue *q) {

datatype x;

if(q->front==q->rear)

{

printf("\nERROR");exit(1); }

x=q->data[q->front];

q->front=(q->front+1)%MAXSIZE; return x;

}

int QueueEmpty(SeqQueue*q) {

return(q->front==q->rear); }

int GetHead(SeqQueue*q)

{

int e;

if(q->front==q->rear)

e=0;

西安交通大学数据结构实验报告!循环链表,C算法!

else

e=q->data[q->front]; return e;

}

void YangHui (int n)

{

SeqQueue *q;

int i,j,s,t;

for(i=1;i<=n;i++)

printf(" ");

printf(" 1\n");

q=InitQueue();

EnQueue(q,0);

EnQueue(q,1);EnQueue(q,1); for(j=1;j<n;j++)

{

for(i=1;i<n-j;i++) printf(" ");

EnQueue(q,0);

do

{

s=DeQueue(q);

西安交通大学数据结构实验报告!循环链表,C算法!

t=GetHead(q);

if(t)printf("%5d",t); else printf("\n"); EnQueue(q,s+t); }

while(t!=0); }

DeQueue(q);

printf("%3d",DeQueue(q)); while(!QueueEmpty(q)) {

t=DeQueue(q); printf("%5d",t); }

}

main()

{

int n;

scanf("%d",&n);

printf("%d”,n\n");

YangHui (n);

}

本文来源：https://www.bwwdw.com/article/a5pj.html