算法---大整数相加

浏览数：23 / 时间：2015年06月08日

　　开通博客开始第一次写发表算法博客。深知一半算法考试都是用C,C++，由于大四开始到今年毕业工作到现在一直从事C#开发，C++用得很少了。链表，指针也只知道一个概念了。用得没以前熟练了。所以后续更新的算法题我都是基于C#语法的。算法主要体现的是解题思路。跟题目一样，本次算法主要实现大数据相加。

解题思路:

1. 将大数据存储到一个链表中，C#中用List<int>来存储，每个节点表示每一位的数字. {1，2，3，4，5} =》12345 和{9，6，5，9，5} =》96595 （C,C++就需要自己通过指针来实现链表功能了。）

　 2. 对数据的每一位进行相加。不进行进位操作。{10，8，8，13，10}

　　 3. 遍历集合，对大于或者等于10的实现进位操作.{1,0,8,9,4,0}

Code 如下:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace BigNumAdd
{
    public class Program
    {
        public static void Main(string[] args)
        {
            List<int> num1 = new List<int>() { 1, 2, 3, 4, 5 };
            List<int> num2 = new List<int>() { 9, 6, 5, 9, 5 };
            List<int> sum = AddTwoNum(num1, num2);

            Console.WriteLine(string.Join("", sum));
            Console.ReadKey();
        }


        /// <summary>
        /// 两数字相加
        /// </summary>
        /// <param name="num1"></param>
        /// <param name="num2"></param>
        /// <returns></returns>
        private static List<int> AddTwoNum(List<int> num1, List<int> num2)
        {
            List<int> longNum = null; // 找出长的数字
            List<int> lessNum = null; // 找出短的数字
            if (num1.Count() >= num2.Count())
            {
                longNum = num1;
                lessNum = num2;
            }
            else
            {
                longNum = num2;
                lessNum = num1;
            }

            // 每一位置数据相加，对应前面思路解析第二条
            for (int index = 0; index < lessNum.Count(); index++)
            {
                longNum[longNum.Count() - 1 - index] += lessNum[lessNum.Count() - 1 - index];
            }

            CheckNum(longNum); // 遍历集合实现进位功能.对应前面思路的第三条

            return longNum;
        }

        /// <summary>
        /// 将每一个位置数据大于或等于10的进位
        /// </summary>
        /// <param name="bigNum">大数字</param>
        private static void CheckNum(List<int> bigNum)
        {
            for (int index = bigNum.Count() - 1; index >= 1; index--)
            {
                if (bigNum[index] >= 10)
                {
                    bigNum[index - 1] += bigNum[index] / 10; //进位
                    bigNum[index] = bigNum[index] % 10; // 求余数
                }
            }

            if (bigNum[0] > 10)
            {
                bigNum.Insert(0, bigNum[0] / 10);
                bigNum[1] = bigNum[1] % 10;
            }
        }
    }
}