单链表实现多项式乘法

多项式乘法比较复杂，先实现多项式的加法，可以大大化简程序，输入输出采用文件的形式。

代码如下：

#include <iostream>
#include <fstream>
using namespace std;

typedef struct PNode
{
	double c;
	int e;
	struct PNode *next;
}PNode, *PolyList;

//创建一个空结点
void CreateNode(PolyList &p)
{
	p = new PNode;
}

//打开文件并读取信息
void OpenFile(double cArray[], int eArray[], int &count)
{
	ifstream ifs;
	ifs.open("poly1.txt", ios::out);

	if (!ifs.is_open())
	{
		cout << "文件打开失败！" << endl;
	}

	char ch;
	double c;
	int e;
	count = 0;

	while (ifs >> c && ifs >> ch && ifs >> e)
	{
		cArray[count] = c;
		eArray[count] = e;
		count++;
	}
}

//将多项式的信息保存到文件中
void SaveFile(PolyList &L)
{
	PolyList p;
	p = L->next;
	int count = 0;
	double cArray[99] = { 0 };
	int eArray[99] = { 0 };

	//读取链表中的数据
	while (p)
	{
		cArray[count] = p->c;
		eArray[count] = p->e;
		p = p->next;
		count++;
	}

	//保存到文件
	ofstream ofs;
	ofs.open("poly3.txt", ios::out);

	if (!ofs.is_open())
	{
		cout << "文件打开失败！" << endl;
	}
	for (int i = 0; i < count; i++)
	{
		ofs << cArray[i] << "," << eArray[i] << " ";
	}
	
}

//创建单链表
void CreateList(PolyList &L, int e[], double c[], int n)
{
	PolyList p, q, L;
	CreateNode(L); //创建头结点
	q = L;

	//尾插法
	for (int i = 0; i < n; i++)
	{
		CreateNode(p);
		p->c = c[i];
		p->e = e[i];
		q->next = p;
		q = p;
	}
	q->next = NULL;
}

//遍历链表
void Traverse(PolyList &L)
{
	PolyList p;
	p = L->next;
	while (p)
	{
		cout << p->c << " ";
		p = p->next;
	}
	cout << endl;
}

//实现两个链表的相加
PolyList add(PolyList &ha, PolyList &hb)
{
	PolyList p, pa, pb, pc, hc;
	pa = ha->next;
	pb = hb->next;
	CreateNode(hc);
	pc = hc;

	while (pa && pb)
	{
		if (pa->e < pb->e)
		{
			p = pa;
			pa = pa->next;
		}
		else if (pa->e > pb->e)
		{
			p = pb;
			pb = pb->next;
		}
		else 
		{
			pa->c += pb->c;
			if (pa->c == 0)
			{
				p = pa; pa = pa->next; delete p;
				p = pb; pb = pb->next; delete p;
				continue;
			}
			p = pb; pb = pb->next; delete p;
			p = pa; pa = pa->next;
		}
		pc->next = p; 
		pc = p;
	}

	if (pa) pc->next = pa;
	else if (pb) pc->next = pb;
	else pc->next = NULL;
	return hc;
}

//实现两个链表的相乘
PolyList muti(PolyList &hp, PolyList &hq)
{
	PolyList p, q, hr, ht, pt;
	CreateNode(hr); hr->next = NULL;
	CreateNode(ht); ht->next = NULL;
	q = hq->next;

	while (q)
	{
		pt = ht;
		p = hp->next;
		while (p)
		{
			CreateNode(pt->next); pt = pt->next;
			pt->c = q->c * p->c;
			pt->e = q->e + p->c;
			p = p->next;
		}
		pt->next = NULL;
		q = q->next;
		p = add(ht, hr);
		delete hr;
		hr = p;
	}
	delete ht;
	return hr;
}

int main()
{
	double c1[10], c2[10] = {0};
	int e1[10], e2[10] = {0};
	int count1, count2;
	OpenFile(c1, e1, count1);
	OpenFile(c2, e2, count2);

	PolyList L1, L2, L3;
	CreateList(L1, e1, c1, count1);
	Traverse(L1);
	CreateList(L2, e2, c2, count2);
	Traverse(L2);
	L3 = muti(L1, L2);
	Traverse(L3);

	SaveFile(L3);
}

本文地址：https://blog.csdn.net/Shallowmm/article/details/108985617