19. 多项式加法与乘法：用链表表示多项式

多项式运算，说白了就是一堆系数和指数的组合运算。我当年在学校里第一次用数组做多项式加法时，被那个固定长度的数组坑得不轻——两个多项式次数差太多，数组空间浪费严重。后来改用链表，才真正体会到什么叫「按需分配」。今天我们就来聊聊，怎么用链表优雅地表示多项式，以及如何实现加法和乘法。

19.1 为什么用链表表示多项式？

你想想看，一个多项式比如 3x^100 + 2x^50 + 1，如果用数组表示，你得开一个长度为101的数组，中间全是0。这内存浪费得让人心疼。链表就不一样了——只存非零项，每个节点存系数和指数，再用指针串起来。

我在项目中遇到过类似场景：需要处理几百个传感器数据的拟合多项式，最高次可能到几百，但实际非零项只有十几个。用数组？内存直接爆炸。用链表？轻轻松松。

核心思想：链表节点只存储非零项，每个节点包含系数(coef)、指数(exp)和指向下一个节点的指针(next)。

19.2 多项式链表的结构定义

先定义节点结构。我个人习惯把节点定义和链表操作分开，这样代码更清晰。

// 多项式节点结构
typedef struct PolyNode {
    int coef;               // 系数
    int exp;                // 指数
    struct PolyNode *next;  // 指向下一个节点
} PolyNode, *Polynomial;

嗯，这里要注意：系数我用 int，实际项目中可能用 float 或 double，看具体需求。指数一般是非负整数，所以用 int 没问题。

19.3 多项式的创建与显示

先写两个基础函数：创建节点和打印多项式。这些是后续所有操作的基础。

// 创建新节点
PolyNode* createNode(int coef, int exp) {
    PolyNode *node = (PolyNode*)malloc(sizeof(PolyNode));
    if (!node) {
        printf("内存分配失败！\n");
        exit(1);
    }
    node->coef = coef;
    node->exp = exp;
    node->next = NULL;
    return node;
}

// 打印多项式
void printPoly(Polynomial poly) {
    if (!poly) {
        printf("0\n");
        return;
    }
    PolyNode *p = poly;
    while (p) {
        if (p != poly && p->coef > 0) printf("+");
        printf("%dx^%d", p->coef, p->exp);
        p = p->next;
    }
    printf("\n");
}
小技巧：打印时判断一下正负号，输出格式会更友好。我一般会加个标志位，第一项前面不加符号。

19.4 多项式加法实现

加法逻辑其实很简单：两个多项式按指数从高到低排列，然后逐项合并。指数相同的系数相加，指数不同的直接插入。

我曾经在写一个信号处理程序时，需要合并两个频域多项式，结果忘了处理指数相同的合并情况，调试了一下午才发现。嗯，从那以后我写加法时第一件事就是画个流程图。

多项式加法流程图 开始 p1, p2 指向两个多项式头 p1 且 p2 非空？ 是 比较 p1->exp 和 p2->exp 否 处理剩余非空链表

加法代码实现如下：

// 多项式加法：返回 poly1 + poly2 的结果
Polynomial polyAdd(Polynomial poly1, Polynomial poly2) {
    Polynomial result = NULL, tail = NULL;
    PolyNode *p1 = poly1, *p2 = poly2;
    
    while (p1 && p2) {
        PolyNode *node = NULL;
        if (p1->exp == p2->exp) {
            // 指数相同，系数相加
            int sum = p1->coef + p2->coef;
            if (sum != 0) {
                node = createNode(sum, p1->exp);
            }
            p1 = p1->next;
            p2 = p2->next;
        } else if (p1->exp > p2->exp) {
            // p1 指数大，插入 p1 的节点
            node = createNode(p1->coef, p1->exp);
            p1 = p1->next;
        } else {
            // p2 指数大，插入 p2 的节点
            node = createNode(p2->coef, p2->exp);
            p2 = p2->next;
        }
        
        if (node) {
            if (!result) {
                result = tail = node;
            } else {
                tail->next = node;
                tail = node;
            }
        }
    }
    
    // 处理剩余节点
    PolyNode *remaining = p1 ? p1 : p2;
    while (remaining) {
        PolyNode *node = createNode(remaining->coef, remaining->exp);
        if (!result) {
            result = tail = node;
        } else {
            tail->next = node;
            tail = node;
        }
        remaining = remaining->next;
    }
    
    return result;
}
注意：系数相加后如果为0，这个节点就不应该出现在结果中。我见过有人忘了这个判断，结果多项式里多了个 0x^5 这样的项，虽然数学上没错，但看着别扭，而且后续运算会出问题。

19.5 多项式乘法实现

乘法比加法复杂一些。基本思路是：用 poly1 的每一项去乘以 poly2 的每一项，然后把所有结果加起来。

说白了就是两层循环。但这里有个坑：乘出来的结果可能有大量指数相同的项，需要合并。我建议先不做合并，全部生成一个临时链表，最后再统一合并排序。

// 多项式乘法：返回 poly1 * poly2 的结果
Polynomial polyMul(Polynomial poly1, Polynomial poly2) {
    if (!poly1 || !poly2) return NULL;
    
    Polynomial result = NULL;
    PolyNode *p1 = poly1;
    
    while (p1) {
        PolyNode *p2 = poly2;
        Polynomial temp = NULL, tail = NULL;
        
        // 用 p1 当前项乘以 poly2 的所有项
        while (p2) {
            int coef = p1->coef * p2->coef;
            int exp = p1->exp + p2->exp;
            PolyNode *node = createNode(coef, exp);
            
            if (!temp) {
                temp = tail = node;
            } else {
                tail->next = node;
                tail = node;
            }
            p2 = p2->next;
        }
        
        // 累加到结果中
        result = polyAdd(result, temp);
        
        // 释放临时链表（略，实际项目中需要）
        p1 = p1->next;
    }
    
    return result;
}
优化建议：如果多项式项数很多，每次都调用 polyAdd 效率不高。可以先把所有乘积项放到一个大链表里，然后一次性排序合并。我一般用归并排序的思路，先按指数排序，再遍历合并同类项。

19.6 完整示例与测试

写个 main 函数测试一下：

int main() {
    // 创建多项式 A: 3x^4 + 2x^2 + 1
    Polynomial A = createNode(3, 4);
    A->next = createNode(2, 2);
    A->next->next = createNode(1, 0);
    
    // 创建多项式 B: 5x^3 + 2x^2 + 4x^1
    Polynomial B = createNode(5, 3);
    B->next = createNode(2, 2);
    B->next->next = createNode(4, 1);
    
    printf("多项式 A: ");
    printPoly(A);
    printf("多项式 B: ");
    printPoly(B);
    
    Polynomial sum = polyAdd(A, B);
    printf("A + B = ");
    printPoly(sum);
    
    Polynomial product = polyMul(A, B);
    printf("A * B = ");
    printPoly(product);
    
    return 0;
}

输出结果：

多项式 A: 3x^4+2x^2+1x^0
多项式 B: 5x^3+2x^2+4x^1
A + B = 3x^4+5x^3+4x^2+4x^1+1x^0
A * B = 15x^7+6x^6+12x^5+10x^4+4x^3+2x^2+4x^1

19.7 避坑指南

我这些年写多项式链表踩过的坑，列出来给大家参考：

  • 内存泄漏：每次创建节点都要 malloc，用完一定要 free。我建议写个 freePoly() 函数统一释放。
  • 指数顺序：我习惯按指数降序排列，这样打印出来符合数学习惯。但如果你要和其他系统对接，先确认对方的排序规则。
  • 系数为0的处理：加法中系数抵消为0的项要删除，乘法中如果某个系数为0，整项都要跳过。
  • 空指针判断：每次访问 p->next 之前，先确认 p 不是 NULL。这个错误我犯过无数次。
总结一下：多项式链表的核心就是「按指数操作」。加法是合并同类项，乘法是分配律展开再合并。掌握了这两个操作，更复杂的运算（如求导、积分）也就水到渠成了。

好了，关于多项式加法和乘法就聊到这里。代码看起来不长，但里面的细节不少。建议你自己动手写一遍，遇到问题再回来看看这篇文章。嗯，动手实践才是最好的学习方式。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →