美文网首页
多项式的链表表示与加法

多项式的链表表示与加法

作者: 小幸运Q | 来源:发表于2018-10-19 23:51 被阅读73次

链表A表示的多项式: 7 * X^1 + 2 * X^2 + 8 * X^5
链表B表示的多项式: 2 * X^1 + (-2 * X^2) + 2 * X^3
链表C是我们最终的和链表
image.png

算法步骤:

1 . 规定三个头指针,分别指向三个链表的头,然后再规定三个移动指针,分别指向当前三个链表中正在处理的那个节点

2 . 我们让A、B、C的移动指针刚开始也处于头指针的位置,然后,我们拿A节点中的指数和B节点中的指数进行比较,这个时候有三种情况:


a情况 . A中当前的节点指数 < B中当前的节点指数 —— 我们将A中的当前节点插入C中,然后向后移动A和C的指针(因为A中当前节点已经处理了)


b情况 . A中当前的节点指数 > B中当前的节点指数 —— 我们将B中的当前节点插入C中,然后向后移动B和C的指针(因为B中当前节点已经处理了) 即图中⑧的情况。


c情况 . A中当前的节点指数 == B中当前的节点指数 —— 此时A和B当前节点指数相同,可以进行系数相加,这时候也会出现两种情况:

  • 情况1 . 系数之和不为0 —— 我们此时将系数之和放到A中的当前节点的系数域,然后将A中的该节点插入C中,然后向后移动C的指针(记住,我们这里不是产生一个新的节点,而是直接更改A的系数域,然后将A的当前节点插入C中),即图中的①和②产生③的过程。

  • 情况2 . 系数之和为0,删除掉A和B对应节点然后移向下一位。即图中的④和⑤产生⑥的过程。


若A、B链表可能长度不一致,此时,我们只需要将另一个链表中未处理的数据直接接在当前已经生产的C链表的后面即可。


第三步:
打印输出最终计算所得的和链表表达式

相关文章

  • 多项式的链表表示与加法

    算法步骤: 1 . 规定三个头指针,分别指向三个链表的头,然后再规定三个移动指针,分别指向当前三个链表中正在处理的...

  • 多项式加减法 (二)

    在多项式加法 (一)中,我们介绍了多项式对应的单链表的几个接口,现在我们来完成本次实验剩余的其他几个接口。 第五步...

  • 第4章编程题

    多项式加法

  • 多项式的加法(单向链表)

    采用不带头节点的单向链表,按照指数递减的顺序排列各项 【算法思路】两个指针P1和P2分别指向这两个多项式第一个节点...

  • 一元多项式

    1 、问题描述: 功能:设计一个一元多项式加法器。 输入并建立多项式,实现两个多项式的加法运算。 要求: 1) 界...

  • 多项式存储

    多项式的表示(用数组就是空间浪费) 一元:幂和系数——数组(index表示幂)或链表(存储幂和系数) 多元:项—指...

  • Java 数组 编程练习题

    1、 多项式加法 题目内容: 一个多项式可以表达为x的各次幂与系数乘积的和,比如: 现在,你的程序要读入两个多项式...

  • 线性结构-相关算法

    编译环境:python v3.5.0, mac osx 10.11.4 多项式加法与乘法运算(队列) 主要思路: ...

  • 多项式乘除法的LFSR实现

    1. 定义操作 定于多项式加减操作为异或,定义乘除为与; 2. 多项式乘法&LFSR表示 有两个多项式: 多项式的...

  • 链表实现两个多项式的加法

    最近遇到这样一个题目,使用链表来实现两个多项式的加法,刚开始觉得应该比较简单,也可能是自己基础不扎实吧,这其中也是...

网友评论

      本文标题:多项式的链表表示与加法

      本文链接:https://www.haomeiwen.com/subject/thhpzftx.html