0

我正在尝试将存储在两个单链表中的数字相乘。但是，我的算法变得非常复杂。我正在按照我们在小学时所做的方式进行乘法运算。获取其中一个列表的值并乘以另一个列表的每个值，直到我们覆盖所有数字。问题是我必须在最后将这些数字相加才能得到乘法的最终结果，这就是我遇到麻烦的地方。我必须找到一种能够将任意数量的元素相乘并能够在最后将结果相加的方法。到目前为止我的代码是这样的

public SingleyLinkedList Multiply(SingleyLinkedList list1, 
                                  SingleyLinkedList list2)
        {
        SingleyLinkedList multiplyList = new SingleyLinkedList();
        SingleyLinkedList tempList1 = new SingleyLinkedList();
        SingleyLinkedList tempList2 = new SingleyLinkedList();

        for (int j = 0; j < list2.Size(); j++)
        {
            int carry = 0;
            int B = Convert.ToInt32(list2.GetValue(j));

            for (int k = 0; k < list1.Size(); k++)
            {

                int A = Convert.ToInt32(list1.GetValue(k));

                if (k == list1.Size()-1)
                {
                    int multiply = ((A * B) + carry);
                    multiplyList.InsertAtFront(multiply);
                    carry = 0;
                }
                if (k < list1.Size()-1)
                {
                    int multiply = ((A * B) + carry) % 10;
                    multiplyList.InsertAtFront(multiply);
                    carry = 0;
                }
                carry = (int)((A * B) / 10);
            }
        }
      //return multiplyList;

        for ( int t = 0 ; t < list2.Size() ; t++)
        {

            for (int n = 0; n < list1.Size(); n++)
            {
                int val = Convert.ToInt32(multiplyList.GetValue(n));
                tempList1.InsertAtFront(val);
            }

            // adding zero to take care of 10th                
            for (int m = 0; m < list2.Size() - 1; m++)
            {
                tempList1.InsertAtFront(0);
            }

        }

        return tempList1;`

在这个阶段之后，我必须将我的值传递给我创建的 Add 方法，该方法将两个链表作为参数并进行加法。我需要能够对任意数量的数字执行此过程。有什么建议，或者您是否知道任何更好的乘法方法？

4

2 回答 2

0

您可能想要复制此 java 代码。

import java.util.LinkedList;
import java.util.ListIterator;

public class MultiplyTwoLinkedLists {

    public static void main(String[] args) {

        LinkedList<Integer> number1 = new LinkedList<Integer>();
        LinkedList<Integer> number2 = new LinkedList<Integer>();
        number1.addFirst(1);
        number1.addFirst(2);

        number2.addFirst(1);
        number2.addFirst(2);

        multiply(number1, number2);
    }

    public static int multiply(LinkedList<Integer> n1, LinkedList<Integer> n2){

        int placeValue1 = 1;
        int sum=0;
        for(int digit1 : n1){
            int placeValue2 = 1;
            for(int digit2 : n2){
                sum+=((digit1*placeValue1) * (digit2*placeValue2));
                placeValue2=placeValue2*10;
            }
            placeValue1=placeValue1*10;
        }
        System.out.println(sum);
        return 1;
    }


}
于 2013-10-29T19:32:12.713 回答
0

这看起来像是对一个简单问题的不必要的复杂实现。闻起来像家庭作业。

您提到最终将值相加时遇到了麻烦（就像在长乘法中一样。

我建议实现一个sum方法，并使用一个sum列表。

将总和列表初始化为 0，然后在乘法过程的每次迭代之后，使用该sum方法将新列表添加到sum列表中。


或者，您可以为乘法的第一部分提供一个列表列表，然后在最后将所有这些列表相加。

此实现将占用更多内存，但可视化也会更容易一些。

于 2012-12-03T19:46:02.957 回答