时间：2022-12-07 09:37:05 | 栏目：JAVA代码 | 点击：次
一元稀疏多项式计算器
【问题描述】 设计一个一元稀疏多项式简单计算器。
【基本要求】一元稀疏多项式简单计算器的基本功能是：
(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。
**
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();
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);
}
}
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;
}
}
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<pos)
{
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才会输出。
{
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;
}
}
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没有入链表，下一次还要比较一遍
}
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;
}
}