使用java中的链表进行多项式加法 [英] polynomial addition using linked list in java
问题描述
这是我使用链接列表添加两个多项式的实现。
例如，如果我想添加
3x ^ 2 + 5 ^ x + 3和4x ^ 3 + 5x + 2
Here's my implementation of a addition of two polynomials using a linked List.
For example if I want to add
3x^2+5^x+3 and 4x^3+5x+2
首先我检查两个多项式中是否存在类似的指数，如果是，我添加它们的系数，并将指数附加到字符串中。 >
添加类似的指数然后使用字符串我将两个多项式中的其余部分添加到最终结果中。
first I check if there are similar exponents in the two polynomials and if so I add their coefficients and I append the exponents to a string.
After adding similar exponents then using the string I add the remaining parts in both polynomials to the final result.
public class Node2{
int coef;
int exp;
Node2 next;
Node2(int c,int e,Node2 n){
coef=c;
exp=e;
next=n;
}
Node2(int c,int e){
coef=c;
exp=e;
}
}
public class LinkedPoly{
static String exponent="";
Node2 head;
Node2 current;
LinkedPoly(){
head=null;
}
public void createList(int c,int e){
head=new Node2(c,e,head);
}
public static LinkedPoly add(LinkedPoly list1,LinkedPoly list2){
LinkedPoly addList=new LinkedPoly();
Node2 temp1=list1.head;
Node2 temp3=temp1;
Node2 temp2=list2.head;
Node2 temp4=temp2;
while(temp1.next!=null){
while(temp2.next!=null){
if(temp1.exp==temp2.exp){
addList.createList((temp1.coef+temp2.coef),temp1.exp);
exponent+=temp1.exp;
}
temp2=temp2.next;
}
temp1=temp1.next;
temp2=temp4;
}
String[] array=exponent.split("");
for(int i=1;i<array.length;i++){
while(temp3.next!=null){
if(temp3.exp!=Integer.parseInt(array[i])){
addList.createList(temp3.coef,temp3.exp);
}
temp3=temp3.next;
}
while(temp4.next!=null){
if(temp4.exp!=Integer.parseInt(array[i])){
addList.createList(temp4.coef,temp4.exp);
}
temp4=temp4.next;
}
}
return addList;
}
public static void main (String args[]){
LinkedPoly l1=new LinkedPoly();
l1.createList(3,2);
l1.createList(5,1);
l1.createList(3,0);
LinkedPoly l2=new LinkedPoly();
l2.createList(4,3);
l2.createList(5,1);
l2.createList(2,0);
LinkedPoly l3=add(l1,l2);
System.out.println(l3.head.next.next.coef);
}
}
根据我的例子，指数字符串包括1和0，但它只将系数加1。而且其余的加法也是错误的。
According to my example the exponent string include 1 and 0 ,but it only sums the coefficient of 1.Also the rest of the addition is also wrong.
我无法看到我在哪里错误。我怎样才能打印出最终的addList，以便我可以检查这个实现是否正常
I can't see where I am mistaking.Also how can I print out the final addList so that I can check if this implementation works fine
推荐答案
这是一个有效的添加方法：
Here's an add method that works:
public static LinkedPoly add(LinkedPoly list1,LinkedPoly list2){
LinkedPoly addList=new LinkedPoly();
Node2 temp1=list1.head;
Node2 temp3=temp1;
Node2 temp2=list2.head;
Node2 temp4=temp2;
while(temp1.next!=null){
while(temp2.next!=null){
if(temp1.exp==temp2.exp){
addList.createList((temp1.coef+temp2.coef),temp1.exp);
exponent+=temp1.exp;
}
temp2=temp2.next;
}
temp1=temp1.next;
temp2=temp4;
addList.print();
}
String[] array=exponent.split("");
while(temp3!=null){
boolean exponentPresent = false;
for(int i=1;i<array.length;i++){
if(temp3.exp==Integer.parseInt(array[i])){
exponentPresent = true;
}
}
if (!exponentPresent) {
addList.createList(temp3.coef,temp3.exp);
}
temp3=temp3.next;
}
while(temp4!=null){
boolean exponentPresent = false;
for(int i=1;i<array.length;i++){
if(temp4.exp==Integer.parseInt(array[i])){
exponentPresent = true;
}
}
if (!exponentPresent) {
addList.createList(temp4.coef,temp4.exp);
}
temp4=temp4.next;
}
return addList;
}
这是一个可以添加到LinkedPoly类的打印方法：
And here's a print method you can add to the LinkedPoly class:
public void print() {
current = head;
System.out.print(current.coef + "x^" + current.exp);
while (current.next != null) {
current = current.next;
System.out.print(" + " + current.coef + "x^" + current.exp);
}
System.out.println();
}
您的添加方法存在两个主要问题。
There were two main issues with your add method.
问题＃1 。第一个是你通过已包含的指数数组的循环在你的循环之外通过多项式链表的节点 - 它应该在内部。你以前的方式，你的过程是这样的：
Issue #1. The first was that your loop through the array of already included exponents was outside of your loops through the nodes of the polynomial linked lists - it should be on the inside. The way you were doing it before, your process went like this:
a。从数组
b中取一个已经包含的指数。遍历每个多项式
c的所有项。如果这些术语中的任何一个具有与a部分中的指数不匹配的指数，则将其添加到结果中。
d。从a。部分重复，但使用已包含的指数中的下一个。
a. Take one of the already included exponents from the array b. Go through all the terms of each polynomial c. If any of those terms has an exponent that doesn't match the exponent from part a., add it to the result. d. Repeat from part a., but using the next of the already included exponents.
这种方法的问题是你只想在结果中添加一个新术语它的指数与已经包含的任何条款都不匹配 - 不仅仅是它与其中一个不匹配。这就是为什么你的结果具有所有额外的x ^ 1项 - 当你的程序在数组的0元素时，它正在添加多项式的x ^ 1项。
The problem with this approach is that you only want to add a new term to the result if its exponent doesn't match ANY of the already included terms - not just if it doesn't match one of them. This is why your result had all those extra x^1 terms - when your program was at the "0" element of the array, it was adding the x^1 terms of the polynomials.
问题＃2 。你应该用（temp3！= null）或（temp4！= null）替换while（temp3.next！= null）或（temp4.next！= null）。否则，你的代码永远不会到达多项式的最后一个节点（它在最后一个节点之前停止，因为它正在检查是否在最后一个节点之后有一个下一个）。这就是为什么你的结果没有x ^ 3和x ^ 4术语 - 你的循环在达到这些条件之前就结束了。
Issue #2. You should replace while (temp3.next!= null) or (temp4.next!=null) with just (temp3!=null) or (temp4!=null). Otherwise, your code never gets to the last node of the polynomial (it stops before the last one because it's checking to see if there's a "next" one after the last one). This is why your result didn't have the x^3 and x^4 terms - your loops were ending before getting to those terms.
一些东西考虑
- 你使用了很多临时变量。尝试给他们更多的描述性名称，或者更好的是，找到一种不使用这么多的方法。
- 我不确定为什么要将已使用的指数添加到exponent中string，然后使用split（）方法分解为数组。考虑从一开始就添加一个数组。
- 你的add方法可能会被重组为更清洁。您可以尝试这样做：在任何多项式中找到最高指数，而不是看到两个多项式有哪些共同点，处理它们，然后处理它们没有共同点的那些。然后，循环遍历从0到该数字的所有指数度数。在每个周期内，循环通过每个多项式，并将具有该指数的所有多项式的系数相加。这样，你的代码就会在一个大循环中。
- 现在，你的代码不能确保多项式保持它们的条件顺序 - 没有办法阻止x ^来自ax ^ 3 term之前的2个词，它来自ax ^ 1 term。考虑向LinkedPoly类添加sort（）方法，在节点添加期间添加一些代码以确保多项式保持有序，或者使用上面的建议＃3，这将允许您在创建它时对求和多项式进行排序。或者，如果将它们按顺序排列并不重要，请不要打扰：）
- You use a lot of temp variables. Try giving them more descriptive names, or better yet, find a way that doesn't use so many.
- I'm not sure why you add the already used exponents to an "exponent" string, which you then break up into an array with the split() method. Consider just adding to an array from the start.
- Your add method could probably be restructured to be a lot cleaner. Instead of seeing which exponents your two polynomials have in common, dealing with those, and then dealing with the ones they don't have in common separately, you could try this: find the highest exponent in any of your polynomials. Then, cycle through all the exponent degrees from 0 to that number. Within each of those cycles, cycle through each polynomial, and add together the coefficients of all the polynomials that have that exponent. That way, your code would all be in one big loop.
- Right now, your code doesn't ensure that the polynomials keep their terms in order - there's no way to stop the x^2 term from coming before a x^3 term, which comes before a x^1 term. Consider either adding a sort() method to your LinkedPoly class, adding some code during node addition that ensures the polynomials stay in order, or going with suggestion #3 above, which would allow you to sort your sum polynomial as you create it. Or, if having them in order isn't important, don't bother :)
这篇关于使用java中的链表进行多项式加法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
