多項式相加、相減、相乘
多項式相加、相減、相乘
( 使用下 以下 struct 與 與 Link List 實作 )
(1) void add(pol_t* X, pol_t* Y, pol_t* Z);
//兩個多項式 X, Y相加，Z是結果
(2) void sub(pol_t* X, pol_t* Y, pol_t* Z);
//兩個多項式 X, Y相減，Z是結果
(3) void mul(pol_t* X, pol_t* Y, pol_t* Z);
//兩個多項式 X, Y相乘，Z是結果
typedef struct node_s {
int coef;
int exp;
struct node_s * next;
} node_t;
typedef node_t * nodep_t;
typedef pol_s {
nodep_t root;
} pol_t
輸出說明
Line 1, X, Y 多項式相加結果
Line 2, X, Y 多項式相減結果
Line 3, X, Y 多項式相乘結果
(從最高次方到 0次方的係數與次方)
Sample Input 1:X 的項數<Y的項數
5
2 3 0 1 -1
6
1 0 -1 4 -3 2
Sample Output 1:
1 5 2 4 2 3 4 2 -2 1 1 0
-1 5 2 4 4 3 -4 2 4 1 -3 0
2 9 3 8 -2 7 6 6 5 5 -6 4 11
3 -7 2 5 1 -2 0
Sample Input 2:X 的項數>Y的項數
6
1 0 -1 4 -3 2
2
1 1
Sample Output 2:
1 5 0 4 -1 3 4 2 -2 1 3 0
1 5 0 4 -1 3 4 2 -4 1 1 0
1 6 1 5 -1 4 3 3 1 2 -1 1 2 0
Sample Input 3:X 的項數=Y的項數
4
9 -8 3 -2
4
11 3 -4 2
Sample Output 3:
20 3 -5 2 -1 1 0 0
-2 3 -11 2 7 1 -4 0
99 6 -61 5 -27 4 37 3 -34 2
14 1 -4 0
Sample Input 4:
X + Y = 0
Sample Output 4:
5
1 2 3 4 5
5
-1 -2 -3 -4 -5
0 4 0 3 0 2 0 1 0 0
2 4 4 3 6 2 8 1 10 0
-1 8 -4 7 -10 6 -20 5 -35 4
-44 3 -46 2 -40 1 -25 0
Sample Input 5:X = Y
5
5 4 3 2 1
5
5 4 3 2 1
Sample Output 5:
10 4 8 3 6 2 4 1 2 0
0 4 0 3 0 2 0 1 0 0
25 8 40 7 46 6 44 5 35 4 20
3 10 2 4 1 1 0
仅供参考：
//链表实现一元多项式的加法减法乘法
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
float coef; //系数
int expn; //指数
struct node *next;
} PolyNode;
typedef PolyNode* Polynomial;
Polynomial createPolynomial() { //创建多项式
PolyNode *p, *q, *head = (PolyNode *)malloc(sizeof(PolyNode));
head->next = NULL;
float coef;
int expn;
printf("输入该多项式每一项的系数和指数，每项一行，输入0 0结束！\n");
while (1) {
scanf("%f %d", &coef, &expn);
if (0.0==coef && 0==expn) break;
if (head->next) {
p = head;
while (p->next && expn < p->next->expn) p = p->next;
if (p->next) {
if (expn == p->next->expn) { //有相同指数的直接把系数加到原多项式
p->next->coef += coef;
if (-0.00001f < p->next->coef && p->next->coef < 0.00001f) { //若是相加后系数为0，则舍弃该节点
q = p->next;
p->next = q->next;
free(q);
}
} else {
q = (PolyNode*)malloc(sizeof(PolyNode));
q->coef = coef;
q->expn = expn;
q->next = p->next;
p->next = q;
}
} else {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = coef;
p->expn = expn;
p->next = NULL;
}
} else {
head->next = (PolyNode*)malloc(sizeof(PolyNode));
head->next->coef = coef;
head->next->expn = expn;
head->next->next = NULL;
}
}
return head;
}
Polynomial polyAdd(Polynomial poly1, Polynomial poly2) { //多项式相加 poly1+poly2形成一个新的多项式
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //和多项式的头节点
poly->next = NULL;
PolyNode *p, *q, *r;
r = poly;
p = poly1->next;
q = poly2->next;
while (p&&q) {
if (p->expn > q->expn) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = p->coef;
r->expn = p->expn;
p = p->next;
} else if (p->expn < q->expn) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = q->coef;
r->expn = q->expn;
q = q->next;
} else {
float m = p->coef + q->coef;
if (!(-0.00001f <m && m < 0.00001f)) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = m;
r->expn = p->expn;
}
q = q->next;
p = p->next;
}
}
while (p) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = p->coef;
r->expn = p->expn;
p = p->next;
}
while (q) {
r->next = (PolyNode*)malloc(sizeof(PolyNode));
r = r->next;
r->coef = q->coef;
r->expn = q->expn;
q = q->next;
}
r->next = NULL;
return poly;
}
Polynomial polySubtract(Polynomial poly1, Polynomial poly2) { //多项式减法 poly1-poly2形成一个新的多项式
//把poly2的系数取相反数，形成一个新的多项式
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //构造头节点
PolyNode *p, *q;
p = poly;
q = poly2->next;
while (q) {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = -(q->coef); //系数取反
p->expn = q->expn;
q = q->next;
}
p->next = NULL;
Polynomial poly3 = polyAdd(poly1, poly); //利用加法
return poly3;
}
void add(Polynomial poly1, Polynomial poly2) { //把 poly2 加到 poly1 上
PolyNode *p, *q, *r;
r = poly1;
p = poly1->next; //指向第一个节点
q = poly2->next;
poly2->next = NULL;
while (p && q) {
if (p->expn > q->expn) {
r->next = p;
p = p->next;
r = r->next;
} else if (p->expn < q->expn) {
r->next = q;
q = q->next;
r = r->next;
} else {
PolyNode *t;
p->coef += q->coef;
if (!(-0.00001f < p->coef && p->coef < 0.00001f)) { //系数不为0
r->next = p;
r = r->next;
p = p->next;
} else {
t = p;
p = p->next;
free(t);
}
t = q;
q = q->next;
free(t);
}
}
if (p) r->next = p;
if (q) r->next = q;
}
void printPoly(Polynomial poly) { //打印多项式
if (poly && poly->next) {
PolyNode *p = poly->next; //p指向第一个节点
while (p->next) {
if (1!=p->expn) printf("%g X^%d", p->coef, p->expn);
else printf("%g X" , p->coef );
p = p->next;
if (p) {
if (p->coef > 0) printf(" +");
else printf(" ");
}
}
if (p->expn == 0)
printf("%g", p->coef); //打印常数项
else {
if (1!=p->expn) printf("%g X^%d", p->coef, p->expn);
else printf("%g X" , p->coef );
}
printf("\n");
} else {
printf("0\n");
}
}
Polynomial multiply(Polynomial poly, float coef, int expn) { //多项式与指定单项式相乘，该单项式为 coefx^expn
PolyNode *p, *q, *Poly = (PolyNode*)malloc(sizeof(PolyNode));
p = Poly;
q = poly->next;
while (q) {
p->next = (PolyNode*)malloc(sizeof(PolyNode));
p = p->next;
p->coef = (q->coef * coef);
p->expn = (q->expn + expn);
q = q->next;
}
p->next = NULL;
// printf("多项式");printPoly(poly);
// printf("乘");printf("%g X^%d\n",coef,expn);
// printPoly(Poly);
return Poly;
}
Polynomial polyMultiply(Polynomial poly1, Polynomial poly2) { //多项式相乘
Polynomial poly = (PolyNode*)malloc(sizeof(PolyNode)); //创建多项式和的头节点
poly->next = NULL;
PolyNode *p;
p = poly2->next;
while (p) {
add(poly, multiply(poly1, p->coef, p->expn));
// printf("子多项式");printPoly(poly);
p = p->next;
}
// printf("结果多项式");printPoly(poly);
return poly;
}
void freePoly(Polynomial poly) { //释放内存
if (poly && poly->next) {
PolyNode *p, *q;
p = poly;
while (p) {
q = p->next;
free(p);
p = q;
}
}
poly = NULL;
}
int main() {
printf("用链表实现多项式的加减乘法\n");
Polynomial poly1, poly2, poly3;
printf("创建多项式一\n");
poly1 = createPolynomial();
printf("创建多项式二\n");
poly2 = createPolynomial();
printf(" 多项式一：");printPoly(poly1);
printf(" 多项式二：");printPoly(poly2);
poly3 = polyAdd(poly1, poly2);
printf("两多项式相加，和为：");printPoly(poly3);
freePoly(poly3);
poly3 = polySubtract(poly1, poly2);
printf("两多项式相减，差为：");printPoly(poly3);
freePoly(poly3);
// printf(" 多项式一：");printPoly(poly1);
// printf(" 多项式二：");printPoly(poly2);
poly3 = polyMultiply(poly1, poly2);
printf("两多项式相乘，积为：");printPoly(poly3);
freePoly(poly3);
freePoly(poly2);
freePoly(poly1);
system("pause");
return 0;
}
//用链表实现多项式的加减乘法
//创建多项式一
//输入该多项式每一项的系数和指数，每项一行，输入0 0结束！
//4 9
//3 6
//2 5
//0 0
//创建多项式二
//输入该多项式每一项的系数和指数，每项一行，输入0 0结束！
//4 9
//3 6
//2 5
//0 0
// 多项式一：4 X^9 +3 X^6 +2 X^5
// 多项式二：4 X^9 +3 X^6 +2 X^5
//两多项式相加，和为：8 X^9 +6 X^6 +4 X^5
//两多项式相减，差为：0
//两多项式相乘，积为：16 X^18 +24 X^15 +16 X^14 +9 X^12 +12 X^11 +4 X^10
//请按任意键继续. . .
PS：问答VIP年卡 【限时加赠：IT技术图书免费领】，了解详情>>> https://vip.csdn.net/askvip?utm_source=1146287632