数据结构第二次实验报告
问题描述：
在数学上，一个一元n次多项式Pn(x)可按降序写成： Pn(x) = pxn+ pxn?1+…+px+p0
nn?11它是由n＋1个系数唯一确定。因此，在计算机里它可以用一个线性表P来表示：
P=（Pn, Pn-1, …, P1, Po）
一元多项式的运算包括加法、减法和乘法，而多项式的减法和乘法都可以用加法来实现。
设Pn(x)和Qm(x)分别为两个一元多项式。试编写程序实现一元多项式的加法运算。
一、需求分析
1、本程序要求用基于线性表的基本操作来实现一元多项式的加法运算，并且需要利用有序链表来实现线性表 2、输入输出的的形式：
输入
输入多项式的项数：4 //表示第一个多项式的项数 输入多项式的各项（系数在前 幂次在后）： 9， 15（回车） //表示9x15 7， 8 （回车） 5， 3 （回车） 3， 1 （回车） 输出 （按降幂输出）
数据结构第二次实验报告
输入的多项式是：+9x^15+ 7x^8+5x^3+3x^1 输入多项式的项数：3 //表示第二个多项式的项数 输入多项式的各项（系数在前 幂次在后）： 6， 3（回车） -7， 8（回车） 2， 0 （回车） 输出
输入的多项式是：-7x^8+ 6x^3+2x^0 他们求和后的多项式是： 9x^15+11x^3+3x^1+ 2x^0
3、输入值得范围：项数为短整型，每一项的系数和幂次为double类型，不对非法输入进行处理，即假定所有的输入都是合法的 4、测试数据： 输入多项式的项数5
输入多项式的各项（系数在前 幂次在后） 9 15 8 9 -7 6 5 4 3 2
输入的多项式是+9x^15+8x^9-7x^6+5x^4+3x^2 输入多项式的项数4
数据结构第二次实验报告
输入多项式的各项（系数在前 幂次在后） 7 12 8 9 7 6 2 1
输入的多项式是+7x^12+8x^9+7x^6+2x^1 他们求和后的多项式是
+9x^15+7x^12+16x^9+5x^4+3x^2+2x^1
二、概要设计
1、抽象数据类型：为实现以上功能，根据题目要求，采用单链表来存储多项式，并声明一个节点类Node，其公有数据类型为两个int型变量用来保存多项式每一项的系数和幂次，以及一个next指针用以指向多项式的下一项。 单链表类的基本操作如下：
sNode(int size=0){ this->size= size;Init();}//建立链表
void setpHead(); //设置链表的表头指针
Node* Remove(Node* t1);//将节点t1放到链表中的正确位置（按降幂排序）
Node* Insert();//插入一个新的节点
void setPloy();//读入多项式并将读入的多项式存储在链表中 void Print(int m,int n);//输出多项式的某一项 void PrintInfo();//输出读入的多项式（降幂输出）
数据结构第二次实验报告
void PloyAdd(sNode s1,sNode s2);//多项式求和并输出求和结果
2、算法的基本思想：
（1）：Node* Remove(Node* t1)函数功能是将从键盘读入的节点t1插入到链表中的正确位置。再插入t1之前的链表是按降幂排好的，所以可从链表的第一个节点开始查找，当某一节点的幂次小于t1的幂次的时候，将t1插到该节点之前即可。当t1的幂次大于表头结点的幂次时单独处理。（即插入排序）
（2）：void PloyAdd(sNode s1,sNode s2)函数的功能是实现两个多项式的加法并打印出其结果。其参数为两个链表s1,s2。从s1,s2的头结点开始运算，如果他们的幂次相同，则将他们的系数相加并把相加后的项输出，并且指针分别后移一位；否则，输出幂次较高的那一个节点项，并将该节点的指针后移一位。若当一个链表的节点已扫描完全而另一链表的节点没有时，顺序输出器为扫描的项即可。 3、主程序的流程：该主程序有六个模块 （1）创建两个链表类对象N1,N2
（2）从键盘读入N1的项数和各项的系数即幂次，并将其存储到链
表N1中（建立链表的过程）
（3）调用N1的成员函数PrintInfo ()输出建立的多项式
（4）从键盘读入N2的项数和各项的系数即幂次，并将其存储到链
表N2中
（5）调用N2的成员函数PrintInfo ()输出建立的多项式
数据结构第二次实验报告
（6）调用N1的成员函数PloyAdd (N1,N2)做加法并将结果输出
三、详细设计
1、物理数据结构：题目没给输入数据的类型和规模限制，但根据具体情况分析应采用短整型保存多项式的项数，用double类型来保存每一项的系数和幂次，根据题目要求，用单链表存储多项式。 2、算法的时空分析和改进设想：
（1）建立链表的函数 void setPloy()采用插入排序的方法在读入一个新的节点时即将其放在链表的正确位置上，该算法最佳情况（即用户输入的多项式是按降幂排好的）的时间复杂度为O(n),最坏情况下（即用户输入的多项式是升幂次序）的时间复杂度为O(n2).由于是采用链表的方式实现的线性表，所以在插入排序时省去了许多赋值语句。
（2）加法器PloyAdd (N1,N2)函数是由几个一层while循环和简单语句实现，所以其时间复杂度为O(n)。
3、函数的调用关系
创建两个连表类对象N1,N2 调用N1的函数setPloy ()构建链表 调用N1的函数Insert()建立链表——>调用函数Remove(Node* t1)实现有序插入 调用N1的函数PrintInfo()输出多项式N1——>调用函数Print(double m,double n)输出每一项 调用N2的函数setPloy ()构建链表（调用关系类同N1. setPloy ()） 调用N2的函数PrintInfo()输出多项式N2——>调用函数Print(double m,double n)输出每一项 调用N1的函数setpHead()设置表头 主函数
调用N1的函数PloyAdd (N1,N2实现加法——>调用函数Print(double m,double n)输出求和后的每一项