问题：使用JAVA语言实现一元多项式的相加/相乘操作
整体结构
思路：
1.首先创建一个单链表的结点类Node，该类包含data,next两个成员变量
data(数据域，用于存放数据–本例中存放多项式如：3x^2)
next(指向下一个结点，结点之间的互相指向就构成了数据结构中的经典结构：链表)
2.创建多项式的项类TermX，包含系数（coef）和项数（xexp）两个成员变量
这个类创建的对象存放到Node类的data中
3.创建多项式排序单链表类PolySinglyList，包含一个asc变量指明排序的顺序和一个头结点head
将数据域为TermX类的实例对象的结点按照指定的顺序（升降序）链接起来就构成了PolySinglyList类
4.创建一个多项式类Polynomial，包含一个PolySinglyList成员变量存放多项式排序单链表类，完成整体封装
提示：以下是实例代码，附带详细注释，仅供参考
一、Node结点类
package datastructure;
public class Node<T> { //单链表节点类，T指定节点的元素类型
public T data; //数据域，存储数据元素
public Node<T> next; //地址域，引用后继节点
public Node(T data, Node<T> next){ //构造方法构造节点，data指定数据元素，next指定后继节点
this.data = data; //T对象引用赋值
this.next = next; //Node<T>对象引用赋值
}
public Node(){
this(null,null);
}
public String toString(){ //返回节点数据域的描述字符串
return this.data.toString();
}
}二、多项式的项类TermX
package datastructure;
//一元多项式的项类，实现可比较接口和可相加接口
public class TermX implements Comparable<TermX>,Addible<TermX>{
protected int coef, xexp; //系数，x指数（可为正，0）.系数也可以是double
public TermX(int coef, int xexp){ //构造一项
this.coef = coef;
this.xexp = xexp;
}
public TermX(TermX term){ //拷贝构造方法
this.coef = term.coef;
this.xexp = term.xexp;
}
//以”系数x^指数“的省略形式构造一元多项式的一项
//省略形式说明，当系数为1或者-1且指数》0时，省略-1，-1只写负号"-",如x^2,-x^3
//当指数为0时，省略x^0,只写系数；当指数为1时，省略^1,只写x
public TermX(String termstr){
int coef;
int xexp;
String[] strarray = termstr.split("x",2);
//从字符串中提取出系数，当"-"时多一步处理
if(!strarray[0].equals("")) { //首先判断系数字符串是否为空，不为空时
if (strarray[0].equals("-")) { //系数字符串为“-”时
strarray[0] = "-1";
coef = Integer.parseInt(strarray[0]);
}else { //正常情况时
coef = Integer.parseInt(strarray[0]);
}
}else{ //系数字符串为空时
strarray[0] = "1";
coef = Integer.parseInt(strarray[0]);
}
//指数字符串提取指数
xexp = Integer.parseInt(strarray[1].substring(1)); //从下标一处开始截取字符串
this.coef = coef;
this.xexp = xexp;
}
public String toString(){ //返回项的”系数x^指数“的省略形式字符串
String[] strarray = new String[3];
if(coef!=0){ //指数和系数的合法性判断
if(coef == -1)
strarray[0] = "-";
if(coef == 1)
strarray[0] = "";
if(coef!=1 && coef!=-1)
strarray[0] = String.valueOf(coef);
}else{
strarray[0] = "0";
}
strarray[1] = "x";
strarray[2] = "^"+String.valueOf(xexp);
return strarray[0]+strarray[1]+strarray[2];
}
public boolean equals(TermX term){ //按照系数和指数比较两项是否相等
if(term instanceof TermX){ //首先判断obj是否是TermX类的实例对象
if(this.coef==term.coef && this.xexp==term.xexp)
return true;
}
return false;
}
public int compareTo(TermX term){ //按x指数比较两项大小，实现Comparable<T>接口
//return this.xexp>term.xexp ? 1 : -1;
if(this.xexp != term.xexp){ //大于返回1，小于返回-1，等于返回0
if(this.xexp > term.xexp){
return 1;
}else{
return -1;
}
}else{
return 0;
}
}
public void add(TermX term){ //相加，this += term,若指数相同，则系数相加；实现Addible<T>接口
if(this.xexp == term.xexp) {
TermX T = new TermX(this.coef + term.coef, this.xexp);
System.out.println(T.toString());
}else{
System.out.println("指数不同，无法相加");
}
}
public boolean removable(){ //若系数为0，则删除元素；实现Addible<T>接口
return this.coef==0 ? true : false;
}
public int getCoef(){
return this.coef;
}
public int setCoef(int coef){
this.coef = coef;
return this.coef;
}
public int getXexp(){
return this.xexp;
}
public int setXexp(int xexp){
this.xexp = xexp;
return this.xexp;
}
public static void main(String[] args) {
TermX term1 = new TermX(0,0);
TermX term2 = new TermX("0x^0");
System.out.println(term1.toString());
System.out.println(term2.toString());
}
}三、多项式的排序单链表类PolySinglyList
package datastructure;
/**
* @Auther: Bender
* @Date: 2021/11/14 - 8:32
* @Description: datastructure
* @version: 1.0
*/
//多项式排序单链表类，继承排序单链表，提供排序单链表结构的多项式加法运算
//T 或者T的某个祖先类“?”必须实现comparable<T>接口；T必须实现Addible<? super T>
public class PolySinglyList<T> {
protected boolean asc; //排序次序true为升序，false为降序
public Node<TermX> head; //头结点指针
public PolySinglyList(){ //无参构造方法
this.head = new Node<TermX>();
this.asc = true; //默认升序排列
}
public PolySinglyList(boolean asc){ //构造方法，asc指定升/降序
this.head = new Node<TermX>();
this.asc = asc;
}
public PolySinglyList(TermX[] terms,boolean asc){ //由项数组指定多项式各式的值深拷贝，复制所有结点，没有复制对象
this.head = new Node<TermX>();
this.asc = asc;
Node<TermX> p = head;
//先将多项式数组按照asc排好序然后插入比先插入再对单链表排序要方便的多
if(asc){ //asc==true,升序，冒泡排序
for(int i=0; i<terms.length-1; i++){
for(int j=0; j<terms.length-i-1; j++){
if(terms[j].xexp>terms[j+1].xexp){
TermX temp = terms[j];
terms[j] = terms[j+1];
terms[j+1] = temp;
}
}
}
}else{ //asc==false,降序
for(int i=0; i<terms.length-1; i++){
for(int j=0; j<terms.length-i-1; j++){
if(terms[j].xexp<terms[j+1].xexp){
TermX temp = terms[j];
terms[j] = terms[j+1];
terms[j+1] = temp;
}
}
}
}
for(int i=0; i< terms.length; i++){ //将按照项数排好序的数组多项式的各个多项式插入单链表
p.next = new Node<TermX>(terms[i],null);
p = p.next;
}
}
public PolySinglyList(PolySinglyList<T> poly){ //拷贝构造方法 要求：深拷贝
this.asc = poly.asc;
this.head = new Node<TermX>(); //首先创建头结点
Node<TermX> rear = this.head;
for(Node<TermX> p=poly.head.next; p!=null; p=p.next){
rear.next = new Node<TermX>(new TermX(p.data),null);
rear = rear.next;
}
}
//多项式相加，this+=list,不改变list。this,list的升/降序属性必须一致。重载
public void addAll(PolySinglyList<TermX> list){
Node<TermX> p = this.head.next;
Node<TermX> q = list.head.next;
while(p!=null && q!=null){
if(p.data.xexp==q.data.xexp){
this.insert(new TermX(q.data.coef,q.data.xexp));
p = p.next;
q = q.next;
}else if(p.data.xexp>q.data.xexp){
this.insert(new TermX(q.data.coef,q.data.xexp));
q = q.next;
}else{
p = p.next;
}
}
while(q!=null){
this.insert(new TermX(q.data.coef,q.data.xexp));
q = q.next;
}
System.out.println(this.toString());
}
//多项式排序单链表类的toString()方法
public String toString(){
String str = "";
if(this.head.next!=null){
Node<TermX> p = this.head.next;
if(p.data!=null){
do{
str += p.data.toString()+"+";
p = p.next;
}while(p!=null);
}
str = str.substring(0,str.length()-1);
}
return str;
}
public void insert(TermX term) { //插入方法，注意：方法调用的变量不是结点而是TermX,有序插入，并且可以插入合并项数相同的多项式
Node<TermX> noterm = new Node<TermX>(term,null); //创建一个结点(data:是要插入的term),这样才能插入排序单链表
int num = 0;
//首先判断执行插入方法的单链表是不是空单链表
if(this.head.next!=null){
//先比较要插入的多项式的项数是否和排序单链表中的某一项相等，如果相等则系数相加，不必插入，如果不等则执行插入操作
for(Node<TermX> p=this.head.next; p!=null; p=p.next){
if(p.data.xexp==noterm.data.xexp){ //项数相等，执行两个多项式相加的操作
p.data.coef += noterm.data.coef;
num++;
break;
}
}
if(num==0){ //无项数相等的多项式,执行插入操作
//首先判断排序单链表是升序还是降序
if(asc){ //升序
Node<TermX> point;
for(point = this.head.next; point.next!=null; point=point.next){ //正常情况插入
while(point.data.xexp<noterm.data.xexp && point.next.data.xexp>noterm.data.xexp){
noterm.next = point.next;
point.next = noterm;
num = 2;
break;
}
}
//头插入或者位插入的情况,前提是上面没有执行插入操作
if(num!=2){
if(noterm.data.xexp<this.head.next.data.xexp){ //升序头插入
noterm.next = this.head.next;
this.head.next = noterm;
}else{ //升序尾插入
point.next = noterm;
}
}
}else{ //降序
Node<TermX> point;
for(point = this.head.next; point.next!=null; point=point.next) { //正常插入
while (point.data.xexp>noterm.data.xexp && point.next.data.xexp < noterm.data.xexp) {
noterm.next = point.next;
point.next = noterm;
num = 2;
break;
}
}
if(num!=2){ //降序头插入或者尾插入
if(noterm.data.xexp>this.head.next.data.xexp){ //降序头插入
noterm.next = this.head.next;
this.head = noterm;
}else{
point.next = noterm;
}
}
}
}
}else{
System.out.println("执行一次空单链表的插入");
this.head.next = noterm;
}
}
public PolySinglyList<TermX> multiply(PolySinglyList<TermX> list) { //深拷贝，不改变list的值，不改变this的值，返回一个新的多项式单链表
PolySinglyList<TermX> result = new PolySinglyList<>(this.asc); //构造一个结果单链表，顺序同this
Node<TermX> p = this.head.next;
while(p!=null){
Node<TermX> q =list.head.next;
while(q!=null){
result.insert(new TermX(p.data.coef*q.data.coef,p.data.xexp+q.data.xexp));
q = q.next;
}
p = p.next;
}
return result;
}
public static void main (String[]args){
//验证数组构造方法
TermX[] terms = {new TermX(2,1),new TermX(2,2),new TermX(2,3),new TermX(2,5)};
PolySinglyList<TermX> ploy = new PolySinglyList(terms,true);
System.out.println(ploy.toString());
//验证插入方法一共六种插入情况
// ploy.insert(new TermX("6x^4"));
// System.out.println(ploy.toString());
// //验证是否是深拷贝构造方法
// PolySinglyList<TermX> ploy1 = new PolySinglyList<>(ploy);
// System.out.println(ploy1.toString());
// ploy1.insert(new TermX("6x^0"));
// System.out.println(ploy.toString());
// System.out.println(ploy1.toString());
//验证addAll方法
TermX[] terms1 = {new TermX(1,0)};
PolySinglyList<TermX> ploy1 = new PolySinglyList<>(terms1,true);
System.out.println(ploy1.toString());
// ploy.addAll(ploy1);
//验证multiply,多项式的乘法
System.out.println(ploy.multiply(ploy1).toString());
}
}四、多项式类Polynomial
package datastructure;
/**
* @Auther: Bender
* @Date: 2021/11/17 - 15:34
* @Description: datastructure
* @version: 1.0
*/
public class Polynomial { //多项式类
private PolySinglyList<TermX> list; //多项式排序单链表，元素是一元多项式的项
public Polynomial(boolean asc) { //构造方法，asc指定升/降序
this.list = new PolySinglyList<>(); //空链表，只有一个头结点和指定的asc
this.list.asc = asc;
}
public Polynomial() {
this.list = new PolySinglyList<>(); //空链表，只有一个头结点和指定的asc
this.list.asc = true; //默认升序
}
public Polynomial(TermX[] terms, boolean asc) {
this.list = new PolySinglyList<>(terms,asc);
}
public Polynomial(String polystr) { //构造方法参数指定多项式的表达式字符串，升序
String[] strarr = polystr.split("\+");
TermX[] goalterm = new TermX[strarr.length];
for(int i=0; i<strarr.length; i++){
goalterm[i] = new TermX(strarr[i]);
}
this.list = new PolySinglyList<>(goalterm,true);
}
public Polynomial(Polynomial poly) { //拷贝构造方法，深拷贝，复制所有结点和对象
this.list = new PolySinglyList<>();
this.list.asc = poly.list.asc; //创建空单链表,复制升/降序属性
Node<TermX> rear = this.list.head; //声明尾指针
for(Node<TermX> p =poly.list.head.next; p!=null; p=p.next){ //p遍历poly单链表
rear.next = new Node<TermX>(new TermX(p.data),null); //复制结点，复制对象
rear = rear.next;
}
}
public String toString() { //返回多项式的描述字符串，覆盖
String str = "";
if(this.list.head.next!=null){ //容错处理
Node<TermX> point;
for(point=this.list.head.next; point!=null; point=point.next){
str += point.data.toString()+"+";
}
str = str.substring(0,str.length()-1);
return str;
}else{
return str;
}
}
public void addAll(Polynomial poly) { //多项式相加，this += poly 只改变this单链表
this.list.addAll(poly.list);
}
public Polynomial union(Polynomial poly) { //多项式加法，返回一个新的多项式
Polynomial resultpoly = new Polynomial(this); //深拷贝poly
resultpoly.addAll(poly);
return resultpoly;
}
public void multi(Polynomial poly) { //多项式相乘 this*=poly
this.list = this.list.multiply(poly.list); //返回一个新的单链表
System.out.println(this.list.toString());
}
public static void main(String[] args) {
//验证参数：字符串的构造方法
Polynomial list1 = new Polynomial("2x^3+2x^1+3x^2");
//验证toString()方法
// System.out.println(list1.toString());
//验证拷贝构造方法
Polynomial list2 = new Polynomial(list1);
// System.out.println(list2.toString());
//验证addAll()方法
// list2.addAll(list1);
// System.out.println(list1.toString());
//验证union方法
list2.union(list1).toString();
System.out.println(list2.toString());
//测试multi方法-----多项式相乘， this*=poly
Polynomial list3 = new Polynomial("4x^0");
list3.multi(list1);
}
}