C語言如何實現動態開辟存儲楊輝三角

C語言如何實現動態開辟存儲楊輝三角

1. 引言

楊輝三角（Pascal’s Triangle）是二項式系數在三角形中的一種幾何排列。它在數學、計算機科學等領域有著廣泛的應用。本文將詳細介紹如何使用C語言動態開辟內存來存儲楊輝三角，并展示如何通過代碼實現這一過程。

2. 楊輝三角的基本概念

楊輝三角的每一行對應于二項式系數。例如，第n行的數字對應于二項式\((a + b)^{n-1}\)的展開系數。楊輝三角的前幾行如下所示：

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
...

每一行的第一個和最后一個數字都是1，中間的數字是上一行相鄰兩個數字之和。

3. 動態內存分配的基本概念

在C語言中，動態內存分配是指在程序運行時根據需要分配內存。常用的動態內存分配函數包括malloc、calloc、realloc和free。

• malloc：分配指定大小的內存塊，返回指向該內存塊的指針。
• calloc：分配指定數量和大小的內存塊，并將內存初始化為0。
• realloc：調整已分配內存塊的大小。
• free：釋放先前分配的內存塊。

4. 實現動態開辟存儲楊輝三角的步驟

4.1 確定楊輝三角的行數

首先，我們需要確定楊輝三角的行數。用戶可以通過輸入指定行數，或者程序可以預設一個默認值。

int rows;
printf("Enter the number of rows: ");
scanf("%d", &rows);

4.2 動態分配二維數組

由于楊輝三角的每一行長度不同，我們需要使用指針數組來動態分配內存。具體步驟如下：

1. 分配一個指針數組，用于存儲每一行的指針。
2. 為每一行分配內存，存儲該行的數字。

int **triangle = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
    triangle[i] = (int *)malloc((i + 1) * sizeof(int));
}

4.3 填充楊輝三角

根據楊輝三角的性質，我們可以通過以下步驟填充數組：

1. 每一行的第一個和最后一個數字都是1。
2. 中間的數字是上一行相鄰兩個數字之和。

for (int i = 0; i < rows; i++) {
    for (int j = 0; j <= i; j++) {
        if (j == 0 || j == i) {
            triangle[i][j] = 1;
        } else {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
}

4.4 打印楊輝三角

填充完楊輝三角后，我們可以通過嵌套循環打印出每一行的數字。

for (int i = 0; i < rows; i++) {
    for (int j = 0; j <= i; j++) {
        printf("%d ", triangle[i][j]);
    }
    printf("\n");
}

4.5 釋放動態分配的內存

使用完動態分配的內存后，必須釋放這些內存以避免內存泄漏。

for (int i = 0; i < rows; i++) {
    free(triangle[i]);
}
free(triangle);

5. 完整代碼示例

以下是一個完整的C語言程序，實現了動態開辟存儲楊輝三角的功能。

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

int main() {
    int rows;

    // 獲取用戶輸入的行數
    printf("Enter the number of rows: ");
    scanf("%d", &rows);

    // 動態分配二維數組
    int **triangle = (int **)malloc(rows * sizeof(int *));
    for (int i = 0; i < rows; i++) {
        triangle[i] = (int *)malloc((i + 1) * sizeof(int));
    }

    // 填充楊輝三角
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j <= i; j++) {
            if (j == 0 || j == i) {
                triangle[i][j] = 1;
            } else {
                triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
            }
        }
    }

    // 打印楊輝三角
    for (int i = 0; i < rows; i++) {
        for (int j = 0; j <= i; j++) {
            printf("%d ", triangle[i][j]);
        }
        printf("\n");
    }

    // 釋放動態分配的內存
    for (int i = 0; i < rows; i++) {
        free(triangle[i]);
    }
    free(triangle);

    return 0;
}

6. 代碼解析

6.1 動態分配二維數組

int **triangle = (int **)malloc(rows * sizeof(int *));
for (int i = 0; i < rows; i++) {
    triangle[i] = (int *)malloc((i + 1) * sizeof(int));
}

• triangle是一個指向指針的指針，用于存儲每一行的指針。
• 外層循環為每一行分配內存，內存大小為(i + 1) * sizeof(int)，因為第i行有i + 1個元素。

6.2 填充楊輝三角

for (int i = 0; i < rows; i++) {
    for (int j = 0; j <= i; j++) {
        if (j == 0 || j == i) {
            triangle[i][j] = 1;
        } else {
            triangle[i][j] = triangle[i - 1][j - 1] + triangle[i - 1][j];
        }
    }
}

• 外層循環遍歷每一行。
• 內層循環遍歷每一行的每一個元素。
• 如果當前元素是第一個或最后一個，則賦值為1。
• 否則，當前元素等于上一行相鄰兩個元素之和。

6.3 打印楊輝三角

for (int i = 0; i < rows; i++) {
    for (int j = 0; j <= i; j++) {
        printf("%d ", triangle[i][j]);
    }
    printf("\n");
}

• 外層循環遍歷每一行。
• 內層循環遍歷每一行的每一個元素，并打印出來。

6.4 釋放動態分配的內存

for (int i = 0; i < rows; i++) {
    free(triangle[i]);
}
free(triangle);

• 外層循環釋放每一行的內存。
• 最后釋放指針數組的內存。

7. 總結

本文詳細介紹了如何使用C語言動態開辟內存來存儲楊輝三角。通過動態內存分配，我們可以靈活地處理不同大小的數據結構，避免了靜態數組的局限性。希望本文能幫助讀者更好地理解動態內存分配和楊輝三角的實現。