如何用链表实现一元多项式相加

杜金庭 唐海川

一元多项式的表示在计算机内可以用链表来表示，为了节省存储空间，只存储多项式中系数非零的项。 链表中的每一个结点存放多项式的一个系数非零项，它包含三个域，分别存放该项的系数、指数以及指向下一个多项式项结点的指针。对于如何利用链表将两个一元多项式分别存入两个链表中，通过相加将链表合并后并输出合成后的新的一元多项式。在运行的过程中主要所运用的就是利用链表的data域相加完成链表的加法运算，输出相加之后的新一元多项式。

数据结构的存储结构有两种：顺序储存结构和链式储存结构，而我们所做的一元多项式的相加及其表示，就是我们要把算法想象成是一种抽象的运行算法，将一元多项式抽象的想象成一个新的线性表。

程序流程如下：

使用typedef 和 struct 定义的新类型名称，其用途与内建类型的名称相同，可以用来：声明和初始化结构体变量;创建并根据自己的意愿初始化结构数组，用链表表示多项式时，每个链表结点储存多项式中的一个非零项，包括系数（data1）和指数（data2）两个数据域及一个指针域（next）。对应的数据结构定义为：

typedef struct LNode

{

int data1;//系数

int data2;//指数

struct LNode *next;//指向下一节点的指针

}LNode， *LinkList;

之后需要初始化链表：因为实现目的过程需要使用链表进行算法的实现，所以开始时需要先创建两个有头结点的空链表，因为初始化的链表拥有两个data域（data1，data2）和一个指针域（next），我们要利用后插法建立单链表，将“X”的系数放入data1中，幂放入data2中，这样指针域next就可以存放下一个节点的地址，初始化函数void Init（LinkList *L）是一个无参函数，这样就能成功实现链表的初始化。

在接下来的过程中，所用到的输入函数LinkList Creat（int n）是一个无返回值的有参函数，用于输入系数和指数。然后通过为“s”申请一块大小为（sizeof（LinkList））的内存，生成一个新的节点“*s”，之后就可以输入多项式当前项的系数和指数然后付给新结点*s的数据域。

根据代码可以判断，我们将要进行指数大小判断，比较函数int Compare（int a， int b）

当p1的指数大于p2的指数时，函数返回1，当p1的指数小于p2的指数时，返回-1，当p1的指数等于p2的指数时，返回0.

连接函数void Attach（int c， int d， LinkList *pRear）

该连接函数用于把得到的结果多项式一项一项的接到用front记录结果多项式链表的头结点的后面，为“p”申请一个新的节点，“p->date1/date2=c/d”表示对“p”这一链表拥有两个data域（data1，data2）进行赋值，将其当前所指向的新结点插入到这一时刻多项式所表达的尾部。

void Attach（int c， int d， LinkList* pRear） {

LinkList p;

p = （LinkList）malloc（sizeof（LinkList））;

p->data1 = c;

p->data2 = d;

p->next = NULL;

（*pRear）->next = p;

*pRear = p;

}

多项式相加函数LinkList PolyAdd（LinkList p1， LinkList p2）

该函数作为代码核心函数，作用是将两个一元多项式中指数相同的每一项加在一起，并返回结果多项式的首地址。首先利用“front”申请新的节点，将结果多项式链表的头节点用前面的“front”来进行记录，。在运算的过程中，就会出现两个多项式可能都有非零项需要进行处理，如果说“p1”的指数大于“p2”的指数，那么“p2”的系数和指数都将会存入多项式链表中，存储完成后，“p2”将会继续指向下一节点，

由此可知，对于“p1”和“p2”的互相比较，为的就是哪一个先进行存入和指向下一步，同理，如果“p1”的指数小于“p2”的指数，那么“p1”的系数和指数都将会存入多项式链表中，存储完成后，“p1”将会继续指向下一节点，当然也不能忘记 “p1”和“p2”的指数相同这种情况，那么和刚刚的两种就会有些不同，他们会将自身相同的系数相加，相加完成之后生成的系数和“p1”的指数存入多项式链表，同时“p1”和“p2”指向下一个节点。

节点的插入也会有顺序之分，当“p1”和“p2”两者中其中有一方已经完全的插入了多项式链表，那么紧接其后的就是另一方全部的插入多项式链表里，插入完成后让上一结构内的“front”去指向结果多项式的第一个非零项，这样就会将释放一个临时空表头结点。

void PrintAns（LinkList ans）这部分的结构体，目的是为了将结果进行打印，将链表中第一个节点输出并指向下一节点，输出后开始对后续的节点依次进行输出，如果链表结束，输出的就是“0”。大部分的结构的进程或者注释都进行了很详细的注释，接下来就是对于我们这个一元多项式的相加进行测验，首先我们要做的就是属于第一个 多项式有几项，第二个多项式有几项，输入的第一个多项式要按照系数指数的顺序进行输入，同理，第二个多项式的顺序与第一个多项式的顺序相同，当然输入的项式的多少，取决于你要测试的项数，所后进行調式，产生最终的运算结果。

一元多项式的相加是对创建链表使用链表最简单的一种运用，大多数函数的使用更需要注重的是函数与函数之间的相互配合，下面所表述的是对实现一元多项式相加的全部代码：

代码主体：

#include

#include

typedef struct LNode

{

int data1;

int data2;

struct LNode* next;

} LNode， * LinkList;

void Init（LinkList* L） {

*L = （LinkList）malloc（sizeof（LinkList））;

（*L）->next = NULL;

}

LinkList Creat（int n） {

LinkList h， s， t;

t = h = （LinkList）malloc（sizeof（LinkList））;

for （int i = 0; i < n; i++） {

s = （LinkList）malloc（sizeof（LinkList））;

h->next = s;

h = s;

scanf（"%d%d"， &s->data1， &s->data2）;

}

h->next = NULL;

t = t->next;

return t;

}

int Compare（int a， int b） {

if （a > b）

return 1;

if （a < b）

return -1;

if （a == b）

return 0;

}

void Attach（int c， int d， LinkList* pRear） {

LinkList p;

p = （LinkList）malloc（sizeof（LinkList））;

p->data1 = c;

p->data2 = d;

p->next = NULL;

（*pRear）->next = p;

*pRear = p;

}

LinkList PolyAdd（LinkList p1， LinkList p2） {

LinkList front， rear， temp;

int sum;

rear = （LinkList）malloc（sizeof（LinkList））;

front = rear;

while （p1 ！= NULL && p2 ！= NULL） {

if （Compare（p1->data2， p2->data2） == 1） {

Attach（p2->data1， p2->data2， &rear）;

p2 = p2->next;

} else if （Compare（p1->data2， p2->data2） == -1） {

Attach（p1->data1， p1->data2， &rear）;

p1 = p1->next;

} else if （Compare（p1->data2， p2->data2） == 0） {

sum = p1->data1 + p2->data1;

if （sum ！= 0）

Attach（ sum， p1->data2， &rear）;

p1 = p1->next;

p2 = p2->next;

}

}

for （; p1 ！= 0; p1 = p1->next）

Attach（p1->data1， p1->data2， &rear）;

for （; p2 ！= 0; p2 = p2->next）

Attach（p2->data1， p2->data2， &rear）;

rear->next = NULL;

temp = front;

front = front->next;

free（temp）;

return front;

}

void PrintAns（LinkList ans） {

if（ans==NULL） {

printf（"0"）;

} else {

printf（"%dX^%d "，ans->data1，ans->data2）;

ans = ans->next;

while（ans！=NULL） {

printf（"+ %dX^%d"，ans->data1，ans->data2）;

ans = ans->next;

}

}

printf（"＼n"）;

}

int main（） {

LinkList head1， head2;

Init（& head1）;

Init（& head2）;

int m， n;

scanf（"%d"， &m）;

scanf（"%d"， &n）;

head1 = Creat（m）;

printf（"第一个多项 式："）;

PrintAns（head1）;

head2 = Creat（n）;

printf（"第二个多项式："）;

PrintAns（head2）;

printf（"相加结果："）;

PrintAns（PolyAdd（head1， head2））;

return 0;

}

在运算的过程中 切记注意节点使用的顺序以及位置，g注意与流程图的配合，搞清楚每个模块的需求，根据功能进行函數调用，最终达到代码的完美实现。