我正在使用字符串标记器和链表，并且链表是此赋值所必需的。有一个外部文件，里面有很多行多项式（每行一行）。使用String Tokenizer和Linked List，我运行了一个while循环，它在每次传递中捕获两行，并将它们添加到链表中。将数字加载到链表中后，目标是将这些多项式从其链表中添加到一起，并创建包含该多项式的新链表。
例如，文件中的前两行是：
2x^4-5x^3+9x^2-10
3x^4-6x^3+10x^2-11
=5x^4-11x^3+19x^2-21
这是我的代码：
public class PolynomialAddition
{
static File dataInpt;
static Scanner inFile;
public static void main(String[] args) throws IOException
{
dataInpt=new File("C:\llpoly.txt");
inFile=new Scanner(dataInpt);
StringTokenizer myTokens;
String line,polyTerm;
Node firstL=new Node();
Node secondL=new Node();
line=inFile.nextLine();
myTokens=new StringTokenizer(line);
polyTerm=myTokens.nextToken();
firstL.value=polyTerm.substring(0,polyTerm.indexOf("x"));
firstL.value2=polyTerm.substring(polyTerm.indexOf("^")+1);
}
}
这是我的节点类：
public class Node
{
public Object value;
public Object value2;
public Node next;
public Node()
{
value=null;
value2=null;
next=null;
}
public Node (Object value, Object value2, Node next)
{
this.value=value;
this.value2=value2;
this.next=next;
}
}
问题出现在这之后，一些行不完整，而必须添加到的行是完整的，如-12x^8+5x^2-3和8x^3+2x
答案应该是-12x^8+8x^3+5x^2+2x-3
我能做些什么来解决这个问题？
好吧，在聊天中经历了漫长的劳动之后，这就是"我们"想到的。我意识到这在某种程度上只是脱口而出。
即便如此，在干净风格的Java1.4代码中实现一个坚实的实现对您的理解有很大帮助。
特别注意以表格形式打印结果，将不同操作数的项排列在各自指数的列中。
代码
有两个文件：
Node.java
class Node {
int factor;
int exponent;
Node next;
public Node() {
factor = 0;
exponent = 0;
next = null;
}
public Node(int factor, int exponent, Node next) {
this.factor = factor;
this.exponent = exponent;
this.next = next;
}
public String toString() {
return String.format("%+4dx^%d ", new Integer[] { new Integer(factor), new Integer(exponent) });
}
}
多项式加法.java
import java.io.*;
import java.util.*;
public class PolynomialAddition {
static File dataInpt;
static Scanner inFile;
public static void main(String[] args) throws IOException {
dataInpt = new File("/tmp/input.txt");
inFile = new Scanner(dataInpt);
while (inFile.hasNextLine()) {
Node first = readPolynomial();
// printList(first);
Node second = readPolynomial();
// printList(second);
Node addition = addPolynomials(first, second);
// printList(addition);
printTabulated(first, second, addition);
System.out.println("n");
}
}
private static Node addPolynomials(Node first, Node second) {
Node head = null, current = null;
while (null!=first || null!=second)
{
boolean pickfirst = false;
boolean haveBoth = (null!=first && null!=second);
Node node;
if (haveBoth && first.exponent == second.exponent)
{
node = new Node(first.factor + second.factor, first.exponent, null);
first = first.next;
second = second.next;
} else
{
pickfirst = first!=null &&
((second == null) || first.exponent > second.exponent);
if (pickfirst)
{
node = new Node(first.factor, first.exponent, null);
first = first.next;
} else
{
node = new Node(second.factor, second.exponent, null);
second = second.next;
}
}
if (current == null)
{
head = node;
current = head;
} else
{
current.next = node;
current = node;
}
}
return head;
}
private static void printTabulated(Node first, Node second, Node addition) {
String line1="", line2="", barline="", line3="";
while (addition != null)
{
String
part1 = " ",
part2 = " ",
part3 = " ";
if (null!=first && first.exponent == addition.exponent)
{
part1 = first.toString();
first = first.next;
}
if (null!=second && second.exponent == addition.exponent)
{
part2 = second.toString();
second = second.next;
}
part3 = addition.toString();
addition = addition.next;
line1 += part1;
line2 += part2;
barline += "-----------";
line3 += part3;
}
System.out.println(line1);
System.out.println(line2);
System.out.println(barline);
System.out.println(line3);
}
private static Node readPolynomial() {
String line = inFile.nextLine();
StringTokenizer myTokens = new StringTokenizer(line);
Node head = null, previous = null;
while (myTokens.hasMoreTokens()) {
Node current = new Node();
String term = myTokens.nextToken();
if (term.startsWith("+"))
term = term.substring(1);
current.factor = Integer.parseInt(
term.substring(0, term.indexOf("x")));
current.exponent = Integer.parseInt(
term.substring(term.indexOf("^") + 1));
if (previous == null)
{
head = current;
previous = head;
} else
{
previous.next = current;
previous = current;
}
}
return head;
}
private static void printList(Node head) {
for (Node ptr = head; ptr != null; ptr = ptr.next)
System.out.print(ptr);
System.out.println();
}
}
示例数据：
输入：
2x^4 -5x^3 +9x^2 -10x^0
3x^4 -6x^3 +10x^2 -11x^0
-2x^1 +4x^0
2x^1 -4x^0
8x^5 +6x^4 +5x^2 -3x^0
-12x^8 +2x^7 +14x^5
1x^5 +7x^2 +8x^1
-5x^4 -7x^3 -4x^2 -3x^0
10x^5 -3x^3 +4x^2 -234x^1 -12x^0
-5x^5 -2x^3 +10x^0
输出：
+2x^4 -5x^3 +9x^2 -10x^0
+3x^4 -6x^3 +10x^2 -11x^0
--------------------------------------------
+5x^4 -11x^3 +19x^2 -21x^0
-2x^1 +4x^0
+2x^1 -4x^0
----------------------
+0x^1 +0x^0
+8x^5 +6x^4 +5x^2 -3x^0
-12x^8 +2x^7 +14x^5
------------------------------------------------------------------
-12x^8 +2x^7 +22x^5 +6x^4 +5x^2 -3x^0
+1x^5 +7x^2 +8x^1
-5x^4 -7x^3 -4x^2 -3x^0
------------------------------------------------------------------
+1x^5 -5x^4 -7x^3 +3x^2 +8x^1 -3x^0
+10x^5 -3x^3 +4x^2 -234x^1 -12x^0
-5x^5 -2x^3 +10x^0
-------------------------------------------------------
+5x^5 -5x^3 +4x^2 -234x^1 -2x^0
我会完全放弃链表方法。或者，如果必须使用它，请将其用作以下方法的输入。
预先分配一个具有一定大小上限的数组，然后使用数组的索引作为x的指数，并在相应的索引/指数处存储项的系数。因此，当您解析2x^3时，您会说polysum[3] += 2（假设数组是用0初始化的）。如果对具有相同polysum数组的两个多项式执行此操作，则会得到一个包含两个多项式之和的系数的数组。
然后你必须创建相应的输出，从数学上讲，它相当于：polysum[0] + polysum[1] * x + polysum[2] * x^2等
如果您可能必须处理完全任意的指数，并且数组的预分配不可行，请使用HashMap，其中键是指数，值是系数。
编辑：如果真的必须使用链接列表来解决问题，请对两个列表进行排序，然后并行迭代列表。在类似Python的伪代码中：
poly1_node = poly1_first_node
poly2_node = poly2_first_node
result_node = result_first_node
while poly1_node != Null and poly2_node != Null:
if poly1_node.value2 == poly2_node.value2:
result_node.value2 = poly1_node.value2
result_node.value = poly1_node.value + poly2_node.value
poly2_node = poly2_node.next
poly2_node = poly2_node.next
if poly1_node.value2 < poly2_node.value2:
result_node.value2 = poly1_node.value2
result_node.value = poly1_node.value
poly1_node = poly1_node.next
if poly2_node.value2 < poly1_node.value2:
result_node.value2 = poly2_node.value2
result_node.value = poly2_node.value
poly2_node = poly2_node.next
result_node.next = new Node()
result_node = result_node.next
while poly1_node != Null:
result_node.value2 = poly1_node.value2
result_node.value = poly1_node.value
poly1_node = poly1_node.next
result_node.next = new Node()
result_node = result_node.next
while poly2_node != Null:
result_node.value2 = poly2_node.value2
result_node.value = poly2_node.value
poly2_node = poly2_node.next
result_node.next = new Node()
result_node = result_node.next
如果你知道输入总是排序的，你可以跳过排序。否则，排序将是不平凡的。
我建议使用数组或arraylist，将数组索引用作多项式指数，并将数组值用作多项式的系数。
例如，3+4*x+5*x^4会3 4 0 0 5为数组列表。
最好创建一个名为Polynomial的类，并定义它的操作，而不是使用Node作为类。
3x^3-x^1与3x^3+0x^2-x^1+0是一样的。试着在读取时用这种方式填充每个值。
这就假设多项式是以指数递减形式写成的：（如果不是这样，请告诉我！）
在读入一行中的元素时，请检查当前元素的指数是否正好比前一个元素小一。如果是，那么就没有问题。如果不是，则采用以下方法：
设a为当前元素的指数，b为前一元素的指数。
然后使用此代码示例来修复此问题：
for(int i = b - 1; i > a; i--)
{
//Insert an element of the form: 0*x^i.
}
我同意使用数组的方法，但如果我们使用hashmap，我们就不能在空间复杂性方面进行更多优化吗。
所以每个多项式方程都是一个散列图，其中键是x的指数，值是x的系数。
现在，您可以简单地遍历一个hashmap的键，并将其添加到另一个hashmap。