一元多项式求和问题的研究与实现学生姓名：指导老师：摘要在数学上，一个一元多项式可按升幂表示为：A(x)=a0+a1x+a2x2+……+anxn，它由n+1个系数唯一确定，一元多项式求和实质上是合并同类项的过程。

在实际应用中，多项式的指数可能很高且变化很大，在表示多项式的线性表中就会存在很多零元素。

因此，采用单链表来存储一个一元多项式的每一个非零项的系数和指数，即每一个非零项对应单链表中的一个结点，且单链表按指数递增有序排列，就可实现两个一元多项式求和问题。

程序通过调试运行，能基本达到设计要求，解决问题。

关键词数据结构；一元多项式；单链表；结点1 引言一个一元多项式可按升幂表示为：A(x)=a0+a1x+a2x2+……+a n x n，它由n+1个系数唯一确定。

因此，可以用一个线性表(a0，a1，a2，……，an)来表示，每一项的指数i隐含在其系数ai的序号里。

若有A(x)= a0+a1x+a2x2+……+a n x n和B(x)=b0+b1x+b2x2+……+b m x m，一元多项式求和也就是求A(x)=A(x)+B(x)，这实质上是合并同类项的过程。

1.1 设计目的设计合理数据结构表示一元多项式，并设计高效算法实现两个一元多项式相加。

1.2 设计要求本课程设计要求用C++实现两个一元多项式的求和问题，用带头结点的单链表村存储多项式。

基本功能要求如下：1．输入并建立多项式，输入形式为整数序列n，x1，y1，x2，y2，……，x n，y n。

其中n是多项式的项数，x i和y i分别是第i项的系数和指数。

2．输出多项式，按指数升序排列。

3．多项式A(x)和B(x)相加，建立多项式A(x)+B(x)，输出相加的多项式，形式为类数学表达式。

2 需求分析2.1 输入形式和输入值的范围从键盘依次输入两个多项式的项数，系数和指数。

系数为任意整数，项数和指数为大于等于0的整数。

2.2 输出形式从屏幕输出，显示用户输入的多项式，并显示两多项式相加后的多项式和值。

2.3 时间性能分析所谓时间性能是指实现基于某种存储结构的基本操作（即算法）的时间复杂度。

像取出线形表中第i个元素这样的按位置随机访问的操作，使用顺序表更快一些，时间性能为O(1)；相比之下，单链表中按位置访问只能从表头开始依次向后扫描，直到找到那个特定的位置，所需要的平均时间为O(n)。

在单链表中进行插入和删除操作不需要移动元素，在给出指向单链表中某个合适位置的指针后，插入和删除操作所需的时间仅为O(1)；而顺序表进行插入和删除操作需移动表长一半的元素，需要的平均时间为O(n)。

作为一般规律，若线性表需频繁查找却很少进行插入和删除操作，或其操作和“数据元素在线性表中的位置”密切相关时，宜采用顺序表作为存储结构；若线性表需频繁进行插入和删除操作，则宜采用单链表作为存储结构。

对于一元多项式求和问题，由于在实际应用中，多项式的指数可能很高且变化很大，一个较好的存储方法是只存非零元素。

这样，一个一元多项式的每一个非零项可由系数和指数唯一表示。

例如，S(x)=5+10x30+90x100就可以用线性表((5,0),(10,30)，(90,100))来表示。

如果采用顺序表存储，对于指数相差很多的两个一元多项式，相加会改变多项式的系数和指数。

若相加的某两项的指数不等，则将两项分别加在结果中，将引起顺序表的插入；若某两项的指数相等，则系数相加，若相加结果为零，将引起顺序表的删除。

因此采用顺序表可以实现两个一元多项相加，但并不可取。

因此，经过分析，在时间性能比较上适宜采用单链表存储，则每一个非零项对应单链表中的一个结点，且单链表应按指数递增有序排列。

2.4 空间性能分析所谓空间性能是指某种存储结构所占用的存储空间的大小。

如果数据域占据的空间较小，则指针的结构性开销就占去了整个结点的大部分，因而从结点的存储密度上讲，顺序表的存储空间利用率较高。

由于顺序表需要预分配一定长度的存储空间，如果事先不知道线性表的大致长度，则有可能对存储空间预分配得过大，致使存储空间得不到充分利用，造成浪费。

若估计得过小，又将发生上溢而造成存储空间的再分配；而单链表不需要为其预分配空间，只要有内存空间可以分配，单链表中的元素个数就没有限制。

在此问题中，一个多项式虽然是由一个包括系数和指数的线性表唯一确定的，可是在实际应用中，多项式的指数往往很高且变化很大，项数也不确定，在线性表中，元素变化较大或者未知时，最好使用单链表实现。

3 概要设计3.1 数据结构设计为了实现任意多项式的加法，通过以上的时间性能和空间性能分析，选择单链表的结构体，结点结构如图3.1所示。

图3.1 一元多项式链表的结点结构其中，valuea ：系数域，存放非零项的系数；valueb ：指数域，存放非零项的指数；next ：指针域，存放指向下一结点的指针。

3.2 程序模块设计根据以上对该一元多项式求和问题的功能要求和需求分析，到如图3.2所示的程序流程图。

图3.2 程序流程图valuea valueb next 选择1 选择2 选择4选择3 输入第一个多项式 两多项式相加 输出第一个多项式 退出程序输入第二个多项式 输出第二个多项式 输出结果运行程序7 0 2 8 12 3 4 1 6 3 2 8 5 20 7 28 ^5 12 ^4 详细设计4.1 菜单设计简单明了的主菜单是程序成功运行的首要条件。

在菜单函数中，调用了函数menuupdown()，该函数用来显示十五次短划线，用作菜单分隔符，使菜单清晰明了，易操作。

其中主要的输出语句如下：cout<<"\t\t\t ┃\t\t\t\t ┃"<<endl;cout<<"\t\t\t ┃\t1.输入一元多项式。

\t ┃"<<endl;cout<<"\t\t\t ┃\t2.输出一元多项式。

\t ┃"<<endl;cout<<"\t\t\t ┃\t3.两多项式相加。

\t ┃"<<endl;cout<<"\t\t\t ┃\t4.退出。

\t\t ┃"<<endl;cout<<"\t\t\t ┃\t\t\t\t ┃"<<endl;cout<<"\t\t\t";cout<<"┗";4.2 主模块设计该课程设计的主模块就是解决求和问题。

为运算方便，采用带头结点的单链表。

先举例分析两个多项式求和的执行过程。

设两个工作指针p 和q ，分别指向两个单链表的开始结点。

两个多项式求和实质上是对结点p 的指数域和结点q 的指数域进行比较，这会出现下列三种情况：(1)若p->valueb<q->valueb ，则结点p 应为结果中的一个结点，将指针p 后移。

示意如图4.1。

AqB图4.1 第一种情况示意图7 0 2 812 34 1 6 3 2 85 20 7 28 ^5 12 ^7 0 18 34 16 3 2 8 5 207 28 ^-2 87 0 18 34 12 8 5 20 7 28 ^ -2 85 12 ^5 12^(2)若p->valueb>q->valueb，则结点q应为结果中的一个结点，将q插入到第一个单链表中结点p之前，再将指针q后移。

示意如图4.2。

pAq qB图4.2 第二种情况示意图(3)若p->valueb=q->valueb，则p与q所指为同类项，将q的系数加到p的系数上。

若相加结果不为0，则将指针p后移，删除结点q；若相加结果为0，则表明结果中无此项，删除结点p和结点q，并将指针p和指针q分别后移。

示意如图4.3所示。

pAq qB(a)相加系数不为零p pAq qB(b)相加系数为零图4.3 第三种情况示意图算法用伪代码描述如下：1.工作指针p、q初始化；2.while（p存在且q存在）执行下列三种情形之一2.1 如果p->valueb<q->valueb，则指针p后移;2.2 如果p->valueb>q->valueb，则2.2.1 将结点q插入到结点p之前；2.2.2 指针q指向原指结点的下一个结点；2.3 如果p->valueb=q->valueb，则2.3.1 p->valuea=p->valuea+q->valuea；2.3.2 如果p->valuea==0，则执行下列操作，否则，指针p后移;2.3.2.1 删除结点p；2.3.2.2 使指针p指向它原指结点的下一个结点；2.3.3 删除结点q；2.3.4 使指针q指向它原指结点的下一个结点；3.如果q不为空，将结点q链接在第一个单链表的后面；上述伪代码描述的算法还有一个问题：将结点q插到结点p之前和将结点p删除需要知道结点p的前驱结点的地址；将结点q删除也需要知道结点q的前驱结点的地址。

所以，在每个单链表中应设两个工作指针。

4.3 类定义1．用单链表存储多项式每一非零项，为该单链表建立item，其类定义如下：class item{private:double valuea;double valueb;double corp;item * next;public:item(double ax,double bx) { }item( ) {cin>>valuea>>valueb;corp=0; next=NULL;}friend class operate;};在item类中，提供了如下成员函数：(1) 函数声明：item(double ax,double bx) { }；完成的功能：有参数构造函数，主要用于生成临时一元多项式的项和头指针。

(2) 函数声明：item( ) {cin>>valuea>>valueb;corp=0;next=NULL;}完成的功能：无参数构造函数，主要用于生成一元多项式时使用。

(3) 函数声明：friend class operate；完成的功能：为了能访问到类item的私有成员，operate应指定为item类的友元类。

2．为操作建立operate，其类定义如下：class operate{private:item * head,* record;public:operate();item * gethead();void creat();item* addsame(item* atemp);void show(item * show);operate operator + (operate lasts);};在operate类中，提供了如下成员函数：(1) 函数声明：operate( )；完成的功能：无参数构造函数，用于生成链表头。