#include<stdio.h>
#include<stdlib.h>
#include<math.h>
//多项式链表结点类型定义
typedef struct {
	float coef;  //系数
	int expn;  //指数
}DataType;
typedef struct node {
	DataType data;
	struct node *next;
}ListNode,*LinkList;
int q;  //定义一全局量
int LocateNode(LinkList L,DataType e)
{ //查找定位算法
	ListNode *p=L->next;
	q=0;  //记录结点位置序号
	while(p&&e.expn<p->data.expn)
	{ p=p->next;
	q++;
	}
	//printf("%f,%d\n",e.coef,e.expn);
	if(p==NULL||e.expn!=p->data.expn)
		return 0; //查找失败
	else
		return 1;
}
//有序链表结点的插入
LinkList InsertNode(LinkList L,DataType e)
{  //在有序表中插入一个结点，仍保持表的有序性
	ListNode *s,*p;
	int i=0;p=L;
	while(p->next&&i<q)
	{ p=p->next;
	i++;
	}//查找插入位置
	s=(ListNode *)malloc(sizeof(ListNode));
	s->data.coef=e.coef;
	s->data.expn=e.expn;
	s->next=p->next;
	p->next=s;
	return L;
}
//多项式链表的建立
LinkList CreatPolyn(int n)
{
	LinkList pa;
	int i;
	DataType e;
	pa=(ListNode *)malloc(sizeof(ListNode));//生成链表头结点
	pa->next=NULL;
	for(i=1;i<=n;i++)
	{
		scanf("%f,%d",&e.coef,&e.expn);
		if(!LocateNode(pa,e))  //当前链表中不存在该指数项
			pa=InsertNode(pa,e);
	}
	return pa;
}
//多项式链表的输出
void printList(LinkList L)
{
	ListNode *p;
	p=L->next;
	while(p)
	{
		printf("%c %fx^%d",(p->data.coef>0 ? "+" : " "),p->data.coef,p->data.expn);
		p=p->next;
	}
	printf("\n");
}
//多项式两遍的相加
LinkList AddPolyn(LinkList La,LinkList Lb)
{  //两个有序链表La和Lb表示多项式相加
	ListNode *pa,*pb,*pc,*s;
	LinkList Lc;
	float sum;
	pa=La->next;pb=Lb->next;  //pa和pb分别指向两个链表的开始结点
	Lc=pc=La;  //用La的头结点作为Lc的头结点
	while(pa&&pb){
		if(pa->data.expn>pb->data.expn){
			pc->next=pa;pc=pa;pa=pa->next;
		}
		else if(pa->data.expn<pb->data.expn)
		{ 
			pc->next=pb;pc=pb;pb=pb->next;
		}
		else {
			sum=pa->data.coef+pb->data.coef;
			if(fabs(sum)>1e-6){ //系数和不为零
				pa->data.coef=sum;
				pc->next=pa;pc=pa;pa=pa->next;
				s=pb;pb=pb->next;free(s);
			}
			else {
				s=pa;pa=pa->next;free(s);
				s=pb;pb=pb->next;free(s);
			}
		}
	}
	pc->next=pa?pa:pb;  //插入链表剩余部分
	free(Lb);   //释放Lb的头结点
	return Lc;
}
//多项式两遍的相加
LinkList SubPolyn(LinkList La,LinkList Lb)
{  //两个有序链表La和Lb表示多项式相加
	ListNode *pa,*pb,*pc,*s;
	LinkList Lc;
	float sum;
	pa=La->next;pb=Lb->next;  //pa和pb分别指向两个链表的开始结点
	Lc=pc=La;  //用La的头结点作为Lc的头结点
	while(pa&&pb){
		if(pa->data.expn>pb->data.expn){
			pc->next=pa;pc=pa;pa=pa->next;
		}
		else if(pa->data.expn<pb->data.expn)
		{ 
			pb->data.coef = -pb->data.coef;
			pc->next=pb;pc=pb;pb=pb->next;
		}
		else {
			sum=pa->data.coef-pb->data.coef;
			if(fabs(sum)>1e-6){ //系数和不为零
				pa->data.coef=sum;
				pc->next=pa;pc=pa;pa=pa->next;
				s=pb;pb=pb->next;free(s);
			}
			else {
				s=pa;pa=pa->next;free(s);
				s=pb;pb=pb->next;free(s);
			}
		}
	}
	s = pb;
	while(s)
	{
		s->data.coef = -s->data.coef;
		s = s->next;
	}
	pc->next=pa?pa:pb;  //插入链表剩余部分
	free(Lb);   //释放Lb的头结点
	return Lc;
}
//主控函数
void main()
{  
	LinkList La,Lb,Lc;
	int n;
	printf("输入第一个多项式的项数:  ");
	scanf("%d",&n);
	printf("输入第一个多项式的每一项的系数,指数:  \n");
	La=CreatPolyn(n);
	printf("第一个多项式为:  ");
	printList(La);
	printf("输入第二个多项式的项数:  ");
	scanf("%d",&n);
	printf("输入第二个多项式的每一项的系数,指数:  \n");
	Lb=CreatPolyn(n);
	printf("第二个多项式为:  ");
	printList(Lb);
	//Lc=AddPolyn(La,Lb);
	//printf("\n相加后的和多项式为:  ");
	Lc=SubPolyn(La,Lb);
	printf("\n相减后的和多项式为:  ");
	printList(Lc);
}