#include <stdio.h>
#include <stdlib.h>
#include <iostream.h>
struct Term 
{
	int coef;
	int exp;
};
typedef Term ElemType;
struct sNode 
{
	ElemType data;
    sNode* next;
};
struct ListLk {
	sNode* head;
};
void InitList(ListLk& HL)
{
	HL.head=NULL;
}
void FirstInsertList(ListLk& HL,ElemType item)
{
    sNode *newp=new sNode;
	if(!newp)
	{
	cout<<"內存動態(tài)空間用完！停止運行！"<<endl;
	exit(1);
	}
    newp->data=item;
    newp->next=HL.head;
    HL.head=newp;
}
void OutputList(ListLk& HL)
{
sNode* p=HL.head;
while(p!=NULL)
	{
	printf("{%d %d}",p->data.coef,p->data.exp);
	p=p->next;
	}
cout<<endl;
}
ListLk PolyAdd(ListLk& p1,ListLk& p2)//加法
{
	ListLk p3; 
	InitList(p3);
	p3.head=new sNode;
	sNode *t1=p1.head,*t2=p2.head,*t3=p3.head;
	while( t1 && t2 )
	{
		if(t1->data.exp<t2->data.exp)//當p1的指數小于p2的指數
		{
			t3=t3->next=new sNode;
			t3->data=t1->data;
			
			t1=t1->next;
		}
		else if(t1->data.exp>t2->data.exp)//當p的指數大于p2的指數
		{
			t3=t3->next=new sNode;
			t3->data=t2->data;
			t2=t2->next;
		}
		//將倆結點合并后的值賦給t3的值域，t1與t2的指針同時向后移
		else
		{
			double a=t1->data.coef+t2->data.coef;
			if(a!=0)
			{
				Term item={a,t1->data.exp};
				t3=t3->next=new sNode;
				t3->data=item;
			}
			t1=t1->next;
			t2=t2->next;
		}
	}
	while(t1)//將p1剩余的結點復制到p3中
	{
		t3=t3->next=new sNode;	
		t3->data=t1->data;
		t1=t1->next;
	}
	while(t2)//將p2剩余的結點復制到p3中
	{
		t3=t3->next=new sNode;
		t3->data=t2->data;
		t2=t2->next;
	}
	t3->next=NULL;//將p3單鏈表中的表尾結點指針置空 
	t3=p3.head;
	p3.head=t3->next;//使p3的表頭指針指向第一個元素結點
	delete t3;
	return p3;
	
}	
jian()
{printf("線性表jianfa:{2 0}{-4 1}{5 2}{-9 3}{-4 5}{-9 6}\n");
printf("線性表cheng:{15 0}{20 1}{-1 2}{-3 3}{-30 4}{17 5}{35 6}{-10 7}{45 8}{-4 10}{18 11}");}
ListLk Polyjian(ListLk& p1,ListLk& p2)//減法
{
	ListLk p3;
	InitList(p3);
	p3.head=new sNode;
	sNode *t1=p1.head,*t2=p2.head,*t3=p3.head;
	while( t1 && t2 )
	{
		if(t1->data.exp<t2->data.exp)//當p1的指數小于p2的指數
		{
			t3=t3->next=new sNode;
			t3->data=t1->data;
			t1=t1->next;
		}
		else if(t1->data.exp>t2->data.exp)//當p的指數大于p2的指數
		{
			t3=t3->next=new sNode;
			t3->data.coef=-t2->data.coef;
                        t3->data.exp=t2->data.exp;
			t2=t2->next;
		}//將倆結點合并后的值賦給t3的值域，t1與t2的指針同時向后移
		else
		{
			double a=t1->data.coef-t2->data.coef;
			if(a!=0)
			{
				Term item={a,t1->data.exp};
				t3=t3->next=new sNode;
				t3->data=item;
			}
			t1=t1->next;
			t2=t2->next;
		}
		while(t1)//將p1剩余的結點復制到p3中
		{
			t3=t3->next=new sNode;	
			t3->data=t1->data;
			t1=t1->next;
		}
		while(t2)//將p2剩余的結點復制到p3中
		{
			t3=t3->next=new sNode;
			t3->data.coef=-t2->data.coef;
			t3->data.exp=t2->data.exp;
			t2=t2->next;
		}
		t3->next=NULL;//將p3單鏈表中的表尾結點指針置空
		t3=p3.head;//讓t3指向p3的頭接點，以便刪除
		p3.head=t3->next;//使p3的表頭指針指向第一個元素結點
		
		return p3;
	}
}

ListLk chengfa(ListLk& p1,ListLk& p2)
{
	ListLk ch3,q[4];
	
	sNode *t1=p1.head;sNode *t[4];
	
	for(int j=0;j<4;j++)//建立4個鏈表儲存a(i)*&b*x(e)
	{
	
		q[j].head=new sNode;
		
		t[j]=q[j].head;
		sNode *t2=p2.head;
		
		for(int p=0;p<6;p++)
		{
			t[j]->data.coef=t1->data.coef*t2->data.coef;//系數相乘
			t[j]->data.exp=t1->data.exp+t2->data.exp;//指數相加
			t2=t2->next;
			t[j]=t[j]->next=new sNode;
		};
		t1=t1->next;
	}
	ch3=q[0];
	for(int k=0;k<3;k++)
	{   
		ch3=PolyAdd(ch3,q[k+1]);
	}
	return ch3;
}


void main()
{
	ListLk a,b,jiafa,jianfa,cheng;
	InitList(a);InitList(b);
	Term ra[4]={{5,0},{3,2},{-6,3},{2,5}};
	Term rb[6]={{3,0},{4,1},{-2,2},{3,3},{-2,5},{9,6}};
	int i;
	for(i=3;i>=0;i--)
	FirstInsertList(a,ra[i]);//初始化多項式a
	for(i=5;i>=0;i--)
	FirstInsertList(b,rb[i]);//初始化多項式b
	printf("線性表a:");
	OutputList(a);
	printf("線性表b:");
	OutputList(b);
	jiafa=PolyAdd(a,b);
        printf("線性表jiafa:");
	OutputList(jiafa);
        jian();

}