Java中用ArrayList类实现正整数大数相加与相乘


在C语言中我们经常用数组处理大数问题，在java中数组功能逐渐被ArrayList类代替，强大的ArrayList类提供了clear()，equals()等32个方法，所以我们能轻松实现各种类的构造，以下代码将提供VeryLongInt类的设计：

[java]
  1. import java.util.ArrayList;  
  2. import java.util.Collections;  
  3.   
  4. class VeryLongInt{  
  5.     ArrayList digits;                          //digits字段，存放大数的各位数字   
  6.     public VeryLongInt(){  
  7.         final int INITIAL_CAPACITY = 500;  
  8.         this.digits = new ArrayList(INITIAL_CAPACITY);  
  9.     };//无参构造   
  10.       
  11.     public VeryLongInt(String s){  
  12.         this.digits = new ArrayList(s.length());  
  13.         for(int i =0; i<s.length();i++){  
  14.             char c=s.charAt(i);  
  15.             if(c>='0' && c<='9'){  
  16.                 this.digits.add(new Integer(c - '0'));  
  17.             }  
  18.         }  
  19.     };//含参构造   
  20.       
  21.     public String toString(){  
  22.         StringBuffer s = new StringBuffer("");  
  23.         for(int i=0;i<this.digits.size();i++)  
  24.             s.append(this.digits.get(i));  
  25.         return s.toString();  
  26.     }//将大数转为字符串形式   
  27.       
  28.     public void add(VeryLongInt otherVeryLong){  
  29.         int largerSize,partialSum,carry=0;  
  30.         VeryLongInt sum = new VeryLongInt();  
  31.         largerSize = this.digits.size()>otherVeryLong.digits.size() ? this.digits.size():otherVeryLong.digits.size();  
  32.         for(int i=0;i<largerSize;i++){  
  33.             partialSum = this.least(i)+otherVeryLong.least(i)+carry;  
  34.             carry = partialSum / 10;  
  35.             sum.digits.add(new Integer(partialSum%10));  
  36.         }  
  37.         if (carry == 1)  
  38.             sum.digits.add(1);  
  39.         Collections.reverse(sum.digits);    //反转sum   
  40.         this.digits.clear();  
  41.         this.digits = sum.digits;  
  42.     }//大数加法   
  43.       
  44.     public void mult(VeryLongInt otherVeryLong){  
  45.         int i = 1;  
  46.         if(((Integer)otherVeryLong.digits.get(0)).intValue()==0){  
  47.             this.digits.clear();  
  48.             this.digits.add(0);  
  49.             return ;  
  50.         }  
  51.         VeryLongInt sum = new VeryLongInt("1");  
  52.         VeryLongInt mult = new VeryLongInt(this.toString());  
  53.         while(!sum.equal(otherVeryLong)){  
  54.             this.add(mult);  
  55.             sum.add(new VeryLongInt("1"));  
  56.         }  
  57.     }//任意大数与单个数字相乘   
  58.       
  59.     public void multiply(VeryLongInt otherVeryLong){  
  60.         int length = otherVeryLong.digits.size();  
  61.         VeryLongInt multiply;  
  62.         VeryLongInt multiplycopy = new VeryLongInt(this.toString());  
  63.         this.digits.clear();  
  64.         this.digits.add(0);  
  65.         for(int i=0;i<length;i++ ){  
  66.             multiply =  new VeryLongInt(multiplycopy.toString());  
  67.             multiply.mult(new VeryLongInt((otherVeryLong.digits.get(i)).toString()));  
  68.             for(int j=1;j<length-i;j++)  
  69.                 multiply.digits.add(0);  
  70.             this.add(multiply);  
  71.         }  
  72.     }//大数与大数相乘   
  73.       
  74.     public int least(int i ){  
  75.         return i>=this.digits.size()?0:((Integer)this.digits.get(this.digits.size()-i-1)).intValue();  
  76.     }//返回从低位到高位第i位数字   
  77.       
  78.     public boolean equal(VeryLongInt v1){  
  79.         if (this.digits.size()!=v1.digits.size())  
  80.             return false;  
  81.         int length = this.digits.size();  
  82.         for(int i=length-1;i>=0;i--){  
  83.             if (((Integer)this.digits.get(i)).intValue()!=((Integer)v1.digits.get(i)).intValue())  
  84.                 return false;  
  85.         }  
  86.         return true;  
  87.     }//判断两大数是否相等   
  88.       
  89. }  
  90. public class ArrListDemo{  
  91.     public static void main(String args[]){  
  92.         VeryLongInt str1 = new VeryLongInt("11114532632462523462362547457357");  
  93.         str1.add(new VeryLongInt("0"));  
  94.         System.out.println(str1.toString());  
  95.         str1.multiply(new VeryLongInt("333333462462346234452643634247"));  
  96.         System.out.println(str1.toString());  
  97.     }  
  98. }  

output：

11114532632462523462362547457357
3704845646029468841285610955774783288521573545337081737305179

附几点ArrayList类与数组的几点区别：

1，当构造数组时必须指定初始容量，但是ArrayList不需要，ArrayList类提供了三种构造方法，以便于你选择是否需要指定初始容量。

2，在数组中插入元素时，必须指定索引值，而在ArrayList类中的add()方法则自动选择在ArrayList对象的末尾插入元素。

3，ArrayList类中的size()方法返回ArrayList对象中元素个数，而数组中的length字段则保存了数组可以插入的元素的最大值。

4，ArrayList类中的set()方法可以更改指定索引位置的元素，类似与数组中的直接赋值。

5，ArrayList类中的remove()方法可以删除指定索引位置的元素，而且时间复杂度为O(1)，而数组中实现这一功能则需要移动所删元素的后半段空间。

6，在数组中查找是否具有某一元素需要进行显式搜索，而在ArrayList类中只需一个indexOf()方法即可搞定。


当然，数组在一些地方依然有着ArrayList类无法替代的位置：

1，索引运算符可以用来访问或者修改数组中的元素。

eg：a[i]=a[j+1];

2，数组可以在构造的时候进行初始化。

eg：String []a = {"a","b","c"};

3，我们可以在数组的任意索引位置存储元素，但是对于ArrayList对象，只能在索引值为0、1、....、size()的位置存储元素。

4，可以创建任意类型（甚至是原始类型，例如int）的数组。对于ArrayList对象，每个元素的类型必须是Object或其子类。

相关内容