欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

PTA甲级考试真题练习9——1009 Product of Polynomials

程序员文章站 2022-06-07 13:06:29
...

题目

PTA甲级考试真题练习9——1009 Product of Polynomials

思路

多项式相乘问题,可以用map,可以用链表,这里使用链表实现

坑点

测试点0!!!系数为0的情况下不输出,注意:这里的系数为0的情况有两种,第一种是本身给的就有系数为0的项,第二种是通过指数相同的项正负抵消后得到的系数为0的项,都要考虑到!!!

代码

typedef struct Node
{
	int exp;       //指数
	double res;    //系数
	struct Node* next;
}Node, * LinkList;

void InitList(LinkList& L)
{
	L = (LinkList)malloc(sizeof(Node));
	L->next = nullptr;
	L->exp = L->res = 0;
	int num;
	cin >> num;
	L->exp = num;
	Node* p = L;
	for (int i = 0; i < num; ++i)
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		cin >> newNode->exp >> newNode->res;
		newNode->next = p->next;
		p->next = newNode;
		p = newNode;
	}
}

void InsertList(LinkList& C, int exp, double res)
{
	Node* p = C -> next;
	Node* pre = C;
	if (!p)
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->exp = exp;
		newNode->res = res;
		newNode->next = C->next;
		C->next = newNode;
		C->exp++;
		return;
	}
	while (p->next!=nullptr)
	{
		if (exp == p->exp)
		{
			p->res += res;
			if (p->res == 0)
			{
				pre->next = p->next;
				free(p);
				C->exp--;
			}
			return;
		}
		if ( (p->exp > exp&& exp > p->next->exp))
		{
			Node* newNode = (Node*)malloc(sizeof(Node));
			newNode->exp = exp;
			newNode->res = res;
			newNode->next = p->next;
			p->next = newNode;
			C->exp++;
			return;
		}
		pre = p;
		p = p->next;
	}
	if (exp == p->exp)
	{
		p->res += res;
		if (p->res == 0)
		{
			pre->next = p->next;
			free(p);
			C->exp--;
		}
		return;
	}
	else
	{
		Node* newNode = (Node*)malloc(sizeof(Node));
		newNode->exp = exp;
		newNode->res = res;
		newNode->next = p->next;
		p->next = newNode;
		C->exp++;
		return;
	}
}

void  mulPol(LinkList& A, LinkList& B,LinkList& C)
{
	C = (Node*)malloc(sizeof(Node));
	C->exp = C->res = 0;
	C->next = nullptr;
	Node* pa = A->next, * pb = B->next;
	while (pa)
	{
		Node* p = pb;
		for (p; p != nullptr; p = p->next)
		{
			int exp = pa->exp + p->exp;
			double res = pa->res * p->res;
			if (fabs(res) >= 1e-5)
			{
				InsertList(C, exp, res);
			}
		}
		pa = pa->next;
	}
}

void PrintPol(LinkList& L)
{
	cout << L->exp;
	Node* p = L->next;
	for (p; p != nullptr; p = p->next)
	{
		printf(" %d %.1lf", p->exp, p->res);
	}
}
int main()
{
	LinkList LA, LB, LC;
	InitList(LA);
	InitList(LB);
	mulPol(LA, LB, LC);
	PrintPol(LC);
	return 0;
}