#include<stdio.h>
#include<stdlib.h>
#include<math.h>

typedef struct{
float coef;
int expn;
}DataType;

typedef struct node{
DataType data;
struct node *next;
}ListNode;

typedef ListNode * LinkList;

int LocateNode(LinkList L,DataType e){
ListNode *p=L->next;
while(p&&e.expn<p->data.expn)
p=p->next;
if(p==NULL||e.expn!=p->data.expn)
return 0;
else
return 1;
}

void InsertNode(LinkList L,DataType e){
ListNode *s,*p;
p=L;
while(p->next&&e.expn<p->next->data.expn)
p=p->next;
s=(ListNode *)malloc(sizeof(ListNode));
s->data.coef=e.coef;
s->data.expn=e.expn;
s->next=p->next;
p->next=s;
}

ListNode *CreatPolyn(LinkList L,int n){
LinkList pa;
int i;
DataType e;
pa=(ListNode *)malloc(sizeof(ListNode));
pa->next=NULL;
for(i=1;i<=n;i++){
printf("请输入第%d项指数和系数：\n",i);
scanf("%f%d",&e.coef,&e.expn);
if(!LocateNode(pa,e))
InsertNode(pa,e);
}
L=pa;
return L;
}

void printfList(LinkList L){
ListNode *p;
p=L->next;
while(p){
printf("%c %6.2fx^%d",(p->data.coef>0?'+':' '),p->data.coef,p->data.expn);
p=p->next;
}
printf("\n");
}

ListNode *AddPolyn(LinkList La,LinkList Lb){
ListNode *pa,*pb,*pc,*s;
LinkList Lc;
float sum;
pa=La->next;
pb=Lb->next;
Lc=pc=La;
while(pa&&pb){
if(pa->data.expn>pb->data.expn){
pc->next=pa;
pc=pa;
pa=pa->next;
}
else if(pa->data.expn<pb->data.expn){
pc->next=pb;
pc=pb;
pb=pb->next;
}
else{
sum=pa->data.coef+pb->data.coef;
if(fabs(sum)>1e-6){
pa->data.coef=sum;
pc->next=pa;
pc=pa;
pa=pa->next;
s=pb;
pb=pb->next;
free(s);
}
else{
s=pa;
pa=pa->next;
free(s);
s=pb;
pb=pb->next;
free(s);
}
}
}
pc->next=pa?pa:pb;
free(Lb);
return Lc;
}

ListNode *CreatPolyn1(LinkList L,LinkList p){
LinkList pa;
DataType e;
pa=(ListNode *)malloc(sizeof(ListNode));
pa->next=NULL;
while(L->next){
e.coef=L->next->data.coef*p->data.coef;
e.expn=L->next->data.expn+p->data.expn;
if(!LocateNode(pa,e))
InsertNode(pa,e);
L=L->next;
}
L=pa;
return L;
}

ListNode *MultiplyPolyn(LinkList La1,LinkList Lb1){
LinkList pa,pc,s,p;
pa=La1;
p=Lb1->next;
pc=(ListNode *)malloc(sizeof(ListNode));
pc->next=NULL;
while(p){
s=CreatPolyn1(pa,p);
pc=AddPolyn(pc,s);
p=p->next;
}
s=pc;
return s;
}

void main(){
LinkList La,Lb,Lc;
int n,k;
printf("输入第一个多项式的项数：");
scanf("%d",&n);
printf("输入第一个多项式的每一项的系数，指数：\n");
La=CreatPolyn(La,n);
printf("第一个多项式为：");
printfList(La);
printf("输入第二个多项式的项数：");
scanf("%d",&n);
printf("输入第二个多项式的每一项的系数，指数：\n");
Lb=CreatPolyn(Lb,n);
printf("第二个多项式为：");
printfList(Lb);
printf("输入1做加法，输入2做乘法：");
scanf("%d",&k