Java一元稀疏多项式计算器

Java一元稀疏多项式计算器

目录要求:实现:Main类Node类LinkLsit类Polynomial类

要求:

一元稀疏多项式计算器

【问题描述】 设计一个一元稀疏多项式简单计算器。

【基本要求】一元稀疏多项式简单计算器的基本功能是：

(1) 输入并建立多项式 ；

(2) 输出多项式，输出形式为整数序列：n，c1，e1，c2，e2，…，cn，en，其中n是多项式的项数，ci 和ei，分别是第 i 项的系数和指数，序列按指数降序排列；

(3) 多项式a和b相加，建立多项式a +b；

(4) 多项式a和b相减，建立多项式a -b 。

【测试数据】

1)(2x+5x8－3.1x11) + (7－5x8+11x9)=(－3.1x11+11x9+2x+7)

2)(6x-3－x+4.4x2－1.2x9) －(-6x-3+5.4x2－x2+7.8x15)=(-7.8x15-1.2x9+12x-3-x)

3)(1 +x + x2+x3+x4+x5)+(-x3－x4)=(1+x+x2+x5)

4)(x+x3)+(-x－x3)=0

5)(x+x100)+(x100 +x200)=(x+2x100+x200)

6)(x+x2+x3)+0=x+x2+x3

7) 互换上述测试数据中的前后两个多项式

【实现提示】 用带表头结点的单链表存储多项式。

【选作内容】

1) 计算多项式在x处的值。

2) 求多项式 a 的导函数 。

3) 多项式a和b相乘，建立乘积多项式ab 。

4) 多项式的输出形式为类数学表达式。例如 ，多项式 -3x8+6x3－18 的输出形式为-3x8+6x3-18，x15+(－8)x7－14的输出形式为s15+(-8)x7-14。注意，数值为1的非零次项的输出形式中略去系数1，如项1x8的输出形式为x8，项 －1x3的输出形式为－x3。

**

实现:

Main类

package usps;

/*

吴乐 汉江师范学院 软件工程2001班

数据结构期末大作业 一元稀疏多项式计算器

开始 2021.12.18 22:00

完成 2021.12.26 00:21

优化 2021.12.26 18:00

*/

import java.util.Scanner;

public class Main

{

public static void main(String[] args)

{

Scanner in=new Scanner(System.in);

Polynomial poly = new Polynomial();

int num;

do

{//菜单

System.out.println("\n 一元稀疏多项式计算器");

System.out.println("——————————————————————————————————————————————————————————");

System.out.println( "1.建立多项式a 2.建立多项式a+b 3.建立多项式a-b " +

"\n4.建立多项式axb 5.多项式a的导函数 6.多项式在x处的值\n7.退出");

System.out.println("——————————————————————————————————————————————————————————");

System.out.print("命令: ");

num=in.nextInt();

switch (num)//命令

{

case 1://建立多项式

{

System.out.println("请输入多项式:");

System.out.println("项的个数n <系数 指数>*n");

LinkList list = poly.inPoly();

System.out.print("\n多项式: ");

list.allPut();

}break;

case 2://多项式 a + b

{

System.out.println("请输入多项式a:");

System.out.println("项的个数n <系数 指数>*n");

LinkList listA = poly.inPoly();

System.out.println("请输入多项式b:");

LinkList listB = poly.inPoly();

System.out.print("\n多项式 a : ");

listA.allPut();

System.out.print("\n多项式 b : ");

listB.allPut();

System.out.print("\n多项式 a+b : ");

poly.addPoly(listA,listB).allPut();

}break;

case 3://多项式 a - b

{

System.out.println("请输入多项式a:");

System.out.println("项的个数n <系数 指数>*n");

LinkList listA = poly.inPoly();

System.out.println("请输入多项式b:");

LinkList listB = poly.inPoly();

System.out.print("\n多项式 a : ");

listA.allPut();

System.out.print("\n多项式 b : ");

listB.allPut();

System.out.print("\n多项式 a-b : ");

poly.minusPoly(listA,listB).allPut();

}break;

case 4://建立多项式axb

{

System.out.println("请输入多项式a:");

System.out.println("项的个数n <系数 指数>*n");

LinkList listA = poly.inPoly();

System.out.println("请输入多项式b:");

LinkList listB = poly.inPoly();

System.out.print("\n多项式 a : ");

listA.allPut();

System.out.print("\n多项式 b : ");

listB.allPut();

System.out.print("\n多项式 axb : ");

poly.mulPoly(listA,listB).allPut();

}break;

case 5://多项式 a 的导函数

{

System.out.println("请输入多项式a:");

System.out.println("项的个数n <系数 指数>*n");

LinkList listA = poly.inPoly();

System.out.print("\n多项式 a : ");

listA.allPut();

System.out.print("\n多项式 a 的导函数: ");

poly.derfPoly(listA).allPut();

}break;

case 6://多项式在x处的值

{

System.out.println("请输入多项式a:");

System.out.println("项的个数n <系数 指数>*n");

LinkList listA = poly.inPoly();

System.out.println("请输入 x : ");

double x = in.nextDouble();

http:// System.out.print("\n多项式 a : ");

listA.allPut();

System.out.print("\nx: "+x);

System.out.printf("\na(x)为(保留三位小数): %.3f",poly.getXValue(listA,x));

}break;

case 7://退出

{

System.out.println("再见");

}break;

default:System.out.println("输入错误了你个蠢蛋");

}

}while(num!=7);

}

}

Node类

package usps;

public class Node

{

Node next;//下一个结点

double coefficient;//系数

double index;//指数

public Node(){

super();

}

public Node(Node next)

{

this.next=next;

}

public Node(Node next,double coefficient, double index)

{

this.next=next;

this.coefficient=coefficient;//系数

this.index=index;//指数

}

public double getCoefficient() {

return coefficient;

}

public void setCoefficient(double coefficient) {

this.coefficient = coefficient;

}

public double getIndex() {

return index;

}

public void setIndex(double index) {

this.index = index;

}

public Node getNext() {

return next;

}

public void setNext(Node next) {

this.next = next;

}

}

LinkLsit类

package usps;

public class LinkList {

Node head;//头结点

int length;//单链表长度

public LinkList()//构造空链表

{

length = 0;

head = new Node(null);

}

public void add(double s1,double s2, int pos)//在链表中加入数据

{

int num=1;

Node p=head;

Node q=head.next;

while(num

{

p=q;

q=q.next;

num++;

}

p.next=new Node(q,s1,s2);//头结点不存放数据

length++;

}

public void allPut()//链表全部输出

{

if(isEmpty())

{

System.out.println("null");

}

else

{

Node p=head.next;

System.out.print("(");

if(p.coefficient!=0)//系数不等于0才会输出。

NFThVYfGC{

if(p.coefficient!=1.0) //如果系数等于1就不用输出

{

if(p.coefficient == -1 && p.index != 0)

System.out.print("-");

else

System.out.print(p.coefficient);//输出系数

}

if(p.coefficient == 1.0 && p.index ==0)

{

System.out.println(1);

}

if(p.index != 0 && p.index != 1.0)

{

System.out.print("X^" + p.index);

}

else if(p.index == 1.0)//如果指数等于1,就不输出指数

{

System.out.print("X");

}

}

p=p.next;

while(p!=null)

{

if(p.coefficient!=0)//系数不等于0才会输出。

{

if(p.coefficient>0)

{

System.out.print("+");//如果系数大于0，前面就带+号

}

if(p.coefficient!=1) //如果系数等于1就不用输出

{

if(p.coefficient == -1 && p.index != 0)

System.out.print("-");

else

System.out.print(p.coefficient);//输出系数

}

if(p.coefficient == 1 && p.index == 0)

{

System.out.print(1);

}

if(p.index != 0 && p.index != 1.0)

{

System.out.print("X^" + p.index);

}

else if(p.index == 1.0)//如果指数等于1,就不输出指数

{

System.out.print("X");

}

}

p=p.next;//继续下一个结点

}

System.out.print(")");

}

}

public boolean isEmpty()//判空

{

return length==0;

}

public int getLength() //求链表长度

{

return length;

}

public void setLength(int length)//改变链表长度

{

this.length = length;

}

}

Polynomial类

package usps;

import java.util.Scanner;

public class Polynomial

{

public Polynomial(){}

public LinkList inPoly()//建立一个多项式

{

Scanner scn=new Scanner(System.in);

int length;//结点个数

LinkList list=new LinkList();

length = scn.nextInt();//输入多项式的各项参数

//排序

for(int i = 1;i <=length;i++)//将参数放进链表

{

list.add(scn.nextDouble(),scn.nextDouble(),i);

}

return sort(notTwo(list));

}

public LinkList addPoly(LinkList a,LinkList b)//多项式相加

{

LinkList list = new LinkList();//存储结果的链表

Node a1=a.head.next;//a的头结点

Node b1=b.head.next;//b的头结点

int length = 1;//结果链表的长度。

while(a1!=null && b1!=null)

{

if(a1.index==b1.index)//如果指数相同，则系数相加

{

list.add(a1.coefficient+b1.coefficient,a1.index,length++);

a1 = a1.next;

b1 = b1.next;//指针后移，排除已经赋值给结果链表的结点

}

else

{

if (a1.index > b1.index)

//如果a1结点系数大于b1结点系数，就提出a1的值，因为b中都是比a1指数小的，不需要再比

{

list.add(a1.coefficient, a1.index, length++);

a1 = a1.next;

//b1没有入链表，下一次还要比较一遍

}

else//如果a1结点系数小于b1结点系数，就提出b1的值，因为a中都是比b1指数小的，不需要再比

{

list.add(b1.coefficient, b1.index, length++);

b1 = b1.next;

//a1没有入链表，下一次还要再比一遍

}

}

}

//将没有比完的结点都赋值给结果链表，此时另外一个链表是空的

while(a1!=null)

{

list.add(a1.coefficient,a1.index,length++);

a1 = a1.next;//下一个结点

}

while(b1!=null)

{

list.add(b1.coefficient,b1.index,length++);

b1 = b1.next;

}

return sort(list);

}

public LinkList minusPoly(LinkList a,LinkList b)//多项式相减

{

LinkList list = new LinkList();//存储结果的链表

Node a1 = a.head.next;

Node b1 = b.head.next;

int length = 1;

while (a1 != null && b1 != null)

{

if (a1.index == b1.index)

{

list.add(a1.coefficient - b1.coefficient,a1.index,length++);

a1 = a1.next;

b1 = b1.next;

}

else

{

if (a1.index > b1.index)

{

list.add(a1.coefficient, a1.index, length++);

a1 = a1.next;

//b1没有入链表，下一次还要比较一遍

http:// }

else

{

list.add(-b1.coefficient, b1.index, length++);

b1 = b1.next;

}

}

}

while(a1!=null)

{

list.add(a1.coefficient,a1.index,length++);

a1 = a1.next;//下一个结点

}

while(b1!=null)

{

list.add(-b1.coefficient,b1.index,length++);

b1 = b1.next;

}

return sort(list);

}

public LinkList mulPoly(LinkList a,LinkList b)//多项式相乘

{

LinkList list = new LinkList();//存储结果的链表

Node a1=a.head.next;//a的头结点

int length = 0;//结果链表的长度。

while(a1!=null )//将a的每个项乘b的每个项

{

Node b1=b.head.next;//b的头结点

//每个轮回让b1回到第一个结点

while(b1!=null)

{

list.add(a1.coefficient*b1.coefficient, a1.index+b1.index, ++length);

list.length=length;

b1=b1.next;

}

a1 = a1.next;

}

return sort(notTwo(list));

}

public double getXValue(LinkList a,double x)//多项式在x处的值

{

double num=0;

Node p = a.head.next;

while(p!=null)

{

num+=p.coefficient*(Math.pow(x,p.index));

p = p.next;

}

return num;

}

public LinkList derfPoly(LinkList a)//求导函数

{

Node p = a.head.next;

while(p!=null)

{

p.setCoefficient(p.coefficient*p.index);

p.setIndex(p.index-1);

p = p.next;

}

return a;

}

public LinkList sort(LinkList list)//排序

{

if(list.isEmpty())

{

System.out.println("null");

}

else

{

Node p = list.head.next;

if (list.isEmpty())

{

System.out.println("null");

}

else

{

while (p != null)

{

Node q = p.next;

Node r = new Node();//中转

while (q != null)

{

if (p.index < q.index)

{

r.setCoefficient(q.coefficient);

r.setIndex(q.index);

q.setCoefficient(p.coefficient);

q.setIndex(p.index);

p.setCoefficient(r.coefficient);

p.setIndex(r.index);

}

q = q.next;

}

p = p.next;

}

}

}

return list;

}

public LinkList notTwo(LinkList a)//合并同类项

{

LinkList list = new LinkList();

Node p=a.head.next;

int length=0;

while(p!=null)//每个轮回会将当前第一个结点与剩余结点比较，合并同类项

{

Node q=p.next;

double coefficient=p.coefficient;

while(q!=null)

{

if(p.index==q.index)//如果指数相等，则合并

{

coefficient += q.coefficient;

q.setCoefficient(0);//删除被合并的结点

q.setIndex(0);

}

q = q.next;//比较下一个结点

}

list.add(coefficient,p.index,++length);//比完一个轮回，将当前的第一个结点输入链表

p = p.next;

}

return list;

}

}

{

p=q;

q=q.next;

num++;

}

p.next=new Node(q,s1,s2);//头结点不存放数据

length++;

}

public void allPut()//链表全部输出

{

if(isEmpty())

{

System.out.println("null");

}

else

{

Node p=head.next;

System.out.print("(");

if(p.coefficient!=0)//系数不等于0才会输出。

NFThVYfGC{

if(p.coefficient!=1.0) //如果系数等于1就不用输出

{

if(p.coefficient == -1 && p.index != 0)

System.out.print("-");

else

System.out.print(p.coefficient);//输出系数

}

if(p.coefficient == 1.0 && p.index ==0)

{

System.out.println(1);

}

if(p.index != 0 && p.index != 1.0)

{

System.out.print("X^" + p.index);

}

else if(p.index == 1.0)//如果指数等于1,就不输出指数

{

System.out.print("X");

}

}

p=p.next;

while(p!=null)

{

if(p.coefficient!=0)//系数不等于0才会输出。

{

if(p.coefficient>0)

{

System.out.print("+");//如果系数大于0，前面就带+号

}

if(p.coefficient!=1) //如果系数等于1就不用输出

{

if(p.coefficient == -1 && p.index != 0)

System.out.print("-");

else

System.out.print(p.coefficient);//输出系数

}

if(p.coefficient == 1 && p.index == 0)

{

System.out.print(1);

}

if(p.index != 0 && p.index != 1.0)

{

System.out.print("X^" + p.index);

}

else if(p.index == 1.0)//如果指数等于1,就不输出指数

{

System.out.print("X");

}

}

p=p.next;//继续下一个结点

}

System.out.print(")");

}

}

public boolean isEmpty()//判空

{

return length==0;

}

public int getLength() //求链表长度

{

return length;

}

public void setLength(int length)//改变链表长度

{

this.length = length;

}

}

Polynomial类

package usps;

import java.util.Scanner;

public class Polynomial

{

public Polynomial(){}

public LinkList inPoly()//建立一个多项式

{

Scanner scn=new Scanner(System.in);

int length;//结点个数

LinkList list=new LinkList();

length = scn.nextInt();//输入多项式的各项参数

//排序

for(int i = 1;i <=length;i++)//将参数放进链表

{

list.add(scn.nextDouble(),scn.nextDouble(),i);

}

return sort(notTwo(list));

}

public LinkList addPoly(LinkList a,LinkList b)//多项式相加

{

LinkList list = new LinkList();//存储结果的链表

Node a1=a.head.next;//a的头结点

Node b1=b.head.next;//b的头结点

int length = 1;//结果链表的长度。

while(a1!=null && b1!=null)

{

if(a1.index==b1.index)//如果指数相同，则系数相加

{

list.add(a1.coefficient+b1.coefficient,a1.index,length++);

a1 = a1.next;

b1 = b1.next;//指针后移，排除已经赋值给结果链表的结点

}

else

{

if (a1.index > b1.index)

//如果a1结点系数大于b1结点系数，就提出a1的值，因为b中都是比a1指数小的，不需要再比

{

list.add(a1.coefficient, a1.index, length++);

a1 = a1.next;

//b1没有入链表，下一次还要比较一遍

}

else//如果a1结点系数小于b1结点系数，就提出b1的值，因为a中都是比b1指数小的，不需要再比

{

list.add(b1.coefficient, b1.index, length++);

b1 = b1.next;

//a1没有入链表，下一次还要再比一遍

}

}

}

//将没有比完的结点都赋值给结果链表，此时另外一个链表是空的

while(a1!=null)

{

list.add(a1.coefficient,a1.index,length++);

a1 = a1.next;//下一个结点

}

while(b1!=null)

{

list.add(b1.coefficient,b1.index,length++);

b1 = b1.next;

}

return sort(list);

}

public LinkList minusPoly(LinkList a,LinkList b)//多项式相减

{

LinkList list = new LinkList();//存储结果的链表

Node a1 = a.head.next;

Node b1 = b.head.next;

int length = 1;

while (a1 != null && b1 != null)

{

if (a1.index == b1.index)

{

list.add(a1.coefficient - b1.coefficient,a1.index,length++);

a1 = a1.next;

b1 = b1.next;

}

else

{

if (a1.index > b1.index)

{

list.add(a1.coefficient, a1.index, length++);

a1 = a1.next;

//b1没有入链表，下一次还要比较一遍

http:// }

else

{

list.add(-b1.coefficient, b1.index, length++);

b1 = b1.next;

}

}

}

while(a1!=null)

{

list.add(a1.coefficient,a1.index,length++);

a1 = a1.next;//下一个结点

}

while(b1!=null)

{

list.add(-b1.coefficient,b1.index,length++);

b1 = b1.next;

}

return sort(list);

}

public LinkList mulPoly(LinkList a,LinkList b)//多项式相乘

{

LinkList list = new LinkList();//存储结果的链表

Node a1=a.head.next;//a的头结点

int length = 0;//结果链表的长度。

while(a1!=null )//将a的每个项乘b的每个项

{

Node b1=b.head.next;//b的头结点

//每个轮回让b1回到第一个结点

while(b1!=null)

{

list.add(a1.coefficient*b1.coefficient, a1.index+b1.index, ++length);

list.length=length;

b1=b1.next;

}

a1 = a1.next;

}

return sort(notTwo(list));

}

public double getXValue(LinkList a,double x)//多项式在x处的值

{

double num=0;

Node p = a.head.next;

while(p!=null)

{

num+=p.coefficient*(Math.pow(x,p.index));

p = p.next;

}

return num;

}

public LinkList derfPoly(LinkList a)//求导函数

{

Node p = a.head.next;

while(p!=null)

{

p.setCoefficient(p.coefficient*p.index);

p.setIndex(p.index-1);

p = p.next;

}

return a;

}

public LinkList sort(LinkList list)//排序

{

if(list.isEmpty())

{

System.out.println("null");

}

else

{

Node p = list.head.next;

if (list.isEmpty())

{

System.out.println("null");

}

else

{

while (p != null)

{

Node q = p.next;

Node r = new Node();//中转

while (q != null)

{

if (p.index < q.index)

{

r.setCoefficient(q.coefficient);

r.setIndex(q.index);

q.setCoefficient(p.coefficient);

q.setIndex(p.index);

p.setCoefficient(r.coefficient);

p.setIndex(r.index);

}

q = q.next;

}

p = p.next;

}

}

}

return list;

}

public LinkList notTwo(LinkList a)//合并同类项

{

LinkList list = new LinkList();

Node p=a.head.next;

int length=0;

while(p!=null)//每个轮回会将当前第一个结点与剩余结点比较，合并同类项

{

Node q=p.next;

double coefficient=p.coefficient;

while(q!=null)

{

if(p.index==q.index)//如果指数相等，则合并

{

coefficient += q.coefficient;

q.setCoefficient(0);//删除被合并的结点

q.setIndex(0);

}

q = q.next;//比较下一个结点

}

list.add(coefficient,p.index,++length);//比完一个轮回，将当前的第一个结点输入链表

p = p.next;

}

return list;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。