数据结构–链表实现多项式求和&&求积

• 首先，数据的组织形式：使用数组来存储结构体数据相对比较简单。但是为了熟悉链表的使用，这里使用链表。
• 多项式的表示：输入的时候先输入系数，然后输入指数。输出同样是这样。

难点：

• 求多项式乘积不像求和，因为后插入数据的指数可能比前一个数据要大，所以需要进行判断。

//链表实现一个多项式的相加和相乘
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>

typedef struct PolyNode* Polynomial;
struct PolyNode
{
	int coef;
	int expon;
	Polynomial link;
};
void attach(int c, int e, Polynomial* pRear)
{
	Polynomial P = (Polynomial)malloc(sizeof(struct PolyNode));
	P->coef = c;
	P->expon = e;
	P->link = NULL;
	(*pRear)->link = P;
	*pRear = P;
}
Polynomial readPoly()
{
	int num1 = 0, c = 0, e = 0;
	printf("请输入多项式的系数：");
	scanf("%d", &num1);
	Polynomial Head = (Polynomial)malloc(sizeof(struct PolyNode));     //构造一个空的头节点
	Polynomial Rear = Head;
	Head->link = NULL;
	while (num1--)
	{
		scanf("%d %d", &c, &e);
		attach(c, e, &Rear);
	}
	Polynomial T = Head;
	Head = Head->link;
	free(T);
	return Head;
}
int compare(int a, int b)
{
	if (a > b) return 1;
	else if (a == b) return 0;
	else return -1;
}
Polynomial polyAdd(Polynomial P1, Polynomial P2)
{
	Polynomial Head, Rear, T;
	Head = (Polynomial)malloc(sizeof(struct PolyNode));
	Head->link = NULL;
	Rear = Head;
	//比较指数大小，指数大的加入结果多项式，然后指针后移。
	int sum = 0;
	while (P1 && P2)
	{
		switch (compare(P1->expon, P2->expon))
		{
		case 1:
			attach(P1->coef, P1->expon, &Rear);
			P1 = P1->link;
			break;
		case 0:
			sum = P1->coef + P2->coef;
			if (sum) attach(sum, P1->expon, &Rear);
			P1 = P1->link; P2 = P2->link;
			break;
		case -1:
			attach(P2->coef, P2->expon, &Rear);
			P2 = P2->link;
			break;
		}
	}
	for (; P1; P1 = P1->link) attach(P1->coef, P1->expon, &Rear);
	for (; P2; P2 = P2->link) attach(P2->coef, P2->expon, &Rear);
	T = Head;
	Head = Head->link;
	free(T);
	return Head;
}
void printPoly(Polynomial P)
{
	int flag = 0;
	while (P)
	{
		if (flag)
		{
			printf(" ");
		}
		else
		{
			flag = 1;
		}
		printf("%d %d", P->coef, P->expon);
		P = P->link;
	}
}
Polynomial polyMulti(Polynomial P1, Polynomial P2)
{
	Polynomial T1, T2, Head, Rear, P;            //需要使用多项式首元素的指针，因此设置了T1，T2
	Head = (Polynomial)malloc(sizeof(struct PolyNode));
	Head->link = NULL;
	Rear = Head;
	T1 = P1;
	while (T1)
	{
		T2 = P2; Rear = Head;
		while (T2)
		{
			//进行排序插入
			int c = T1->coef * T2->coef;
			int e = T1->expon + T2->expon;
			while (Rear->link && Rear->link->expon > e)
			{
				Rear = Rear->link;
			}
			if (Rear->link && Rear->link->expon == e)
			{
				if (c + Rear->link->coef) Rear->link->coef = c + Rear->link->coef;
				else
				{
					Polynomial tmp = Rear->link;
					Rear->link = tmp->link;
					free(tmp);
				}
			}
			else
			{
				P = (Polynomial)malloc(sizeof(struct PolyNode));
				P->coef = c;
				P->expon = e;
				P->link = Rear->link;
				Rear->link = P;
				Rear = Rear->link;
			}
			T2 = T2->link;
		}
		T1 = T1->link;
	}
	Polynomial ttt = Head;
	Head = ttt->link;
	free(ttt);
	return Head;
}
int main()
{
	//输入多项式1 && 输入多项式2
	Polynomial P1 = readPoly();
	Polynomial P2 = readPoly();
	//计算多项式和并输出
	Polynomial P3 = polyAdd(P1, P2);
	printPoly(P3);
	//计算多项式乘积并输出
	Polynomial P4 = polyMulti(P1, P2);
	printf("\n");
	printPoly(P4);
	return 0;
}

结果如下

如求多项式：
3x⁴+5x²+6x¹+2 和
5x²⁰+7x⁴+3x 的乘积

和是：5x²⁰+10x⁴+5x²+9x+2
乘积为：15x²⁴+25x²²+30x²¹+…