java中使用链表的多项式加法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/24394860/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
polynomial addition using linked list in java
提问by clarkson
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
这是我使用链表实现两个多项式相加的实现。
例如，如果我想添加
3x^2+5^x+3 和 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);
}
}
}
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.
根据我的例子，指数字符串包括 1 和 0 ，但它只对系数 1 求和。此外，其余的加法也是错误的。
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
我看不出哪里出错了。另外，我如何打印出最终的 addList 以便我可以检查此实现是否正常工作
采纳答案by user3771832
Here's an add method that works:
这是一个有效的 add 方法：
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;
}
And here's a print method you can add to the LinkedPoly class:
这是您可以添加到 LinkedPoly 类的打印方法：
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.
您的 add 方法有两个主要问题。
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:
问题#1。第一个是通过已包含的指数数组的循环在通过多项式链表的节点的循环之外 - 它应该在内部。你以前的做法，你的过程是这样的：
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.
一种。从数组 b 中取出已包含的指数之一。遍历每个多项式 c 的所有项。如果其中任何一项的指数与 a. 部分的指数不匹配，则将其添加到结果中。d. 从 a. 部分重复，但使用下一个已包含的指数。
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.
这种方法的问题在于，如果新项的指数与任何已包含的项都不匹配，您只想在结果中添加一个新项——而不仅仅是当它不匹配其中一个项时。这就是为什么您的结果具有所有这些额外的 x^1 项 - 当您的程序位于数组的“0”元素时，它会添加多项式的 x^1 项。
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.
问题#2。您应该将 while (temp3.next!= null) 或 (temp4.next!=null) 替换为 (temp3!=null) 或 (temp4!=null)。否则，您的代码永远不会到达多项式的最后一个节点（它在最后一个节点之前停止，因为它正在检查最后一个节点之后是否还有“下一个”节点）。这就是为什么您的结果没有 x^3 和 x^4 项的原因 - 您的循环在达到这些项之前就结束了。
A few things to consider
需要考虑的几件事
- 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 :)
- 您使用了很多临时变量。尝试为它们提供更具描述性的名称，或者更好的是，找到一种不使用这么多名称的方法。
- 我不确定为什么要将已经使用的指数添加到“指数”字符串中，然后使用 split() 方法将其分解为数组。考虑从一开始就添加到数组中。
- 您的 add 方法可能会重组为更清晰。与其查看您的两个多项式有哪些共同的指数，然后分别处理它们，然后再处理它们没有共同点的指数，您可以尝试以下操作：找到任何多项式中的最高指数。然后，循环遍历从 0 到该数字的所有指数度数。在每个循环中，循环遍历每个多项式，并将所有具有该指数的多项式的系数相加。这样，您的代码将全部处于一个大循环中。
- 现在，您的代码并不能确保多项式按顺序排列它们的项 - 无法阻止 x^2 项出现在 ax^3 项之前，而 ax^3 项出现在 ax^1 项之前。考虑向 LinkedPoly 类添加 sort() 方法，在节点添加期间添加一些代码以确保多项式保持有序，或者使用上面的建议 #3，这将允许您在创建和多项式时对其进行排序。或者，如果按顺序排列它们并不重要，请不要打扰:)
