#include <stdio.h>
#include <stdlib.h>
#define MAX 10
typedef struct LNode
{
	int data;
	int exp;
	struct LNode *next;
}SqList;
void Sort(SqList *&l)
{
	SqList *p=l->next,*q,*r;
	if(p!=NULL)
	{
		r=p->next;
		p->next=NULL;
		p=r;
		while(p!=NULL)
		{
			r=p->next;
			q=l;
			while(q->next!=NULL&&q->next->exp<p->exp)
				q=q->next;
			p->next=q->next;
			q->next=p;
			p=r;
		}
	}
	 p=l->next;
	while(p!=NULL)
	{
		if(p==l->next)
		   printf("%dx^%d",p->data,p->exp);
		else if(p->data>0)
			printf("+%dx^%d",p->data,p->exp);
		else
			printf("%dx^%d",p->data,p->exp);
		p=p->next;
	}
	printf("\n");
}
void Bulid(SqList *&l,int x)
{
     SqList *p,*q;
	 int n=0,i;
	 l=(SqList*)malloc(sizeof(SqList));
	 l->next=NULL;
	 p=l;
     printf("請(qǐng)輸入第%d個(gè)多項(xiàng)式\n",x);
	 printf("請(qǐng)輸入多項(xiàng)式的項(xiàng)數(shù)：");
	 scanf("%d",&n);
	 printf("請(qǐng)輸入多項(xiàng)式：\n");
	 for(i=0;i<n;i++)
     {
        q=(SqList*)malloc(sizeof(SqList));
		scanf("%d %d",&q->data,&q->exp);
        q->next=p->next;
		p->next=q;
		p=q;
	 }
	 p=l->next;
	while(p!=NULL)
	{
		if(p==l->next)
		   printf("%dx^%d",p->data,p->exp);
		else if(p->data>0)
			printf("+%dx^%d",p->data,p->exp);
		else
			printf("%dx^%d",p->data,p->exp);
		p=p->next;
	}
	printf("\n");
	 Sort(l);
}

void Add(SqList *head1,SqList *head2,SqList *&head)
{
	SqList *p,*q,*r,*s;
	head=(SqList*)malloc(sizeof(SqList));
	head->next=NULL;
	p=head1->next;
	q=head2->next;
	r=head;
	while(p!=NULL&&q!=NULL)
    {   
		if(p->exp<q->exp)
		{
			s=(SqList*)malloc(sizeof(SqList));
			s->exp=p->exp;
			s->data=p->data;
        	p=p->next;
		    r->next=s;
			r=s;
        }
		else if(p->exp==q->exp)
		{
			if(p->data+q->data!=0)
			{
				s=(SqList*)malloc(sizeof(SqList));
				s->exp=p->exp;
			    s->data=p->data+q->data;
                r->next=s;
			    r=s;
			}
            p=p->next;
			q=q->next;
		}
		else 
		{
			s=(SqList*)malloc(sizeof(SqList));
			s->exp=q->exp;
			s->data=q->data;
			q=q->next;
		    r->next=s;
			r=s;
		}

	}
	if(p==NULL)
		while(q!=NULL)
		{
			s=(SqList*)malloc(sizeof(SqList));
			s->data=q->data;
			s->exp=q->exp;
			s->next=r->next;
			r->next=s;
			r=s;
			q=q->next;

		}
    else
        	while(p!=NULL)
		{
			s=(SqList*)malloc(sizeof(SqList));
			s->data=p->data;
			s->exp=p->exp;
			s->next=r->next;
			r->next=s;
			r=s;
			p=p->next;

		}
			r->next=NULL;
}
void main()
{
	SqList *head1,*head2,*head;
	SqList *p;
	Bulid(head1,1);
	Bulid(head2,2);
	Add(head1,head2,head);
	p=head1->next;
	printf("第一個(gè)多項(xiàng)式為:\n");
	while(p!=NULL)
	{
		if(p==head1->next)
		   printf("%dx^%d",p->data,p->exp);
		else if(p->data>0)
			printf("+%dx^%d",p->data,p->exp);
		else
			printf("%dx^%d",p->data,p->exp);
		p=p->next;
	}
	printf("\n");
	p=head2->next;
    printf("第二個(gè)多項(xiàng)式為:\n");
	while(p!=NULL)
	{
		if(p==head2->next)
		   printf("%dx^%d",p->data,p->exp);
		else if(p->data>0)
			printf("+%dx^%d",p->data,p->exp);
		else
			printf("%dx^%d",p->data,p->exp);
		p=p->next;
	}
	printf("\n");
	p=head->next;
	printf("結(jié)果為:\n");
	while(p!=NULL)
	{
		if(p==head->next)
		   printf("%dx^%d",p->data,p->exp);
		else if(p->data>0)
			printf("+%dx^%d",p->data,p->exp);
		else
			printf("%dx^%d",p->data,p->exp);
		p=p->next;
	}
	printf("\n");

}