1.题目

例3.6打印杨辉三角形。
利用队列打印杨辉三角形。杨辉三角形的图案如图3.18所示。

2.算法思路

3.代码

//
// Created by trmbh on 2023-09-12.
//
#include <stdio.h>
#include <stdlib.h>

#define TRUE 1
#define FALSE 0
#define MAXSIZE 50
#define QueueElementType int
/* 顺序队列 */
typedef struct {
    QueueElementType element[MAXSIZE];
    int front;
    int rear;
} SeqQueue;

void InitQueue(SeqQueue *Q) {
    Q->front = Q->rear = 0;
}

int EnterQueue(SeqQueue *Q, QueueElementType x) {
    /* 队列满(如果均用Q->front == Q->rear,那么无法判断队满还是队空，所以牺牲一个存储空间) */
    if ((Q->rear + 1) % MAXSIZE == Q->front) return FALSE;
    Q->element[Q->rear] = x;
    Q->rear = (Q->rear + 1) % MAXSIZE;
    return TRUE;
}

int DeleteQueue(SeqQueue *Q, QueueElementType *x) {
    /* 队列空 */
    if (Q->front == Q->rear) return FALSE;
    *x = Q->element[Q->front];
    Q->front = (Q->front + 1) % MAXSIZE;
}

int DestoryQueue(SeqQueue *Q) {
    Q->front = Q->rear = 0;
    return TRUE;
}

QueueElementType GetHead(SeqQueue *Q) {
    return Q->element[Q->front];
}

int IsEmpty(SeqQueue *Q) {
    if (Q->front == Q->rear) return TRUE;
    else return FALSE;
}

void Print_Space(){ printf("   ");}

void Format_Adjustment(int n, int count){
    /* 注意由于目前要打印的行其实是count-1， 所以如下所示n-（count-1）*/
    for (int i = 0; i < n - count + 1; i++) {
        Print_Space();
    }
}

void Print_Yang_Hui_Triangle(SeqQueue *Q) {
    /* 这里初始化第一行后，从第二行开始 */
    int count = 2;
    int n;
    QueueElementType temp, x;
    scanf("%d", &n);
    /* 初始化第一行第一个元素,这里由于下一行的值取决于上一行的值，所以先弄第一行作为基础 */
    EnterQueue(Q, 1);

    /* count的值对应第n行*/
    while (count <= n) {
        /* 第n行首个元素 */
        EnterQueue(Q, 1);
        Format_Adjustment(n, count);
        /* 获得第n行中间n-2个元素，同时打印第n-1行前n-2个元素*/
        for (int i = 1; i <= count - 2; i++) {
            DeleteQueue(Q, &temp);
            printf("%d", temp);
            Print_Space();
            Print_Space();
            x = GetHead(Q);
            EnterQueue(Q, temp + x);
        }
        /* 打印n-1行最后一个元素,第n行最后一个元素入队*/
        DeleteQueue(Q, &x);
        printf("%d\n", x);
        EnterQueue(Q, 1);
        count++;
    }

    /* 这里注意一个问题，第n行的元素在打印第n-1行时得到，在获得第n+1行时打印，有一个延迟，所以单独处理最后一行（第n行只入队未出队）*/
    while (!IsEmpty(Q)) {
        DeleteQueue(Q, &x);
        printf("%d", x);
        Print_Space();
        Print_Space();
    }
}

int main() {
    SeqQueue Q;
    InitQueue(&Q);
    Print_Yang_Hui_Triangle(&Q);
    DestoryQueue(&Q);
    return 0;
}