当先锋百科网

首页 1 2 3 4 5 6 7

打印杨辉三角

  • 杨辉三角是比较常见的队列的应用,下面一行的数是上面2个数字的和,数列首位都是1,高中数学里牛顿二项式展开式应该有说。

代码收获

  • 这题主要是找规律。利用下面一行比上面一行数字多一个,队列头为上一行,除了入队首尾的1之外,入队的上一行2个数的和等于新入队的元素,每入一次出一个上一行元素。
  • 分开讨论第3行以下和第3行及第三行后的。

队列归档

队列的顺序存储
队列的链式存储
队列的应用—打印杨辉三角

#include<stdio.h>
#include<stdlib.h>
# define MAXSIZE 100
typedef struct que{
    int ele[MAXSIZE];
    int front,rear;
}quene,*quenep;
void InitialStack(quenep* QE){
    *QE=(quenep)malloc(sizeof(quene));
    (*QE)->rear=0;
    (*QE)->front=0;//2指针相等代表空
}
int PushQuene(quenep QE,int x){
    if((QE->rear+1)%MAXSIZE==QE->front){
        printf("队列满\n");
        return 1;
    }else{
        QE->ele[QE->rear]=x;
        QE->rear=(QE->rear+1)%MAXSIZE;//入队列就是尾指针等于赋值的数,尾指针加一余上总大小
        return 0;
    }
}
int PopQuene(quenep QE,int*x){
    if(QE->front==QE->rear){
        printf("队列空\n"); return 1;
    }else{
        *x = QE->ele[QE->front];
        QE->front=(QE->front+1)%MAXSIZE;//出队列和入队列一样
        return 0;
    }
}

void Printquene(quenep QE){
    int sa;
    printf("队列里有\n");
    for(sa=QE->front;sa!=QE->rear;sa=(sa+1)%MAXSIZE){
        printf("%d",QE->ele[sa]);
    }
}
void yanghuitriangle(quenep QE){
    printf("输入需要输出几行\n");
    int num,rec=2,nei;
    scanf("%d",&num);
    getchar();
    PushQuene(QE,1);
    for(;rec<=num+2;rec++){//如果生成5行,必须循环到第7行
        PushQuene(QE,1);
        if(rec-2>0){//从第三行开始
            for(nei=1;nei<=rec-2;nei++){//看需要生成几个数,从第三行有第一个数生成
                int new;
                int x;
                new=QE->ele[QE->front]+QE->ele[QE->front+1];//上一层2数合
                PopQuene(QE,&x);
                printf("%d",x);
                PushQuene(QE,new);
            }
            int x3;
            PopQuene(QE,&x3);
            printf("%d",x3);
            PushQuene(QE,1);
            printf("\n");
        }else{//第二行,把第一行的1出掉
            int x2;
            PushQuene(QE,1);
            PopQuene(QE,&x2);
            printf("%d",x2);
            printf("\n");
        }
    }
}
void main(){
    quenep QE;
    InitialStack(&QE);
    yanghuitriangle(QE);
    Printquene(QE);
}

输入需要输出几行
9
9
1
11
121
1331
14641
15101051
1615201561
172135352171
18285670562881
193684126126843691
队列里有
1104512021025221012045101
Process finished with exit code 66