一、數組的基本特性

• 定義：

  int arr[3][3]; // 3x3二維數組

• 存儲方式：

  • 行優先存儲（C語言默認）：元素按行連續存儲。

  • 列優先存儲：需手動實現（如科學計算中的Fortran風格）。

• 訪問元素：

arr[i][j] = value; // 直接訪問

二、?特殊矩陣的壓縮存儲

針對特定規律的矩陣（如對稱、稀疏），可通過壓縮存儲減少空間占用。

(1) 對稱矩陣

• 特點：a[i][j] = a[j][i]，只需存儲上三角或下三角。

• 壓縮存儲：

  • 將下三角元素存入一維數組，元素總數：n(n+1)/2。

  • 下標轉換公式（行優先）：

    • 當?i ≥ j?時，一維數組索引?k = i*(i+1)/2 + j。

    • 當?i < j?時，交換?i?和?j。

示例代碼：

// 壓縮對稱矩陣
int compressSymmetric(int matrix[][N], int n, int compressed[]) {int k = 0;for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) { // 存儲下三角compressed[k++] = matrix[i][j];}}return k; // 返回壓縮后長度
}// 訪問壓縮后的元素
int getElement(int compressed[], int i, int j) {if (i < j) { // 上三角轉下三角int temp = i;i = j;j = temp;}return compressed[i*(i+1)/2 + j];
}

(2) 三角矩陣

• 上三角矩陣：只存儲主對角線及以上元素。

• 下三角矩陣：只存儲主對角線及以下元素。

• 壓縮存儲：類似對稱矩陣，但需額外存儲剩余部分的常量（如0）。

示例代碼（下三角矩陣）：

// 壓縮下三角矩陣（包含對角線）
void compressLowerTriangular(int matrix[][N], int n, int compressed[]) {int k = 0;for (int i = 0; i < n; i++) {for (int j = 0; j <= i; j++) {compressed[k++] = matrix[i][j];}}
}

(3) 稀疏矩陣

• 特點：絕大多數元素為0，通過壓縮存儲非零元素。

• 存儲方式：

  1. 三元組表示法：存儲非零元素的行、列、值。

  2. 十字鏈表：適合頻繁插入/刪除操作（如圖像處理）。

三元組表示法示例：

typedef struct {int row, col, value;
} Triple;// 壓縮稀疏矩陣
void compressSparse(int matrix[][M], int rows, int cols, Triple compressed[]) {int k = 0;for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (matrix[i][j] != 0) {compressed[k].row = i;compressed[k].col = j;compressed[k].value = matrix[i][j];k++;}}}
}// 訪問稀疏矩陣元素
int getSparseElement(Triple compressed[], int size, int i, int j) {for (int k = 0; k < size; k++) {if (compressed[k].row == i && compressed[k].col == j) {return compressed[k].value;}}return 0; // 未找到則返回0
}

三、對比與選擇

四、操作復雜度

• 普通數組：

  • 訪問：O(1)

  • 插入/刪除：不適用（需重構數組）

• 壓縮存儲矩陣：

  • 訪問：O(1)（對稱/三角）或 O(non_zero)（稀疏矩陣遍歷）

  • 插入/刪除：僅稀疏矩陣支持高效操作（如十字鏈表）

五、實際應用

• 圖像處理：稀疏矩陣存儲圖像的非零像素。

• 科學計算：對稱矩陣用于物理模擬中的剛度矩陣。

• 機器學習：三角矩陣用于LU分解加速計算。

六、總結

在C語言中，數組是基礎數據結構，而特殊矩陣通過壓縮存儲可顯著優化空間和操作效率。根據矩陣特性和應用場景選擇合適的存儲方式：

• 對稱/三角矩陣：用一維數組壓縮存儲。

• 稀疏矩陣：用三元組或十字鏈表實現動態操作。

?