数据结构实验报告
实验名称：实验一题目3 一元多项式
学生姓名：许虎
班级：信通20
班内序号：10
学号：2011210578
日期：2012年11月2日
1．实验要求
实验目的：
利用线性表实现一个一元多项式Polynomial
f(x) = a0 + a1x + a2x2 + a3x3+ … + a n x n
并实现相应功能。
实验内容：
使用一元多项式类存储多项式元素，通过定义并实现相关函数完成相应的功能，并通过设计的main函数测试了其正确性。用户可自行输入正确的多项式进行相关运算，得到相应结果。
相关函数实现的功能：1.能够实现一元多项式的输入和输出
2.能够进行一元多项式相加
3.能够进行一元多项式相减
4.能够计算一元多项式在x处的值
5.能够计算一元多项式的导数
6.能够进行两个一元多项式相乘
2. 程序分析
2.1 存储结构
存储结构：单链表（带头节点）
单链表示意图如下：
在本程序中使用结构类型element（赋给模版类型T）数组data储存数据成员，包含coef（系数）和exp（指数）两个成员，但仍为一维数组。在节点构造类型Node（运用了模版类）中定义了指针域next指向下一个结点，直到链表尾将next置空，front头指针为该链表类私有数据成员，如此得到多项式链表（单链表）。
2.2 关键算法分析
1、关键算法：
1）一元多项式类求和函数
（1）初始化工作指针p_prior(指向A链表头结点),p(p->next)，q(指向B链表第一个结点)。
（2）若p和q都不为空，则循环下列操作：
（3）若p->data.expdata.exp，则p_prior=p;p=p->next。
（4）否则，若p->data.exp>q->data.exp，则：
将q结点加入到A链表p结点之前，q指向B链表下移个结点。
（5）否则，p->data.coef=p->data.coef+q->data.coef;
（6）若p->data.coef==0，删除p结点，p指向下一个结点，删除q结点，q指向下一个结点。
（7）跳出循环，若p为空且q不为空，则将q结点及其后所有结点追加到A链表的最后。
（8）将B链表置空。
2）一元多项式相乘函数
（1）设置两个空链表分别为C、D，其中C为储存X每个元素链表与Y链表全部元素相乘结果的链表，D为最终两个多项式相乘结果的链表。
（2）初始化工作指针p1（X链表第一个结点），p2（Y链表第一个结点）。
（3）若p1不为空，则循环下列操作：
（4）初始化工作指针p3（指向C链表头结点），临时指针temp（p2）。
（5）当Y链表第一个结点存在，即temp非空时，则循环下列操作：
（6）定义新结点s，储存X链表中一个元素与Y链表中一个元素相乘结果，将此结点插入C链表中。
（7）如（6）操作，使用尾插法建立了C链表。
（8）跳出内循环，将C链表加到D链表中，C链表被置空，p1指针后移一个。
（9）跳出外循环，打印出最终的D链表。
2、代码详细分析：
1）一元多项式类求和函数
（1）情况1,X链元素指数小于Y链元素（p->data.exp < q->data.exp）
①p_prior=p;
②p=p->next;
情况1示意图
（2）情况2，X 链元素指数大于Y 链元素
①p_prior->next=q;
②p_prior=q;
③q=q->next;
④p_prior->next=p;
情况2示意图
（3）情况3，指数相等可相加的情况
（Ⅰ）合并系数为零
① p_prior->next = p->next;
② delete p;
③ p = p_prior->next;
④ Node * temp = q;
⑤ q = q->next;
⑥ delete temp;
(Ⅰ)示意图
（Ⅱ）合并系数不为零
① p_prior = p;
② p=p_prior->next;
③ Node * temp = q;
④
q = q->next; ⑤ delete temp;
① p_prior->next=q;
2
）一元多项式相乘函数
(1)每次外循环用尾插法得到链表C
①s->data.coef=p1->data.coef*temp->data.coef;
s->data.exp=p1->data.exp+temp->data.exp;
②p3->next=s;
③p3=s;
④p3->next=NULL;
示意图
以上相应算法步骤说明参见关键算法部分，在此不再赘述。
3、计算关键算法的时间、空间复杂度
1）一元多项式类求和函数
时间复杂度为O （n ），空间复杂度为O （n ）
2）一元多项式相乘函数
时间复杂度为O （n^2），空间复杂度为O （n^2）
2.3 其他
相应的减法函数Sub 为将Y 链个元素系数置空后调用加法函数Add 得到，在此不做具体说明。求多项式的值函数GetValue 和求导函数Dir 并未改变整个链表的结构，所以不做具体说明。在相乘函数Mul 中传入的形参引用空链表C 、D 为在main 函数中预先定义的对象，并未写入这个多项式类中。
