用C＋＋编写求两个一元多项式相乘的算法

给个网站你
http://www.luocong.com/dsaanotes/index-Z-H-3.htm#node_sec_2.3

2.3 应用：一元多项式（加法和乘法）

2.3.1 基础知识
我们使用一元多项式来说明单链表的应用。假设有两个一元多项式：

P1(X) = X^2 + 2X + 3

以及

P2(X) = 3X^3 + 10X + 6

现在运用中学的基础知识，计算它们的和：

P1(X) + P2(X) = (X^2 + 2X + 3) + (3X^3 + 10X + 6)
= 3X^3 + 1X^2 + 12X^1 + 9

以及计算它们的乘积：

P1(X) * P2(X) = (X^2 + 2X + 3) * (3X^3 + 10X + 6)
= 3X^5 + 6X^4 + 19X^3 + 26X^2 + 42X^1 + 18

怎么样，很容易吧？:) 但我们是灵长类动物，这么繁琐的计算怎么能用手工来完成呢？（试想一下，如果多项式非常大的话……）我们的目标是用计算机来完成这些计算任务，代码就在下面。

2.3.2 代码实现

///////////////////////////////////////////////////////////////////////////////
//
// FileName : poly.cpp
// Version : 0.10
// Author : Luo Cong
// Date : 2004-12-30 17:32:54
// Comment :
//
///////////////////////////////////////////////////////////////////////////////

#include
#include "slist.h"

#define Max(x,y) (((x)>(y)) ? (x) : (y))

typedef struct tagPOLYNOMIAL
{
CSList Coeff;
int HighPower;
} * Polynomial;

static void AddPolynomial(
Polynomial polysum,
const Polynomial poly1,
const Polynomial poly2
)
{
int i;
int sum;
int tmp1;
int tmp2;

polysum->HighPower = Max(poly1->HighPower, poly2->HighPower);
for (i = 1; i <= polysum->HighPower + 1; ++i)
{
tmp1 = poly1->Coeff.GetAt(i);
tmp2 = poly2->Coeff.GetAt(i);
sum = tmp1 + tmp2;
polysum->Coeff.AddTail(sum);
}
}

static void MulPolynomial(
Polynomial polymul,
const Polynomial poly1,
const Polynomial poly2
)
{
int i;
int j;
int tmp;
int tmp1;
int tmp2;

polymul->HighPower = poly1->HighPower + poly2->HighPower;

// initialize all elements to zero
for (i = 0; i <= polymul->HighPower; ++i)
polymul->Coeff.AddTail(0);

for (i = 0; i <= poly1->HighPower; ++i)
{
tmp1 = poly1->Coeff.GetAt(i + 1);
for (j = 0; j <= poly2->HighPower; ++j)
{
tmp = polymul->Coeff.GetAt(i + j + 1);
tmp2 = poly2->Coeff.GetAt(j + 1);
tmp += tmp1 * tmp2;
polymul->Coeff.SetAt(i + j + 1, tmp);
}
}
}

static void PrintPoly(const Polynomial poly)
{
int i;

for (i = poly->HighPower; i > 0; i-- )
printf( "%dX^%d + ", poly->Coeff.GetAt(i + 1), i);
printf("%d\n", poly->Coeff.GetHead());
}

int main()
{
Polynomial poly1 = NULL;
Polynomial poly2 = NULL;
Polynomial polyresult = NULL;

#ifdef _DEBUG
_CrtSetDbgFlag(_CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);
#endif

poly1 = new (struct tagPOLYNOMIAL);
if (NULL == poly1)
goto Exit0;

poly2 = new (struct tagPOLYNOMIAL);
if (NULL == poly2)
goto Exit0;

polyresult = new (struct tagPOLYNOMIAL);
if (NULL == polyresult)
goto Exit0;

// P1(X) = X^2 + 2X + 3
poly1->HighPower = 2;
poly1->Coeff.AddHead(0);
poly1->Coeff.AddHead(1);
poly1->Coeff.AddHead(2);
poly1->Coeff.AddHead(3);

// P2(X) = 3X^3 + 10X + 6
poly2->HighPower = 3;
poly2->Coeff.AddHead(3);
poly2->Coeff.AddHead(0);
poly2->Coeff.AddHead(10);
poly2->Coeff.AddHead(6);

// add result = 3X^3 + 1X^2 + 12X^1 + 9
AddPolynomial(polyresult, poly1, poly2);
PrintPoly(polyresult);

// reset
polyresult->Coeff.RemoveAll();

// mul result = 3X^5 + 6X^4 + 19X^3 + 26X^2 + 42X^1 + 18
MulPolynomial(polyresult, poly1, poly2);
PrintPoly(polyresult);

Exit0:
if (poly1)
{
delete poly1;
poly1 = NULL;
}
if (poly2)
{
delete poly2;
poly2 = NULL;
}
if (polyresult)
{
delete polyresult;
polyresult = NULL;
}
}

2.3.3 说明
原书中只给出了一元多项式的数组实现，而没有给出单链表的代码。实际上用单链表最大的好处在于多项式的项数可以为任意大。（当然只是理论上的。什么？你的内存是无限大的？好吧，当我没说……）

我没有实现减法操作，实际上减法可以转换成加法来完成，例如 a - b 可以换算成 a + (-b)，那么我们的目标就转变为做一个负号的运算了。至于除法，可以通过先换算“-”，然后再用原位加法来计算。（现在你明白加法有多重要了吧？^_^）有兴趣的话，不妨您试试完成它，我的目标只是掌握单链表的使用，因此不再继续深究。

给你编完了;在VC6下可以运行

#include
#include
using namespace std;
void cheng(int a[],int b[],int w)
{int shi[40];
for (int k=0;k<40;k++)
{shi[k]=0;}
for(int q=w;q>=0;q--)
{for(int p=w;p>=0;p--)
{
shi[q+p]=shi[q+p]+a[q]*b[p];
}
}
cout<for(int l=2*w;l>=0;l--)
{
cout<}
cout<<0<}
void main()
{
int i;int x[20];int y[20];
cout<<"请输入最高次幂为多少"<cin>>i;
for(int j=0;j<=i;j++)
{
cout<<"请输入第一个多项式"<cin>>x[j];
cout<<"请输入第二个多项式"<cin>>y[j];
}
cheng(x,y,i);
}