APP下载

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

2020-07-06杜金庭唐海川

青年生活 2020年16期

杜金庭 唐海川

一元多项式的表示在计算机内可以用链表来表示,为了节省存储空间,只存储多项式中系数非零的项。 链表中的每一个结点存放多项式的一个系数非零项,它包含三个域,分别存放该项的系数、指数以及指向下一个多项式项结点的指针。对于如何利用链表将两个一元多项式分别存入两个链表中,通过相加将链表合并后并输出合成后的新的一元多项式。在运行的过程中主要所运用的就是利用链表的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)是一个无参函数,这样就能成功实现链表的初始化。……

登录APP查看全文