[C++知识库]学习记录——一次多项式相加

//头指针---头结点
#include <iostream>
using namespace std;

class Link
{
public:
	int coff;//系数
	int exp;//指数
	Link* next;
};
int m = sizeof(Link);

void iniLink(Link *head)//要加&吗？
{
	head->next = NULL;
	cout << "请输入项数：" << endl;
	int n; cin >> n;
	for (int i = 0; i < n; i++)
	{
		Link* p = (Link*)malloc(m);
		cin >> p->coff >> p->exp;
		Link* q = head; Link* pre = head;
		while (q->next && q->next->exp <= p->exp)//直到最后一项或下一项的系数比它大
		{
			pre = q;
			q = q->next;
		}
		if (!q->next)//如果到最后一项
		{
			if (q!=head&&q->exp == p->exp)//不是空表且次数相等
			{
				q->coff += p->coff;
				if (!q->coff)//系数为0
				{
					pre->next = q->next;
				}
				free(p);
			}
			else
			{
				p->next = q->next;
				q->next = p;
			}
		}
		else//下一项系数比它大
		{
			if (q->exp == p->exp)//次数相等
			{
				q->coff += p->coff;
				if (!q->coff)//系数为零
				{
					pre->next = q->next;
				}
				free(p);
			}
			else
			{
				p->next = q->next;
				q->next = p;
			}
		}
	}
}

void displayList(Link *head)
{
	Link* p = head->next;
	if (p)
	{
		if (p->exp)
		{
			cout << p->coff << "x^" << p->exp;
		}
		else
		{
			cout << p->coff;
		}
	}
	p = p->next;
	while (p)
	{
		if (p->exp)
		{
			cout << " + " << p->coff << "x^" << p->exp;
		}
		else
		{
			cout << " + " << p->coff;
		}
		p = p->next;
	}
	cout << endl;
}

int cmp(int a,int b)
{
	if (a < b) return -1;
	else if (a == b) return 0;
	else return 1;
}

void addList(Link* ha, Link* hb)//把a和b相加，结果赋给a
{
	Link *pa = ha->next; Link* pb = hb->next;//pa、pb指向第一个结点，pc指向头结点
	Link* pc = ha;
	while (pa && pb)
	{
		switch (cmp(pa->exp, pb->exp))
		{
		case -1://a的次数小
			pc->next = pa;
			pa = pa->next; pc = pc->next;
			break;
		case 0://次数相等
			pa->coff += pb->coff;
			if (pa->coff)//a的系数不为0
			{
				pc->next = pa;//同case -1
				pc = pc->next;
			}
			else//a的系数为0
			{
				pc->next = pa->next;//删去a中该结点
			}
			pa = pa->next; pb = pb->next; 
			break;
		case 1:
			pc->next = pb;
			pb = pb->next; pc = pc->next;
		}
	}
	if (pa)//把剩下的链表链到后面
	{
		pc->next = pa;
	}
	if (pb)
	{
		pc->next = pb;
	}
}

int main()
{
	Link* headA = (Link*)malloc(m);
	Link* headB = (Link*)malloc(m);
	iniLink(headA);
	displayList(headA);
	iniLink(headB);
	displayList(headB);
	addList(headA, headB);
	cout << "--------after add--------" << endl;
	displayList(headA);

	return 0;
}