多项式的加法与乘法.docx
《多项式的加法与乘法.docx》由会员分享,可在线阅读,更多相关《多项式的加法与乘法.docx(18页珍藏版)》请在冰点文库上搜索。
多项式的加法与乘法
多项式的加法与乘法
1、课题内容和要求
给定两个多项式,用程序实现这两个多项式的相加和相乘。
(可以利用单链表法实现)
例如给定多项式x+3x2-4x3+5x4和多项式x2+3x3-4x4。
2、需求分析
整个程序中有两个大类,项结点的Term类和多项式的polynominal的类。
Term类用以存放项结点,polynominal类用以构建多项式的每一项。
而在进行多项式的加法和乘法时要进行多次的插入和删除操作,因此采用线性表的链接存储。
主要的实现函数有多项式类的输入输出函数,多项式的相加函数,多项式的相乘函数,几个友元函数。
而多项式类的构造函数和析构函数也是必不可少的。
最后加上主函数即能完成课题内容和要求。
3、概要设计
先定义链表类型结点和一元多项式,然后申明各个功能函数,并编写功能函数的算法,然后定义一个主函数,用于调用各个功能函数。
其中输入输出函数由链表进行存储。
其系统结构如图所示:
一元多项式的创建流程图如下:
N
Y
(1)一元多项式的创建流程图
(2)多项式相加流程图
(3)多项式的相乘流程图
四、详细设计
在定义多项式类polynominal之前,首先构建一个项结点的c++类Term,用以存放系数coef和指数exp。
具体实现代码如下:
classTerm
{public:
Term(intc,inte);
Term(intc,inte,Term*nxt);
Term*InsertAfter(intc,inte);//在this指针指示的结点后插入新结点
private:
intcoef;
intexp;
Term*link;
friendostream&operator<<(ostream&,constTerm&);//重载"<<",输出多项式的一项
friendclassPolynominal;
};
Term:
:
Term(intc,inte):
coef(c),exp(e)
{link=0;
}
Term:
:
Term(intc,inte,Term*nxt):
coef(c),exp(e)
{link=nxt;
}
Term*Term:
:
InsertAfter(intc,inte)
{link=newTerm(c,e,link);//为新项申请结点的存储单元,并用Term函数将
returnlink;//c,e和this->link的值填入新结点的相应域
}
其中公有成员函数InsertAfter的功能是建立一个新的项结点,系数为c,指数为e,并将新结点插入调用该函数项结点及其后继结点之间。
执行过程如下:
在图a所示的链表中,调用q1->InsertAfter(3,14)。
函数InsertAfter将执行第一条语句link=newTerm(c,e,link)。
该语句中有两处link没有明确指定是哪个结点的link域,那么他们就是this指针指向的link域。
由于是q1调用的InsertAfter,按c++语法,this就是q1,link域就是q1指向的结点的link域,因此可以将语句link=newTerm(c,e,link)看成是q1->link=newTerm(c,e,q1->link)。
先将执行该语句赋值号右边newTerm(c,e,q1->link),即先申请新项结点的存储单元(如图b所示),然后调用Term类的三个参数的构造函数Term(intc,inte,Term*next),将c、e和q1->link的值分别赋给新相结点的coef、exp和link域(如图c所示),最后执行赋值,即将新项结点的地址赋值给q1的link域,最终结果(如图d所示)。
qx
-
此时通过重载运算符“<<”实现一个项结点的输出。
输出时,用coefX^exp形式表示coefxexp
例如,用-4x^2表示-4x2
下面还要构建多项式的c++类。
具体代码如下:
classPolynominal
{public:
Polynominal();
Polynominal&operator=(Polynominal&);
voidAddTerms(istream&in);//输入多项式的各项,构造多项式链表
voidOutput(ostream&out)const;//将多项式送输出流
voidPolyAdd(Polynominal&r);//多项式相加
voidPolyMul(Polynominal&r1,Term*r2);
voidPolyMul(Polynominal&r1,Polynominal&r2);//多项式相乘
private:
Term*theList;//单循环链表的表头指针
voidClear();
friendostream&operator<<(ostream&,constPolynominal&);
friendistream&operator>>(istream&,Polynominal&);
friendPolynominal&operator+(Polynominal&,Polynominal&);
friendPolynominaloperator*(Polynominal&,Polynominal&);
};
上述程序中给出了多项式类Polynominal的定义,其中包括3个公有函数成员:
AddTerm、Output和PolyAdd。
AddTerms函数通过输入流in,输入多项式的各项构造一个多项式的单循环链表;Output函数将多项式按降幂方式送输出流;PolyAdd函数将多项式r加到指针this指示的多项式上。
可以通过重载运算符“<<”,”>>”和“+”,并将它们定义为多项式类的友元函数的方法,使之更符合输入输出和多项式运算的书写习惯。
既然已经有了我们需要的两大类,现在就可以编写相应的具体实现函数,来实现我们需要的功能。
当然首先需要的是多项式类的构造和析构函数。
具体代码如下:
Polynominal:
:
Polynominal()//创建多项式的空的单循环链表
{theList=newTerm(0,-1);//分配表头结点的存储单元
theList->link=theList;//构成循环链表
}
voidPolynominal:
:
Clear()//撤销多项式的单循环链表
{
Term*p=theList->link;
while(p!
=theList)
{theList->link=p->link;//删除p结点
deletep;//释放p之存储空间
p=theList->link;//p指向下1个待删除结点
}
}
有了上述条件现在就可以建立多项式的输入输出函数,具体代码如下:
voidPolynominal:
:
AddTerms(istream&in)//按降幂输入各项,构造单循环链表
{Term*q=theList;
intc,e;
for(;;)
{cout<<"按降幂输入多项式的系数和指数(exp,coef)以(0,0)结尾。
"<cin>>c>>e;
if(c==0&&e==0)break;//当输入的指数小于0时,构造过程结束
q=q->InsertAfter(c,e);//将c,e插入表尾结点q之后
}
}
voidPolynominal:
:
Output(ostream&out)const
{intfirst=1;Term*p=theList->link;
for(;p!
=theList;p=p->link)
{if(!
first&&(p->coef>0))out<<"+";//在非第一项的正系数前输出+号
first=0;
out<<*p;//调用Term类上重载的"<<"操作
}
cout<}
AddTerms函数从输入流in按降幂输入各项(c,e)来构造多项式的单循环链表,当输入(0,1)时构造结束。
Output函数遍历单循环链表将多项式按降幂方式送输出流,它调用项类Term上重载的“<<”操作符实现按项输出。
当上述所有的基础功能模块都完成时,我们就可以着手开始编写最重要的函数代码,多项式的相加和相乘函数了。
首先来分析下多项式相加的算法。
设有多项式p(x)和q(x),分别用单循环链表表示。
现将两个多项式相加,结果仍称为q(x),p(x)不变,即实现q(x)<-q(x)+p(x)。
设p和q分别指向多项式p(x),q(x)的当前正进行比较的项结点,初始时分别指向两多项式中最高次幂的项结点。
q1指向q的前驱结点。
对p(x)进行遍历,根据指针p,q的exp域的大小情况做相应处理实现加法运算。
多项式相加的算法步骤如下:
(1)若p->expexp,则q指示的项应该成为结果多项式中的一项,所以q1和q向右移一项,指针p不动。
(2)若p->exp==q->exp,则系数相加,即q->coef=q->coef+p->coef。
如果q->coef不为零,则指针q1和q均右移一个节点,否则从q(x)中删除q指示的结点,指针p右移一项。
(3)若p->exp>q->exp,则复制p指向的结点,并将其插入在q1之后,指针p右移一项。
重复上述处理,直到p(x)中全部结点都处理完。
下面给出多项式的相加函数:
//程序2.10多项式相加函数
voidPolynominal:
:
PolyAdd(Polynominal&r)
{//将多项式r加到多项式this上
Term*q,*q1=theList,*p;//q1指向表头结点
p=r.theList->link;//p指向第一个要处理的结点
q=q1->link;//q1是q的前驱,p和q就指向两个当前进行比较的项
while(p->exp>=0)//对r的单循环链表遍历,直到全部结点都处理完
{while(p->expexp)//跳过q->exp大的项
{q1=q;q=q->link;
}
if(p->exp==q->exp)//当指数相等时,系数相加
{q->coef=q->coef+p->coef;
if(q->coef==0)//若相加后系数为0,则删除q
{q1->link=q->link;delete(q);
q=q1->link;//重置q指针
}
else
{q1=q;q=q->link;//若相加后系数不为0,则移动q1和q
}
}
else//p->exp>q->exp的情况
q1=q1->InsertAfter(p->coef,p->exp);//以p的系数和指数生成新结点,插入q1
p=p->link;
}
}
voidPolynominal:
:
PolyMul(Polynominal&r1,Term*r2)
{Term*p=r1.theList->link,*q=theList;
while(p->exp>=0)
{q=q->InsertAfter(p->coef*r2->coef,p->exp+r2->exp);
p=p->link;
}
}
voidPolynominal:
:
PolyMul(Polynominal&r1,Polynominal&r2)
{Polynominalpoly;
Term*p=r2.theList->link;
while(p->exp>=0)
{poly.PolyMul(r1,p);
PolyAdd(poly);
poly.Clear();
p=p->link;
}
}
多项式相加函数完成后,我们来看看多项式相乘函数:
voidPolynominal:
:
PolyMul(Polynominal&r1,Term*r2)
{Term*p=r1.theList->link,*q=theList;
while(p->exp>=0)
{q=q->InsertAfter(p->coef*r2->coef,p->exp+r2->exp);
p=p->link;
}
}
voidPolynominal:
:
PolyMul(Polynominal&r1,Polynominal&r2)
{Polynominalpoly;
Term*p=r2.theList->link;
while(p->exp>=0)
{poly.PolyMul(r1,p);
PolyAdd(poly);
poly.Clear();
p=p->link;
}
}
然后给出几个友元函数:
//程序2.11多项式C++类的几个友员函数。
ostream&operator<<(ostream&out,constPolynominal&x)
{x.Output(out);
returnout;
}
istream&operator>>(istream&in,Polynominal&x)
{x.AddTerms(in);
returnin;
}
Polynominal&operator+(Polynominal&a,Polynominal&b)
{a.PolyAdd(b);
returna;
}
Polynominaloperator*(Polynominal&a,Polynominal&b)
{Polynominalr;
r.PolyMul(a,b);
returnr;
}
最后给出主函数:
voidmain()
{
Polynominalp,q,q1;
cin>>p;cout<<"p="<
cin>>q;cout<<"q="<q1=q;
q=q+p;
cout<<"q2=p+q="<q1=q1*p;
cout<<"q1=q1*p="<}
5、测试数据及其结果分析
测试用例为:
多项式x+3x2-4x3+5x4和多项式x2+3x3-4x4
图示为输入第一个多项式p:
x+3x2-4x3+5x4
图示为输入第二个多项式并计算出结果。
六、调试过程中的问题
出现的问题有很多,现在只截取一个简单的且具有代表性的问题如图所示:
这个问题是众多小问题的一个代表,告诫我,以后要在编程中细心,不仅需要注意算法,同时也要注意细节。
七、程序设计总结
虽然多项式的加法和乘法运算这个程序不是很难,尤其在自己已经刚刚学过了数据结构单链表部分后,但在两个星期的编程中自己仍碰到了不少问题,暴漏了自己在编程中的不足,导致很多问题都要求助网络或同学。
由此坚定了我以后要踏踏实实学好编程,注重算法,更注重细节的准则。
,