数据结构05-多项式相加

先上代码再解释

#include
using namespace std;
//链表的应用-进行多项式的相加

//创建一个多项式节点：

typedef struct Node {
	int coeff;
	int exp;
	struct Node* next;
}Poly, * Polyptr;

//有以下几个函数
//初始化，打印，测试，添加，相加。

Polyptr Poly_Init()
{
	Polyptr temp = new Poly;
	if (!temp)
	{
		cout << "申请内存失败！" << endl;
		return NULL;
	}
	temp->coeff = temp->exp = 0;
	temp->next=NULL;
	return temp;
}

void Print_Poly(Polyptr temp)
{
	Polyptr p = temp;
	for (; p->next != NULL; p = p->next)
	{
		cout << p->coeff << "*10^" << p->exp << (p->next->coeff >= 0 ? "+":"");
	}
	cout << p->coeff << "*10^" << p->exp << endl;
}



void Poly_Append(Polyptr Zpow, int paracoeff, int paraexp)
{
	int flag = 10;
	if (paraexp < 0)
	{
		cout << "暂不支持处理幂次小于0的多项式" << endl;
		return;
	}
	Polyptr p = Zpow, q = NULL;
	Polyptr temp = new Poly;
	if (!temp)
	{
		cout << "申请内存失败" << endl;
		return;
	}
	temp->coeff = paracoeff;
	temp->exp = paraexp;
	while (p != NULL&&paraexp > p->exp)
	{
		q = p;
		p = p->next;
	}
	if (p == NULL) { flag = 0; }
	else if (paraexp == p->exp) { flag = 1; }
	else if (paraexp < p->exp) { flag = 2;}
	switch (flag)
	{
	case 0:
		if (q) {
			q->next = temp;
			temp->next = NULL;
		}
		break;
	case 1:
		p->coeff += temp->coeff;
		delete temp;
		if (temp != NULL)
			temp = NULL;
		break;
	case 2:
		temp->next = p;
		q->next = temp;
		break;
	default:
		cout << "给我整不会了" << endl;
		break;
	}
}


Polyptr Polys_Add(Polyptr poly1, Polyptr poly2)
{
	Polyptr q = poly2;
	if (poly1 == NULL)
		return poly2;
	else if (poly2 == NULL)
		return poly1;
	while (q!= NULL)
	{
		Poly_Append(poly1, q->coeff, q->exp);
		q = q->next;
	}
	return poly1;
}
void test()
{
	Polyptr Zpow1 = Poly_Init();
	cout << "初始化" << endl;
	Poly_Append(Zpow1, 10, 5);
	Poly_Append(Zpow1, 6, 3);
	Poly_Append(Zpow1, 6, 3);
	Poly_Append(Zpow1, -666, 3);
	Poly_Append(Zpow1, -666, 13);
	Print_Poly(Zpow1);
	Polyptr Zpow2 = Poly_Init();
	cout << "初始化" << endl;
	Poly_Append(Zpow2, 10, 5);
	Poly_Append(Zpow2, 6, 3);
	Poly_Append(Zpow2, 6, 3);
	Poly_Append(Zpow2, 5, 3);
	Poly_Append(Zpow2, 1, 13);
	Print_Poly(Zpow2);
	Zpow1=Polys_Add(Zpow1, Zpow2);
	Print_Poly(Zpow1);
}
int main()
{
	test();
	return 0;
}

多项式相加是数据结构中链表的一个扩展，通过每一个链表来存储不同次幂的不同系数，达到一个链表存储一个多项式的效果，既然是链表，那么这里面的 *** 作大致都是从链表中衍生出来的，所以我们这里只讲一下最难的部分：在多项式中添加一个项。
这里是具体代码：

void Poly_Append(Polyptr Zpow, int paracoeff, int paraexp)
{
	int flag = 10;
	if (paraexp < 0)
	{
		cout << "暂不支持处理幂次小于0的多项式" << endl;
		return;
	}
	Polyptr p = Zpow, q = NULL;
	Polyptr temp = new Poly;
	if (!temp)
	{
		cout << "申请内存失败" << endl;
		return;
	}
	temp->coeff = paracoeff;
	temp->exp = paraexp;
	while (p != NULL&&paraexp > p->exp)
	{
		q = p;
		p = p->next;
	}
	if (p == NULL) { flag = 0; }
	else if (paraexp == p->exp) { flag = 1; }
	else if (paraexp < p->exp) { flag = 2;}
	switch (flag)
	{
	case 0:
		if (q) {
			q->next = temp;
			temp->next = NULL;
		}
		break;
	case 1:
		p->coeff += temp->coeff;
		delete temp;
		if (temp != NULL)
			temp = NULL;
		break;
	case 2:
		temp->next = p;
		q->next = temp;
		break;
	default:
		cout << "给我整不会了" << endl;
		break;
	}
}

看完了代码，我们来细说这些代码的作用。
首先是数据的合法性检测，由于本人能力有限，目前只能先写出幂次为不小于0的多项式，所以这里做了一个多项式幂次的判断。

if (paraexp < 0)
	{
		cout << "暂不支持处理幂次小于0的多项式" << endl;
		return;
	}

随后则是老生常谈的申请内存加初始化了

Polyptr temp = new Poly;
	if (!temp)
	{
		cout << "申请内存失败" << endl;
		return;
	}
	temp->coeff = paracoeff;
	temp->exp = paraexp;

接下来，则是这部分的难点，添加一个项。
首先，我们来谈谈我们添加项的分类的逻辑。
第一种，假如所要添加的项的幂次大于原来多项式的所有项，那么我们进行一个尾插法即可。
第二种，如果恰好在多项式中有一项的幂次和需要添加的项的幂次相等，那么我们只需要进行系数的相加即可。
第三种，也是最后一种，我们所要添加的项的幂次既不等于多项式中的项的幂次，也不是最大的，这时候就要用到我们之前在单链表中运用到的根据位置来插入的方法来添加项了。
讲完了大概逻辑，我们可以来看看代码了。
首先我定义了一个flag变量来标志我们要进行哪一种 *** 作：int flag = 10;
然后是进行迭代判断，这里我们用q变量作为p的前驱，方便待会的插入 *** 作 ：

while (p != NULL&&paraexp > p->exp)
	{
		q = p;
		p = p->next;
	}
	if (p == NULL) { flag = 0; }
	else if (paraexp == p->exp) { flag = 1; }
	else if (paraexp < p->exp) { flag = 2;}

首先我们先判断循环是否遍历完全，如果我们遍历完全并且需添加项的幂次没有小于多项式中的话，我们就记录为0，进行尾插法。后面两个判断方法也是基于这个。
随后我们进行相关的 *** 作：

switch (flag)
	{
	case 0:
		if (q) {
			q->next = temp;
			temp->next = NULL;
		}
		break;
	case 1:
		p->coeff += temp->coeff;
		delete temp;
		if (temp != NULL)
			temp = NULL;
		break;
	case 2:
		temp->next = p;
		q->next = temp;
		break;
	default:
		cout << "给我整不会了" << endl;
		break;
	}

以上