#include<stdio.h>
#include<stdlib.h>
typedef struct Node {
	int xishu;       //多项式系数
	int zhishu;      //多项式指数
	struct Node* next;
}node, * list;
void create(list& p) {
	int n;
	printf("建立多项式，输入元素个数:");
		scanf_s("%d", &n);
	p = (list)malloc(sizeof(node));        //为头结点分配空间
	p->next = NULL;
	list s, pre, q;
	for (int i = 1; i <= n; i++) {
		printf("请输入第%d项的系数和指数: ", i);
		s = (node*)malloc(sizeof(node));    //为后续结点分配空间
		scanf_s("%d %d", &s->xishu, &s->zhishu);
		pre = p;
		q = p->next;
		//使节点系数从小到大
		while (q && q->zhishu < s->zhishu) {
			pre = q;
			q = q->next;
		}
		//头插法实现多项式链表
		s->next = q;
		pre->next = s;
	}
}
//拷贝函数
list copy(list q) {
	//为拷贝的链表创建头结点
	list p = (list)malloc(sizeof(node));
	p->next = NULL;
	list s, t, x;
	t = q->next;
	x = p;
	while (t != NULL) {
		//创建结点
		s = (list)malloc(sizeof(node));
		//将原多项式的值赋值给拷贝链表
		s->xishu = t->xishu;
		s->zhishu = t->zhishu;
		s->next = x->next;
		x->next = s;
		t = t->next;
		x = x->next;
	}
	return p;
}
//加法运算
list add(list a, list b) {
	node* pa, * pb, * pc, * p;
	pa = a->next;     //pa指向a链表的头结点
	pb = b->next;     //pb指向b链表的头结点
	list t = a;       //t指针指向a的表头
	pc = t;
	while (pa && pb) {
		//分三种情况
		//pa指数小于pb指数
		if (pa->zhishu < pb->zhishu) {
			pc->next = pa;
			pa = pa->next;
			pc = pc->next;
		}
		//pa指数小于pb指数
		else if (pa->zhishu > pb->zhishu) {
			p = pb;
			pc->next = pb;
			pb = pb->next;
			pc = pc->next;
		}		
		else {
			if (pa->xishu + pb->xishu == 0) {
				p = pa;
				pa = pa->next;
				free(p);
				p = pb;
				pb = pb->next;
				free(p);
				p = NULL;
			}
			//pa指数小于pb指数
			else {
				pc->next = pa;
				pa->xishu += pb->xishu;
				pa = pa->next;
				p = pb;
				pb = pb->next;
				pc = pc->next;
				free(p);
				p = NULL;
			}
		}
	}
	//将未运算完的链表部分添加到新链表后
	if (pa)
		pc->next = pa;
	if (pb)
		pc->next = pb;
	//返回相加之后链表的表头
	return t;
}
//减法运算
list sub(list a, list b) {
	//与加法类似
	node* pa, * pb, * pc, * p;
	pa = a->next;
	pb = b->next;
	list t = a;
	pc = t;
	while (pa && pb) {
		if (pa->zhishu < pb->zhishu) {
			pc->next = pa;
			pa = pa->next;
			pc = pc->next;
		}
		else if (pa->zhishu > pb->zhishu) {
			pb->xishu = -(pb->xishu);
			pc->next = pb;
			pb = pb->next;
			pc = pc->next;
		}
		else {
			if (pa->xishu - pb->xishu == 0) {
				p = pa;
				pa = pa->next;
				free(p);
				p = pb;
				pb = pb->next;
				free(p);
				p = NULL;
			}
			else {
				pc->next = pa;
				pa->xishu -= pb->xishu;
				pa = pa->next;
				p = pb;
				pb = pb->next;
				pc = pc->next;
				free(p);
				p = NULL;
			}
		}
	}
	if (pa)
		pc->next = pa;
	while (pb) {
		pb->xishu = -(pb->xishu);
		pc->next = pb;
		pc = pc->next;
		pb = pb->next;
	}
	return t;
}
//打印多项式链表
void print(list q) {
	list t = q->next;
	while (t != NULL) {
		while (t->xishu == 0) {
			t = t->next;
		}
		printf("%d*x^%d", t->xishu, t->zhishu);
		if (t->next != NULL) {
			list s = t->next;
			if (s->xishu > 0)printf("+");
		}
		t = t->next;
	}
	printf("\n");
}
int main() {
	list a, b;
	create(a);
	print(a);     //创建打印多项式a
	create(b);
	print(b);     //创建打印多项式b
	printf("\n");
	//将多项式a拷贝给a1，多项式b拷贝给b1
	list a1 = copy(a);
	list b1 = copy(b);
	list c = add(a, b);
	printf("a+b=");
	print(c);
	//加法运算后多项式a,b断开，将多项式a,b还原
	a = copy(a1);
	b = copy(b1);
	list d = sub(a, b);
	printf("a-b=");
	print(d);
	return 0;
}