当先锋百科网

首页 1 2 3 4 5 6 7

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

杨辉三角形是形如：
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");
}

 

转载于:https://www.cnblogs.com/yundong333/p/10542648.html