Java数据结构编程题目一条单链表可以表示一个一元多项式，每个结点包括三个域：指数域、系数域和后继结点链。表示多项式3x(4次方)-6x(2次方)+5x-10的单链表。给定两个多项式，实现两个多

Question

Java数据结构编程题目
一条单链表可以表示一个一元多项式，每个结点包括三个域：指数域、系数域和后继结点链。表示多项式3x(4次方)-6x(2次方)+5x-10的单链表。给定两个多项式，实现两个多项式相加算法。（最好有详细解析，如果解析的好会再加分）

Answer 1

自己参考下吧，希望对你有用！
//用单链表来实现多项式的加法，代码如下
public class Polynomial {
private Monomial first; // 首项
// 添加单项式
public void append(Monomial monomial) {
if (monomial == null) {
// do nothing
} else if (first == null) {
first = monomial;
} else {
Monomial current = first;
while (current != null) {
// 提示:如果指数相同，则相加
if (current.index == monomial.index) {
current.coefficient += monomial.coefficient;
break;
} else if (current.next == null) { // 否则直接把此项扔到最后
current.next = monomial;
break;
}
current = current.next;
}
}
}
public void append(int c, int i) {
append(new Monomial(c, i));
}
public String toString() {//toString()方法就是把对象转换成String类型
//比如一个Integer对象的toString方法就是把这个对象表示的整数转化成字符串，133就成了"133"。
StringBuffer sb = new StringBuffer();
Monomial current = first;
while (current.next != null) {
sb.append("(" + current.coefficient + "x^" + current.index
+ ") + ");
current = current.next;
}
sb.append("(" + current.coefficient + "x^" + current.index + ")");
return sb.toString();
}
// 两个多项式相加
public Polynomial add(Polynomial p2) {
Polynomial result = new Polynomial();
Monomial current = this.first;
while (current != null) {
result.append(current.coefficient, current.index); // 提示:注意这里
current = current.next;
}
current = p2.first;
while (current != null) {
result.append(current.coefficient, current.index);
current = current.next;
}
return result;
}
public static void main(String[] args) {
//构造多项式p1的每一项
Polynomial p1 = new Polynomial();
p1.append(3, 4);
p1.append(-6, 2);
p1.append(5, 1);
p1.append(-10, 0);
System.out.println("p1: " + p1);
//构造多项式p2的每一项
Polynomial p2 = new Polynomial();
p2.append(2, 5);
p2.append(-6, 2);
p2.append(5, 1);
System.out.println("p2: " + p2);
Polynomial result = p1.add(p2);
System.out.println("p1+p2= " + result);
}
}
/**
* 这是一个内部类
* 单项式的表示
*/
class Monomial {
int coefficient; // 系数
int index; // 指数
Monomial next; // 后继结点
public Monomial() {
}
public Monomial(int c, int i) {
this.coefficient = c;
this.index = i;
}
}