1、- 1 -多项式的加法与乘法1、课题内容和要求给定两个多项式，用程序实现这两个多项式的相加和相乘。 （可以利用单链表法实现）例如给定多项式 X+3X2-4X3+5X4 和多项式 X2+3X3-4X4。2、需求分析整个程序中有两个大类，项结点的 TERM 类和多项式的 POLYNOMINAL的类。T ERM 类用以存放项结点，POLYNOMINAL 类用以构建多项式的每一项。而在进行多项式的加法和乘法时要进行多次的插入和删除操作，因此采用线性表的链接存储。主要的实现函数有多项式类的输入输出函数，多项式的相加函数，多项式的相乘函数，几个友元函数。而多项式类的构造函数和析构函数也是必不可少的。最后加
2、上主函数即能完成课题内容和要求。3、概要设计先定义链表类型结点和一元多项式，然后申明各个功能函数，并编写功能函数的算法，然后定义一个主函数，用于调用各个功能函数。其中输入输出函数由链表进行存储。其系统结构如图所示：一元多项式的加法乘法运算一元多项式的创建一元多项式的乘法一元多项式的加法一元多项式的消除- 2 -一元多项式的创建流程图如下：NY（1）一元多项式的创建流程图开 始创建一个含有 n 个链表类型结点的项按降幂分别输入各项系数和指数系数指数均小 0？一元多项式创建成功- 3 -（2）多项式相加流程图 开 始判断输入的 p 多项式系数=0?P q 指数相等时系数相加当 q 的系数大于p，则
3、跳过 q-exp大的项当 q 的系数小于 p，则 p 的系数和指数生成新的节点插入 p进行运算- 4 -开 始给出两个多项式将系数相乘，指数相加将运算结果相加，并输出（3）多项式的相乘流程图四、详细设计在定义多项式类 polynominal 之前，首先构建一个项结点的 c+类 Term，用以存放系数 coef 和指数 exp。具体实现代码如下：class Term public:Term(int c,int e);Term(int c,int e,Term* nxt);Term* InsertAfter(int c,int e); /在 this 指针指示的结点后插入新结点private:in
4、t coef;int exp;Term *link;friend ostream friend Polynominalfriend Polynominal operator *(Polynominal ;上述程序中给出了多项式类 Polynominal 的定义，其中包括 3 个公有函数成员：AddTerm、Output 和 PolyAdd。AddTerms 函数通过输入流 in，输入多项式的各项构造一个多项式的单循环链表；Output 函数将多项式按降幂方式送输出流；PolyAdd 函数将多项式 r 加到指针 this 指示的多项式上。可以通过重载运算符“”和“+”，并将它们定义为多项式类的友
5、元函数的方法，使之更符合输入输出和多项式运算的书写习惯。既然已经有了我们需要的两大类，现在就可以编写相应的具体实现函数，来实现我们需要的功能。当然首先需要的是多项式类的构造和析构函数。具体代码如下：Polynominal:Polynominal() /创建多项式的空的单循环链表 theList=new Term(0,-1); /分配表头结点的存储单元theList-link=theList; /构成循环链表void Polynominal:Clear() /撤销多项式的单循环链表Term* p=theList-link;while(p!=theList) theList-link=p-link
6、; /删除 p 结点delete p; /释放 p 之存储空间p=theList-link; /p 指向下 1个待删除结点有了上述条件现在就可以建立多项式的输入输出函数，具体代码如下：void Polynominal: AddTerms(istream int c,e;for(;) coutce;- 9 -if (c=0 /当输入的指数小于 0 时，构造过程结束q=q-InsertAfter(c,e); /将 c,e 插入表尾结点 q 之后void Polynominal:Output(ostream Term *p=theList-link;for ( ; p!=theList ; p=p-
7、link) if (!first /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=q
8、1-link; /重置 q 指针else q1=q; q=q-link; /若相加后系数不为 0，则移动 q1和 qelse /p-expq-exp 的情况 q1=q1-InsertAfter(p-coef,p-exp); /以 p 的系数和指数生成新结点，插入 q1p=p-link;void Polynominal:PolyMul(Polynominalwhile(p-exp=0) q=q-InsertAfter(p-coef*r2-coef,p-exp+r2-exp);p=p-link;void Polynominal:PolyMul(PolynominalTerm *p=r2.theList-link;while(p-exp=0) poly.PolyMul(r1,p);PolyAdd(poly);poly.Clear();p=p-link;
