// 杨辉三角.cpp : Defines the entry point for the console application. //
#include
#include
#define MAXSIZE 20
int N;
typedef struct {
int *base;
int front;
int rear;
}SqQueue;//定义队列
bool InitQueue(SqQueue &Q)//初始化队
{
Q.base=(int *)malloc(MAXSIZE*sizeof(int));
if (!Q.base)
{
printf("OVERFLOW\n");
return false;
}
Q.front=0;
Q.rear=0;
return true;
}
bool QueueEmpty(SqQueue Q)//判断队是否空
{
if (Q.front==Q.rear)
{
return true;
}
else
return false;
}
int GetHead(SqQueue Q,int &e)//取队头元素
{
if (QueueEmpty(Q))
{
return -1;
}
else
{
e=Q.base[Q.front];
return 0;
}
}
int QueueLength(SqQueue Q)//求队长
{
return (Q.rear-Q.front+MAXSIZE)%MAXSIZE;
}
bool EnQueue(SqQueue &Q,int e)//入队
{
if (Q.front==(Q.rear+1)%MAXSIZE)
{
printf("Queue full\n");
return false;
}
Q.base[Q.rear]=e;
Q.rear=(Q.rear+1)%MAXSIZE;
return true;
}
bool DeQueue(SqQueue &Q,int &e)//出队
{
if (Q.front==Q.rear)
{
printf("Queue empty\n");
return false;
}
e=Q.base[Q.front];
Q.front=(Q.front+1)%MAXSIZE;
return true;
}
void print_n(int n)//打印N*3个空格
{
int i;
for(i=0;i { printf(" "); } } void C_Queue(SqQueue &Q,int e)//生产杨辉三角并输出{ int m=0; int pre; int i; printf("%d:",e); print_n(N-e); for(i=0;i<=e;i++) { pre=m; DeQueue(Q,m); printf("%3d ",m); EnQueue(Q,m+pre); } EnQueue(Q,m); printf("\n"); } int main(int argc, char* argv[]) { SqQueue Q; InitQueue(Q); int i; int n; printf("请输入杨辉三角的阶数(0-12)："); scanf("%d",&n); N=n; if (n>12||n<0) { printf("输入不合法\n"); return -1; } EnQueue(Q,1); for(i=0;i<=N;i++) { C_Queue(Q,i); } return 0; } 杨辉三角的规律以及定理 李博洋 摘要杨辉三角中的一些规律 关键词杨辉三角幂二项式 引言 杨辉是我国南宋末年的一位杰出的数学家。在他所着的《详解九章算法》一书 中，画了一张表示二项式展开后的系数构成的三角图形，称做“开方做法本源”，现 在简称为“杨辉三角”，它是世界的一大重要研究成果。我们则来对“杨辉三角”的 规律进行探讨和研究。 内容 1二项式定理与杨辉三角 与杨辉三角联系最紧密的是二项式乘方展开式的系数规律，即。 杨辉三角我们首先从一个二次多项式(a+b)2的展开式来探讨。 由上式得出：(a+b)2＝a2+2ab+b2此代数式的系数为：121 则(a+b)3的展开式是什么呢？答案为：a3+3a2b+3ab2+b3由此可发现，此代数式的系数 为：1331但似乎没有什么规律，所以让我们再来看看(a+b)4的展开式。 展开式为：a4+4a3b+6a2b2+4ab3+b4由此又可发现，代数式的系数为： 14641似乎发现了一些规律，就可以发现以下呈三角形的数列： 1(110) 11(111) 121(112) 1331(113) 14641(114) 15101051(115) 1615201561(116) 因此可得出二项式定理的公式为： (a+b)n=C(n,0)a^n*b^0+C(n,1)a^(n-1)*b^1+...+C(n,r)a^(n-r)*b^r...+C(n,n)a^0*b^n 因此，二项式定理与杨辉三角形是一对天然的数形趣遇，它把带进了。求二项式展开式系数的问题，实际上是一种组合数的计算问题。用系数来计算，称为“式算”；用杨辉三角形来计算，称作“图算”。 2杨辉三角的幂的关系 首先我们把杨辉三角的每一行分别相加，如下： 1(1) 11(1+1=2) 121(1+2+1=4) 1331(1+3+3+1=8) 14641(1+4+6+4+1=16) 15101051(1+5+10+10+5+1=32) 1615201561(1+6+15+20+15+6+1=64) …… 相加得到的数是1，2，4，8，16，32，64，…刚好是2的0，1，2，3，4，5，6，…次幂，即杨辉三角第n行中n个数之和等于2的n-1次幂 3杨辉三角中斜行和水平行之间的关系 (1) 1(2)n=1 11(3)n=2 121(4)n=3 1331(5)n=4 网上看了许多杨辉三角队列实现的代码，结果运行时都或多或少有点小问题，为此我提供一份自己运行正确的。 程序无误，细心做一下 注意，这是做成三个文件运行的 第一个文件命名 stdafx.h #include int GetQueueFirstData(SqQueue Q) { return Q->base[Q->front]; } int isEmptyQueue(SqQueue Q) { if(Q->front=Q->rear) return 1; else return 0; } SqQueue InitQueue() { SqQueue Q; Q=(SqQueue)malloc(sizeof(struct queue)); if (Q==NULL) return NULL; Q->base=(int *)malloc(Max*sizeof(int)); if(Q->base==NULL) return NULL; Q->front=Q->rear=0; return Q; } int EnQueue(SqQueue Q,int e) { if((Q->rear+1)%Max==Q->front) return 0; Q->base[Q->rear]=e; Q->rear=(Q->rear+1)%Max; return 1; } int DeQueue(SqQueue Q) { int e; if(Q->front==Q->rear) return 0; e=Q->base[Q->front]; Q->front=(Q->front+1)%Max; return e; } 显示杨辉三角实验报告 姓名：许严班级：计122 学号：1213023050 1.问题描述 杨辉三角如图2.4.3所示，其特点是两个腰上数值是1，其他位置上的每一个整数都是它的上一行相邻两个整数之和。问题是：对于指定的最大行数rmax,要求从第一行到第rmax逐行显示杨辉三角形的所有元素。 2.基本要求 ⑴设计输出形式，尽量反映杨辉三角的特点。 ⑵设计计算杨辉三角形各行数值的方法。 ⑶输入：rmax从键盘输入。 ⑷输出：屏幕输出杨辉三角形. 3.实现提示 ⑴存储设计 计算杨辉三角形第i行时，如果在第i-1行两侧各添加一个0，则第i行的第j个元素等于第i-1行的第j-1个元素与第j个元素的和。计算如图2.4.4所示。第i行计算完，第i-1行的数据就没有用了，依据第i行数据可计算第i+1行的数据。 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 … 图2.4.3 杨辉三角形 从上述计算中不难看出，第i行的元素从左往右依次可被求得，求解过程中也是从左往右依次使用地i-1行的数据，显然，具有先入先出的特点。所以，可借助一个队列存放计算过程中所需的数据，如图2.4.5所示。 但随着航数的增加，队列会很长。所以，可以设置一循环队列，队长不少于rmax+2,边计算边出队。 （2）算法设计 计算各行元素的算法步骤如下。 Step1:队列初始化，0、1入队。队头ftont指向0处，队尾指向1后。 Step2:i从1到rmax,循环执行下列操作，求第i行数据。 2.1 0入队。 2.2 从队首起直到队尾，每出队两元素，求和后入队。 输出时注意0不输出。 杨辉三角形规律 每行数字两边对称每行数字左右对称，由1开始逐渐变大，然后变小，回到1。 第n行的数字个数为n个。 第n行数字和为2^(n－1)。（2的（n-1）次方） 每个数字等于上一行的左右两个数字之和。可用此性质写出整个帕斯卡三角形。 将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第2n个斐波那契数。将第2n行第2个数，跟第2n+1行第4个数、第2n+2行第6个数……这些数之和是第2n-1个斐波那契数。 第n行的第1个数为1，第二个数为1×(n-1)，第三个数为1×(n-1)×（n-2）/2，第四个数为1×(n-1)×（n-2）/2×（n-3）/3…依此类推。 两个未知数和的n次方运算后的各项系数依次为杨辉三角的第(n+1)行 杨辉三角在弹球游戏中的应用 如图1的弹球游戏，小球向容器内跌落，碰到第一层挡物后向两侧跌落碰到第二层阻挡物，再向两侧跌落第三层阻挡物，如此一直下跌最终小球落入底层。根据具体地区获的相应的奖品（。 图1 我们来分析一下为什么小球落到不同区域奖品会有如此大的差别？A 区的奖品价值高于D 区，说明小球落入A 区的可能性要比落入D 区的可能性小，转化为数学问题就是小球落入A 区和D 区的概率。小球要落入D 区的情况有两种，有概率知识得： D 1 D 2 就是说，小球落入D 区的概率是等于它肩上两区域概率之和的 2 1，据此小球落入各区的概率为可以按以上方法类推，如下： 2121 1 8381 3213232323232 1 64646641564206415646641 A B C D E F G 图2 队列实验 学号：姓名： 一、实验目的： 1．掌握队列的顺序存储结构 2．掌握队列先进先出运算原则在解决实际问题中的应用 二、实验内容： 利用循环顺序队列打印杨辉三角形。杨辉三角形的特点是两个腰上的数字都为1，其它位置上的数字是其上一行中与之相邻的两个整数之和。所以在打印过程中，第i行上的元素要由第i-1行中的元素来生成。在循环队列中依次存放第i-1行上的元素，然后逐个出队并打印，同时生成第i行中间的（n-2）个元素并入队列。打印的杨辉三角形如下所示： 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 三、队列顺序存储结构的基本操作： 杨辉三角形输出的行数可以在程序中由输入控制。 队列的基本操作代码参考如下： #include /*初始化操作*/ void InitQueue(SeqQueue *Q) { /* 将*Q初始化为一个空的循环队列*/ Q->front=Q->rear=0; } /*入队操作*/ int EnterQueue(SeqQueue *Q, int x) { /*将元素x入队*/ if((Q->rear+1)%MAXSIZE==Q->front) /*队列已经满了*/ return(FALSE); Q->rear=(Q->rear+1)%MAXSIZE; /* 重新设置队尾指针*/ Q->element[Q->rear]=x; return(TRUE); /*操作成功*/ } /*出队操作*/ int DeleteQueue(SeqQueue *Q, int *x) { /*删除队列的队头元素，用x返回其值*/ if(Q->front==Q->rear) /*队列为空*/ return(FALSE); Q->front=(Q->front+1)%MAXSIZE; /*重新设置队头指针*/ *x=Q->element[Q->front]; return(TRUE); /*操作成功*/ } /*提取队列的队头元素，用x返回其值*/ int GetHead(SeqQueue *Q, int *x) { if(Q->front==Q->rear) /*队列为空*/ return(FALSE); *x=Q->element[Q->front]; return(TRUE); /*操作成功*/ } 四、打印杨辉三角的函数： void PrintTriangle (int N ) { int i,,n,x,temp; SeqQueue Q; ?、实验目的 1. 了解队列的特性。 2. 掌握队列的顺序表示和实现。 3. 掌握队列的链式表示和实现。 1、实验内容 实验3. 3队列的顺序表示和实现 编写一个程序实现顺序队列的各种基本运算（采用循环队列）， 主程序，完成如下功能： ⑴ 初始化队列。 ⑵ 建立顺序队列。 ⑶ 入队。 ⑷ 岀队。 (5) 判断队列是否为空。 ⑹ 取队头元素。 (7) 遍历队列。 实验3.4队列的链式表示和实现 编写一个程序实现链队列的各种基本运算，并在此基础上设计 能： (1) 初始化并建立链队列 ⑵ 入链队列。 ⑶ 岀链队列。 ⑷ 遍历链队列。 #i nclude int Ini tQueue(SqQueue &Q) { Q.base=(i nt*)malloc(MAXQSIZE*sizeof(i nt)); if(!Q.base)exit(O); Q.fro nt=Q.rear=0; return 0; }//初始化顺序队列 int QueueLe ngth(SqQueue Q) { int i; i=(Q.rear-Q.fro nt+MAXQSIZE)%MAXQSIZE; printf(“队列长度％5d\n",i); if(i)printf(" 队列非空“)； else printf(" 队列为空"); return 0; }//判断队列是否为空 int En Queue(SqQueue &Q,i nt e) { if((Q.rea 叶1)%MAXQSIZE==Q.fro nt)return 0; Q.base[Q.rear]=e; Q.rear=(Q.rea r+1)%MAXQSIZE; return 0; }//将元素e入队 int DeQueue(SqQueue & Q,i nt e) { if(Q.fro nt==Q.rear)return 0; e=Q.base[Q.fro nt]; prin tf("%5d\n",e); Q.fron t=(Q.fr on t+1)%MAXQSIZE; return 0; }// 删除元素e并返回其值 第三章栈和队列试题 一、单项选择题 1.栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 2.当利用大小为n的数组顺序存储一个栈时，假定用top==n表示栈空，则向这个栈插入一个元素时， 首先应执行（）语句修改top指针。 A. top++; B. top--; C. top = 0; D. top; 3.若让元素1,2,3依次进栈，则出栈次序不可能出现（）种情况。 A. 3, 2, 1 B. 2, 1, 3 C. 3, 1, 2 D. 1, 3, 2 4.在一个顺序存储的循环队列中，队头指针指向队头元素的（）位置。 A. 前一个 B. 后一个 C. 当前 D. 后面 5.当利用大小为n的数组顺序存储一个队列时，该队列的最大长度为（）。 A. n-2 B. n-1 C. n D. n+1 6.从一个顺序存储的循环队列中删除一个元素时，需要（）。 A. 队头指针加一 B. 队头指针减一 C. 取出队头指针所指的元素 D. 取出队尾指针所指的元素 7.假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front+1 == rear B. rear+1 == front C. front == 0 D. front == rear 8.假定一个链式队列的队头和队尾指针分别为front和rear，则判断队空的条件为（）。 A. front == rear B. front != NULL C. rear != NULL D. front == NULL 9.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一 个由指针s所指的结点，则应执行操作（）。 A. top->link = s; B.s->link = top->link; top->link = s; C. s->link = top; top = s; D. s->link = top; top = top->link; 10.设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点， 并将被摘除结点的值保存到x中，则应执行操作（）。 A. x = top->data; top = top->link; B. top = top->link; x = top->data; C. x = top; top = top->link; D. x = top->data; 11.设循环队列的结构是 #define MaxSize 100 typedef int ElemType; Main： queue.h： typedef int ElemType; typedef struct Inode{ ElemType data; struct Inode *next; }Inode; typedef struct linkque{ Inode *front; Inode *rear; }linkque; int QueInit(linkque &); int QueIn(linkque &,ElemType); int QueOut(linkque &,ElemType &); app.cpp： #include printf("%d",e2); printf("\n"); } while(q2.front!=q2.rear){ QueOut(q2,e); QueIn(q1,e); } } } queue.cpp： #include for(i=1;i<=N;++i) { for(j=0;j<30-3*i;++j)//打印每行前面的空格 printf(" "); do { DeQueue(); GetHead(); if(e!=0) printf("%6d",e); EnQueue(); }while(e!=0); UpQueue(); puts("");//每行后回车换行 } 以n=4举例 结果为： 1 1 1 2 1 1 3 3 1 1 4 6 4 1 解析： queue_size=n+2;//队列的最大容量queue_size=6（数组空间大小） for(i=0;i 继续执行do……while语句因为e不为0 DeQueue(); 删除队首元素，并将queue[2]赋值s front=3 GetHead(); 取队首元素，e= queue[front]=queue[3]=1 if(e!=0) printf("%6d",e); e！=0 打印e 即1 EnQueue(); 在队尾添加元素s+e 此时queue[rear]=queue[0]=2 rear=1 继续执行do……while语句因为e不为0 DeQueue(); 删除队首元素，并将queue[3]赋值s front=4 GetHead(); 取队首元素，e= queue[front]=queue[4]=0 if(e!=0) printf("%6d",e); e==0 不执行printf（）语句 EnQueue(); 在队尾添加元素s+e 此时queue[rear]=queue[1]=1 rear=2 此时e==0跳出do……while语句 即打印第一行完毕输出： 1 1 UpQueue(); 在队尾添加元素0 即queue[rear]=queue[2]=0 rear=3 队列为： 2 1 0 1 0 1 puts("");//每行后回车换行rear front 实验二栈与队列操作 实验目的： (1)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。 (2)了解复杂问题的递归算法设计。 本次实验中，下列实验项目选做一。 1、顺序栈的基本操作 [问题描述] 设计算法，实现顺序栈的各种基本操作 [基本要求] （1）初始化栈s。 （2）从键盘输入10个字符以$结束，建立顺序栈。 （3）从键盘输入1个元素，执行入栈操作。 （4）将栈顶元素出栈。 （5）判断栈是否为空。 （6）输出从栈顶到栈底元素。 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 2、链栈的基本操作 [问题描述] 设计算法，实现链栈的各种基本操作 [基本要求] （1）初始化栈s。 （2）从键盘输入10个字符以$结束，建立带头结点的链栈。 （3）从键盘输入1个元素，执行入栈操作。 （4）完成出栈操作。 （5）判断栈是否为空。 （6）输出从栈顶到栈底元素。 （7）输出链栈的长度。 要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 3、循环队列的基本操作 [问题描述] 设计算法，实现循环顺序队列的建立、入队、出队等操作。 [基本要求] （1）从键盘输入10个字符以$结束，建立循环队列，并显示结果。 （2）从键盘输入1个元素，执行入队操作，并显示结果。 （3）将队头元素出队，并显示结果。 （4）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。 4、只用尾指针表示的循环链表队列的综合操作 [问题描述] 假设以带头结点的的循环链表表示队列，并且只设一个指针指向队尾元素的结点（注意不设头指针），试编写队列初始化、入队、出队函数。 [基本要求及提示] （1）首先定义链表结点类型。 （2）编写带头结点的循环链表的初始化函数，只用尾指针表示。 （3）编写入队函数、出队函数。 （4）在主函数中编写菜单（1.初始化；2.入队；3.出队；4.退出），调用上述功能函数。 5、用标志域表示队空队满状态的循环队列的综合操作 [问题描述] 要求循环队列不损失一个空间全部都得到利用，设置一个标志域tag，以0和1来区分当队头与队尾指针相同时队列状态的空和满，试编写与此结构相对应的入队和出队操作。 [基本要求及提示] （1）教材中为区分当队头与队尾指针相同时队列状态的空和满，以牺牲一个空间的代价来实现的，空：Q->front==Q->rear,满：（Q->rear+1）%MAXSIZE==Q->front。 （2）本题不损失一个空间全部都得到利用，为此如下定义循环队列类型： Typedef struct { QueueElementType element[MAXSIZE]; int front; int rear; int tag; }SeqQueue; 此时，循环队列空和满的条件分别为： Q->front==Q->rear&&tag==0 和 Q->front==Q->rear&&tag==1 （3）编写入队函数、出队函数。 （4）在主函数中编写菜单（1.入队；2.出队；3.退出），调用上述功能函数。 6、利用辅助数组进行栈的逆置 [问题描述] 利用辅助栈将栈中的元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入栈；2.出栈；3.逆置；4.退出）调试运行程序。 7、利用辅助栈进行队列的逆置 [问题描述] 利用辅助栈进行队列元素逆置。 [基本要求及提示] 在主函数中编写菜单（1.入队；2.出队；3.逆置；4.退出）调试运行程序。 8、Hanoi塔问题 精心整理 杨辉三角的规律以及定理 二项式定理与杨辉三角1与杨辉三角联系最紧密的是二项式乘方展开式的系数规律，即二项式定理。 2的展开式来探讨。杨辉三角我们首先从一个二次多项式(a+b)222此代数式的系数为：121 由上式得出：(a+b)+2ab+b＝由此可发现，此代数式的系+3+b+3ab(a+b 的展开式是什么呢？答案为(a+b的展开式。为133但似乎没有什么规律，所以让我们再来看b2+4a展开式为由此又可发现，代数式的系数为+4+b+6464似乎发现了一些规律，就可以发现以下呈三角形的数列：1 ) 1(1)11(112) 121(113) 1331(114) 14641(115) 15101051(116) 1615201561(11）1,4,6,4,1,（,1,2,1）（1,3,3,1）1,杨辉三角形的系数分别为：（1,1）,（：所以（）,1,7,21,35,35,21,7,1） （1,5,10,10,5,1）,（1,6,15,20,15,6,17642547765233 (a+b)=ab+7ab+21a+bb+35a+7abb+35a。b+21a n的次数依次上b-n，n-n 等于a的次数依次下降、n-1、2...n由上式可以看出，(a+b) (2) 方。系数是杨辉三角里的系数。、、升，01 杨辉三角的幂的关系2 精心整理． 精心整理 首先我们把杨辉三角的每一行分别相加，如下： 1(1) 11(1+1=2) 121(1+2+1=4) 1331(1+3+3+1=8) 14641(1+4+6+4+1=16) 15101051(1+5+10+10+5+1=32) 1615201561(1+6+15+20+15+6+1=64) … 相加得到的数136…刚好，6，…次幂，即杨辉三角行个数之和等n-次 杨辉三角中斜行和水平行之间的关 (1) 1(2)n=1 11(3)n=2 121(4)n=3 1331(5)n=4 14641(6)n=5 15101051n=6 1615201561 把斜行(1)中第7行之前的数字相加得1+1+1+1+1+1+1=6 /* Name: 杨辉三角算法集锦 Copyright: 始发于goal00001111的专栏；允许自由转载，但必须注明作者和出处Author: goal00001111 Date: 27-11-08 19:04 Description: 分别使用了二维数组，一维数组，队列，二项式公式，组合公式推论和递归方法等9种算法 算法思路详见代码注释——注释很详细，呵呵 */ #include cout << endl; Fun_6(row); cout << endl; Fun_7(row); cout << endl; Fun_8(row); cout << endl; Fun_9(row); system("pause"); return 0; } //输出n个空格 void PrintBlank(int n) { for (int i=0; i 杨辉三角显示实验报告 1.问题描述： 编写程序，根据输入的行数，屏幕显示杨辉三角。 2.基本要求： （1）行数不大于20行。 （2）基于队列的操作来实现杨辉三角的不断生成过程。（注：不要用其它的公式计算的方法或者二维数组来实现） （3）基于数组实现队列的物理数据结构 3.需求分析： 1、输入形式：输入一个整数n ，0<=n<=20 2、输出形式：打印出来前(n+1)行的杨辉三角数列 3、功能实现：输出前20层的杨辉三角序列 4、样例输入输出：（数据加强版） 输入：10 输出： 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 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 5、效率分析：O(n) 4.概要设计： 利用到队列先进先出的性质（First In First Out），基本的算法实现是利用已经进队的元素在其出队之前杨辉三角的下一行数列，----即利用要出队的元素来不断地构造新的进队的元素，即在第N行出队的同时，我们来构造杨辉三角的第N+1行，从而实现打印杨辉三角的目的。 5.详细设计： 算法思想已经在概要设计中提到了，现在通过基于队列基本操作的函数以及程序的模块化思想来实现杨辉三角的打印输出问题。 算法函数描述： 队列类： 队列类的数据成员： int front，rear,//ront和rear分别是指向队头和队尾的指针 maxsize;//队列中的元素数 int* listArray //存放队列中的元素 队列的基本操作： V oid Queue(int ) function://构造一个空队列 #include 软件学院 上机实验报告 课程名称：数据结构 实验项目：队列的应用 实验室：耘慧420 姓名：学号 专业班级：实验时间： 2016.11.17 一、实验目的及要求 (一) 目的 1．掌握栈队列特点及顺序存储结构(循环队列)下基本操作的实现。 2．掌握队列的应用，能根据问题特点选择队列结构。 （二）.要求 1．定义循环队列的存储结构 2．完成入队、出队、取队头等基本操作的实现。 3．利用队列的基本操作实现n行杨辉三角的输出。 4．主函数调用杨辉三角输出函数，实现n行杨辉三角输出。 二、性质 设计性 三、实验学时 2学时 四、实验环境 C与C++程序设计学习与实验系统 五、实验内容及步骤 (一).内容 1．定义循环队列的存储结构，完成入队、出队、取队头等基本操作的实现。 2. 利用循环队列实现杨辉三角的输出 (二).步骤 1.//---------循环队列—队列的顺序存储结构 ----- #define MAXSIZE 100 typedef struct { QElemType *base; //初始化的动态分配存储空间 int front; //头指针，队列不空指向队列头元素 int rear; //尾指针，队列不空指向队列尾元素下一位置 } SqQueue; 2.杨辉三角: 1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 …………………… 这是一个初等数学中讨论的问题。系数表中的第 k行有 k个数，除了第一个和最后一个数为1之外，其余的数则为上一行中位其左、右的两数之和。 如果要求计算并输出杨辉三角前n行的值，则队列的最大空间应为 n+2。假设队列中已存有第 k 行的计算结果，并为了计算方便，在两行之间添加一个"0"作为行界值，则在计算第 k+1 行之前，头指针正指向第 k 行的"0"，而尾元素为第 k+1 行的"0"。由此从左到右依次输出第 k 行的值，并将计算所得的第 k+1 行的值插入队列的基本操作为： void YangHui(int n) { printf("1\n"); EnQueue(&q,0); /*开始*/ EnQueue(&q,1); /*第1行*/ EnQueue(&q,1); for(j=2;j<=n;j++) { EnQueue(&q,0); do{ //------循环队列—队列的顺序存储结构----- #include 杨辉三角的规律以及定理 1 二项式定理与杨辉三角 与杨辉三角联系最紧密的是二项式乘方展开式的系数规律，即二项式定理。 杨辉三角我们首先从一个二次多项式 (a+b) 2 的展开式来探讨。 由上式得出： (a+b) 2＝ a 2+2ab+b 2 此代数式的系数为： 1 2 1 则 (a+b) 3 的展开式是什么呢？答案为： a 3+3a 2b+3a b 2+b 3 由此可发现， 此代数式的系数为： 1 3 3 1 但 似乎没有什么规律，所以让我们再来看看 (a+b) 4 的展开式。 展开式为： a 4 +4a 3b+6a 2b2+4ab 3+b 4 由此又可发现，代数式的系数为： 1 4641 似乎发现了一些规律，就可以发现以下呈三角形的数列： 1 (11 ) 1 1 (11 1 ) 1 2 1 (11 2 ) 1 3 3 1 (11 3 ) 1 4 6 4 1 (11 4 ) 1 5 10 10 5 1 (11 5 ) 1 6 15 20 15 6 1 (11 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,7,21,35,35,21,7,1）所以： (a+b) 7=a 7+7a 6 b+21a 5b 2+35a 4b 3+35a 3b 4+21a 2b 5+7ab 6+b 7。 由上式可以看出， (a+b) n 等于 a 的次数依次下降 n 、n-1 、n- 2?n -n ，b 的次数依次上升， 0、1、2?n 次方。系数是 杨辉三角里的系数。 2 杨辉三角的幂的关系 首先我们把杨辉三角的每一行分别相加，如下： 1 ( 1 ) 1 1 ( 1+1=2 ) 1 2 1 (1+2+1=4 ) 1 3 3 1 (1+3+3+1=8 ) 1 4 6 4 1 (1+4+6+4+1=16 ) 1 5 10 10 5 1 (1+5+10+10+5+1=3 2 ) 1 6 15 20 15 6 1 (1+6+15+20+15+6+1=64 ) ?? 相加得到的数是 1， 2， 4， 8， 16， 32， 64，?刚好是 2 的 0， 1，2， 3， 4， 5， 6，? n 次幂，即杨辉三角第 n 行中 n 个数之和等于 2 的 n-1 次幂 3 杨辉三角中斜行和水平行之间的关系 《算法与数据结构》课程 一、实验目的 掌握队列的存储结构及进队/出队等操作的实现。 二、实验内容及要求 1.实现队列的一种存储结构。 2.实现队列的相关操作。 3.利用队列的操作特点，借助进队与出队操作完成打印二项式系数的任务。 三、系统分析 （1）数据方面：该队列数据元素类型采用整型，在此基础上进行队列的一些基本操作，应用体现在打印二项式系数即打印杨辉三角形。 （2）功能方面： 1.进队操作：若队列不满，则将元素x进入队列。 2.出队操作：若队列不空，则退出队头元素x并由函数返回true，否则返 回false。 3.获取队头元素：若队列不为空，则函数返回true及队头元素的值，否则 返回false。 4.判断队列是否为空、判断队列是否满。 5.计算队列中元素个数：直接返回队列中元素个数。 6.清空队列内容：队头指针和队尾指针置0。 7.打印杨辉三角形前n行数字。 四、系统设计 （1）设计的主要思路 队列得基于数组得存储表示亦称为顺序队列，是利用一个一维数组作为队列元素的存储结构，并且设置两个指针front和rear，分别指示队列的队头和队尾位置。每当添加一个新元素时，先将新元素添加到rear所指位置，再让队尾指针 rear进1。每当退出队头元素，应当先把front所指位置元素记录下来，再让队头指针进1，指示下一队头元素位置，最后把记录下来的元素值返回。 但当队头指针front==rear，队列为空；而当rear==maxSize时，队列满，如果再加入新元素，就会产生“溢出”。但这种“溢出”可能时假溢出，因为在数组的前端可能还有空位置。为了能够充分地使用数组中的存储空间，把数组的前端和后端连接起来，形成一个环形表，即把存储队列元素的表从逻辑上看成一个环，成为循环队列。循环队列的首尾相接，当队头指针front和队尾指针rear进到maxSize-1后，再前进一个位置就自动到0.这可以利用除法取余的运算实现。（2）数据结构的设计 队列的定义是一种限定存取位置的线性表。它只允许在表的一端插入，在另一端删除。允许插入的一端叫做队尾，允许删除的一端叫做队头。最先进入队列的元素最先退出队列，队列这种特性叫做先进先出。 空队列 A进队 对头指针进1：front=(front+1)%maxSize; 队尾指针进1：rear=(rear+1)%maxSize; 队列初始化：front=rear=0; 循环队列的队头指针和队尾指针初始化时都设置为0：front=rear=0.在队尾插入新元素和删除队头元素时，两个指针都按顺时针方向进1.当它们进到maxSize-1时，并不表示表的终结，只要有需要，利用%运算可以前进到数组的0号位置。 五、编程环境与实验步骤 （1）编程环境 操作系统：Windows操作系统；编程工具软件：Visual Studio 2017 （2）实验步骤 无文件操作。 （3）编译参数杨辉三角的规律以及推导公式
杨辉三角队列实现
显示杨辉三角实验报告
杨辉三角形的生活运用和规律
队列实验
数据结构实验——队列(附程序)
数据结构第三章栈和队列3习题
队列实现杨辉三角
杨辉三角解析(队列实现)
实验二 栈与队列操作实验题目
杨辉三角的规律以及推导公式
杨辉三角的各种算法实现
杨辉三角队列实现
顺序队列的基本操作
数据结构——队列的应用
数据结构-利用循环队列打印杨辉三角
杨辉三角的规律以与推导公式-杨辉三角规律
数据结构实验报告—队列
相关主题
文本预览