数据结构：多项式加法（Polynomial Addition）
目录
多项式加法
什么是多项式加法？
我们怎么找“相同指数”的项？
归并思想：遍历两个数组合并
最终代码实现：加法函数 add(A, B) → C
多项式加法
我们有两个多项式 A(x) 和 B(x)，希望计算出它们的和：C(x) = A(x) + B(x)
这就是多项式加法（Polynomial Addition）。
我们要在 C语言中，用我们之前定义的数据结构来实现这个运算。现在开始从最基本定义出发推导整个过程。
回顾我们已有的数据结构：数据结构：多项式表示（polynomial representation）-CSDN博客
struct Term {int coef; // 系数int exp; // 指数
};struct Polynomial {int n; // 实际项数struct Term* t; // 指向项数组的指针
};
什么是多项式加法？
A(x) = a1*x^e1 + a2*x^e2 + ... + am*x^em
B(x) = b1*x^f1 + b2*x^f2 + ... + bn*x^fn
我们要构造：
C(x) = (a1*x^e1 + b1'*x^e1) + (a2*x^e2 + b2'*x^e2) + ...
也就是说：
-
指数相同的项合并（系数相加）
-
指数不同的项原样保留
举个具体例子：
A(x) = 3*x^4 + 2*x^2 + 7
B(x) = 5*x^3 + 2*x^2 + 1
相加：
-
3*x^4 保留
-
5*x^3 保留
-
2x^2 + 2x^2 = 4*x^2
-
7 + 1 = 8
所以结果：
C(x) = 3*x^4 + 5*x^3 + 4*x^2 + 8
✅ 第一个结论：我们必须“按指数合并项”
我们怎么找“相同指数”的项？
这是 C 语言中的实际挑战。
如果两个多项式中的项：
-
是按照指数从大到小排序的，那我们可以用“归并思想”来合并
-
否则就只能每项都去另一边“找一圈”，效率低（O(n²)）
所以我们规定前提：
所有多项式的项，必须按指数降序排列（从大到小）
✅ 第二个结论：我们将两个排好序的项数组合并，遇到相同指数就合并，不同指数就直接放入结果。
归并思想：遍历两个数组合并
我们设有两个多项式 A 和 B：
struct Polynomial A, B;
它们各有 A.n 和 B.n 项，对应数组 A.t[] 和 B.t[]
我们创建一个新多项式 C，记录结果：
struct Polynomial C;
C.t = (struct Term*) malloc((A.n + B.n) * sizeof(struct Term));
最多有 A.n + B.n 项（如果两边指数完全不同）
用三个指针变量：
int i = 0; // 遍历 A
int j = 0; // 遍历 B
int k = 0; // 当前写入 C 的位置
✅ 遍历规则（归并过程）：
当 i < A.n 且 j < B.n 时：
如果 A.t[i].exp > B.t[j].exp：
-
把 A.t[i] 放进 C.t[k]
-
i++,k++
如果 A.t[i].exp < B.t[j].exp：
-
把 B.t[j] 放进 C.t[k]
-
j++,k++
如果 A.t[i].exp == B.t[j].exp：
-
系数相加：new_coef = A.t[i].coef + B.t[j].coef
-
如果 new_coef ≠ 0：
-
把 (new_coef, exp) 放进 C.t[k]
-
k++
-
-
i++,j++
🔚 最后处理剩余项：
-
如果 A 还有剩余：
while (i < A.n) { C.t[k++] = A.t[i++]; } -
如果 B 还有剩余：
while (j < B.n) { C.t[k++] = B.t[j++]; }
最终代码实现：加法函数 add(A, B) → C
struct Polynomial add(struct Polynomial A, struct Polynomial B) {struct Polynomial C;C.t = (struct Term*) malloc((A.n + B.n) * sizeof(struct Term));int i = 0, j = 0, k = 0;while (i < A.n && j < B.n) {if (A.t[i].exp > B.t[j].exp) {C.t[k++] = A.t[i++];} else if (A.t[i].exp < B.t[j].exp) {C.t[k++] = B.t[j++];} else {int sum_coef = A.t[i].coef + B.t[j].coef;if (sum_coef != 0) {C.t[k].coef = sum_coef;C.t[k].exp = A.t[i].exp;k++;}i++; j++;}}while (i < A.n) C.t[k++] = A.t[i++];while (j < B.n) C.t[k++] = B.t[j++];C.n = k;return C;
}
完整代码
#include <stdio.h>
#include <stdlib.h>struct Term {int coef;int exp;
};struct Polynomial {int n;struct Term* t;
};struct Polynomial add(struct Polynomial A, struct Polynomial B) {struct Polynomial C;C.t = (struct Term*) malloc((A.n + B.n) * sizeof(struct Term));int i = 0, j = 0, k = 0;while (i < A.n && j < B.n) {if (A.t[i].exp > B.t[j].exp) {C.t[k++] = A.t[i++];} else if (A.t[i].exp < B.t[j].exp) {C.t[k++] = B.t[j++];} else {int sum_coef = A.t[i].coef + B.t[j].coef;if (sum_coef != 0) {C.t[k].coef = sum_coef;C.t[k].exp = A.t[i].exp;k++;}i++; j++;}}while (i < A.n) C.t[k++] = A.t[i++];while (j < B.n) C.t[k++] = B.t[j++];C.n = k;return C;
}void printPoly(struct Polynomial p) {for (int i = 0; i < p.n; i++) {printf("%d*x^%d", p.t[i].coef, p.t[i].exp);if (i != p.n - 1) printf(" + ");}printf("\n");
}int main() {struct Polynomial A, B, C;A.n = 3;B.n = 3;A.t = (struct Term*) malloc(A.n * sizeof(struct Term));B.t = (struct Term*) malloc(B.n * sizeof(struct Term));// A(x) = 3*x^4 + 2*x^2 + 7A.t[0] = (struct Term){3, 4};A.t[1] = (struct Term){2, 2};A.t[2] = (struct Term){7, 0};// B(x) = 5*x^3 + 2*x^2 + 1B.t[0] = (struct Term){5, 3};B.t[1] = (struct Term){2, 2};B.t[2] = (struct Term){1, 0};C = add(A, B);printf("A(x) = "); printPoly(A);printf("B(x) = "); printPoly(B);printf("C(x) = A(x) + B(x) = "); printPoly(C);free(A.t);free(B.t);free(C.t);return 0;
}