最近在上数据结构与算法，期末老师要求同学抽问题，然后写这个算法问题的实验报告；其中就包含了用队列来实现杨辉三角形，这里就先提前练下手，万一运气好我就刚好抽到这个呢了(好了，不开玩笑了，进入正题吧)

算法思想：

首先先创建一个循环队列：

typedef struct sq
{
 int a[MAXSIZE];//队列元素空间
 int front,rear;//队头和队尾指针
}*SeqQue;

SeqQue InitQue()
{
 SeqQue q;
 q=(SeqQue)malloc(sizeof(sq));
 if(q==NULL)
 {
  cout<<"创建循环队列失败！"<<endl;
  return NULL;
 }
 q->front=q->rear=0;//设置队头和队尾指针初值为0
 return q;
}

其次实现这个算法只需用到入队(在队尾入队)和出队(在队头出队)操作，但其中的细节还是要抓，比如：判断队列是否为空或已满

void enter(SeqQue q,int x)//入队函数
{
 if((q->rear+1)%MAXSIZE==q->front)//判断队列是否已满
 {
  cout<<"循环队列已满！"<<endl;
  return;
 }
 q->a[q->rear]=x;
 q->rear=(q->rear+1)%MAXSIZE;//队尾指针加1
}

int OutQue(SeqQue q)//出队函数
{
 int x;
 if(q->rear==q->front)//判断队列是否为空
 {
  cout<<"循环队列已空"<<endl;
  return 0;
 }
 x=q->a[q->front];//取出队头元素并返回
 q->front=(q->front+1)%MAXSIZE;//队头指针加1
 return x;
}

上面的队头和队尾指针有的博客可能不明白为什么要求模MAXSIZE，其实很简单，就是这是个循环队列，入队和出队函数运行了很多次，如果不求模MAXSIZE，队头和队尾指针可能就超过了MAXSIZE，并且求模后才是真正的队头和队尾指针。

下面才是这个算法的核心：
1>将第一行的元素1入队；
2>从第二行开始，现在的队头指向上一行，先将每行的固定元素1入队，然后循环操作求和过程：(将队首元素出队，并保存它的值为t1；获取当前队首的元素的值为t2，并进行x=t1+t2，且将x入队)
3>循环结束后，每行最后输出固定元素1，然后将x赋值为1，并将每行的最后一个固定元素1入队；
4>循环2、3步就可以输出杨辉三角形了。

核心代码如下：

 SeqQue q;
 int x=1,i;
 cout<<"请输入杨辉三角形打印的行数:"<<endl; 
 cin>>i;
 q=InitQue();//创建一个初始化循环队列
 for(int n=0;n<i;n++)
 {
     for(int m=0;m<i-1-n;m++)
     {
      cout<<" ";
     }
     if(n==0)
     {
     cout<<1<<endl;
     enter(q,x);
     }
     else
     {
        int t1=0,t2=0;//方便队首元素的保存和获取
        for(int r=0;r<n;r++)
        {
         t1=t2;//保存上一个队首元素的值
         t2=OutQue(q);//获取当前队首元素的值
         x=t1+t2;//保证x是等于上一行它的左边元素和右边元素(位置)的和
         enter(q,x);//将求和的值入队，用于下一行元素的计算
         cout<<x<<" "; 
        }
        cout<<1<<endl;
        x=1;
        enter(q,x);//将每行的最后一个固定元素1入队
      } 
 }

其实你仔细调试代码后，就会发现每执行完一次大循环，循环队列中的元素就是对应的那一行元素的值：上一次循环队列的元素出队，当前对应的杨辉三角形这行元素入队。

AC代码如下：

#include <iostream>
using namespace std;
#define MAXSIZE 500

typedef struct sq
{
 int a[MAXSIZE];
 int front,rear;
}*SeqQue;

SeqQue InitQue()
{
 SeqQue q;
 q=(SeqQue)malloc(sizeof(sq));
 if(q==NULL)
 {
  cout<<"创建循环队列失败！"<<endl;
  return NULL;
 }
 q->front=q->rear=0;
 return q;
}

void enter(SeqQue q,int x)
{
 if((q->rear+1)%MAXSIZE==q->front)
 {
  cout<<"循环队列已满！"<<endl;
  return;
 }
 q->a[q->rear]=x;
 q->rear=(q->rear+1)%MAXSIZE;
}

int OutQue(SeqQue q)
{
 int x;
 if(q->rear==q->front)
 {
  cout<<"循环队列已空"<<endl;
  return 0;
 }
 x=q->a[q->front];
 q->front=(q->front+1)%MAXSIZE;
 return x;
}

int main()
{
 SeqQue q;
 int x=1,i;
 cout<<"请输入杨辉三角形打印的行数:"<<endl; 
 cin>>i;
 q=InitQue();
    for(int n=0;n<i;n++)
    {
     for(int m=0;m<i-1-n;m++)
     {
      cout<<" ";
     }
     if(n==0)
     {
     cout<<1<<endl;
     enter(q,x);
     }
     else
     {
        int t1=0,t2=0;
        for(int r=0;r<n;r++)
        {
         t1=t2;
         t2=OutQue(q);
         x=t1+t2;
         enter(q,x);
        cout<<x<<" "; 
       }
       cout<<1<<endl;
       x=1;
       enter(q,x);
    } 
   }
 return 0;
}

最后我觉得我的数据结构老师这学期讲不完这门课了，可以请各位大佬出些关于算法的干货吗 嘻嘻。。。

杨辉三角规律图

 1.静态规律图

 2.动态规律图

代码实现

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#define MAXQSIZE 200

typedef struct {
    int  *base;
    int front;
    int rear;
}Queue;

//初始化队列 
void initQueue(Queue &Q){
    Q.base=(int *)malloc(MAXQSIZE*sizeof(int));
    Q.front=Q.rear=0;
}

//队列长度 
int length(Queue &Q){
    return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

//入队列
void inQueue(Queue &Q,int e){
    if((Q.rear+1)%MAXQSIZE ==Q.front) exit(1);//队列满了 
    Q.base[Q.rear]=e;
    Q.rear=(Q.rear+1)%MAXQSIZE;
}

//出队列 
void outQueue(Queue &Q,int &e){
    e=Q.base[Q.front];
    Q.front=(Q.front+1)%MAXQSIZE;
}

int getHead(Queue &Q){
    return Q.base[Q.front];
}
int main(){
    int N,n,c,i;
    int t,x;
    Queue f,Q;
    initQueue(Q);
    printf("请输入要打印的杨辉三角函数，不建议过大以获得良好效果:\n");
    scanf("%d",&N);
    inQueue(Q,1);
    for(n=2;n<=N+1;n++){
    	inQueue(Q,1);
        for(int j = 0; j < N-n+1;j++){ 
            printf("   ");
        }
        for(c=1;c<=n-2;c++){
            t=getHead(Q);
            outQueue(Q,t);
            printf("%6d",t);
            x=getHead(Q);
            t=t+x;
            inQueue(Q,t);  
        }
        inQueue(Q,1);
        printf("%6d",getHead(Q));
        outQueue(Q,t);
        printf("\n");
    }
    while(Q.front!=Q.rear){
        printf("%3d",getHead(Q));
        printf("   ");
        outQueue(Q,t);
    }
    printf("\n");
    return 0;
}

运行结果

问题导入什么是杨辉三角呢？之前用过C/C++数组实现过打印杨辉三角，那么如何使用队列来实现呢？

1、什么是杨辉三角

杨辉三角（也称帕斯卡三角）相信很多人都不陌生，它是一个无限对称的数字金字塔，从顶部的单个1开始，下面一行中的每个数字都是上面两个数字的和。

1.1 图形

下图就是杨辉三角前7行

1.2 特点

杨辉三角的实质是二项式(a+b)ⁿ展开后各项的系数排成的三角形。

特点如下：
	1、各行的第一个数都是1
	2、各行的最后一个数都是1
	3、从第3行起，除上面指出的第一个数和最后一个数外，其余各数是上一行同列和前一列两个数之和。

2、什么是队列

2.1 队列的定义

队列(queue)是一种先进先出(First In First Out, FIFO) 的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾(rear),允许删除的一端则称为队头(front)。

2.2 队列的常用公式

一般使用循环队列（提高空间的利用率）

初始化：				Q.front = Q.rear = 0;
入队操作：			Q.rear=( Q.rear+1 )%MaxQueueSize;
出队操作：			Q.front=( Q.front+1 )%MaxQueueSize;
判断队空：			Q.front = Q.rear;
判断队满：			( Q.rear + 1 ) % MaxQueueSize == Q.front;
计算队列长度：		( Q.rear - Q.front + MaxQueueSize ) % MaxQueueSize;

3、队列实现杨辉三角原理

3.1 图形演示

• 第i行元素与第i+1行元素的关系示意图：
  

原理是打印每行系数元素，每行之间用0间隔开来。

• 从第i行的数据出队并计算出第i+1行的数据入队的示意图：
  
  从第三行开始，除每行首末元素外，第i+1行每个元素都为第i行同列和前一列两个数之和,以此类推，第i行一个系数出队，计算第i+1行系数，并入队。

3.2 主要算法实现

EnQueue(Q , 0);				//各行间插入一个0
for(j = 1; j <= i+2; j++){
	DeQueue(Q , t);			//一个系数出队
	EnQueue(Q , s+t);		//计算下一行系数，并入队
	s = t;
	if(j != i+2)
		printf("%d" , s);	//第 i+2 个 0
}

4、代码实现

4.1 main.cpp

//使用队列输出杨辉三角
#include<stdio.h>
#include<stdlib.h>
#define MAXQSIZE 1000000//队列可达到的最大长度
#define OVERFLOW -1
#define ERROR 0
#define OK 1
typedef int QElemType;
typedef int Status;
typedef struct {
	QElemType *base;//定义队列指针
	int front;		//头指针
	int rear;		//尾指针
} SqQueue;

//初始化
Status InitQueue(SqQueue &Q) {
	Q.base = new QElemType[MAXQSIZE];//为队列分配一个最大容量为MAXQSIZE的数组空间
	if(!Q.base) exit(OVERFLOW);  	//存储分配失败
	Q.front = Q.rear = 0;     		//头指针和尾指针置为零，队列为空
	return OK;
}

//入队
Status EnQueue(SqQueue &Q, QElemType e) {
	if ((Q.rear + 1) % MAXQSIZE == Q.front)//队列已经满了
		return ERROR;
	Q.base[Q.rear] = e;      			  //新元素插入队尾
	Q.rear = (Q.rear + 1) % MAXQSIZE;     //队尾指针加1
	return OK;
}

//出队
Status DeQueue(SqQueue &Q, QElemType &e) {//删除Q的对头元素，用e返回其值
	if (Q.front == Q.rear)
		return ERROR;                   //队空
	e = Q.base[Q.front];                //保留对头元素
	Q.front = (Q.front + 1) % MAXQSIZE;//对头指针加1

	return OK;
}

//取对头元素
Status GetHead(SqQueue &Q, QElemType &e) {
	if (Q.front == Q.rear)
		return ERROR;                    //队空
	e = Q.base[Q.front];                //保留对头元素
	return OK;

}

//判断队列是否为空
int IsEmpty(SqQueue &Q) {
	if (Q.rear == Q.front)//队空
		return OK;
	else
		return ERROR;
}

//创建杨辉三角，N表示三角形的行数
void YHTriangle(int n){
	int i,j,s=0,t=0;
	SqQueue Q;          		//定义队列Q
	InitQueue(Q);               //初始化队列
	EnQueue(Q,1);
	EnQueue(Q,1);               //第一行元素入队 1 1
	for(i = 1;i < n;i++){
		EnQueue(Q,0);           //各行间插入一个0
		for(j = 1;j <= i+2;j++){
			DeQueue(Q,t);       //一个系数出队
			EnQueue(Q,s+t);     //计算下一行系数，并入队
			s = t;
			if(j!=i+2){
				printf("%d ",s);//第i+2个0
			}
		}
		//输出形式，二选一
		printf("0 ");           //输出一维数组，每行用0间隔
		printf("\n");           //输出杨辉三角形
	}
}

//主函数
int main() {
	int N;
	printf("请输入杨辉三角行数 N : ");
	scanf("%d", &N);
	YHTriangle(N);			//调用杨辉三角函数
	return 0;
}

4.2 运行结果

4.2.1按杨辉三角形打印

YHTriangle() 函数中最后的一行 为printf("\n");

请输入杨辉三角行数 N : 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

4.2.2 按一维数组方式打印一行

YHTriangle() 函数中最后的一行 为printf("0 ");

请输入杨辉三角行数 N : 10
1 0 1 1 0 1 2 1 0 1 3 3 1 0 1 4 6 4 1 0 1 5 10 10 5 1 0 1 6 15 20 15 6 1 0 1 7 21 35 35 21 7 1 0 1 8 28 56 70 56 28 8 1 0 1 9 36 84 126 126 84 36 9 1 0

注：部分图片源自教材和教学PPT；
部分名词已链接百度百科，可以进行更详细的阅读。