队列解决杨辉三角.cpp

队列解决杨辉三角

// 队列解决杨辉三角.cpp : Defines the entry point for the console application.
//


#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"
#define MAXSIZE 100

typedef struct {

	int data[MAXSIZE];

	int front,rear;

}Seqqueue;


void initQueue(Seqqueue *sq){     //初始化空队列

	sq->front =-1;

	sq->rear=-1;
}

bool empty(Seqqueue *sq){   //判队空函数，若Q为空栈，则函数返回值为“真”或为1，否则为“假”或为0

	if(sq->front==sq->rear){

		return 1;
	}
	else
		return 0;
}

int getfront(Seqqueue *sq){    //取队头元素

	int front;

	if(empty(sq)){

		printf("Queue is empty!\n");

		exit(0);
	}
	else
	{
	  
		front=sq->front;

		front=(front+1)%MAXSIZE;

	}

	return sq->data[front];
}

void enqueue(Seqqueue *sq,int e)   //队尾插入元素
{

      if(sq->front==(sq->rear + 1) % MAXSIZE){
		  
		  printf("Queue is full!\n");
         
	      exit(0);
	  }
      else{ 
		  sq->rear = (sq->rear + 1) % MAXSIZE;

		  sq->data[sq->rear]=e;
	  }
}
int dequeue(Seqqueue *sq)      //队头删除元素
{
      int e;
      if(empty(sq)){
		  
		  printf("Queue is empty!\n");
      
		  e = NULL;
	  }
      else{  
		  
		  sq->front = (sq->front + 1) % MAXSIZE;

		  e=sq->data[sq->front];
	  }
	  
	  return e;

}

//打印杨辉三角

/*            1  1  0
             1  2  1  0
		    1  3  3  1  0
*/

void display(Seqqueue *sq,int n){  //n为打印的层数

	// 初始化队列
	enqueue(sq,1);
	enqueue(sq,1);
	enqueue(sq,0);

	int temp,temp1,temp2,i;

	i=n;

	while(i>0){

		enqueue(sq,1);

		while((temp=getfront(sq))!=0){
			
			temp1=dequeue(sq);            //删除队头元素，并保存到temp1

			printf("%d ",temp1);

			temp2=getfront(sq);          //去队头元素

			enqueue(sq,temp1+temp2);     //temp1与temp2相加
		}

		temp=dequeue(sq);            //把0删掉

		enqueue(sq,0);               //加个0

		printf("\n");

		i--;
	}
}

void main(){

	Seqqueue *sq;

	sq=(Seqqueue *)malloc(sizeof(Seqqueue));

	printf("请输入打印杨辉三角的层数：\n");

	int n;

	scanf("%d",&n);

	display(sq,n);
}