1

我正在寻找有关 Java 作业的一些建议。我被要求做的是对存储在链表中的数字执行不同的操作，每个数字都在一个单独的节点中。重点是编写一个可以对非常大的数字进行算术运算的程序。

我正在寻求帮助的特定问题是编写一个比较两个数字的方法，类似于整数的常规 compareTo() 方法。如果 this.num < num 则返回 -1，如果 this.num > num 则返回 +1，如果相等则返回 0。

让我感到困难的是，赋值指定链表应该以相反的顺序存储数字。例如，数字 145 的链表如下所示：

5 => 4 => 1 => 空

这使得将数字相加更容易，但在尝试比较时让我很头疼。这是我想出的，评论解释了它应该如何工作。

public int compareTo(LLNum list)
{ // Compares two numbers.
  // If the two numbers are of a different length, clearly the shortest is the smallest.
  // If the two numbers are of equal length, call traverseToCompare to do the comparison.
  if (this.len > list.len)
  {
    compareResult = 1;
  }
  else if (this.len < list.len)
  {
    compareResult = -1;
  }
  else if (this.len == list.len)
  {
    traverseToCompare(this.head, list.head);
  }

  return compareResult;
}


public void traverseToCompare(ListNode node1, ListNode node2)
{ // In the case that both numbers are of the same length, recursively traverse the list.
  // compare each digit individually while unwinding the stack.
  // Once two digits are found to be different, break out of the unwinding (Note: I could not find a way of breaking out)
  // Since the dominant digit is at the tail end, this ensures the least number of   comparisons.
  if (node1 == null || node2 == null) 
  { // Base case. Handles the case where both numbers are identical.
    compareResult = 0;
    return;
  }
  traverseToCompare(node1.getNext(), node2.getNext());
  if (node1.getItem() > node2.getItem())
  {
    compareResult = 1;
  }
  if (node1.getItem() < node2.getItem())
  {
    compareResult = -1;
  }

  return; 
}

倒序的数字是让我走向递归的原因。我以为我会递归地遍历列表，然后在输出时比较每个数字，并以某种方式在不相同的第一个数字处打破递归。我意识到这不是使用递归的常用方法，但我不知道该怎么做。有没有一种方法可以在不抛出异常的情况下中断？我觉得这可能有点太草率了。或者关于如何在没有递归的情况下做到这一点的任何建议？

请不要只给我一些代码来复制和粘贴。我只是想指出正确的方向。谢谢！

4

4 回答 4

0

如果我必须这样做，我会首先检查两个列表的长度（就像你做的那样）。如果它们相等，进行比较的更好方法是为每个列表创建一个迭代器。然后，您可以同时递增迭代器并比较链表中该位置的值。这样做，一旦您确定一个列表包含比另一个更大的数字，您就可以简单地停止比较列表。

于 2013-02-18T04:52:52.007 回答
0

最好的方法是遍历每个数字的列表并构造数字，然后比较两个数字。

从列表中构造数字的方法是

int i = 0
int f = 1
Do while GetNext() <> Null
    i = i + GetCurrentItem() * f
    f = f * 10
End Do

例如。如果数字是 145，那么列表将有 5->4->1

所以运行上面的代码

i = 0
f = 1

i = i + 5*1 = 5
f = f * 10 = 10

i = i + 4*10 = 45
f = f * 10 = 100

i = i + 1*100 = 145
f = f * 10 = 1000

所以得出 i = 145。

于 2013-02-18T04:54:14.657 回答
0

使用纯字符串会容易得多；因为您可以存储任何长度的数据。但无论如何，要求是 LinkedList ：

现在数据以相反的顺序存储；这意味着您在浏览完整列表之前无法决定compareTo方法的响应，因为最重要的数据存储在最后一个位置。

  5 --> 4  --> 1    == 145
  1 --> 4 --> 5     == 541

所以至少通读一遍；然后您可以将值存储在String中，然后决定compareTo方法结果。

为相同长度的项目调用traverseToCompare方法。因此，您可以编写自己的算法来比较存储在String中的两个数字。

编辑 如果不允许字符串

然后会建议你手动做同样的事情；遍历整个列表比较最后一个节点，如果最后一个节点相同，则比较前一个节点，依此类推...

于 2013-02-18T04:56:16.130 回答
0

在 traverseToCompare 中，您需要处理一些情况。如果你不使用递归，它会更好更干净。以下可以是一个解决方案

boolean areSame = true;
boolean digitDiffer = false;
int compareResult = 0;
int length = node1.length
for(int i=0; i<length; i++)
{
   if(!digitDiffer && ((node1.getItem() == node2.getItem()))
   {
     continue
   }
   else
   {
      digitDiffer = true;
      if(node1.getItem() >= node2.getItem())
      {
         compareResult = 1
      }
      else
      {
        compareResult = -1;
      }
   }
}

return compareResult;
于 2013-02-18T04:58:00.593 回答