2022/9/15

#define  _CRT_SECURE_NO_WARNINGS
#pragma GCC optimize
#include <bits/stdc++.h>
using  namespace std;
typedef struct SNode
{
	int eof;
	int exp;
	struct SNode* next;
}LNode, * Linklist;
//打印一元多项式
void print(Linklist L)
{
	Linklist p = L->next;
	while (p != NULL)
	{
		printf("%dx^%d", p->eof, p->exp);
		if (p->next != NULL && p->next->eof > 0)
			printf("+");
		p = p->next;
	}
}
void createList(Linklist& L)
{
	printf("开始创建单链表...\n");
	printf("请按递减顺序输入一元多项式中的各项，以（-999，-999）结束：");
	L = (Linklist)malloc(sizeof(LNode));
	L->next = NULL;
	Linklist p, last = L;
	p = (Linklist)malloc(sizeof(LNode));
	scanf("%d,%d", &p->eof, &p->exp);
	while (p->eof != -999 && p->exp != -999)
	{
		last->next = p;
		last = p;
		p = (Linklist)malloc(sizeof(LNode));
		scanf("%d,%d", &p->eof, &p->exp);
	}
	last->next = NULL;
	printf("创建成功！\n");
}
////进行两个一元多项式求和合并
void unoinList(Linklist LA, Linklist LB)
{
	Linklist t = LA;	//t指向LA的头节点
	Linklist flag = t;	//用来标记LA的头节点
	LA = LA->next;
	LB = LB->next;	//LA,LB分别指向首元节点
	while (LA && LB) {	//LA,LB均非空时运行
		if (LA->exp == LB->exp) {	//指数相等时
			LA->eof += LB->eof;	//系数相加，存的LA里
			if (LA->eof) {	//eof不等于0时
				t->next = LA;	//将修改后的LA当前节点链在t之后
				t = LA;	//t指向LA
				LA = LA->next;	//LA指向下一项
				//Linklist r = LB;	//临时存储LB节点
				LB = LB->next;	//LB后移
				//delete r;	//删除原LB节点
			}
			else {	//系数和为0
				//Linklist r = LA;	//临时存储LA节点
				LA = LA->next;	//LA后移
				//delete r;	//删除原LA节点
				//Linklist rr = LB;	//临时存储LB节点
				LB = LB->next;	//LB后移
				//delete rr;	//删除原LB节点
			}
		}
		else if (LA->exp < LB->exp) {	//LA指数小于LB指数
			t->next = LA;	//将修改后的LA当前节点链在t之后，
			t = LA;	//t指向LA
			LA = LA->next;	//指向下一项
		}
		else {	//LA的指数大于LB的指数
			t->next = LB;	//将修改后的LB当前节点链在t之后，
			t = LB;	//t指向LB
			LB = LB->next;	//指向下一项
		}
	}	//while
	t->next = LA ? LA : LB;	//插入非空多项式的剩余片段
	cout << "相加的结果为：" << endl;
	print(flag);	//输出结果
	delete LB;	//释放LB空间
}

int main() {
	LNode *L1 , *L2;
	createList(L1);
	createList(L2);

	unoinList(L1, L2);

	/*print(L1);
	cout << endl;
	print(L2);*/
	return 0;
}