#include<stdio.h>
#include<stdlib.h>
typedef struct Node{
	double coef;
	int expn;
	Node *next;
}*Sqlist;

void Createlist(Sqlist &ha,int n)
{
	double x;
	int y;
    ha=(Sqlist)malloc(sizeof(Node));
	ha->next=NULL;
	Sqlist pa=ha;
	printf("请输入多项式的系数和指数:");
	while(n){
		scanf("%lf%d",&x,&y);
		Sqlist p=(Sqlist)malloc(sizeof(Node));
		p->coef=x;
		p->expn=y;
		pa->next=p;
		pa=p;
		pa->next=NULL;
		n--;
	}
}
void showlist(Sqlist p)
{
    p=p->next;
    printf("p=");
	while(p)
	{
	    if(p->next)
		printf("%.1lf*X^%d+",p->coef,p->expn);
		else
            printf("%.1lf*X^%d",p->coef,p->expn);
        p=p->next;
    }
    printf("\n");
}
Sqlist add(Sqlist ha,Sqlist hb)
{
		int t=0;
        Sqlist pa=ha->next,pb=hb->next,pc;
        Sqlist hc=(Sqlist)malloc(sizeof(struct Node));
        hc->next=NULL;
        pc=hc;
		while(pa!=NULL&&pb!=NULL)
		{
			if(pa->expn==pb->expn)
			{
				t=pa->coef+pb->coef;
				if(t)
				{
					Sqlist p=(Sqlist)malloc(sizeof(struct Node));
                    p->coef=t;
	            	p->expn=pb->expn;
					pc->next=p;
					pc=p;
                    pc->next=NULL;
					pa=pa->next;
					pb=pb->next;
				}
				else if(pa->expn!=pb->expn)
				{
					pa=pa->next;
					pa=pb->next;

				}
			}
				else if(pa->expn<pb->expn)
				{
                Sqlist p=(Sqlist)malloc(sizeof(struct Node));
                        p->coef=pa->coef;
	            	    p->expn=pa->expn;
				     	pc->next=p;
					    pc=p;
                        pc->next=NULL;
					    pa=pa->next;

				}
                else if(pa->expn>pb->expn)
					{
						Sqlist p=(Sqlist)malloc(sizeof(struct Node));
                        p->coef=pb->coef;
	            	    p->expn=pb->expn;
				     	pc->next=p;
					    pc=p;
                        pc->next=NULL;
					    pb=pb->next;

					}
			}
			while(pb!=NULL)
			{

                        Sqlist p=(Sqlist)malloc(sizeof(struct Node));
                        p->coef=pb->coef;
	            	    p->expn=pb->expn;
				     	pc->next=p;
					    pc=p;
                        pc->next=NULL;
					    pb=pb->next;

			}
			while(pa!=NULL)
			{

			     Sqlist p=(Sqlist)malloc(sizeof(struct Node));
                        p->coef=pa->coef;
	            	    p->expn=pa->expn;
				     	pc->next=p;
					    pc=p;
                        pc->next=NULL;
					    pa=pa->next;
			}
			return hc;
		}

void paixu(Sqlist &head,int n)
{
	int i,j;
	Sqlist p1=head->next,p2=p1,temp=(Sqlist)malloc(sizeof(struct Node));
    printf("排序结果：");
	for(i=0;i<n-1;i++,p1=p1->next)
		for(p2=p1->next,j=i;j<n-1;j++,p2=p2->next)
			if(p1->expn>p2->expn)
			{
			    temp->coef=p2->coef;
			    temp->expn=p2->expn;
			    p2->coef=p1->coef;
			    p2->expn=p1->expn;
			    p1->coef=temp->coef;
			    p1->expn=temp->expn;
			}

}

int main()
{
	Sqlist ha,hb,hc;
	int i,j;
	printf("请输入第一个二项式的项数：");
	scanf("%d",&i);
	Createlist(ha,i);
	paixu(ha,i);
	showlist(ha);

	printf("请输入第一个二项式的项数：");
	scanf("%d",&j);
	Createlist(hb,j);
	paixu(hb,j);
	showlist(hb);


	hc=add(ha,hb);
	printf("合并后的二项式：");
	showlist(hc);
}