#include <stdlib.h>
typedef struct node {
int coefficient, power
struct node* next
}term
term* new_term(int coefficient, int power) {
term* t = (term*)malloc(sizeof(term))
t->next = NULL
t->coefficient = coefficient
t->power = power
return t
}
void free_term(term* t) {
free(t)
}
typedef struct list {
term head
}polynomial
void init_polynomial(polynomial* p) {
p->head.next = NULL
}
void clear_polynomial(polynomial* p) {
term* t = p->head.next
term* del
while (t != NULL) {
del = t
t = t->next
free_term(del)
}
p->head.next = NULL
}
void insert_polynomial(polynomial* p, term* t) {
t->next = p->head.next
p->head.next = t
}
void sort(polynomial* p) {
term* t
term* next
int finish = 0, temp
while (!finish) {
finish = 1
t = p->head.next
while (t != NULL) {
next = t->next
if (next != NULL) {
if (t->power < next->power) {
temp = t->coefficient
t->coefficient = next->coefficient
next->coefficient = temp
temp = t->power
t->power = next->power
next->power = temp
finish = 0
}
}
t = next
}
}
}
void combine(polynomial* p) {
term* t = p->head.next
term* next
while (t != NULL) {
next = t->next
if (next != NULL && next->power == t->power) {
t->coefficient += next->coefficient
t->next = next->next
free_term(next)
}
else {
t = next
}
}
}
void multiply(polynomial* p1, polynomial* p2, polynomial* p3) {
term* t1 = p1->head.next
term* t2
clear_polynomial(p3)
init_polynomial(p3)
while (t1 != NULL) {
t2 = p2->head.next
while (t2 != NULL) {
insert_polynomial(p3, new_term(t1->coefficient*t2->coefficient, t1->power + t2->power))
t2 = t2->next
}
t1 = t1->next
}
sort(p3)
combine(p3)
}
void input(polynomial* p) {
int coef, power
char c
init_polynomial(p)
while (true) {
scanf("%d%d", &coef, &power)
insert_polynomial(p, new_term(coef, power))
c = getchar()
if (c == '\n') break
}
sort(p)
combine(p)
}
void output(polynomial* p) {
term* t = p->head.next
while (t != NULL) {
printf("%d %d ", t->coefficient, t->power)
t = t->next
}
}
int main() {
int i
polynomial p[3]
for (i = 0 i < 3 i++) {
init_polynomial(&p[i])
}
for (i = 0 i < 2 i++) {
input(&p[i])
}
multiply(&p[0], &p[1], &p[2])
output(&p[2])
}
这个是母函数的知识,这一块我没怎么看,楼主可以自己百度一下。大概的意思就是: a[x]:x表示指数,a[x]存系数。如 3x^2+4x+5:可表示为:a[2]=3,a[1]=4,a[0]=5. 多项式加减就是a[x]相加减。多项式相乘就是x相加。也就是下标的运算按题目要求应该是(1+X)*(1+X)=X2+1吧可以用单链表表示多项的指数,比如1+X可以表示为0,1
X2+1可以表示为2,0,Xn+X(n-1)+...+1即n,n-1,.....0
所有的指数建议按大小排序,可以在单链表插入时进行。
加法,可以新建一个链表C做为结果,把链表A的内容复制到C,然后把另一个链表B中的每一项插入C,如果要插入的项已存在,则不插入并且删除这个结点。
乘法,新建一个链表C作为结果,要用2层循环遍历A和B中的每一项,对AB中的每个项都要算个加法,把和插入C中,如果这个和已存在,则不插入并且删除这个结点。