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+5×8－3.1×11) + (7－5×8+11×9)=(－3.1×11+11×9+2x+7)
2)(6x-3－x+4.4×2－1.2×9) －(-6x-3+5.4×2－x2+7.8×15)=(-7.8×15-1.2×9+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+2×100+x200)
6)(x+x2+x3)+0=x+x2+x3
7) 互換上述測試數據中的前後兩個多項式
【實現提示】 用帶表頭結點的單鏈表存儲多項式。
【選作內容】
1) 計算多項式在x處的值。
2) 求多項式 a 的導函數 。
3) 多項式a和b相乘，建立乘積多項式ab 。
4) 多項式的輸出形式為類數學表達式。例如 ，多項式 -3×8+6×3－18 的輸出形式為-3×8+6×3-18，x15+(－8)x7－14的輸出形式為s15+(-8)x7-14。註意，數值為1的非零次項的輸出形式中略去系數1，如項1×8的輸出形式為x8，項 －1×3的輸出形式為－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();
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<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;
}
}
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沒有入鏈表，下一次還要比較一遍
}
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;
}
}
到此這篇關於Java一元稀疏多項式計算器的文章就介紹到這瞭,更多相關Java計算器內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！
推薦閱讀：
- Java找出兩個大數據量List集合中的不同元素的方法總結
- 大數組元素差異removeAll與Map效率對比
- Java數據結構之鏈表詳解
- Java實現單鏈表SingleLinkedList增刪改查及反轉 逆序等
- Java實現哈希表的基本功能