#include <stdio.h>
#include <stdlib.h>
typedef struct PolyNode *Polynomial;
struct PolyNode {
int coef;
int expon;
Polynomial link;
};
void Attach(int c,int e,Polynomial *pRear) {
if(c==0){return;}
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, t, Rear;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
Rear = P;
scanf("%d",&N);
while (N--) {
scanf("%d %d", &c, &e);
if( c != 0) Attach(c,e,&Rear);
}
t = P;
P = P->link;
free(t);
return P;
}
int Compare(int a,int b) {
if (a>b) {
return 1;
}else if (a<b) {
return -1;
}
return 0;
}
Polynomial Add(Polynomial P1, Polynomial P2) {
Polynomial T1, T2, P, rear, tempP;
int sum;
if (!P1 && !P2) { return NULL; }
T1 = P1;
T2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
rear = P;
while (T1 && T2) {
switch (Compare(T1->expon, T2->expon)) {
case 1:
Attach(T1->coef, T1->expon, &rear);
T1 = T1->link;
break;
case -1:
Attach(T2->coef, T2->expon, &rear);
T2 = T2->link;
break;
case 0:
sum = T1->coef + T2->coef;
if (sum) Attach(sum, T1->expon, &rear);
T1 = T1->link;
T2 = T2->link;
break;
}
}
for (; T1; T1 = T1->link) Attach(T1->coef, T1->expon, &rear);
for (; T2; T2 = T2->link) Attach(T2->coef, T2->expon, &rear);
rear->link = NULL;
tempP = P;
P = P->link;
free(tempP);
return P;
}
Polynomial Mult(Polynomial P1,Polynomial P2) {
Polynomial P, T1, T2, Rear,tempP,t;
int c, e;
if (!P1 || !P2) { return NULL; }
T1 = P1;
T2 = P2;
P = (Polynomial)malloc(sizeof(struct PolyNode));
P->link = NULL;
Rear = P;
while (T2) {
Attach(T1->coef*T2->coef, T1->expon + T2->expon, &Rear);
T2 = T2->link;
}
T1 = T1->link;
while (T1) {
T2 = P2;
Rear = P;
while (T2) {
c = T1->coef * T2->coef;
e = T1->expon + T2->expon;
while (Rear->link && Rear->link->expon > e) {
Rear = Rear->link;
}
if (Rear->link && Rear->link->expon == e) {
if (Rear->link->coef + c) { //!=0时
Rear->link->coef += c;
}
else {
tempP = Rear->link;
Rear->link = tempP->link;
free(tempP);
}
}
else {
t = (Polynomial)malloc(sizeof(struct PolyNode));
t->coef = c;
t->expon = e;
t->link = Rear->link;
Rear->link = t;
Rear = Rear->link;
}
T2 = T2->link;
}
T1 = T1->link;
}
tempP = P;
P = P -> link;
free(tempP);
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;
}