[数据结构与算法]大数相乘 （字符串相乘）

例如："123" 与 "456"，我们的得出结果 "56088"。

模拟人做乘法，两个数相乘，首先将第一个数和第二个数的最后一位相乘，然后将第一个数和第二个数的倒数第二位相乘并左移一位和之前的结果相加，这里就要用到大整数的加法。

代码的一些的说明：?

#include <iostream>
#include<string>
using namespace std;

//这里面试官提到如果给定的字符串前缀有 0 的情况，即 "0123"、"0456" 的情况，如何处理：
//由于此函数会用于去掉 num1、num2 以及返回的结果 res 前缀多余的0，为了减少重复代码，于是有了此函数
//此函数的作用就是去掉字符串中前缀多余的 0，例："0123" --> "123"
string removeZero(string str) {
	int n = str.size();
	int i = 0;
	while (str[i] == '0') {
		++i;
	}
	return str.substr(i, n - i);    //substr()函数的作用：获得从 i 位开始长度为 n - i 的字符串
}
string multiply(string num1, string num2) {
	//先考虑如果有一个字符串为 "0"，那么直接返回 "0"即可，因为任何数和 0 相乘结果都为 0
	if (num1 == "0" || num2 == "0") {
		return "0";
	}
	//其次考虑 num1 或 nums2 其中有一个为 "1" 的这种情况，任何数和 1 相乘，结果为自身
	if (num1 == "1") return num2;
	if (num2 == "1") return num1;
	//这里的 num1、num2 是去掉多余前缀 0 之后的字符串
	num1 = removeZero(num1);
	num2 = removeZero(num2);
	//大数 * 小数，效率高一些
	if (num1.size() < num2.size()) {
		swap(num1, num2);
	}
	int m = num1.size();
	int n = num2.size();
	//提前开一个足够大的 string， m 位数和 n 位数的乘法，结果不会超过 m + n位数
	string res(m + n, '0');
	//外层循环的作用是：依次从右向左，每次 for循环 固定 num2 的一位
	for (int i = n - 1; i >= 0; --i) {
		//如果当前与 num1 各个位相乘的 num2 中的元素为 0 的话，那么就没有继续的必要了，直接结束本次循环
		if (num2[i] == '0') continue;
		int c_in = 0; //进位
		//内层循环的作用是：用外层循环固定的 nums2 中的一位，分别与 num1 从右向左的每一位相乘，并把结果相加放入到 res 结果集中
		for (int j = m - 1; j >= 0; --j) {
			//new_num：当前 num2 与 num1 元素乘积 + 此num2[i]之后的元素在res[i + j + 1]留下的元素和 + 进位 
			int new_num = (num1[j] - '0') * (num2[i] - '0') + (res[i + j + 1] - '0') + c_in;
			c_in = new_num / 10;
			new_num = new_num % 10;
			res[i + j + 1] = char(new_num + '0');
		}
		//如果 c_in 大于 0，说明需要往前多写一位
		if (c_in > 0) res[i] = char(c_in + '0');
	}
	//如果最后一次运算的 c_in 不大于 0 ，说明没有产生进位，由于我们的 res 初始化是按照两数相乘能得到的最大的位数，所以 res 的前缀必将多出 0，我们要去掉多出的前缀 0 
	res = removeZero(res);
	return res;
}
int main() {
	string num1, num2;
	cin >> num1;
	cin >> num2;
	string res = multiply(num1, num2);
	cout << res << endl;
	return 0;
}

运行结果：

?