多项式加法实验报告

题 目： 多项式加法

多项式加法

一、 课题概述

线性表是一种最简单、最基本，也是最常用的数据结构，其用途十分广泛，例如，用带表头结点的单链表求解一元整系数多项式加法和乘法运算。现给两个一元整系数多项式，请求解两者之和。

输入

两组数据，每一组代表一个一元整系数多项式，有多行组成，其中每一行给出多项式每一项的系数和指数，这些行按指数递减次序排序，每一组结束行为0 -1。

输出

三组数据，前两组为一元整系数多项式，最后一组为两个多项式的和。 一元整系数多项式输出形式如下： （1）多项式项4x输出为4X （2）多项式项4x2输出为4X^2

（3）第一项系数为正数时，加号不要输出

（4）除常系数项外，项系数为1不显式输出，-1输出为-

例如，4x3- x2+x-1正确输出形式为4X^3-X^2+X-1，错误输出形式为 +4X^3-1X^2+1X-1

1

二、 设计与实现

1、类的层次关系及核心算法分析：

项节点类Trem中定义了三个私有变量，系数coef、指数exp和指向下一个项节点的指针域link。多项式类Polynominal被声明成项节点类Trem类的友元类。公有函数InsertAfter构造一个新的项节点，其系数为c指数为e,并将新节点插入在调用该函数的项节点及后继节点之间。

多项式类Polynominal中包含了3个公有成员函数：AddTerms，Output和 PolyAdd。AddTerms函数通过输入流in,输入多项式的各项构造一个多项式的单循环链表；Output函数将多项式按降幂方式送输出流；PolyAdd函数实现将多项式r加到指针this指示的多项式上。AddTerms函数从输入流in按降幂输入各项（c,e）来构造多项式的单循环链表，当输入（0，-1）是构造过程结束。Output函数遍历单循环链表将多项式按降幂方式送输出流，它调用项类Trem上重载的“<<”操作符实现按项输出。

多项式加法，设有多项式p(x)和q(x),分别用单循环链表表示。

设p和q分别指向多项式p(x)和q(x)的当前正进行比较的项节点，初始时分别指向两多项式中最高幂次的项节点。q 1指向q的前驱节点。对p(x)进行遍历。直到处理完所有节点。当p->expexp，则q指示的项应该为多项式结果中的一项，所以q 1和 q 右移一项，指针p不动。当多项式指数相等时（p->exp=q->exp），系数相加，即q->coef=q->coef+p->coef。加完之后如果系数为0，则删除节点，p右移一项，如果加完之后系数不为0，指针q 1和q均右移一个节点。当p->exp>q->exp，则复制p所指示的节点，并将其插入在q 1后；指针右移一个节点。

2