使用单链表实现多项式的加法和乘法运算（java版）

开始前说些走流程的废话，由于是第一次发博客，表达和讲解方法都不是那么成熟，
　　如果有什么地方有待改正，欢迎并感谢亲们在评论区留言
　　（让我感受一下捏你们对萌新的善意，谢谢谢谢）
　　那么，我们正式开始

单链表的基础概念

利用单链表解决多项式的加法和乘法，实际上就是利用简单的单链表结构体存储数据并进行运算，在解决这个问题之前，我们首先得知道，什么是单链表：
　　链表是一种数据结构（存储的数据分散在内存中，每个结点只能也只有它能知道下一个结点的存储位置），而单链表是链表的一种（特点是链表的链接方向是单向的），单链表由不定数量的节点构成，开始于对外暴露的头结点，结束于终端节点（引用为ＮＵＬＬ）。
　　而节点的组成则包括节点自身存储的对象，以及下一节点的引用next（如下图图1），由于对外暴露的都只有头节点，所以对链表的所有操作，都是直接或者间接地通过其头节点来进行的。
　　　　　　　　　　　　　　　　　　　　　（图１）

利用单链表解决多项式运算的算法流程

从算法思路开始说起
（此段为详细说明，整体代码在文末，只想看代码可以直接跳过）

一，设计多项式

不管是单项式加法还是乘法，第一步都是设计多项式，
　　我的想法是将多项式分解为一个个单项式，设计一个单项式类做节点，再设计链表，将各个单项式连接起来就形成了多项式。
　　（单项式类中应含有系数和指数这两种参数，同时还需要有对应的处理方法）

1，设置单项式节点

先建立单项式节点，使单项式可以表达出来
　　
　　具体代码如下

package example;

public class PolymialNode {
   //建立一个多项式节点，包含系数和指数
	private double coef;//系数
	private int index;//指数
	public PolymialNode next;//下一节点的引用
	public PolymialNode() {
    //初始默认值设置为0
	this(0, 0); 
	}
	 public PolymialNode(double coef, int index) {
    
		 this.coef = coef; 
		 this.index = index; 
	 }
	 public double getCoef() {
   
		 return coef; 
	 } 
	 public void setCoef(double coef) {
   
		 this.coef = coef; 
	 } 
	 public int getindex() {
    
		 return index; 
	 } 
	 public void setindex(int index) {
   
		 this.index = index; 
	 } 
}

2，连接单项式形成多项式

设置完单项式节点之后，我们就需要把单项式连接起来形成多项式，
此时就运用到了单链表，如图

代码部分如下

package example;

public class PolyList {
   
	 PolymialNode head;//头节点
	 PolymialNode current; //当前单项式节点
	 public PolyList(){
   
		 head = new PolymialNode();
		 current = head;
		 head.next = null;//设置下一节点头文件默认为空
		 } 
	 public boolean isEmpty() {
    
		 return head.next == null;
		 }//判断多项式是否为空
	 public void insert(PolymialNode node) {
    
		 current.next = node;
		 current = node; 
	 } //把数据插入多项式链表
	 public String express(){
    //设置一个函数表达多项式
		 StringBuilder pl = new StringBuilder(); 
		 PolymialNode node = head.next; 
		 while (node != null) {
    
			 pl.append(node.getCoef() + "x^"+node.getindex()); 
			 pl.append(" + "); 
			 node = node.next;
			 } 
		 return pl.substring(0, pl.length() - 2); //头尾皆无数据，故-2
	 }
}

可以看到，代码部分通过单链表，将各个单项式连接起来，这样就形成了多项式

二，多项式加法

因为多项式的加法运算与乘法运算不同，于是先解决多项式加法的问题

匹配指数相同的单项式，并使系数相加

要使系数相加直接加就完了，需要思考的是如何匹配指数相同的单项式。
　　我们知道，单链表是顺序存储的，要找到一个元素，必须找到所在单链表的前一位元素（例如找第n位元素必须先找到第n-1位元素，这是由单链表的结构决定的）。
　　所以我们要匹配指数相同的项，不能直接按指数相加系数，而需要从头节点开始，统计指数相同的项，并在结果中将系数相同的项相加并保存起来。
那么由于两个多项式项的数量不一定相等，所以我们在创建多项式时除了两个用于计算的多项式外，还需要再新建一个多项式用于统计结果。
　　
　　以下是加法部分的所有代码，我将它放在多项式链表类PolyLIst中

                      /*加法*/
public static PolyList addPoly(PolyList p, PolyList q) {
    
	PolymialNode pnext = p.head.next; 
	PolymialNode qnext = q.head.next; 
	PolyList result = new PolyList(); 
	while (pnext != null && qnext != null) {
   
		int pindex = pnext.getindex(); 
		int qindex = qnext.getindex(); 
		double pcoef = pnext.getCoef();
		double qcoef = qnext.getCoef(); 
		if (pindex == qindex) {
    
			if (pcoef+qcoef != 0) {
   //指数相同时系数相加并保存到结果多项式result中
				PolymialNode node = new PolymialNode(pcoef + qcoef, pindex); 
				result.insert(node); 
			}
			pnext = pnext.next; 
			qnext = qnext.next; 
		}