链表

• 定义：用任意的存储单元存储数据，通过指针链接。
• 结构：结点 = 数据域 + 指针域。
• 头结点 (Header Node)：在第一个数据结点之前附设的一个结点。
  • 作用：使空表和非空表的处理统一，简化插入/删除操作。
• 关键操作代码 (C语言)：
• 插入 (Insert)：在 $p$ 之后插入 $s$

s->next = p->next; 
p->next = s; // 顺序不可反，否则丢失后续链表

• 删除 (Delete)：删除 $p$ 之后的结点

q = p->next;
p->next = q->next;
free(q);

• 变体：
  • 循环链表：最后一个结点的指针指向头结点。判空条件是 p->next == head。
  • 双向链表：每个结点有两个指针 prior 和 next。

多项式加法

typedef struct PolyNode {
    float coef;         // 系数 (Coefficient)
    int exp;            // 指数 (Exponent)
    struct PolyNode *next;
} PolyNode, *Polynomial;

void AddPolynomial(Polynomial Pa, Polynomial Pb) {
    Polynomial p1 = Pa->next; // 假设有头节点
    Polynomial p2 = Pb->next;
    Polynomial pre = Pa;      // 用于构建结果链表
    Polynomial temp;
 
    while (p1 && p2) {
        if (p1->exp > p2->exp) {
            // 情况 A：p1 指数大，直接将 p1 接在结果后，指针后移
            pre->next = p1;
            pre = p1;
            p1 = p1->next;
        } 
        else if (p1->exp < p2->exp) {
            // 情况 B：p2 指数大，将 p2 接在结果后
            pre->next = p2;
            pre = p2;
            p2 = p2->next;
        } 
        else {
            // 情况 C：指数相等，系数相加
            float sum = p1->coef + p2->coef;
            if (sum != 0) {
                p1->coef = sum; // 更新 p1 的系数
                pre->next = p1;
                pre = p1;
                p1 = p1->next;
                // p2 已经没用了，释放掉
                temp = p2;
                p2 = p2->next;
                free(temp);
            } else {
                // 系数归零，p1 和 p2 都要释放，且不接入结果链表
                temp = p1; p1 = p1->next; free(temp);
                temp = p2; p2 = p2->next; free(temp);
            }
        }
    }
    // 最后处理剩余的链表（类似归并排序的扫尾）
    pre->next = p1 ? p1 : p2;
}