#include <stdio.h>
#include <stdlib.h>
typedef struct PolyNode* PolyNomial;
struct PolyNode{
int coef;//conficient 系数
int expon;//exponenmial 指数
PolyNomial link;
};
void Attach(int c,int e,PolyNomial *pRear){
//链接到数组里
PolyNomial P;
P=(PolyNomial)malloc(sizeof(struct PolyNode));
P->coef=c;
P->expon=e;
P->link=NULL;
(*pRear)->link=P;
*pRear=P;
}
PolyNomial ReadPoly( ){
int n,c,e;
PolyNomial P,Rear;
P=(PolyNomial)malloc(sizeof(struct PolyNode));
P->link=NULL;
Rear=P;
scanf("%d",&n);
while(n--){
scanf("%d %d",&c,&e);
Attach(c,e,&Rear);
}
Rear=P;
P=P->link;//让数组的头结点也存储东西
free(Rear);
return P;
}
PolyNomial Add(PolyNomial P1,PolyNomial P2){
PolyNomial P,Rear,t1,t2;
P=(PolyNomial)malloc(sizeof(struct PolyNode));
P->link=NULL;
Rear=P;
t1=P1;
t2=P2;
while(t1&&t2){
if(t1->expon==t2->expon){
if(t1->coef+t2->coef){
Attach(t1->coef+t2->coef,t1->expon,&Rear);
}
t1=t1->link;
t2=t2->link;
}else if(t1->expon>t2->expon){
Attach(t1->coef,t2->expon,&Rear);
t1=t1->link;
}else{
Attach(t2->coef,t2->expon,&Rear);
t2=t2->link;
}
}
while(t1){
Attach(t1->coef,t1->expon,&Rear);
t1=t1->link;
}
while(t2){
Attach(t2->coef,t2->expon,&Rear);
}
Rear=P;
P=P->link;
free(Rear);
return P;
}
PolyNomial Mult(PolyNomial P1,PolyNomial P2){
PolyNomial t1,t2,P,PRear,QRear;
P=(PolyNomial)malloc(sizeof(struct PolyNode));
P->link=NULL;
PRear=P;
t1=P1;
t2=P2;
if(!P1||!P2){
return NULL;
}
while(t2){
//先让t1的第一项乘以t2,以P为主式
Attach(t1->coef*t2->coef,t1->expon+t2->expon,&PRear);
t2=t2->link;
}
t1=t1->link;
PRear=P;
P=P->link;//让P可以进行加法
free(PRear);
while(t1){
PolyNomial Q;//重新定义一个Q,让Q记录每次t1中的一项和t2中相乘后得到的多项式
t2=P2;
Q=(PolyNomial)malloc(sizeof(struct PolyNode));
Q->link=NULL;
QRear=Q;
while(t2){
Attach(t1->coef*t2->coef,t1->expon+t2->expon,&QRear);
t2=t2->link;
}
QRear=Q;
Q=Q->link;
free(QRear);
P=Add(P,Q);
t1=t1->link;
}
return P;
}
void PrintPoly(PolyNomial P){
int flag=0;
if(!P){
printf("0 0\n");
return ;
}
while(P){
if(!flag){
flag=1;
}else{
printf(" ");
}
printf("%d %d",P->coef,P->expon);
P=P->link;
}
printf("\n");
}
int main(){
PolyNomial P1,P2,PP,PS;
P1=ReadPoly();
P2=ReadPoly();
PP=Mult(P1,P2);
PrintPoly(PP);
PS=Add(P1,P2);
PrintPoly(PS);
return 0;
}
input
1 1 1
1 1 1
outout
1 2
2 1
(基本多项式只有1的都可以)
(加法的结果也基本可以)
input
4 3 4 -5 2 6 1 -2 0
3 5 20 -7 4 3 1
然后结果就出不来了