二項式係數生成：基於隊列的楊輝三角實現（OJ 經典題）

題目背景

二項式 (a + b)^i 展開的係數構成楊輝三角（Pascal 三角）。要求使用隊列數據結構，輸入冪次 i (1 ≤ i ≤ 30)，輸出對應行的所有係數，數字間以空格分隔，行末無多餘空格。

隊列模擬楊輝三角的核心思路

利用隊列的先進先出特性，逐行構建：

1. 隊列初始化為兩個 1（對應第 1 行）。
2. 對於第 k 行（k = 2..n），循環 k-1 次：出隊首元素 x，讀取新隊首 y，將 x+y 入隊。
3. 每行結束後額外入隊一個 1（行尾係數）。
4. 每行生成完畢即可輸出隊列中該行的所有元素。

完整 C 語言實現（含隊列封裝）

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElemType;

typedef struct Node {
    ElemType data;
    struct Node *next;
} Node;

typedef struct Queue {
    Node *front;
    Node *rear;
    int length;
} Queue;

Queue *queue_new() {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->front = q->rear = NULL;
    q->length = 0;
    return q;
}

bool IsEmpty(Queue *q) { return q->length == 0; }

bool EnQueue(Queue *q, ElemType e) {
    Node *p = (Node *)malloc(sizeof(Node));
    if (!p) return false;
    p->data = e; p->next = NULL;
    if (IsEmpty(q)) q->front = q->rear = p;
    else { q->rear->next = p; q->rear = p; }
    q->length++;
    return true;
}

bool DeQueue(Queue *q, ElemType *e) {
    if (IsEmpty(q)) return false;
    Node *p = q->front;
    *e = p->data;
    q->front = p->next;
    if (q->front == NULL) q->rear = NULL;
    free(p);
    q->length--;
    return true;
}

void PrintRow(Queue *q, int n) {
    Node *cur = q->front;
    for (int i = 0; i < n; i++) {
        printf("%d", cur->data);
        if (i != n-1) printf(" ");
        cur = cur->next;
    }
    printf("\n");
}

void GenerateRow(int n) {
    Queue *q = queue_new();
    EnQueue(q, 1);
    EnQueue(q, 1); // 第 1 行：1 1
    if (n == 1) { PrintRow(q, 2); return; }

    for (int row = 2; row <= n; row++) {
        int prev, curr;
        DeQueue(q, &prev); // 取出行首 1
        for (int i = 1; i < row; i++) {
            DeQueue(q, &curr);
            EnQueue(q, prev + curr);
            prev = curr;
        }
        EnQueue(q, 1); // 行尾 1
    }
    PrintRow(q, n+1);
    // 釋放隊列內存略
}

int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        GenerateRow(n);
    }
    return 0;
}

關鍵點提示

• 輸入可能包含多組測試用例，需循環讀取直到 EOF。
• 係數最大不超過 C(30,15) ≈ 1.5e8，int 足夠容納。
• 輸出格式嚴格：行末無空格，每行單獨換行。