【单链表】一元多项式求和(C++)

要求&&实现流程

代码实现

#include<iostream>
using namespace std;

typedef struct LinkNode
{
	int cofe;//系数
	int  exp;//次方
	struct LinkNode* next;
}LinkList,LinkNode;

//初始化链表
void initLinkList(LinkList*& L)
{	
	L = new LinkList;
	L->next = NULL;
}
//尾插
void LinkPushBack(LinkList* L, int _cofe, int _exp)
{
	LinkNode* node = new LinkNode;
	node->cofe = _cofe;
	node->exp = _exp;

	LinkNode* temp = L;
	while (temp->next)
	{
		temp = temp->next;
	}
	temp->next = node;
	node->next = NULL;
}

//输入数据
void inputPoly(LinkList* L1, LinkList* L2)
{
	//系数，次方
	int l1cofe = 0;
	int l2cofe = 0;
	int l1exp = 0;
	int l2exp = 0;

	//几项式
	int l1num = 0;
	int l2num = 0;

	cout << "第一个多项式有几项?" << endl;
	cin >> l1num;
	for (int i = 0; i < l1num; i++)
	{
		cout << "请输入第"<<i+1<<"项的系数:" << endl;
		cin >> l1cofe;
		cout << "请输入第" << i+1 << "项的次方:" << endl;
		cin >> l1exp;
		LinkPushBack(L1, l1cofe, l1exp);
	}
	cout << "第一个多项式输入完毕!" << endl;

	cout << "第二个多项式有几项?" << endl;
	cin >> l2num;
	for (int i = 0; i < l2num; i++)
	{
		cout << "请输入第" << i+1<< "项的系数:" << endl;
		cin >> l2cofe;
		cout << "请输入第" << i+1 << "项的次方:" << endl;
		cin >> l2exp;
		LinkPushBack(L2, l2cofe, l2exp);
	}
	cout << "第二个多项式输入完毕！" << endl;
	cout << "多项式输入完毕!" << endl;
}

//多项式求和运算
void sumList(LinkList* L1, LinkList* L2)
{
	LinkNode* p = L1->next;//p为结果链表
	LinkNode* q = L2->next;
	LinkNode* pFront = L1;
	LinkNode* qFront = L2;
	//cofe系数
	//exp次方

	while (q && p)
	{
		if (p->exp == q->exp)//是同类项，可以合并，结果合并到p中
		{
			p->cofe += q->cofe;
			LinkNode* temp = new LinkNode;
			//删除q的结点
			temp = q;
			qFront->next = temp->next;
			delete temp;

			//工作指针后移
			pFront = p;
			p = p->next;

			q = qFront->next;
		}
		else if(p->exp < q->exp)//结果链表对应次方比q链表对应结点次方小，结果链表中工作指针后移
		{
			pFront = p;
			p = p->next;
		}
		else if(p->exp > q->exp)//结果链表对应次方比q链表对应结点次方大，q对应结点插过来。
		{
			//将这个结点插入到结果结点中

			qFront->next = q->next;
			pFront->next = q;
			q->next = p;
			
			q = qFront->next;//重新回到对应链表
			//结果链表的前指针后移
			pFront = pFront->next;
		}
	}
	//如果多项式L2的长度大于L1的，此时结束时，L2还有没遍历到的结点，次方大于L1所有的结点，直接插入到结果链表(L1)尾部
	if (q)//加个判断条件防止，L1最后一个项，系数大于L2的，也进入下面这个循环
	{
		while (q)
		{
			pFront->next = q;
			pFront = pFront->next;
			q = q->next;
		}
		pFront->next = NULL;//链接完成后尾结点next域置空
	}
	L2->next = NULL;//到达这里，L2除了head结点之外，后面的就算有内容也不属于它了。

	cout << "相加结果为:" << endl;
	L1 = L1->next;
	while (L1)
	{
		cout << "(" << L1->cofe << "," << L1->exp << ")" << " ";
		L1 = L1->next;
	}	
}
//销毁链表
void destoryLink(LinkNode*& L)
{
	LinkNode* tempNode = L;
	while (tempNode)
	{
		L = L->next;
		delete tempNode;
		tempNode = L;
	}
}
int main(void)
{
	LinkList* L1;
	LinkList* L2;
	initLinkList(L1);
	initLinkList(L2);
	
	inputPoly(L1, L2);
	sumList(L1, L2) ;

	destoryLink(L1);
	destoryLink(L2);

	return 0;
}

输出结果：