java单链表实现一元多项式加法和乘法运算

yesihao 2014-10-09

展开全文

设有一个一元多项式 f(x)=∑a_ixⁱ ，我们要用一个单链表将它表示出来，并实现它的加和乘运算。多项式的每一项放在一个结点中，每个结点中放两个信息，即每一项的系数和幂。在这里我们用有头结点的链表来表示，那么对于某个多项式 p=2x²+100x³+45x⁵+3x²⁰，它的单链表表示如下：

尽可能地简单，结点PolyNode类如下：

[java] view plain copy

package poly;
public class PolyNode {
private int a;
private int i;
PolyNode next;
public PolyNode(int a,int i){
this.a=a;
this.i=i;
this.next=null;
}
public PolyNode(){
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;
}
}

加法运算的算法如下图：

多项式 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 。不过结果最后有一个合并同类项的问题，这也不难，无非就是每一项跟它后面的所有项比较，如果幂相同的话，就把它们加起来，这里不再赘述，看代码吧。

链表类 PolyList 如下：

[java] view plain copy

package poly;
public class PolyList {
PolyNode head;
PolyNode current;
public PolyList(){
head=new PolyNode();
current=head;
head.next=null;
}
//是否为空
public boolean isEmpty(){
return head.next==null;
}
//这里只考虑按顺序插入元素
public void insert(PolyNode node){
current.next=node;
current=node;
}
//打印多项式
public String printS(){
StringBuilder s=new StringBuilder("");
StringBuilder a=new StringBuilder("");
StringBuilder i=new StringBuilder("");
StringBuilder theOne=new StringBuilder("");
current=head.next;
while(current!=null){
a.delete(0, a.length());
i.delete(0, i.length());
theOne.delete(0, theOne.length());
if(current.getA()==1)
a.append("");
else
a.append(String.valueOf(current.getA()));
if(current.getI()==1)
{
i.append("");
theOne.append(a.toString()).append("x").append(i.toString());
} else{
i.append(String.valueOf(current.getI()));
theOne.append(a.toString()).append("x^").append(i.toString());
}
if(current==head.next)
s.append(theOne.toString());
else
s.append("+").append(theOne.toString());
current=current.next;
}
return s.toString();
}
//加法运算
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 PolyNode(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 PolyNode(a,i));
p2.current=p2.current.next;
}
p1.current=p1.current.next;
p2.current=p2.head.next;
}
//合并同类项
result.current=result.head.next;
PolyNode tempPrevious=result.current;
PolyNode 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=temp.next;
}
}
result.current=result.current.next;
tempPrevious=result.current;
temp=result.current.next;
}
return result;
}
}