高精度算法和链表

高精度算法

前言

计算机最初、也是最重要的应用就是数值运算。在编程进行数值运算时，有时会遇到运算的精度要求特别高，远远超过各种数据类型的精度范围；有时数据又特别大，远远超过各种数据类型的极限值。这种情况下，就需要进行“高精度运算”。

高精度算法（High Accuracy Algorithm）是处理大数字的数学计算方法。在一般的科学计算中，会经常算到小数点后几百位或者更多，当然也可能是几千亿几百亿的大数字。一般这类数字我们统称为高精度数，高精度算法是用计算机对于超大数据的一种模拟加，减，乘，除，乘方，阶乘，开方等运算。对于非常庞大的数字无法在计算机中正常存储，于是，将这个数字拆开，拆成一位一位的，或者是四位四位的存储到一个数组中，用一个数组去表示一个数字，这样这个数字就被称为是高精度数。高精度算法就是能处理高精度数各种运算的算法，但又因其特殊性，故从普通数的算法中分离，自成一家。 —-百度百科

加法

用字符串输入两个数，再导入数组，然后每位相加，如果某位数字>10，则此位模10，下一位加一，最后用while循环去除前导零再输出即可。
先上最喜欢的AC代码

cpp


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
    int a[10010] = {0},b[10010] = {0},c[10010] = {0};
    int la = 0,lb = 0,lc = 0;
    string s1,s2;
    cin >> s1 >> s2;
    la = s1.size();
    lb = s2.size();
    for (int i = 0;i < la;i++) a[la - i] = s1[i] - '0';
    for (int i = 0;i < lb;i++) b[lb - i] = s2[i] - '0';
    lc = max(la,lb);
    for (int i = 1;i <= lc;i++)
    {
        c[i] += a[i] + b[i];
        c[i + 1] += c[i] / 10;
        c[i] %= 10;
    }
    if (c[lc + 1] > 0)  lc++;
    while (c[lc] == 0 && lc > 1)    lc--;
    for (int i = lc;i >= 1;i--) cout >> c[i];
    return 0;
}

没啥难度，主要就是数太大，超范围，要用string存储。

这时候，冥场面 start:

g老师：…霹雳扒拉一大堆…
某某同学：老师，你刚刚说加法在加时进了1位，还是只可能进一位，我觉得能进2位，什么时候进2位？

全班寂静…ing

g老师/myq同学/zzy同学：乘法啊，你加法不管再怎么大，也只进一位，举个栗子：最大9+9也才进一位

全班无语…ing

减法

用字符串输入两个数，再导入数组，判断是否后数比前数，如果是则输出负号再交换数组。然后按位相减不够借1，最后用while循环去除前导零再输出即可。
AC代码

cpp


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
    int a[10010] = {0},b[10010] = {0},c[10010] = {0};
    int la = 0,lb = 0,lc = 0;
    string s1,s2;
    cin >> s1 >> s2;
    la = s1.size();
    lb = s2.size();
    if (la < lb || la == lb && s1 < s2)
    {
        cout << "-";
        swap(s1,s2);
        swap(la,lb);
    }
    for (int i = 0;i < la;i++) a[la - i] = s1[i] - '0';
    for (int i = 0;i < lb;i++) b[lb - i] = s2[i] - '0'; 
    lc = la;
    for (int i = 1;i <= lc;i++)
    {
        if (a[i] < b[i])
        {
            a[i] += 10;
            a[i + 1]--;
        }
        c[i] = a[i] - b[i];
    }
    while (c[lc] == 0 && lc > 1)    lc--;
    for (int i  = lc;i >= 1;i--)    cout << c[i];
    return 0;
}

也是没有可说的，记得，减法最重要的是删掉前导0（其实每个好像都要）

乘法

导入方法与前面一样，导入后按乘法竖式思路相乘，再按常规思路进位。最后去除前导零就行了。
AC代码

cpp


#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;
int main()
{
    string s1,s2;
    int b[1010] = {0},la = 0,lb = 0,a[1010] = {},lc = 0,c[1010] = {};
    cin >> s1 >>  s2;
    la = s1.size();
    lb = s2.size();
    for (int i = 0;i < la;i++)  a[la - i] = s1[i] - '0';
    for (int i = 0;i < lb;i++)  b[lb - i] = s2[i] - '0';
    lc = la + lb;
    for (int i = 1;i <= la;i++)
    {
        for (int j = 1;j <= lb;j++)
        {
            c[i + j - 1] += a[i] * b[j];
            c[i + j] += c[i + j - 1] / 10;
            c[i + j - 1] %= 10;
        }
    }
    while (c[lc] == 0 && lc > 1)    lc--;
    for (int i = lc;i >= 1;i--) cout << c[i];
    return 0;
}

细心的同学估计发现了，3个好像没有区别，都是模版，只改了一点点东西，所以是可以背背模版的。

除法

cpp


#include <bits/stdc++.h>
using namespace std;
const int N = 101;
int a[N],b,c[N];
int main()
{
    string s1;
    cin >> s1 >> b;
    int la = s1.size();
    for(int i = 0;i < la;i++) a[i] = s1[i] - '0';
    long long x = 0;
    for (int i = 0;i < la;i++)
    {
        x *= 10;
        x += a[i];
        c[i] = x / b;
        x %= b;
    }
    int lc = 0;
    while(c[lc] == 0 && lc < la - 1) lc++;
    for (int i = lc;i < la;i++) cout << c[i];
    cout << " " << x;
}

链表

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。
每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相比于线性表顺序结构，操作复杂。
由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，
但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

优点

不必预估空间大小
插入和删除很方便

优点有多强多好，缺点就有多明显多恶心。

缺点

不可随意访问任意元素

它的删除和插入到底有多简单呢，看↓
插入

原表： 1 -> 2 -> 4
指令：插入3
做法： p -> next = s->next;
s -> next = p;
就是直接将第2项指向下一项的指针指向插入的元素（将2 -> 4 改为 2 -> 3）
再将插入的元素指向后面那一个元素（将2 -> 4 改为 3 -> 4）
表就变为： 1 -> 2 -> 3 -> 4

删除