稀疏多项式的运算（链表，C语言）

在C语言中，稀疏多项式通常指的是那些大部分系数为0的多项式，如果用数组来存储会非常浪费空间。为了高效处理这种数据结构，可以使用链表来存储非零项。每个节点代表多项式的一个项，包含系数和对应的指数。

以下是基本操作的概述：

1. **创建**：创建一个稀疏多项式链表时，初始化头节点，当有新项时，新建一个节点添加到链表末尾。

typedef struct {
    double coef; // 系数
    int exp;    // 指数
    struct SparsePolyNode* next; // 指向下一个项的指针
} SparsePolyNode;

SparsePolyNode* createSparsePoly() {
    return malloc(sizeof(SparsePolyNode));
}

2. **插入**：给定系数和指数，检查是否已有对应项，若有则更新系数，若无则添加新节点。

void insertTerm(SparsePolyNode** head, double coef, int exp) {
    SparsePolyNode* newNode = createSparsePoly();
    newNode->coef = coef;
    newNode->exp = exp;
    newNode->next = *head;
    if (newNode->exp > 0) *head = newNode;
}

3. **加法和减法**：遍历两个链表，找到对应指数的项相加或相减，然后合并结果。

4. **乘法**：可以使用Karatsuba算法或快速傅立叶变换等高效方法，先预处理指数再计算。

5. **求值**：对于特定的x值，从高指数开始遍历链表，累乘并加和。

double evaluate(double x, SparsePolyNode* head) {
    double result = 0.0;
    while (head != NULL) {
        if (head->exp != 0) result *= x;
        result += head->coef;
        head = head->next;
        if (head != NULL) head->exp--;
    }
    return result;
}

// 示例
SparsePolyNode* polyA = createSparsePoly(); // 初始化链表...
SparsePolyNode* polyB = createSparsePoly(); // 另一个链表...

insertTerm(&polyA, 2, 2);
insertTerm(&polyB, 3, 1);

// 进行运算...