用队列方法输出杨辉三角

#ifndef DS_H#define DS_H#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2//Status是函数的类型，其值是函数结果状态代码typedef int Status;#endif//////////////////////////////////////#include "ds.h"#ifndef SqQueue_H#define SqQueue_H#define MAXQSIZE 100//最大队列长度typedef int QElemType;typedef struct{QElemType *base;//动态分配存储空间int front;//头指针,若队列不空,指向队列头元素int rear; //尾指针,若队列不空,指向队列尾元素的下一个位置}SqQueue;Status InitQueue(SqQueue &,int);Status EnQueue(SqQueue &,QElemType);Status DeQueue(SqQueue &,QElemType &);void GetHead(SqQueue,QElemType &);bool QueueEmpty(SqQueue);#endif///////////////////////////////////////#include <stdlib.h>#include "ds.h"#include "SqQueue.h"Status InitQueue(SqQueue &Q,int x){//构造一个空队列QQ.base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType));if(!Q.base)exit(OVERFLOW);//存储分配失败Q.front=Q.rear=0;return OK;}Status EnQueue(SqQueue &Q,QElemType e){//插入元素e为Q的新的队尾元素if((Q.rear+1)%MAXQSIZE==Q.front)return ERROR; //队列满Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%MAXQSIZE;return OK;}Status DeQueue(SqQueue &Q,QElemType &e){//若队列不空,则删除Q的队头元素用e返回其值,并返回OK;否则返回ERROR if(Q.front==Q.rear)return ERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;return OK;}void GetHead(SqQueue Q,QElemType &e){e=Q.base[Q.front];}bool QueueEmpty(SqQueue Q){if(Q.front==Q.rear)return true;elsereturn false;}////////////////////////////////////////////////////#include <iostream.h>#include "ds.h"#include "SqQueue.h"void yanghui(int n){//打印输出杨辉三角的前n(n>0)行SqQueue Q;int i;QElemType e;int k;for(i=1;i<=n;i++)cout<<' ';cout<<'1'<<endl;//在中心位置输出杨辉三角最顶端的"1"InitQueue(Q,n+2);// 设置最大容量为n+2的空队列EnQueue(Q,0);//添加行界值EnQueue(Q,1);EnQueue(Q,1 );//第一行的值入队列k=1;while(k<n){//通过循环队列输出前n-1行的值QElemType s;for(i=1;i<=n-k;i++)cout<<' ';//输出n-k个空格以保持三角型EnQueue(Q,0);//行界值"0"入队列do{//输出第k行,计算第k+1行DeQueue(Q,s);GetHead(Q,e);if(e)cout<<e<<' ';//若e为非行界值0,则打印输出e的值并加一空格else cout<<endl;//否则回车换行,为下一行输出做准备EnQueue(Q,s+e);}while(e!=0);k++;}//whileDeQueue(Q,e);//行界值"0"出队列while(!QueueEmpty(Q)){//单独处理第n行的值的输出DeQueue(Q,e);cout<<e<<' ';}//while}//yanghuivoid main(){yanghui(4);}////////////////////////////////////////////。

//----- 循环队列的顺序存储结构#define MAXQSIZE 100 //最大队列长度QElemType *base;int front;int rear;}SqQueue//-----循环队列的基本操作的函数原型说明-----Status InitQueue(ListQueue &Q) 构造一个空队列Status EnQueue(ListQueue &Q,e) 素e入队列QStatus DeQueue(ListQueue &S,&e) 出队列到元素e//-----循环队列的基本操作的算法描述-----Status InitQueue(SqQueue &Q){//构造一个空队列Q. base = (QElemType *)malloc(MAXQSIZE * sizeof(QElemType));if (!Q.base) exit (OVERFLOW);Q.front = Q.rear = 0; //初始空队列return OK;}Status EnQueue(SqQueue &Q,QElemType e){//插入元素e为Q的新队尾元素if ((Q.rear+1)%MAXQSIZE == Q.front) return ERROR;Q.base[Q.rear] = e;Q.rear = (Q.rear+1)%MAXQSIZE;return OK;}Status DeQueue(SqQueue &Q,QElemType &e){//若队列不为空，删除队头元素用e返回，并返回OK//否则返回ERRORif (Q.front == Q.rear) return ERROR;e = Q.base[Q.front];Q.front = (Q.front +1)%MAXQSIZE;return OK;}void YANGVI ( int n ) {InitQueue(Q); //队列初始化EnQueue (Q,1); EnQueue (Q,1); //预放入第一行的两个系数for ( int i=1; i<=n; i++ ) { //逐行处理EnQueue (0); //两行之间增加一个标志0s=0;for ( int j=1; j<=i+2; j++ ) { //处理第i行的i+2个系数DeQueue (Q,e); //读取系数1EnQueue ( s+e ); //计算下一行系数，并进队列s = e;if ( j != i+2 ) printf(s); //打印一个系数，第i+2个为0 else printf(“\n”); //换行}}}//YANGVI。

/*用队列方法输出杨辉三角。

*/#include<iostream.h>#include<iomanip.h>#include<stdlib.h>#define ElemType int/*-----LNode的结点类型定义-----*/struct LNode{ElemType data; //值域LNode* next; //链接指针域};/*-----队列的链接存储结构的定义-----*/struct LinkQueue{LNode* front; //队首指针LNode* rear; //队尾指针};/*------1.初始化链队-----*/void InitQueue(LinkQueue& HQ){HQ.front=HQ.rear=NULL; //把队首和队尾指针置为空}/*-----2.向链队中插入一个元素------*/void EnQueue(LinkQueue& HQ, ElemType item){LNode* newptr=new LNode; //得到一个新的结点newptr->data=item; //把item 的值赋给新结点的值域newptr->next=NULL; //把新结点的指针域置为空if(HQ.rear==NULL) //若链队为空，则新结点既是队首又是队尾{HQ.front=HQ.rear=newptr;}else //若链队非空，则新结点被链接到队尾并修改队尾指针{HQ.rear=HQ.rear->next=newptr;}}/*-------3.从队列中删除一个元素-------*/ElemType OutQueue(LinkQueue& HQ){if(HQ.front==NULL) //若链队为空则终止运行{cerr<<"链队为空，无法删除！"<<endl;exit(1);}ElemType temp=HQ.front->data; //暂存队首元素以便返回LNode* p=HQ.front; //暂存队首指针以便收回队首指针HQ.front=p->next; //使队首指针指向下一个结点if(HQ.front==NULL) //若删除后链队为空，则使队尾指针为空{HQ.rear=NULL;}delete p; //回收原队首结点return temp; //返回被删除的队首元素}void YanyHuiTriangular(LinkQueue& HQ, int n){int i,j; //i，j 都是循环变量int first,second; //first,second 分别记录上一行的两个累加数EnQueue(HQ,1);for(i=1; i<n+1; i++){ //第 0 至 n-1 行元素分别入列，并输出；最后第 n 行入列first=0; second=0;//控制每行前头空格的输出for(j=0; j<n-i+1; j++){cout<<setw(3)<<' ';}for(j=0; j<i; j++){second=OutQueue(HQ);cout<<setw(3)<<second<<setw(3)<<' ';EnQueue(HQ,first+second);first=second;}cout<<endl; //输完一行，回车EnQueue(HQ,second);}//最后输出最后一行元素（即第 n 行出列）for(j=0; j<n+1; j++){cout<<setw(3)<<OutQueue(HQ)<<setw(3)<<' '; }cout<<endl;}void main(){LinkQueue LQ;InitQueue(LQ);cout<<"用队列输出杨辉三角!"<<endl<<endl; int n;cout<<"请输入要输出多少行杨辉三角："; cin>>n;YanyHuiTriangular(LQ,n);}。

数据结构实验报告实验一杨辉三角形(Pascal’s triangle)一、需求分析1.输入的形式和输入值的范围本程序中，需输入的杨辉三角级数level为正整数，由键盘输入，以回车结束2.输出的形式通过屏幕输出杨辉三角3.程序所能达到的功能用户从键盘输入需要的杨辉三角级数，从屏幕输出杨辉三角4.测试数据输入：5输出： 1 11 2 11 3 3 11 4 6 4 11 5 10 10 5 1二、概要设计以链队列结构实现该实验1.抽象数据类型定义ADT Queue {数据对象：D = { ai | ai∈ElemSet , i = 1,2,…,n,n≥0 }数据关系：R1={<ai-1,ai> | ai-1 , ai∈D, i=2,…,n}约定其中ai端为队列头，an端为队列尾基本操作：InitQueue ( &Q )操作结果：构造一个空队列QDestroyQueue ( &Q )初始条件：队列Q已存在操作结果：队列Q被销毁，不再存在ClearQueue ( &Q )初始条件：队列Q已存在操作结果：将Q清为空队列QueueEmpty ( Q )初始条件：队列Q已存在操作结果：若Q为空队列，则返回TRUE，否则FALSEQueueLength ( Q )初始条件：队列Q已存在操作结果：返回Q的元素个数，即队列长度GetHead ( Q , &e )初始条件：Q为非空队列操作结果：用e返回Q的队头元素EnQueue ( &Q , e )初始条件：队列Q已存在操作结果：插入元素e为Q的新队尾元素DeQueue ( &Q , &e )初始条件：Q为非空队列操作结果：删除Q的队头元素，并用e返回其值QueueTraverse ( Q , visit( ) )初始条件：Q已存在且非空操作结果：从队头到队尾，依次对Q的每个数据元素调用函数visit( )。

实验4 杨辉三角1 实验要求打印二项展开式（a+b）^i的系数，将其系数构成杨辉三角形。

2 简单的需求分析1，该程序的描述是：建立一个循环队列，以及一个利用队列实现逐行打印杨辉三角形的前n行的算法，最后在主函数中输入所要打印的杨辉三角形的行数，调用函数输出结果。

2，程序运行后,首先会出现"请输入二项式为几次幂"，用户根据自己的选择输入后，系统便会输出打印的情况。

3 概要设计1、所用的抽象数据类型：（1）//循环队列的类定义template<class T>class SeqQueue{public:SeqQueue(int sz=10); //构造函数~SeqQueue(){delete[] elements;} //析构函数bool EnQueue(const T& x); //若队列不满，则将x进队，否则队溢出处理bool DeQueue(T& x); //若队列不空，则退出队头元素x并由函数返回true，否则队空，返回falseprotected:int rear,front; //队尾与队头指针T* elements; //存放队列元素的数组int maxSize; //队列最大可容纳元素个数};（2） //链式栈的类定义void YANGVI(int n){//分行打印二项式(a+b)^n展开式的系数，在程序中利用一个队列，在输出上一行系数时，将其//下一行的系数预先放入队列中，在各行系数之间插入一个0int k;SeqQueue<int> q(n+2); //建立队列对象并初始化int i=1,j,s=k=0,t,u,m; //计算下一行系数时用到的工作单元q.EnQueue(i);q.EnQueue(i); //预先放入第一行的两个系数for(i=1;i<=n;i++) //逐行处理{cout<<endl; //换一行q.EnQueue(k); //各行间插入一个0for(j=1;j<=i+2;j++) //处理第i行的i+2个系数（包括一个0）{q.DeQueue(t); //读取一个系数u=s+t; q.EnQueue(u); //计算下一行系数，并进队列s=t;if(j!=i+2) cout<<s<<' '; //打印一个系数，第i+2个是0 }}}2、函数调用关系：在main（）函数中，先输入所要打印的杨辉三角形的行数，然后调用YANGVI(int n)函数4 详细设计部分#include<iostream.h>#include<assert.h>#include<stdio.h>//循环队列的类定义template<class T>class SeqQueue{public:SeqQueue(int sz=10); //构造函数~SeqQueue(){delete[] elements;} //析构函数bool EnQueue(const T& x); //若队列不满，则将x进队，否则队溢出处理bool DeQueue(T& x); //若队列不空，则退出队头元素x并由函数返回true，否则队空，返回falseprotected:int rear,front; //队尾与队头指针T* elements; //存放队列元素的数组int maxSize; //队列最大可容纳元素个数};//循环队列的构造函数template<class T>SeqQueue<T>::SeqQueue(int sz):front(0),rear(0),maxSize(sz){//建立一个最大具有maxSize个元素的空队列elements=new T[maxSize];//创建队列空间assert(elements!=NULL);//断言：动态存储分配成功与否}//循环队列的进队template<class T>bool SeqQueue<T>::EnQueue(const T& x){if((rear+1)%maxSize==front) {return false;} //队列满则插入失败，返回else{elements[rear]=x; //按照队尾指针指示位置插入rear=(rear+1)%maxSize; //队尾指针加1return true; //插入成功，返回}}//循环队列的出队template<class T>bool SeqQueue<T>::DeQueue(T& x){if(front==rear) {return false;} //若队列空则删除失败，返回else{x=elements[front];front=(front+1)%maxSize; //队头指针加1return true;//删除成功，返回}}//打印杨辉三角形的前n行函数定义void Y ANGVI(int n){//分行打印二项式(a+b)^n展开式的系数，在程序中利用一个队列，在输出上一行系数时，将其//下一行的系数预先放入队列中，在各行系数之间插入一个0int k;SeqQueue<int> q(n+2); //建立队列对象并初始化int i=1,j,s=k=0,t,u,m; //计算下一行系数时用到的工作单元q.EnQueue(i);q.EnQueue(i); //预先放入第一行的两个系数for(i=1;i<=n;i++) //逐行处理{cout<<endl; //换一行q.EnQueue(k); //各行间插入一个0for(j=1;j<=i+2;j++) //处理第i行的i+2个系数（包括一个0）{q.DeQueue(t); //读取一个系数u=s+t; q.EnQueue(u); //计算下一行系数，并进队列s=t;if(j!=i+2) cout<<s<<' '; //打印一个系数，第i+2个是0}}}//主函数void main(){int m;cout<<"请输入二项式为几次幂"<<endl;cin>>m;Y ANGVI(m);cout<<endl;}/5 调试与测试1.输入所要打印的杨辉三角形的行数2，显示结果。

循环队列和杨辉三角（Cyclic queue and Yang Hui triangle）circulatequeue。

H：类circulatequeue{私人：int数据；/ /数组在前、后；/ /队头队尾指针，下标int长度；/ /队列长度const int ini_mem_length；/ /动态数组初始大小const int增量；/ /数组扩展增量/ / / /内存利用率const双率；国际current_mem_length；/ /当前数组内存单元大小公共：circulatequeue（int = 100，int = 10）；//构造~ circulatequeue() /析构{删除[ ]数据；}输出（void）；/ /输出，调试用无效enterqueue（int值）；/ /入队列int DeleteQueue（int值）；/ /出队列国际getqueuelength（void）/获取当前队列的长度{返回的长度；}int GetTop（int值）/取队头元素{如果（0 =长度）返回- 1；int i =（前+ 1）% current_mem_length；值=数据[ i ]；返回1；}}；CirculateQueue.cpp：#包括“circulatequeue。

”#包含iostream > <使用名称空间；circulatequeue：：CirculateQueue（int，int newsize，newincrement）：ini_mem_length（newsize）、增量（newincrement）{数据=新国际[ ini_mem_length ]；长度= 0；前面=后面= 0；current_mem_length = ini_mem_length；}无效circulatequeue：：输出（void）{如果（0 =长度）{cout <<“当前队列为空！“<<”不当前队列动态数组长度为：“<< current_mem_length << endl；}其他的{cout <<“当前队列长度为：“<<长<<“不当前队列动态数组长度为：“<< current_mem_length << end l；cout <<“当前队列内容为：”；int pos =（前+ 1）% current_mem_length；对于（int = i 1；i =长度；i + +）{cout <<数据【词性】<<“T”；POS =（POS + 1）% current_mem_length；cout << endl；}}无效circulatequeue：：enterqueue（int值）{如果（长度= =（current_mem_length-1））/ /{/ /int *温度=新国际[ current_mem_length +增量]；int pos =（前+ 1）% current_mem_length；对于（int = i 1，j = 1；i =长度；i +，+ +）/ i，j {温度=数据[ POS ]；POS =（POS + 1）% current_mem_length；}删除[ ]数据；数据=温度；前0；后=长度；current_mem_length = current_mem_length +增量；}后=（后+ 1）% current_mem_length；数据[后面] =值；长度+；}国际circulatequeue：：DeleteQueue（int值）{如果（0 =长度）/返回- 1；前=（前+ 1）% current_mem_length；值=数据[前]；长度-；返回0；}main.cpp：#包含iostream > <使用名称空间；#包括“circulatequeue。

数据结构总结系列（四）——循环队列之杨辉三⾓今天我们来写⼀个循环队列的应⽤哦！解决的是杨辉三⾓问题~~对于这样⼀个上下多层之间有密切联系的数据，如果只是⽤数组和循环来解决的话，显然会浪费⼤量的空间和时间，所以我们⽤队列来解决这⼀问题：之所以选⽤循环队列也是因为它对于空间的利⽤是⾮常有效的，⽅便我们的⼯作：开始定义结构体：typedef struct//定义循环队列{int data[MAXMIZE];int Front;int Rear;}RollQueue;这⾥的最⼤值（MAXMIZE）⼤家可以⽤宏定义来⾃⼰定义想要的限制呦关于循环队列，由于它没有浪费空间，所以⾮常有⽤的背后就是要多计算⼀点插⼊的位置：所以我们之后的判断条件会多⼀点~队列相关函数的设置：由于队列是⼀种只能从队尾插⼊，从队头删除的结构，因此简化了我们的操作：void InitQueue(RollQueue &R)//队列初始化函数{R.Front=R.Rear=0;//博主这⾥没有⽤指针，直接⽤了数组~}void InsertQueue(RollQueue &R,int Data)//插⼊队尾{//⾸先判断是否满队列。

if((R.Rear+1)%MAXMIZE==R.Front)//满队列条件{cout << "This queue is full." << endl;}else{R.data[R.Rear]=Data;R.Rear=(R.Rear+1)%MAXMIZE;//success}}int DeleteQueue(RollQueue &R,int &Re)//删除队头元素，⽤re返回{if(R.Rear==R.Front)//判断是否队空{cout << "This queue is empty." << endl;return0;}else{Re=R.data[R.Front];R.Front=(R.Front+1)%MAXMIZE;return Re;}}最后是杨辉三⾓的建⽴：void YangHui(int n){RollQueue R;InitQueue(R);InsertQueue(R,1);//预先放⼊第⼀⾏的系数InsertQueue(R,1);//预先放⼊第⼀⾏的系数int s=0;for(int i=1;i<=n;i++){cout << endl;//这⾥换⾏鸭InsertQueue(R,0);//开头插⼊⼀个0⽤来进⾏第⼀次加法for(int j=1;j<=i+2;j++)//处理第i⾏的i+2个系数{int t;DeleteQueue(R,t);InsertQueue(R,s+t);//这⾥把上⼀⾏的两个数据相加得到这⼀⾏的数据s s=t;if(j!=i+2){cout << s << '' ;}}}}最后是整个程序：#include <bits/stdc++.h>using namespace std;#define MAXMIZE 100typedef struct//定义循环队列{int data[MAXMIZE];int Front;int Rear;}RollQueue;void InitQueue(RollQueue &R)//队列初始化函数{R.Front=R.Rear=0;//博主这⾥没有⽤指针，直接⽤了数组~}void InsertQueue(RollQueue &R,int Data)//插⼊队尾{//⾸先判断是否满队列。

循环队列实现杨辉三⾓形的打印知识温习循环队列：即将顺序队列的数组看成是⼀个环状的空间，规定最后⼀个单元的后继为第⼀个单元。

运⽤循环队列可以有效的解决链队列的“假溢出”现象。

假溢出其实是指在链队列中，当rear==MAXSIZE时就认为队满。

然⽽由于元素的出队，使得数组前⾯出现⼀些空单元，⽽元素⼜只能在队尾⼊队，如果此时已经到数组的尾部，就认为队列已满，但其实还存在上述那些空单元未使⽤，队列并未真正满。

这种现象即为“假溢出”现象。

真正的队满条件应该是rear-front==MAXSIZE。

在循环队列中，我们通过数学中的求模运算来改变头指针和尾指针的位置。

进队操作时，队尾指针的变化是：rear=（rear+1）mod MAXSIZE；⽽出队操作时，队头指针的变化是：front=（front+1）mod MAXSIE。

杨辉三⾓形11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1从上图中可以看出，杨辉三⾓形的特点：每⾏的第⼀个元素和最后⼀个元素都为1，其他位置上的元素总是等于上⼀⾏与之相邻的两个元素之和。

故第i⾏的元素要由第i-1⾏的元素来⽣成。

可以利⽤循环队列实现杨辉三⾓形的打印过程：在循环队列中依次存放第i-1⾏上的元素，然后逐个出队并打印，同时⽣成第i⾏元素并⼊队。

下⾯⽤第6⾏元素⽣成第7⾏元素为例⼦来说明打印过程：①第7⾏的第⼀个元素1⼊队。

element[Q->rear] = 1;Q->rear = (Q->rear + 1)% MAXSIZE;②循环做以下操作，⽣成第7⾏的中间5个元素并⼊队。

element[Q->rear] = element[Q->front] + element[(Q->front+1)%MAXSIZE];Q->rear = (Q->rear + 1)%MAXSIZE;Q->front = (Q->front + 1)%MAXSIZE;③第6⾏的最后⼀个元素1⼊队。

队列实现杨辉三角的算法原理
杨辉三角是一种数学模式，每个位置上的数字等于它上方两个数字之和。

队列可以用来实现杨辉三角的算法，其原理如下：
1. 首先，创建一个空的队列。

2. 将1入队列，作为第一行的元素。

3. 进行循环，从第二行开始到第n行：
- 将当前队列中的元素依次出队，并将它们存储在一个临时数组temp中。

- 在temp数组末尾添加一个0，作为哨兵元素。

- 再将temp数组中的元素依次相加，并将结果入队列。

4. 打印队列中的元素，即可得到杨辉三角的结果。

这个算法的基本思路是利用队列先进先出的特性，每次处理一行的数据。

在处理每一行时，将队列中的元素依次出队，并计算它们的和，然后将和再次入队，作为下一行的元素。

通过不断重复这个过程，最终得到的队列中的元素就是杨辉三角的结果。

利用链队列输出杨辉三角用链队列做存储结构计算并打印杨辉三角#include#include#define l sizeof(struct node)#define m sizeof(struct linkqueue)typedef struct node{int data;struct node *next;}node;typedef struct linkqueue{node*front,*rear;}linkqueue;void init_queue(linkqueue*Q) //初始化链队列{node*p; p=(node*)malloc(l);Q->front=Q->rear=p;Q->rear->next=NULL;}void en_queue(linkqueue*Q,int x) //入队{node*p;p=(node*)malloc(l);p->data=x;p->next=NULL;Q->rear->next=p;Q->rear=p;}int out_queue(linkqueue*Q) //出队{int x;node*u;if(Q->front==Q->rear) printf("NULL"); else{ x=Q->front->next->data;u=Q->front->next;Q->front->next=u->next;free(u);if(Q->front->next==NULL){Q->rear=Q->front;}return x;}}void yhsj(int n) //输出杨辉三角{int i,j,a,b;linkqueue*Q;Q=(struct linkqueue*)malloc(m);if(n<=0) printf("error\n");else{init_queue(Q);for(i=1;i<n;i++)< p="">{printf(" "); //第一行1前的空格}printf(" 1\n");en_queue(Q,1);for(i=2;i<=n;i++){for(j=1;j<n-i+1;j++)< p=""> {printf(" ");}a=0;for(j=1;j<i;j++)< p="">{b=out_queue(Q);printf("%3d ",a+b);en_queue(Q,a+b);a=b;}printf(" 1\n");en_queue(Q,1);}}}void main(){int n;printf("您想输出杨辉三角的行数为：\n"); scanf("%d",&n);yhsj(n);}</i;j++)<></n-i+1;j++)<></n;i++)<>。