`
128kj
  • 浏览: 601208 次
  • 来自: ...
社区版块
存档分类
最新评论

链表实现的多项式加法与乘法

阅读更多

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
分享到:
评论

相关推荐

    双向链表实现多项式加法和乘法.cpp

    双向链表实现多项式加法和乘法

    用链表实现多项式的加法和乘法

    用链表实现多项式的加法和乘法,用输入运算符重载的方法大大简化了链表的创建过程,乘法方面用了数组,主要是利用其线性的优点。

    链表实现多项式加法和乘法(C语言实现)

    使用链表实现多项式的加法和乘法,数据结构常见问题的C语言实现

    C++链表基于类实现多项式的加法和乘法

    本话题将探讨如何利用链表类来实现多项式的加法和乘法运算。这些操作在数学计算、数值分析以及计算机图形学等领域有广泛的应用。 首先,我们需要创建一个表示多项式的类。这个类通常会包含一个节点类,用于存储...

    多项式加法和乘法C代码

    本文将深入解析一个用C语言编写的多项式加法与乘法程序。该程序主要利用链表结构来表示多项式,并通过栈的方式来处理多项式的运算。程序不仅实现了多项式的加法运算,还实现了乘法运算。 #### 主要功能 1. **多项式...

    用链表实现的多项式的加法与乘法

    问题描述:有两个指数递增的一元多项式,写一程序先求这两个多项式的和,再求它们的积

    多项式的加法与乘法(数据结构)

    本主题聚焦于多项式加法与乘法的实现,这是数据结构与算法的一个经典应用。理解如何高效地处理多项式对于优化计算任务至关重要,尤其是在数值计算、图形学、信号处理等领域。 多项式可以被看作是一系列系数与变量的...

    链表多项式的加法与乘法设计报告

    链表多项式的加法与乘法设计报告,含开发思路,内附源码。

    多项式的加法和乘法的算法

    本文将介绍如何使用单链表来实现多项式的加法和乘法运算。 多项式的表示 ------------- 在计算机科学中,多项式可以用链表来表示。每个节点代表一个项,包括系数(coef)和指数(expn)。这样可以方便地实现多项式...

    用链表实现多项式相乘以及相加

    在多项式的运算中,链表可以用来实现多项式的加法、乘法和幂展开等操作。 在链表实现多项式相乘和相加中,需要定义一个链表结构体,包括基数、指数和指针三个成员变量。然后,需要实现创建多项式、输出多项式、加法...

    双向链表及其应用——实现多项式的加法及乘法

    本文将深入探讨双向链表的实现以及它在一项特殊应用中的体现:一元多项式的加法与乘法运算。 首先,我们要理解双向链表的概念。双向链表是一种线性数据结构,每个节点包含两个指针,分别指向其前一个节点和后一个...

    两个高次多项式加法和乘法运算课程设计

    两个高次多项式加法和乘法运算课程设计 本次课程设计的主题是实现两个高次多项式的加法和乘法运算,以帮助学生掌握软件开发过程中的问题分析、系统设计、程序编码、测试等基本方法和技能,并提高独立分析和解决问题...

    C++实现多项式的加法和乘法

    C++编写,基于单链表实现多项式的加法和乘法

    用链表实现多项式_C++_

    在这个场景中,我们讨论的是如何使用C++通过链表来实现多项式的加、减、乘、除运算。首先,我们需要理解链表的基本概念以及如何将其应用到多项式表示上。 链表不同于数组,它不连续存储元素,而是通过节点之间的...

    用C++链表结构实现多项式的加法,乘法运算

    以上就是用C++链表结构实现多项式加法和乘法运算的基本思路。实际编程时,还需要考虑错误处理、内存管理以及优化等细节。通过这种方式,我们可以高效地处理多项式运算,这对于解决各种数学问题或在数值分析、科学...

    一元多项式加法和乘法,单链表

    // 一元多项式加法 Polynomial add(const Polynomial& other) { // 实现代码... } // 一元多项式乘法 Polynomial multiply(const Polynomial& other) { // 实现代码... } }; ``` 对于一元多项式的加法,...

    数据结构——一元多项式加法、减法、乘法运算的实现

    ### 数据结构——一元多项式加法、减法、乘法运算的实现 #### 设计内容及要求 本节详细介绍了如何使用不同的数据结构来实现一元多项式的加法、减法以及乘法运算。 ##### 1.1 设计内容 1. **使用顺序存储结构实现...

    C++ 单链表实现多项式乘法

    #### 设计与实现 为了实现上述功能,本设计采用了单链表来存储两个多项式,每个节点包含单项式的系数、幂指数以及指向下一个元素的指针。此外,还定义了相关的数据结构和方法来辅助运算。 **存储结构**: ```cpp ...

    用链表实现多项式运算

    本项目“用链表实现多项式运算”聚焦于利用链表来表示和操作多项式,涵盖了多项式的基本运算:加法、减法、乘法以及求导。下面将详细讨论这些知识点。 首先,链表是一种非连续存储结构,由一系列节点组成,每个节点...

Global site tag (gtag.js) - Google Analytics