#include
#include
using namespace std;
#define MAX 20            //多项式最多项数

typedef struct               //定义存放多项式的数组类型
{
	float coef;              //系数
	int exp;				 //指数
}PolyArray[MAX];

typedef struct pNode         //定义单链表结点类型
{
	float coef;
	int exp;
	struct pNode *next;
}PolyNode;

void DispPoly(PolyNode * L)   //输出多项式
{
	PolyNode *p=L->next;
	while(p!=NULL)
	{
		printf("%gX^%d",p->coef,p->exp);
		p=p->next;
	}
	printf("\n");
}

void CreateListR(PolyNode * &L,PolyArray a,int n)     //尾插法建表
{
	PolyNode *s,*r;
	int i;
	L=(PolyNode *)malloc(sizeof(PolyNode));           //创建头结点
	L->next=NULL;
	r=L;											  //r始终指向终端结点，开始时指向头结点
	for(i=0;icoef=a[i].coef;
		s->exp=a[i].exp;
		r->next=s;									  //将*s插入*r后
		r=s;
	}
	r->next=NULL;                                     //终端结点next域置为NULL
}

void Sort(PolyNode * &head)                           //按exp域递减排序
{
	PolyNode *p=head->next,*q,*r;
	if(p!=NULL)                                       //若原单链表中有一个或多个数据结点
	{
		r=p->next;                                    //r保存*p结点的后继结点的指针
		p->next=NULL;                                 //构造只含一个数据结点的有序表
	    p=r;
		while(p!=NULL)
		{
			r=p->next;                                 //r保存*p结点的后继结点的指针
			q=head;
			while(q->next!=NULL&&q->next->exp>p->exp)
				q=q->next;                            //在有序表中找插入*p的前驱结点*q
			p->next=q->next;                          //将*p插入到*q之后
			q->next=p;
			p=r;
		}
	}
}

void Add(PolyNode *ha,PolyNode *hb,PolyNode *&hc)     //求两个有序集合的并
{
	PolyNode *pa=ha->next,*pb=hb->next,*s,*tc;
	float c;
	hc=(PolyNode *)malloc(sizeof(PolyNode));          //创建头结点
	tc=hc; 
	while(pa!=NULL&&pb!=NULL)
	{
		if(pa->exp >pb->exp)
		{
			s=(PolyNode *)malloc(sizeof(PolyNode));   //复制结点
			s->exp=pa->exp;
			s->coef=pa->coef;
			tc->next=s;
			tc=s;
			pa=pa->next;
		}
		else if(pa->exp exp)
		{
			s=(PolyNode *)malloc(sizeof(PolyNode));  //复制结点
			s->exp=pb->exp;
			s->coef=pb->coef;
			tc->next=s;
			tc=s;
			pb=pb->next;
		}
		else                                       //pa->exp==pb->exp
		{
			c=pa->coef+pb->coef;
			if(c!=0)                               //系数之和不为0时创建新结点
			{
				s=(PolyNode *)malloc(sizeof(PolyNode)); 
				s->exp=pa->exp;
				s->coef=c;
				tc->next=s;
				tc=s;
			}
			pa=pa->next;
			pb=pb->next;
		}
	}
	if(pb!=NULL)
		pa=pb;									    //复制余下的结点
	while(pa!=NULL)
	{
		s=(PolyNode *)malloc(sizeof(PolyNode)); 
		s->exp=pa->exp;
		s->coef=pa->coef;
		tc->next=s;
		tc=s;
		pa=pa->next;
	}
	tc->next=NULL;
}

void main()
{
	PolyNode *ha,*hb,*hc;
	PolyArray a={{1.2,0},{2.5,1},{3.2,3},{-2.5,5}};
	PolyArray b={{-1.2,0},{2.5,1},{3.2,3},{2.5,5},{5.4,10}};
	CreateListR(ha,a,4);
	CreateListR(hb,b,5);
	printf("原多项式A：");
	DispPoly(ha);
	printf("原多项式B：");
	DispPoly(hb);
	Sort(ha);
	Sort(hb);
	printf("排序后多项式A：");
	DispPoly(ha);
	printf("排序后多项式B：");
	DispPoly(hb);

	Add(ha,hb,hc);
	printf("多项式相加：");
	DispPoly(hc);

}