(实验)自行为稀疏一元多项式设计存储结构，并实现如下功能：
① 输入：从键盘输入多项式的各项系数和指数，创建一元多项式；
② 输出：按给定格式输出一元多项式；（例如：3*x^20-x7+10）
③ 多项式加法： 任意输入另一个多项式，输出其与原多项式的和。
④ 多项式减法： 任意输入另一个多项式，将其作为减数输出其与原多项式的差。
⑤ 多项式乘法： 任意输入另一个多项式，输出其与原多项式的积。

#include <iostream>
using namespace std;
typedef struct LNode
{
	int coef;					//系数
	int expn;					//指数
	struct LNode* next;			//节点的指针域
}LNode,*LinkList;           //LinkList为指向结构体LNode的指针类型

//单链表的初始化
LinkList InitList(LinkList &L) {
	L = new LNode;          //生成头结点
	L->next = NULL;         //头结点的指针域置为空
	return L;
}


//单链表的创建
LinkList CreatList(LinkList& L) {
	L->next = NULL;
    int n = 0;
	cout << "请输入要创建的多项式有几项" << endl;
	cin >> n;
    for(int i = 0;i<n;i++)		//依次录入各项的系数和指数
    {
        LNode* p = new LNode;

        cout << "系数：" << endl;	//录入系数
        int c = 0;
        cin >> c;
        p->coef = c;
        cout << "指数：" << endl;	//录入指数
        int e = 0;
        cin >> e;
        p->expn = e;
        p->next = L->next;
        L->next = p;
    }
    return L;
}
//单链表的创建（重载函数）
LinkList CreatList(LinkList& L,int num) {
	L->next = NULL;
	int n = 0;
	for (int i = 0; i < n; i++)
	{
		LNode* p = new LNode;

		cout << "系数：" << endl;
		int c = 0;
		cin >> c;
		p->coef = c;
		cout << "指数：" << endl;
		int e = 0;
		cin >> e;
		p->expn = e;

		p->next = L->next;
		L->next = p;
	}
	return L;
}

//多项式的加法
LinkList add(LinkList L1, LinkList L2, LinkList& L) {
	LNode* a = L1->next;
	LNode* b = L2->next;
	L->next = NULL;
	LNode* p = new LNode;
	while (a&&b) {
		LNode* temp = new LNode;
		if (a->expn == b->expn) {	//指数相等时，系数相加
			temp->coef = a->coef + b->coef;
			temp->expn = a->expn;

			temp->next = L->next;
			L->next = temp;

			a = a->next;
			b = b->next;

		}
		else if (a->expn > b->expn) {	//a的指数大于b时
			temp->coef = b->coef;
			temp->expn = b->expn;
			temp->next = L->next;
			L->next = temp;
			b = b->next;
		}
		else {							//b的指数大于a时
			temp->coef = a->coef;
			temp->expn = a->expn;
			temp->next = L->next;
			L->next = temp;
			a = a->next;
		}
	}
	if (a) {							//当b遍历完而a还未结束时，把a剩下的部分加上
		while (a->next !=NULL)
		{
			p->coef = a->coef;
			p->expn = a->expn;
			p->next = L->next;
			L->next = p;
			a = a->next;
		}

	}
	else {								//当a遍历完而b还未结束时，把b剩下的部分加上
		while (b)
		{
			p->coef = b->coef;
			p->expn = b->expn;
			p->next = L->next;
			L->next = p;
			b = b->next;
		}
	}
	return L;
}

//多项式相减
LinkList subtraction(LinkList L1, LinkList L2, LinkList& L) {
	LNode* a = L1->next;
	LNode* b = L2->next;
	L->next = NULL;
	LNode* p = new LNode;
	while (a && b) {
		LNode* temp = new LNode;
		if (a->expn == b->expn) {					//指数相等时，系数相减
			temp->coef = a->coef - b->coef;
			temp->expn = a->expn;

			temp->next = L->next;
			L->next = temp;

			a = a->next;
			b = b->next;

		}
		else if (a->expn > b->expn) {				//a的指数大于b时

			temp->coef = -b->coef;
			temp->expn = b->expn;
			temp->next = L->next;
			L->next = temp;
			b = b->next;
		}
		else {										//b的指数大于a时
			temp->coef = a->coef;
			temp->expn = a->expn;
			temp->next = L->next;
			L->next = temp;
			a = a->next;
		}
	}
	if (a) {
		while (a->next != NULL)						//当b遍历完而a还未结束时，把a剩下的部分加上
		{
			p->coef = a->coef;
			p->expn = a->expn;
			p->next = L->next;
			L->next = p;
			a = a->next;
		}

	}
	else {											//当a遍历完而b还未结束时，加上b剩下的部分的相反数
		while (b)
		{
			p->coef = -b->coef;
			p->expn = b->expn;
			p->next = L->next;
			L->next = p;
			b = b->next;
		}
	}
	return L;
}

//多项式相乘
LinkList MultiplyPolyn(LinkList L1, LinkList L2, LinkList& L)	
{
	L = L1;
	LinkList p1, p2, p3, p;
	p1 = L1->next;
	L->next = NULL;
	int sum;	//保存指数相加的结果
	for (; p1; p1 = p1->next)	//循环p1的每一个结点
	{
		for (p2 = L2->next; p2; p2 = p2->next)	//循环p2的每一个结点
		{
			p3 = L;	
			sum = p1->expn + p2->expn;		//保存指数相加的结果
			while (p3->next && p3->next->expn > sum)	//当p3存在,并且指数小于计算的，p3后移
			{
				p3 = p3->next;
			}
			if (p3->next && p3->next->expn == sum)	//当p3存在,并且指数等于计算的，p3系数加上计算的系数
			{
				p3->next->coef += (p1->coef * p2->coef);
			}
			else	//否则将计算后的结果插入p3
			{
				p = new LNode;
				p->expn = sum;
				p->coef = p1->coef * p2->coef;
				p->next = p3->next;
				p3->next = p;
			}
		}
	}
	delete L2;	
	return L;
}

//打印多项式
void ListPrint(LinkList& L) {
	LNode* p = L;
	while (p->next != NULL) {
		cout << p->next->coef << "*X^" << p->next->expn;
		if (p->next->coef<0 && p->next->next)
		{
			cout << "-";
		}
		else if (p->next->coef > 0 && p->next->next) {
			cout << "+";
		}
		p = p->next;
	}
	cout << endl;
}

int main() {
	LinkList L1,L2,L3;
	//初始化
	L1 = InitList(L1);
	L2 = InitList(L2);
	L3 = InitList(L3);
	//创建
	L1 = CreatList(L1);
	ListPrint(L1);
	L2 = CreatList(L2);
	ListPrint(L2);
	L3 = CreatList(L3, 0);
	ListPrint(L3);
	//多项式相加
	L3 = add(L1,L2,L3);
	cout << "相加得：";
	ListPrint(L3);
	//多项式相减
	L3 = subtraction(L1, L2, L3);
	cout << "相减得：";
	ListPrint(L3);
	//多项式相乘
	cout << "相乘得：";
	L3 = MultiplyPolyn(L1, L2, L3);
	ListPrint(L3);
}