超长整型加减法报告

1. 实验目的

1. 了解Java语言中链表、队列等线性数据结构的使用；
2. 掌握在链表、队列等线性数据结构基础上，设计与实现特定算法的能力；

2. 实验环境

1. 操作系统：Windows / Mac OS X / Linux
2. JDK版本：JDK 1.7及以上
3. 开发工具：Eclipse/IntelliJ IDEA

3．实验题目1-使用链表实现高精度整数加减法运算

【测试数据】：

输入数据可以采用每三位整数一组（中间加逗号），也可以不加逗号（比如： 100000000）。

（1）0；0；+ ，输出“0”。

（2）100，100，100；100，100，100，+，输出：200，200，200

（4）自选数据

4. 实验总结

一、需求分析

在计算机中有存储整数的数据类型，比如整型、长整型、无符号整型等，但它们的存储位数是有限的。一般整型为16位长，长整型为32位长。所以该程序是设计一个实现任意长的整数进行加减法运算的算法程序。运算符和运算数由键盘输入。

在该程序中，有一些要求及规范处理：

1、需要利用链表来存储数据（该程序使用的为双链表）。

2、数据的输入：要进行非法字符的判断，若格式有误，需要提示错误信息。

3、结果的输出：要求每3位以逗号分隔。

二、设计方案

1、流程

第一，通过Scanner输入，把两个运算数的每一位通过addFirst(e)循环存入linkedList链表（String类型）。因为是把每一位放在链表的头，所以如果用户输入的是“1234”，存入链表的是[4,3,2,1]，运算数的最高位在链表的尾部。

第二，根据输入的数据判断是否合法。运算数不能以0开头且必须为0~9的数字、运算符只能是“+”或“-”，否则提示错误信息。

第三，对存入链表的两个数，比较大小。长度不同时，把链表长度大的链表赋给max，链表长度短的赋给min；长度相同时，通过循环依次转换成int类型的数字，逐个从链表尾部比较，大的赋给max，小的赋给min。

第四，根据输入的运算符号判断是加号还是减号，从而去进行加减法运算，并返回String类型的结果。

第五，对返回的结果进行格式化处理。

2、用到的方法

把字符串传入链表	private static linkedList Str2List(String str)
检查字符合法性	private static String check(String str_a, String str_b, String str_s)
判断是否为数字	public static boolean isNumeric(String str)
比较大小	private static Map Compare(linkedList a, linkedList b)
加法运算	private static String add(linkedList max, linkedList min)
减法运算	private static String sub(linkedList max, linkedList min)
处理结果字符串	public static String displayWithComma(String str)

3、关键算法

加法运算流程：

（1）初始化计算结果result,保存进位值的变量carry=0

（2）取两个运算数的最低位数值，分别存入变量max_i和min_i

（3）计算r=max_i+min_i+carry

（4）若r>10，则carry=1，将r=r%10存入result的链表头部；否则，carry=0， 将r存入result的链表头部

（5）取运算数max和min的前一位数值，分别存入变量max_i和min_i。若min_i不存在，则将min_i置为0，跳转至第4步；若max_i不存在，则结束运算。

减法运算流程：

（1）初始化计算结果result,保存借位值的变量borrow=0

（2）取两个运算数的最低位数值，分别存入变量max_i和min_i

（3）计算r=max_i-min_i-borrow

（4）若r<0，则borrow=1，将r=r+10存入result的链表头部；否则，borrow ＝0，将r存入result的链表头部

（5）取运算数max和min的前一位数值，分别存入变量max_i和min_i。若min_i不存在，则将min_i置为0，跳转至第4步；若max_i不存在，则结束运算。

三、测试程序

1、非法字符测试

2、加法测试

3、减法测试

（1）长度不等，大减小

（2）长度不等，小减大

（3）长度相等，大减小

（4）长度相等，小减大

四、遇到的问题与解决方法

问题：由于加减法运算的情况比较多，一开始我是根据情况分别进行运算。如上面测试减法时，有四种情况，我是每一种情况下，都写了一边减法的基本算法，而且比较大小的代码也是写在减法的函数里的，这造成了我的代码重复率高，而且不清楚，比较混乱。

解决方法：把比较大小的代码封装成一个方法，略加判断，就可以判断长度相等与不等时的两数大小。而且不管上面哪种情况都把大的赋给max，小的赋给min，这样一来之前补零的地方也不用分情况判断，都是往min里补零。此方法加法运算和减法运算时都有用，大程度减少了代码的重复。

但是这里又遇到一个问题，return只能返回一个变量，然而这里有max链表、min链表、flag判断正负数的标志词三个变量需要返回到主函数。

所以，我通过Map集合，把这三个变量以键值对方式存入map里，返回map；在由主函数通过map.get(key)获取到其中的数据。

这样便实现了传回多个值，获取多个值的效果。

五、源代码

package 第一周;

import java.util.HashMap;
import java.util.linkedList;
import java.util.Map;
import java.util.Scanner;

public class CopyOfIntegerAddSub {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		System.out.print("请输入a：");
		String str_a = scan.next();
		linkedList list_a = Str2List(str_a);
		System.out.print("请输入b：");
		String str_b = scan.next();
		linkedList list_b = Str2List(str_b);
		System.out.print("请输入运算符：");
		String str_s = scan.next();
		String str_pd = check(str_a, str_b, str_s); // 检查
		Map map = Compare(list_a, list_b);
		
		linkedList max = (linkedList) map.get("max");
		linkedList min = (linkedList) map.get("min");
		linkedList flag = (linkedList) map.get("flag");
		//System.out.println(flag);
		
		if (str_pd.length() > 0) {
			System.out.println(str_pd);
		} else {
			if (str_s.equals("+")) {
				String result_add = displayWithComma(add(max, min));
				System.out.println("加法结果为：" + result_add);
			} else if (str_s.equals("-")) {
				String result_sub = displayWithComma(sub(max, min));
				if(flag.getFirst().equals("-")){
					result_sub = "-" + result_sub;
				} 
				System.out.println("减法结果为：" + result_sub);
			}
		}

	}

	
	
	private static String add(linkedList max, linkedList min) {
		int carry = 0; // 是否进位，1为进位
		int r = 0; // 每位相加的结果
		linkedList result = new linkedList();

		int size_max = max.size(); // 链表a的长度
		int size_min = min.size(); // 链表b的长度

		for (int i = 0; i < size_max; i++) {
			int max_i = Integer.parseInt(max.get(i).toString());
			int min_i;
			if (i < size_min) {
				min_i = Integer.parseInt(min.get(i).toString());
			} else {
				min_i = 0;
			}
			r = max_i + min_i + carry;
			if (r < 10) {
				result.addFirst(r);
				carry = 0;
			} else {
				result.addFirst(r % 10);
				carry = 1;
				if (i == size_max - 1) { // 控制最后一次循环；如果不加，最后一位相加时，不会把1存入链表
					result.addFirst(carry);
				}
			}
		}

		String str = "";
		for (int i = 0; i < result.size(); i++) {
			str = str + result.get(i).toString();
		}
		return str;
	}

	
	
	private static String sub(linkedList max, linkedList min) {
		int borrow = 0; // 是否借位 1借
		int r = 0; // 每位相减的结果
		linkedList result = new linkedList();

		int size_max = max.size(); // 链表a的长度
		int size_min = min.size(); // 链表b的长度

			for (int i = 0; i < size_max; i++) {
				int max_i = Integer.parseInt(max.get(i).toString());
				int min_i;
				if (i < size_min) {
					min_i = Integer.parseInt(min.get(i).toString());
				} else {
					min_i = 0;
				}
				r = max_i - min_i - borrow;
				if (r < 0) {
					result.addFirst(r + 10);
					borrow = 1;
				} else {
					if (i == size_max - 1 && r == 0) { // 控制最后一次循环，两数相减如果为0，不显示0
						break;
					}
					result.addFirst(r);
					borrow = 0;
				}
			}
		
		String str = "";
		for (int i = 0; i < result.size(); i++) {
			str = str + result.get(i).toString();
		}
		return str;
	}

	
	
	private static Map Compare(linkedList a, linkedList b) {

		Map map = new HashMap(); // 为了可以返回多个值

		int size_a = a.size(); // 链表a的长度
		int size_b = b.size(); // 链表b的长度

		linkedList max = new linkedList();
		linkedList min = new linkedList();

		linkedList flag = new linkedList();

		if (size_a > size_b) {
			max = a;
			min = b;
			flag.addFirst("+");
		} else if (size_a < size_b) {
			max = b;
			min = a;
			flag.addFirst("-");
		} else {
			for (int i = 0; i < size_a; i++) {
				int a_i = Integer.parseInt(a.get(size_a - 1 - i).toString());
				int b_i = Integer.parseInt(b.get(size_b - 1 - i).toString());
				if (a_i == b_i) {
					continue;
				} else if (a_i < b_i) {
					flag.addFirst("-");
					max = b;
					min = a;
					break;
				} else {
					flag.addFirst("+");
					max = a;
					min = b;
					break;
				}
			}
		}
		map.put("max", max);
		map.put("min", min);
		map.put("flag", flag);
		return map;
	}

	
	
	private static linkedList Str2List(String str) {
		linkedList list = new linkedList();
		for (int i = 0; i < str.length(); i++) {
			char c = str.charAt(i);
			list.addFirst(c);
			
		}
		// System.out.println("输出："+list);
		return list;
	}

	
	
	public static String displayWithComma(String str) {
		str = new StringBuffer(str).reverse().toString(); // 先将字符串颠倒顺序
		String str2 = "";

		int size = (str.length() % 3 == 0) ? (str.length() / 3)
				: (str.length() / 3 + 1); // 每三位取一长度

		
		for (int i = 0; i < size - 1; i++) { // 前n-1段
			str2 += str.substring(i * 3, i * 3 + 3) + ",";
		}

		for (int i = size - 1; i < size; i++) { // 第n段
			str2 += str.substring(i * 3, str.length());
		}

		str2 = new StringBuffer(str2).reverse().toString();

		return str2;
	}


	
	
	public static boolean isNumeric(String str) {
		for (int i = str.length(); --i >= 0;) {
			if (!Character.isDigit(str.charAt(i))) {
				return false;
			}
		}
		return true;
	}

	
	
	private static String check(String str_a, String str_b, String str_s) {
		boolean result = true;
		String str = "";
		if ((str_a.startsWith("0")) || (isNumeric(str_a) == false)) {
			str = str + " a 为非法数值";
		}
		if ((str_b.startsWith("0")) || (isNumeric(str_b) == false)) {
			str = str + " b 为非法数值";
		}
		if (!((str_s.equals("+")) || (str_s.equals("-")))) {
			str = str + " 非法运算符";
		}
		return str;
	}
}