陣列實現多項式加減乘運算：固定大小結構體與高效演算法

陣列實現多項式運算：定長陣列結構與核心演算法

使用固定大小陣列存儲係數，下標即指數。結構簡單、隨機訪問快，適合次數上限已知、密集分佈的多項式。

數據結構定義

#define MaxDegree 100  // 最大指數

typedef struct {
    int CoeffArray[MaxDegree + 1];  // 係數陣列，索引=指數
    int HighPower;                  // 最高非零項指數
} *Polynomial;

核心操作實現

初始化：歸零

void ZeroPolynomial(Polynomial Poly) {
    for (int i = 0; i <= MaxDegree; i++)
        Poly->CoeffArray[i] = 0;
    Poly->HighPower = 0;
}

加法：係數對應相加

void AddPolynomial(const Polynomial P1, const Polynomial P2, Polynomial Sum) {
    ZeroPolynomial(Sum);
    Sum->HighPower = (P1->HighPower > P2->HighPower) ? P1->HighPower : P2->HighPower;
    for (int i = Sum->HighPower; i >= 0; i--)
        Sum->CoeffArray[i] = P1->CoeffArray[i] + P2->CoeffArray[i];
}

乘法：卷積累加

void MultPolynomial(const Polynomial P1, const Polynomial P2, Polynomial Prod) {
    ZeroPolynomial(Prod);
    Prod->HighPower = P1->HighPower + P2->HighPower;
    if (Prod->HighPower > MaxDegree) FatalError("Exceeded array size");

    for (int i = 0; i <= P1->HighPower; i++)
        for (int j = 0; j <= P2->HighPower; j++)
            Prod->CoeffArray[i + j] += P1->CoeffArray[i] * P2->CoeffArray[j];
}

陣列版 vs 鏈表版對比

適用場景建議

• 陣列版：密集多項式、指數上限小（<1000）、高性能計算核心、嵌入式無堆環境
• 鏈表版：稀疏多項式、指數跨度大、動態次數、通用符號計算系統

擴展優化方向

• 動態陣列（realloc）突破 MaxDegree 限制
• 模板化支援 float/double/complex 係數
• 結合 FFT 加速大次數多項式乘法（O(n log n)）
• 稀疏陣列壓縮存儲（三元組/十字鏈表）