大数的运算思想

??? 一、数字储存的实现

?????????? 大数计算的因数和结果精度一般是少则数十位，多则几万位。在C/C++语言中定义的类型中精度最多只有二十多位，因而我们采取用链表存贮的方式来存放大数。在计算中会用到从高位开始计算，和从低位开始计算数值的两种情况。所以我们将链表定义为双向链表，其中为一个单元来存贮数据，一个指针指向前方的数据，另一个指向后的数据。其结构为：

struct Node??// 定义一个双向链表用来存贮结果
{     char data;????// 数据*定义为字符的原因：要显示负号
     Node *next;???// 尾指针
    Node *ahead;???// 首指针
};

? 二、大数加法运算的实现

?? 处理中注意的问题：

????????? 1、必须判断出操作数A、B的长度，以位长的一个作为循环基础。

???????? 2、最后一位（最高位）的运算中，若进位不为0，则需增设多一个存储结点。

? 三、减法运算的实现

????? 算法也是从低位开始减。先要判断减数和被减数那一个位数长，减数位数长是正常减；被减数位数长，则被减数减减数，最后还要加上负号；两数位数长度相等时，最好比那一个数字大，否则负号处理会很繁琐；处理每一项时要，如果前一位相减有借位，就先减去上一位的借位，无则不减，再去判断是否能够减开被减数，如果减不开，就要借位后再去减，同时置借位为1，否则置借位为0。

处理中注意的问题：

? ? ? 1、如果被减数大于减数时，指针和相应循环长度控制变量也要做相应的修改?

????? 2、结果可能会出现前面是一堆0的情况，要处理好，如当减数为112，而被减数为111时，会出现001?

四、乘法运算的实现

????????????? 首先说一下乘法计算的算法，从低位向高位乘，在竖式计算中，我们是将乘数第一位与被乘数的每一位相乘，记录结果，之后，用第二位相乘，记录结果并且左移一位，? 以此类推，直到计算完最后一位，再将各项结果相加。得出最后结果。当然我们可以直接用这种方法，但要用多个链表来保存计算出的分结果， 之后结果再相加得到最后结果，但是这样会浪费很多空间。

????????????? 只用一个链表来表示结果，先把第一位乘数与被乘数的结果保存在链表中，之后把存储结果的头部后移一位、也就是从链表的第二加起，当第二位乘数与被乘数结果加到第二之后的各个项内。以此类推，直到结束。这样就可以用一个链表来存储相乘后的结果。

??

处理中注意的问题：

????? 1、传入和保存的都是字符，所以计算时要将字符转化为数字，算完再转化为字符存储

?????? 2、另外进位时要处理，当前的值加上进位的值再看本位数字是否又有进位；

? ? ? 3、 输出时要逆序输出，因为链表首指针是存的结果的最低位。函数为了对应输入输出结果的一致性，都有采用了字符串输出，所以在输出时又将链表转为了字符串

五、除法运算的实现

?????????????? 首先说一下我们所要的结果，当除数除不开被子除数时，不用除到小数，当除数小于被除数时，除数作为余数既可，不用再向下除了。

???????????????? 除法算法最容易想到的数字电路，或模拟电路时里面有用门实现的除法器，做法是用除数减被除数，再用一个加法器去计算存储结果，算法简单明了，计算速度比算乘方时还慢，电路中计算的长度不过8位，16位，32位，而且都是硬件实现，现要算的是几千位，几万位。特别是两数位长度差很大时计算速度相当慢，如10000-3时要进行多少次链表运算啊。

??????????? 就是从高位向低位减，减时以被除数长度为单位，从高位取出大于被除数的字符串，和被除数相减，减的次数为结果，余数从剩下的除数高位再取出几位做补位，直到大于被除数。再减，循环减到被减数大于余数加上补位，那么这个新的余数作为结果返回。

?

?

处理中注意的问题：

?? 1/? 除法算法计算时是用的最高位开始向低位减，所以要注意指针的位置。

??? 2/余数和被减数相减时，一定要注意：一旦能够减开被除数时，一定要每从除数那里取一个字符时，结果也要对应补一个0。如111222/111

六、幂运算的实现

幂的实现是最为简单的了，国为有了前面的算法做铺垫，就是调用乘法函数，来循环去自乘，幂指数相应减1，直到幂指数变为0时结束。