#include<iostream.h>
struct celltype{
	double element;
    double element1;
	celltype *next;
};
typedef celltype *list;
typedef celltype* position;
void insert(double x,double x1,position p,list &l);//插入結點
void dele(position p,list &l);//刪除結點
void and_sub(position p,list &l,position p1,list &l1,int i);//加減操作,i為1為加
void mul1(list &l,list &l1,list &l3);//乘法操作
void dele_l(list &l);//刪除鏈至頭結點
void copy_l(list &l1,list l,double n,double m);//復制鏈,且第一個數乘n,第二個數加m
void div1(list &l,list &l1,list &l2,list &l3);//除法操作
//此程序輸入以 0 0結尾
void main()
{
	
	double num1,num2;
    char x;

    list l,l1,l2,l3;
    position p,p1,p2;

	l=new celltype;
	l->next=NULL;
	p=l;
	l1=new celltype;
	l1->next=NULL;
	p1=l1;
    l2=new celltype;
    l2->next=NULL;
    l3=new celltype;
    l3->next=NULL;
	p2=l2;
    cout<<"輸入多項式,降冪排列,以0 0結尾\n";//輸入
	do{
         cin>>num1;  
	     cin>>num2;
		 if(num1!=0)
		 {
             insert(num1,num2,p,l);
	         p=p->next;
		 }
	}while(num1!=0||num2!=0);
    p=l;
    cout<<"輸入第二個多項式,降冪排列,以0 0結尾\n";
    do{
	     cin>>num1; 
	     cin>>num2;
		 if(num1!=0)
		 {
              insert(num1,num2,p1,l1);
	          p1=p1->next;
		 }
	}while(num1!=0||num2!=0);
	p1=l1;
    cout<<"輸入運算符(+ - * /)\n";
    cin>>x;
	switch (x)//運算
	{
	case'+':
      and_sub(p,l,p1,l1,1);
			break;
    case'-':
       and_sub(p,l,p1,l1,0); 
			break;
    case'*':
         mul1(l,l1,l3);   
			break;
    case'/':
		if(l1->next!=NULL)
         div1(l,l1,l3,l2);
			break;
	
	}
	p=l;
	if(x=='/')//輸出
	{  
		if(p2->next==NULL)
		{
             cout<<"除數為零,錯誤:\n";
		}
		else 
		{
			cout<<"商為:\n";
	        while(p2->next!=NULL)
			{
                cout<<p2->next->element<<' ';
                cout<<p2->next->element1<<'\n';
                p2=p2->next;
			}
            cout<<"余數為:\n";
	        if(p->next==NULL)
	        	cout<<"0\n";
            while(p->next!=NULL)
			{
                cout<<p->next->element<<' ';
                cout<<p->next->element1<<'\n';
                p=p->next;
			}
		}
    
	}
	else
	{
	     cout<<"結果為:\n";
	     if(p->next==NULL)
		      cout<<"0\n";
         while(p->next!=NULL)
		 {
              cout<<p->next->element<<' ';
              cout<<p->next->element1<<'\n';
              p=p->next;
		 }
	}
    dele_l(l);
	delete(l); 
	dele_l(l1);
	delete(l1); 
	dele_l(l2);
	delete(l2); 
	dele_l(l3);
	delete(l3); 
}
void insert(double x,double x1,position p,list &l)
{
	position q;
	q=new celltype;
	q->element=x;
    q->element1=x1;
	q->next=p->next;
	p->next=q;

}
void dele(position p,list &l)
{
    position q;
	if(p->next!=NULL)
	{
		q=p->next;
		p->next=q->next;
		delete q;
	}
}
void and_sub(position p,list &l,position p1,list &l1,int i)
{
	double n,num,num1;
     
     while(p1->next!=NULL)
		{   if(i==0)
		        num1=0-p1->next->element;
	       else
                num1=p1->next->element;
		    
			if(p->next!=NULL)
			{
                 n=p->next->element1-p1->next->element1;
			     if(n==0)
				 {
			           num	= p->next->element+num1;
				      if(num==0)
				     	   dele(p,l);
				      else
					  {
					       p->next->element=num;
					       p=p->next;
					  }
				      p1=p1->next;
				 }
			     else if(n>0)
				 {
				      p=p->next;	
				 }
			     else
				 {   
				         insert(num1,p1->next->element1,p,l);
	                  p1=p1->next;
				 }
				
			} 
			else
			{
                 insert(num1,p1->next->element1,p,l);
	                  p1=p1->next;
			}
		}
}
void mul1(list &l,list &l1,list &l2)
{
	double num,num1;
    list l3;
    position p,p1,p2,p3;

	p=l;
	p1=l1;
	l3=new celltype;
	l3->next=NULL;
    p2=l2;
	p3=l3;
	while(p1->next!=NULL)
	{
		while(p->next!=NULL)
		{
             num=p1->next->element*p->next->element;
             num1=p1->next->element1+p->next->element1;
			 insert(num,num1,p3,l3);
			 p3=p3->next;
			 p=p->next;
		}
		p2=l2;
		p3=l3;
        and_sub(p2,l2,p3,l3,1);
		p1=p1->next;
		p=l;
        dele_l(l3);
	}   
    dele_l(l);    
    l=l2;
	l2=p;
    dele_l(l3);
	delete(l3);
}
void div1(list &l,list &l1,list &l3,list &l2)
{
	 position p,p1,p2,p3;
     p=l;
	 p1=l1;
	 p2=l2;
	 p3=l3;
     double n,m;
     while(p->next!=0&&(m=p->next->element1-p1->next->element1)>=0)
	 {
		 n=p->next->element/p1->next->element;
		 copy_l(l3,l1,n,m);
		 and_sub(p,l,p3,l3,0);
		 insert(n,m,p2,l2);
		 p2=p2->next;
		 dele_l(l3);
	 }
}
void dele_l(list &l)
{
    position p;
	p=l;
    while(p->next!=NULL)
	{
		dele(p,l);
	}
    
}
void copy_l(list &l1,list l,double n,double m)
{
    position p,p1;
	p=l;
	p1=l1;
    while(p->next!=NULL)
	{
       insert(n*p->next->element,m+p->next->element1,p1,l1);
	   p1=p1->next;
	   p=p->next;
	}
}