public class Node {
private int a;
private int i;
Node next;
public Node(int a,int i,Node next){
this.a=a;
this.i=i;
this.next=next;
}
public Node(int a,int i){
this.a=a;
this.i=i;
this.next=null;
}
public Node(){
this(0,0);
}
public int getA() {
return a;
}
public int getI() {
return i;
}
public void setA(int a) {
this.a = a;
}
public void setI(int i) {
this.i = i;
}
}
多项式类(单链表实现)
public class PolyList {
Node head;
Node current;
public PolyList(){
head=new Node();
current=head;
head.next=null;
}
//是否为空
public boolean isEmpty(){
return head.next==null;
}
//这里只考虑按顺序插入元素
public void insert(Node node){
current.next=node;
current=node;
}
//加法运算
public static PolyList add(PolyList p1,PolyList p2){
PolyList result=new PolyList();
//分别指向p1 p2的第一个元素
p1.current=p1.head.next;
p2.current=p2.head.next;
while(p1.current!=null && p2.current!=null){
if(p1.current.getI()==p2.current.getI()){
result.insert(new Node(p1.current.getA()+p2.current.getA(),p1.current.getI()));
p1.current=p1.current.next;
p2.current=p2.current.next;
}
else if(p1.current.getI()<p2.current.getI()){
result.insert(p1.current);
p1.current=p1.current.next;
}else{
result.insert(p2.current);
p2.current=p2.current.next;
}
}
while(p1.current!=null){
result.insert(p1.current);
p1.current=p1.current.next;
}
while(p2.current!=null){
result.insert(p2.current);
p2.current=p2.current.next;
}
return result;
}
//乘法运算
public static PolyList multiply(PolyList p1,PolyList p2){
PolyList result=new PolyList();
//分别指向p1 p2的第一个元素
p1.current=p1.head.next;
p2.current=p2.head.next;
while(p1.current!=null){
while(p2.current!=null)
{
int a=p1.current.getA()*p2.current.getA();
int i=p1.current.getI()+p2.current.getI();
result.insert(new Node(a,i));
p2.current=p2.current.next;
}
p1.current=p1.current.next;
p2.current=p2.head.next;
}
合并同类项
result.current=result.head.next;
Node tempPrevious=result.current;
Node temp=result.current.next;
while(result.current.next!=null){
while(temp!=null)
{
if(temp.getI()!=result.current.getI())
{
temp=temp.next;
tempPrevious=tempPrevious.next;
}else{
result.current.setA(result.current.getA()+temp.getA());
tempPrevious.next=temp.next; //temp节点已经合并,将其从result中删除。
temp=temp.next;
}
}
result.current=result.current.next;
tempPrevious=result.current;
temp=result.current.next;
}
return result;
}
}
多项式加法: result 用来保存结果。p1.current 和 p2.current 分别指向 p1 和 p2 的第一个元素,比较它们的幂,如果相等,将它们的系数相加,幂不变,这一新项插入到 result 中,p1.current 和 p2.current 都往后移一位;如果 p1.current 所指向的项的幂小于 p2.current ,则把 p1.current 所指向的这一项插入到 result 中,p1.current 后移一位;同样地,如果 p2.current 所指向的项的幂小于 p1.current ,执行类似的操作。重复这一过程,直到这两个指针都指向 null 。(在单链表中,最后一个结点的 next 指向null)这里还有一个细节,就是这两个指针中一般都会有一个先指向 null ,那么这时候很简单,把剩下的那个指针往后遍历,它及其后面所指向的项都插入 result 即可。
乘法运算的算法比加法还要简单,同样result 用来保存结果, p1.current先固定, p2.current 遍历,p1.current 的指向乘以 p2.current 所指的每一项,这一次结束后 p1.current 后移一位,重复上述过程,直到 p1.current 指向 null 。不过结果最后有一个合并同类项的问题。
下载源码:
- 大小: 17.6 KB
分享到:
相关推荐
双向链表实现多项式加法和乘法
用链表实现多项式的加法和乘法,用输入运算符重载的方法大大简化了链表的创建过程,乘法方面用了数组,主要是利用其线性的优点。
使用链表实现多项式的加法和乘法,数据结构常见问题的C语言实现
C++链表基于类实现多项式的加法和乘法; C ++ list class-based polynomial addition and multiplication.
问题描述:有两个指数递增的一元多项式,写一程序先求这两个多项式的和,再求它们的积
链表多项式的加法与乘法设计报告,含开发思路,内附源码。
用链表实现多项式的加法 乘法 幂展开 。。。。。。。。。。。。。。。。。
C++编写,基于单链表实现多项式的加法和乘法
定义了线性表的抽象类,以及双向链表类及其结点类,实现双向链表的基本功能,还进一步应用到一元多项式的储存、加法和乘法,里面包含了项目文件,测试文件以及报告文件(一元多项式实现的思路)。
(数据结构)用链表结构(C++)实现多项式的加法和乘法运算。
使用C++语言,利用单链表实现多项式乘法,文档中有对设计思路、调试方式的阐述,并附有源代码。
用数据结构里面的链表实现多项式的加法、减法和乘法
多项式关联使用链表的多项式加法和乘法
用C语言建立链表实现多项式的加法、减法 和乘法的完整程序。
1. 编写使用freelist 的带头、尾结点的双向链表类的定义,实现双向... 利用双向链表实现2个一元多项式的加法和乘法运算,运算结果得到的链表要求按照指数降序排列的多项式。 3. 最后提交完整的实验报告和源程序。
实验内容及要求: 从字符文件输入两个多项式的非零系数及对应的指数,建立多项式的链式存储结构,计算这两个多项式的乘积,输出乘积多项式的全部...实验目的:掌握单向链表的基本操作以及基于链表的多项式加法与乘法。
使用链表来实现单元多项式的加法、减法、乘法。其中,加法是其它运算的基础,减法:poly1-poly2=poly1+(-poly2),乘法:poly1*poly2,可用poly1乘以poly2的每一项,相加其乘积结果。
完美的数据结构大作业之选。C语言+链表 实现。不用提前知道多项式项数,可以自动排序,可以合并同类项,可以进行加法、乘法运算。VS环境可运行,其他编程软件找到cpp复制粘贴即可
用C语言实现的链表多项式的运算,实现多项式加法和乘法