高精度算法和链表
高精度算法
前言
计算机最初、也是最重要的应用就是数值运算。在编程进行数值运算时，有时会遇到运算的精度要求特别高，远远超过各种数据类型的精度范围；有时数据又特别大，远远超过各种数据类型的极限值。这种情况下，就需要进行“高精度运算”。
高精度算法（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
删除
原表：1 -> 2 -> 3 – > 4 指令：删除2 做法： s->next=p->next 就是将 删除的数的上一项直接指向 删除的数的下一项（将 1 -> 2 -> 3 直接改为 1 -> 3）
课上最Amzing的是老师讲的遍历二叉树的投机小技巧，可惜这在这上面我不知道如何表达
emmmmmmmmmmmmmm…
下课好吧，点个赞再走！！！
那年 • 今日