目录
多项式加法
我们有两个多项式 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 + 7
A.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 + 1
B.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;
}