#include<iostream.h>
struct node
{
	int coef;//系數(shù)

	int expn;//指數(shù)
	node*next;
};
typedef node*pointer;

node* create()
{
	int c,e;
	node*head,
        *ps,
		*pend;
	head=new node;
	ps=head;
	head->next=NULL;
	cout<<"輸入多項式的系數(shù)和指數(shù)：\n";
	cin>>c>>e;
	while(c!=0)
	{
		pend=new node;
		pend->coef=c;
		pend->expn=e;
		ps->next=pend;
	    ps=pend;
	    pend->next=NULL;
		cin>>c>>e;
	}
    pend->next=NULL;

	return head;
	//delete ps;
}
void attach(int c,int e,pointer&p)
{
	p->next=new node;
	p=p->next;
	p->coef=c;
	p->expn=e;
}
void addpolyn(pointer ha,pointer hb,pointer&hc)
{
	pointer pa,pb,pc;
	int x;
	pc=new node;
	pa=ha->next;
	pb=hb->next;
	pc=hc;
	while(pa&&pb)
	{
		if(pa->expn==pb->expn)
		{
			x=pa->coef+pb->coef;
			if(x)attach(x,pa->expn,pc);
			pa=pa->next;
			pb=pb->next;
		}
		else if(pa->expn>pb->expn)
		{
			attach(pb->coef,pb->expn,pc);
			pb=pb->next;
		}
		else
		{
			attach(pa->coef,pa->expn,pc);
			pa->next;
		}
	}
	while(pa)
	{
		attach(pa->coef,pa->expn,pc);
		pa=pa->next;
	}
	while(pb)
	{
		attach(pb->coef,pb->expn,pc);
		pb=pb->next;
	}
	pc->next=NULL;
	//delete pa,pb,pc;
}
void output(node*h)
{
	node*p;
	p=h->next;

	cout<<p->coef<<"*x^"<<p->expn<<"+";
	p=p->next;
	while(p!=NULL)
	{
		cout<<p->coef<<"*x^"<<p->expn<<"+";
		p=p->next;
	}
	//delete p;
}
void mutiply(node*ha,node*hb,node*&hc)
{
	node*pa,*pb,*pc;
	int x,y;
	pa=ha->next;
	pb=hb->next;	
	pc=new node; 
    pc=hc;
	while(pa!=NULL)
	{
		while(pb!=NULL)
		{		
	        x=pa->coef*pb->coef;
        	y=pa->expn+pb->expn;
			attach(x,y,pc);
			pb=pb->next;
		}
		pb=hb->next;
        pa=pa->next;
	//	delete pa,pb,pc;
	}
 pc->next=NULL;
}
void main()
{
	node*ha,*hb,*hc;
	ha=create();
	hb=create(); 
	cout<<"第一個多項式為:";
	output(ha);
	cout<<"第二個多項式為:";
    output(hb);  
    addpolyn(ha,hb,hc);
	cout<<"相加的多項式為:";
    output(hc);	
    mutiply(ha,hb,hc);
	cout<<"相乘的多項式為:";
	output(hc);
	 //delete ha,hb,hc;
}