二、多项式相加

1、 实验目的

1）            掌握链表的灵活运用；

2）            学习链表初始化和建立一个新的链表；

3）            知道怎样去实现链表删除结点操作与插入结点；

4）            理解链表的基本操作（包括数据域数据的相加）并能灵活运用。

2、       实验内容

 建立两个链表为稀疏多项式，将他们每项按项相加，最后将得到的链表打印出来。

 要求：运用单链表来存储多项式，并且结果链表要用原来的链表空间，空间复杂度为O（1）

3、       数据结构及算法思想

 typedef int ElemType;

typedef struct CLNode

{

    ElemType coef;

    ElemType exp;

    struct CLNode *next;

} CLNode, *CLinkList;

    建立两个单链表，并按要求将结点数据相加，将结果链表存储在C中。

4、       模块化分

a)      主程序；2）初始化单链表；3）建立单链表； 4）相加多项式

5、       详细设计及运行结果

a)      设计思路分析

 要解决多项式相加，必须要有多项式，所以必须首先建立两个多项式，在这里采用链表的方式存储链表，所以我将结点结构体定义为

运用尾插法建立两条单链表，以单链表polya和polyb分别表示两个一元多项式A和B，A+B的求和运算等同于单链表的插入问题（将单链表polyb中的结点插入到单链表polya中），因此“和多项式”中的结点无须另生成。

  为了实现处理，设p、q分别指向单链表polya和polyb的当前项，比较p、q结点的指数项，由此得到下列运算规则：

① 若p->exp<q->exp，则结点p所指的结点应是“和多项式”中的一项，令指针p后移。

② 若p->exp=q->exp，则将两个结点中的系数相加，当和不为0时修改结点p的系数。

③ 若p->exp>q->exp，则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后移。

b)      运行结果