两个给定的一元稀疏多项式相加（C语言数据结构）

在C语言中，为了表示一元稀疏多项式并进行相加操作，我们可以设计一个自定义的数据结构，如`SparsePolynomial`，它包含一个数组（通常用链表或动态数组）存储非零系数及其对应的指数。以下是基本的设计和相加函数：

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

// 定义数据结构
typedef struct {
    int coefficient; // 系数
    int exponent;     // 指数
} Term;

typedef struct {
    int size;
    Term* coefficients;
} SparsePolynomial;

// 初始化一个空的稀疏多项式
SparsePolynomial* createSparsePolynomial() {
    SparsePolynomial* poly = (SparsePolynomial*)malloc(sizeof(SparsePolynomial));
    poly->size = 0;
    poly->coefficients = NULL;
    return poly;
}

// 添加项到多项式
void addTerm(SparsePolynomial* poly, int coefficient, int exponent) {
    if (!poly->coefficients || poly->size == sizeof(poly->coefficients)) {
        Term* newCoeffs = realloc(poly->coefficients, (poly->size + 1) * sizeof(Term));
        if (!newCoeffs) {
            printf("Memory allocation failed.\n");
            exit(1);
        }
        poly->coefficients = newCoeffs;
    }
    poly->coefficients[poly->size].coefficient = coefficient;
    poly->coefficients[poly->size].exponent = exponent;
    poly->size++;
}

// 相加两个稀疏多项式
void addPolynomials(SparsePolynomial* result, const SparsePolynomial* poly1, const SparsePolynomial* poly2) {
    for (int i = 0; i < poly1->size; ++i) {
        for (int j = 0; j < poly2->size && poly2->coefficients[j].exponent >= poly1->coefficients[i].exponent; ++j) {
            result->coefficients[result->size] = poly1->coefficients[i];
            result->coefficients[result->size].coefficient += poly2->coefficients[j].coefficient;
            addTerm(result, result->coefficients[result->size].coefficient, result->coefficients[result->size].exponent);
        }
    }
    // 将剩余的 poly1 的项添加到结果
    for (; i < poly1->size; ++i) {
        addTerm(result, poly1->coefficients[i].coefficient, poly1->coefficients[i].exponent);
    }
}

// 打印多项式
void printPolynomial(const SparsePolynomial* poly) {
    printf("( ");
    for (int i = 0; i < poly->size; ++i) {
        printf("%d*x^%d ", poly->coefficients[i].coefficient, poly->coefficients[i].exponent);
    }
    printf(")");
}

int main() {
    SparsePolynomial* poly1 = createSparsePolynomial();
    SparsePolynomial* poly2 = createSparsePolynomial();

    // 添加一些项到多项式
    addTerm(poly1, 5, 2);  // 5x^2
    addTerm(poly1, 2, 1);  // 2x^1

    addTerm(poly2, 3, 3);   // 3x^3
    addTerm(poly2, 1, 0);  // 1x^0 (常数项)

    // 相加
    SparsePolynomial* sum = createSparsePolynomial();
    addPolynomials(sum, poly1, poly2);

    // 输出结果
    printPolynomial(sum);

    free(poly1);
    free(poly2);
    free(sum);
    return 0;
}

在这个示例中，我们首先创建了两个`SparsePolynomial`实例，然后分别添加项。最后，我们通过`addPolynomials`函数将它们相加，并打印出结果。