| 循环队列实现杨辉三角（两种输出形式） | 您所在的位置：网站首页 › 编程打印出杨辉三角的前10行JAVA › 循环队列实现杨辉三角（两种输出形式） |
循环队列实现杨辉三角（两种输出形式）
|
问题导入什么是杨辉三角呢？之前用过C/C++数组实现过打印杨辉三角，那么如何使用队列来实现呢？ 目录 1、什么是杨辉三角1.1 图形1.2 特点 2、什么是队列2.1 队列的定义2.2 队列的常用公式 3、队列实现杨辉三角原理3.1 图形演示3.2 主要算法实现 4、代码实现4.1 main.cpp4.2 运行结果4.2.1按杨辉三角形打印4.2.2 按一维数组方式打印一行 1、什么是杨辉三角杨辉三角（也称帕斯卡三角）相信很多人都不陌生，它是一个无限对称的数字金字塔，从顶部的单个1开始，下面一行中的每个数字都是上面两个数字的和。 1.1 图形下图就是杨辉三角前7行 杨辉三角的实质是二项式(a+b)n展开后各项的系数排成的三角形。 特点如下： 1、各行的第一个数都是1 2、各行的最后一个数都是1 3、从第3行起，除上面指出的第一个数和最后一个数外，其余各数是上一行同列和前一列两个数之和。 2、什么是队列 2.1 队列的定义队列(queue)是一种先进先出(First In First Out, FIFO) 的线性表。它只允许在表的一端进行插入，而在另一端删除元素。这和日常生活中的排队是一致的，最早进入队列的元素最早离开。在队列中，允许插入的一端称为队尾(rear),允许删除的一端则称为队头(front)。 一般使用循环队列（提高空间的利用率） 初始化： 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
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
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； 部分名词已链接百度百科，可以进行更详细的阅读。 |
【本文地址】
公司简介
联系我们