【数据结构】队列 杨辉三角

2019/03/16 15:56
阅读数 135

杨辉三角形是形如:
1
1   1
1   2   1
1   3   3   1
1   4   6   4   1

使用《队列》的思想来实现杨辉三角的流程:

1>首先,需要初始化一个队列,即对头=队尾=0;

2>将第一行的元素1入队,接着操作第二行(一二行不需要求和操作,直接将元素入队即可);

3>从第三行开始,现在的对头指向N-1行,先将每行的固定元素1入队,然后循环操作求和过程:

将队首元素出队,并保存它的值temp;

获取当前队首的元素x,并进行temp=temp+x,且将temp入队;

4>循环结束后,队首在N-1行的最后一个元素处,现将其出队,然后将每行最后的固定元素1入队;

5>循环3、4步就可以输出杨辉三角形了。 

注意:杨辉三角的特点是第N行的中间值等于N-1行两值的和,队列采用的是单进单出。 

or///////////////

其基本算法如下: 
   假设n行 
   当n=1时将1入队 
   当n>=2时当生成第n行第j个时 
   如果j=1时,将1入队 
   如果j=n时,将1入队,并将队列第一个出对 
   当1<j<n时,将队列第一个出对记录其值并和此时队列第一个元素的和入队 


代码:【前部分为循环队列初始化 插入(队尾)  删除(队首) 取队首 是否空】

//使用队列输出杨辉三角
#include "stdafx.h"
#include<stdio.h>
 
#define MAXSIZE 50
#define FALSE 0 
#define TRUE 1
typedef int QueueElemType;
 
typedef struct
{
    QueueElemType element[MAXSIZE];
    int front;//队头
    int rear;//队尾
}SeqQueue;
 
void InitQueue(SeqQueue *Q)//初始化
{
    Q->front = Q->rear = 0;
}
 
int EnterQueue(SeqQueue *Q, QueueElemType x)//入队
{
    if ((Q->rear + 1) % MAXSIZE == Q->front)///队列已经满了
        return FALSE;
    Q->element[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return TRUE;
}
 
int DelQueue(SeqQueue *Q, QueueElemType *x)//出对
{
    if (Q->front == Q->rear)
        return FALSE;
    *x = Q->element[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
 
    return TRUE;
}
int GetHead(SeqQueue *Q, QueueElemType *x)//取对头元素
{
    if (Q->front == Q->rear)
        return FALSE;
    *x = Q->element[Q->front];
    return TRUE;
 
}
int IsEmpty(SeqQueue *Q)
{
    if (Q->rear == Q->front)
        return TRUE;
    else
        return FALSE;
}
//创建杨辉三角,N表示三角形的行数
void YangHuiTriangle(int N)
{
    int n, i, x, temp;
    SeqQueue Q;
    InitQueue(&Q);
    EnterQueue(&Q, 1);//第一行元素入队
    for (n = 2; n <= N; n++)
    {
        EnterQueue(&Q, 1);//入队
        for (i = 1; i <= n - 2; i++)
        {
            DelQueue(&Q, &temp);//出队的数赋给temp
            printf("%d ", temp);
            GetHead(&Q, &x);
            temp = temp + x;
            EnterQueue(&Q, temp);
        }
        DelQueue(&Q, &x);//出队
        printf("%d ", x);
        EnterQueue(&Q, 1);
        printf("\n");
    }
    while (!IsEmpty(&Q))
    {
        DelQueue(&Q, &x);
        printf("%d ", x);
 
    }
}
void main()
{
    int N;
    printf("please input the N:");
    scanf("%d", &N);
    YangHuiTriangle(N);
    printf("\n");
}

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部