本章内容

高精度

链表

 

位数再多，只管稳稳进位，终会把答案写满。

一、高精度

1. 什么是高精度

• • 定义

“高精度整数”指不受 C++ 原生整型 (int / long long) 位宽限制，而用数组模拟任意位数的大整数。

• • 必要性

64 位 long long 仅能保存到 9 × 10¹⁸。五级真题里随手就超出：

• • • 2023-12 单选 11 要填写“高精度加法”代码行，默认操作数可达上百位；
  • • 2025-03 单选 15 要补全“高精度乘法”进位处理，测试数据位长同样远超原生类型；
  • • 2024-09 单选 14 直接考察高精度四则运算复杂度与实现要点。
  • • 在组合数、阶乘、超长斐波那契 等场景里也必须使用高精度。

---

2. 数据结构设计

2.1 存储方案

① 先谈“存储哲学”——把大整数拆成“块”并线性摆放

高精度实质上是把人类熟悉的十进制笔算过程，翻译成 C++ 的数组操作。任何一个千位、万位甚至百万位的十进制整数，都可以视作“若干个低位到高位连续排列的数字块”。高精度使用者的责任，就是决定“每个块存多少信息”、决定“块们的排列方向”，并确保 进位、借位、比较、截零 等操作在这样的布局下都能高效完成。存储方案因此成为高精度体系的基石：如果选得好，后续加减乘除皆可顺滑；若选得拙劣，则会在常数时间和代码复杂度上付出高昂代价。

② “一位一存”——最朴素但也最易懂的方案

最原始的做法是：把十进制的每一位（0‥9）直接存在 int 数组里。假设要存 31415926，则定义 int a[8]，把低位 6 放到 a[0]（也可以存在 a[1]），再依次存 2、9、5 … 直至最高位 3 存入 a[7]。这种“小端倒序”布局有几大显见好处：

• • 程序逻辑几乎与手算一一对应：加减从 a[0] 开始循环，满 10 进 1，直观不易错。
• • 输出时只需逆序打印即可；调试时直接扫数组就能看到各位数字。
• • 在五级最常见的“补全代码”单选题中，命题人为了降低阅读门槛，也常给出这种一位一存模板，让考生专注在“进位语句”或“前导零删除”细节。

然而，“一位一存”也有天然瓶颈：循环次数与十进制位数完全等长。5000 位整数相加就得跑 5000 次循环，乘法则是平方级——两数都是 5000 位时，朴素乘法将运行 25 000 00 次乘-加-进位，极容易被 OJ 的 1 s 时限卡住。再者，同样 5000 位数字，数组占 5000×4 B≈20 KB，乘法的中间数组更大，对高速缓存不友好。

在实际使用者中，若题目已声明“输入位数 ≤ 2000”且只牵涉加法或减法，使用一位一存完全能 AC；若涉及乘法、尤其是阶乘、快速幂等 n² 量级循环，则需要考虑更高效的“块存储”。

③ 升级一步：十进制“块”存储，为什么是 10⁴ 或 10⁹？

所谓块存储，就是把若干位十进制数字打包进一个元素。32 位平台常用 BASE=10 000（4 位），因为 9999×9999 不会溢出 32 位有符号整型。64 位平台可提到 BASE=1 000 000 000（9 位）；999 999 999×999 999 999≈10¹⁸ 仍落在 64 位无符号范围，但若要存进位之和就需要 long long 或加上额外 carry。对比单独一位，这样做的优势肉眼可见：

• • 位数压缩：原本 5000 位 → ceil(5000/9)=556 块；循环立减 9 倍。
• • Cache 友好：数据更紧凑，CPU 每次读入一次 cache line 可以操作更多“有效位”，缓存命中率提升。
• • 乘法加速：乘法内部两层循环加进位处理常数大幅下降，BASE=10⁹ 的朴素乘法可轻松处理一万位 × 一万位于 0.5 s 内，而单位存储会超时。

但块也不是越大越好。BASE=10¹⁰ 会让一次相乘结果溢出 64 位，需要手写 128 位拆分或使用 __int128。竞赛常用 10⁹ 正是折中的“黄金”——既压缩了位数，又能在支持 __int128 的 GNU C++14 下安全地乘完后取低 64 位和进位 64 位。本篇后续给出的数组模板也选用 BASE=10⁹。

④ “大端”还是“小端”？倒序到底好在何处？

• • 小端 (Little-Endian) 命名来源于计算机字节序，在高精数组中意味着“低位在下标 0 or 1”。优点：从低到高自然遍历，符合加减乘除的进位传播方向；缺点：打印要倒序。
• • 大端 (Big-Endian) 则高位在 0，下标越大位权越小，打印方便，但每次运算都要从末尾往前走，写法繁琐。

我们常见和常做的，就是以小端基础，倒序适应我们的四则运算。

2.2 统一符号

① 把正负逻辑从核心运算里剥离
加、减、乘、除的本质都发生在“非负绝对值”之间。如果每一步都掺杂正负判断，会让代码分支膨胀、进位逻辑混乱。

② 避免“负零”
若 0 仍保留 s = -1，那么两个“零”比较会出现“‐0 < +0”的假象。统一约定：只要值为 0，就把符号改回 +1。

③ 简化比较
先看符号即可粗判大小（正数必然大于负数），只有符号相同才需比较绝对值。

3. 核心算法

3.1 加法

计算 12345 + 789 图解如下：

倒序输出即 12345 + 789 = 13134。

具体题目：只考虑同号，输入两个位数为 的正整数，求它们的和。

下面我们用字符串输入，转数组进行高精度加法：

#include<bits/stdc++.h>
using namespace std;
char a1[305], b1[305];
int a[305], b[305], c[305]; //加法最多进一位
int main(){cin >> a1 >> b1;int la = strlen(a1);int lb = strlen(b1);for(int i = la-1; i >= 0; i--) a[la-1-i] = a1[i] - '0';for(int i = lb-1; i >= 0; i--) b[lb-1-i] = b1[i] - '0';//字符串转数组倒序保存int lc = max(la, lb) + 1;        for(int i = 0; i < lc; i++){    //枚举各位相加c[i] += a[i]+b[i];            //相加，这里建议相加和进位分开写，更清楚不易错if(c[i] >= 10){                //需要进位c[i] -= 10;c[i+1]++;}} while(c[lc] == 0 && lc > 0) lc--;    //去前导零for(int i = lc; i >= 0; i--){    //倒序输出cout << c[i];} return 0;
}

3.2 减法

只考虑同号，输入两个位数为 的正整数，求它们的差，但不确定被减数和减数的大小。

下面我们用字符串输入，转数组进行高精度减法：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 305
string a, b;
int na[MAXN], nb[MAXN], ans[MAXN]; 
bool flag;int main(){cin >> a >> b;if((a < b && a.size() == b.size()) || a.size() < b.size()){swap(a, b);flag = true;}for(int i = a.size(); i > 0; i--) na[i] = a[a.size() - i] - '0';for(int i = b.size(); i > 0; i--) nb[i] = b[b.size() - i] - '0';//字符串转整数数组int maxl = max(a.size(), b.size());//找到两个数中的最大位for(int i = 1; i <= maxl; i++){if(na[i] < nb[i]){na[i + 1] --;na[i] += 10;}ans[i] = na[i] - nb[i];}while(ans[maxl] == 0) maxl--;  //去前导零if(flag == true) cout << "-"; //b>a时，a - b < 0 所以打上负号 for(int i = maxl; i > 0; i--) cout << ans[i];if(maxl < 1) cout << "0";return 0;
}

3.3 乘法

只考虑同号，输入两个位数为 的正整数，求它们的乘积。

下面我们用字符串输入，转数组进行高精度乘法：

#include<bits/stdc++.h>
using namespace std;
char a1[1005], b1[1005];
int a[2005], b[2005], c[2005];
int main(){cin >> a1 >> b1;int la = strlen(a1);int lb = strlen(b1);int x = 0;for(int i = la-1; i >= 0; i--) a[x++] = a1[i] - '0';x=0;for(int i = lb-1; i >= 0; i--) b[x++] = b1[i] - '0';//转整数数组int lc = la + lb;for(int i = 0; i < la; i++){        //两数相乘for(int j = 0; j < lb; j++){c[i+j] += a[i]*b[j];        //思考，如果最低位保存在下标 1 会怎么样} }for(int i = 0; i < lc; i++){        //进位c[i+1] += c[i]/10;c[i] = c[i]%10;}while(c[lc]==0 && lc > 0) lc--;    //去前导零for(int i = lc; i >= 0; i--) cout << c[i];return 0;
}

3.4 大整数 ÷ 小整数

给定一个位数 大正整数和一个小正整数 ，大整数除以小整数得到的商和余数分别是多少？

string s; int k;    //输入大整数 s（字符串）和小整数 k
cin >> s >> k;    
int l = s.size(), a = 0, t = 0;
for (int i = 0; i < l; i++){a = a*10 + s[i] - '0';        //未除尽的数到下一位 *10if (a >= k){                //能除则输出值 和 计算未除尽的数cout << a/k;a %= k;t = 1;}else if (t) cout << 0;        //出现过商才会出现0，防止有前导零
}
cout << " " << a << endl;

3.5 其它常用扩展

功能	代码思路
modInt(a,m)	逐位 %m 累积余数
快速幂 powBig(a,k)	大数乘法 × 指数二分
阶乘 fact(n)	循环 mul(ans,i)

---

4. 复杂度 & 易错点

运算	时间复杂度	空间
加/减	O(n)	O(n)
乘	O(n²)	O(n)
÷ 小整	O(n)	O(n)
÷ 大整	O(n²)	O(n)

1. 1. 进位/借位遗漏——考试常用选择题在这里挖坑（见 23-12 单选 11）。
2. 2. 符号重置——结果为 0 必须让 sgn=1。
3. 3. 前导零——trim() 每次运算后都要调用，否则比较和打印会错。
4. 4. 先除后乘——计算 LCM 或做 “a*b/gcd” 时先 a/gcd 再乘，防止溢出；这条在高精同样适用。

---

5. 真题映射与练习建议

知识点	真题位置	建议练习
高精加法核心循环	2023-12 题 11 选择填空	手写 5000 位两数求和
进位处理	2025-03 题 15 选择填空	随机生成 1000 位×1000 位乘法
算法复杂度判断	2024-09 题 14 单选	对比 n² vs Karatsuba 的性能
完整编程	历年五级编程题经常给出“大数阶乘 / 大数相加”	独立实现加、乘、阶乘

---

二、链表

1. 结点定义

struct Nod{            // 单向链表结点int v;             // 数据域Nod* n;            // 指针域 (next)Nod(int x = 0, Nod* p = nullptr) : v(x),n(p){}
};

说明

• • 每个结点保存一个整数 v 与一条指向下一结点的指针 n。
• • 头指针 hd 可指向首结点；若链表为空，hd == nullptr。

---

2. 遍历 (输出全部元素)

void prn(Nod* hd){for(Nod* p = hd; p; p = p->n) cout << p->v <<" ";cout << "\n";
}

过程：让游标 p 从头开始，依次沿 n 前进，直到遇到 nullptr 为止。

---

3. 头插法创建链表

Nod* crt(const vector<int>& a){   // 传入数组生成链表Nod* hd = nullptr;for(int x : a) hd = new Nod(x, hd);     // 新结点指向原头return hd;                         // 返回新头
}

头插的特点：总 O(1) 时间把新元素压到最前面；生成顺序与原数组相反。

---

4. 尾插法（在末尾追加）

void pus(Nod*& hd,int x){if(!hd){hd = new Nod(x); return; }  // 空链Nod* p = hd;while(p->n) p = p->n;               // 找尾p->n = new Nod(x);
}

尾插需先遍历到尾结点，因此最坏 O(n)。若频繁尾插，可另设尾指针 tl 优化为 O(1)。

---

5. 查找首个值为 x 的结点

Nod* fnd(Nod* hd, int x){for(Nod* p = hd; p; p = p->n)if(p->v == x) return p;return nullptr;
}

返回：指向匹配结点的指针，若不存在返回 nullptr。

---

6. 在值为 x 的结点之后插入 y

bool ins(Nod* hd, int x, int y){Nod* p = fnd(hd, x);if(!p) return false;               // 未找到p->n = new Nod(y, p->n);return true;
}

步骤

1. 1. 先调用 fnd 找目标结点 p。
2. 2. 若存在，则建新结点 q，其 n 指向 p->n，然后把 p->n 改为 q。
3. 3. 整体 O(n)（因为查找）。

---

7. 删除首个值等于 x 的结点

bool era(Nod*& hd, int x){if(!hd) return false;if(hd->v == x){                      // 删除头结点Nod* t = hd;hd = hd->n; delete t;return true;}for(Nod* p = hd; p->n; p = p->n)if(p->n->v == x){Nod* t = p->n;p->n = t->n; delete t;return true;}return false;                      // 未找到
}

• • 需要额外保存前驱指针。
• • 释放内存后确保断链。

---

8. 销毁整条链表（防内存泄漏）

void clr(Nod*& hd){while(hd){Nod* t = hd;hd = hd->n;delete t;}
}

---

小结

• • 创建：头插最快；尾插多时可设尾指针。
• • 遍历：沿 next 走到 nullptr。
• • 查找 / 插入 / 删除：最坏 O(n)；删除需保存前驱。
• • 内存管理：用 new 创建结点后务必在删除或销毁时 delete，否则泄漏。

---

三、链表拓展

1. 单向链表（Singly Linked List）

1.1 结点结构

struct Nod{int v;          // 数据Nod* n;         // next 指针Nod(int x = 0, Nod* p = nullptr) : v(x),n(p){}
};

1.2 基本操作

• • 头插

void addH(Nod*& h, int x){h = new Nod(x, h);        // 新结点指向旧头
}

• • 按值删除首个 x

bool delV(Nod*& h, int x){if(!h) return 0;if(h->v == x){Nod* t = h; h = h->n; delete t; return 1;}for(Nod* p = h; p->n; p = p->n)if(p->n->v == x){Nod* t = p->n; p->n = t->n; delete t; return 1;}return 0;
}

• • 遍历输出

void prt(Nod* h){for(Nod* p = h; p; p = p->n) cout << p->v <<" ";cout << "\n";
}

时空复杂度：头插 O(1)；删除/查找最坏 O(n)；空间 O(n)（结点指针域额外占用）。

---

2. 双向链表（Doubly Linked List）

2.1 定义

struct Dnd{int v;Dnd* l;      // prevDnd* r;      // nextDnd(int x=0) : v(x), l(nullptr), r(nullptr){}
};

2.2 插入与删除要点

• • 插入 p 之后放 q

q->r = p->r;
q->l = p;
if(p->r) p->r->l = q;
p->r = q;

• • 删除结点 p

if(p->l) p->l->r = p->r;
if(p->r) p->r->l = p->l;
delete p;

因为有 prev 指针，删除 不必再找前驱，常数时间完成；代价是每结点多 1 个指针，耗内存加倍。

---

3. 循环链表（Circular List）

3.1 单向循环

• • 尾结点 last->n 指回头结点。
• • 遍历：for(Nod* p=h; p; p=p->n) { ... if(p->n==h) break; }

3.2 典型场景

• • 约瑟夫问题（Josephus）
• • 操作系统队列（循环就绪队、时间片轮转）

循环链表省去判空：只要持有 last 指针，就能 O(1) 头插尾插；但遍历时务必用“再次到达起点”作为停止条件。

---

4. OJ 高速写法——“数组模拟链表”

在线评测常限制 new/delete 或追求极限速度，故常用 平行数组 取代指针。

4.1 核心数组

const int N = 1000005;   // 最大结点数
int val[N];              // 数据域
int nxt[N];              // next 下标
int cur = 1;             // 可用的下标指针  [0] 预留作“头结点”

4.2 基本例程

• • 清空

void ini(){nxt[0] = -1;         // 头结点指向实际首元cur = 1;             // 下标 1 起做新结点
}

• • 在 结点 idx 后插入 x

void add(int idx,int x){ // idx 是已有结点下标val[cur] = x;nxt[cur] = nxt[idx];nxt[idx] = cur;++cur;
}

• • 删除 idx 后的结点

void rem(int idx){       // idx 前驱if(nxt[idx] == -1) return;nxt[idx] = nxt[nxt[idx]];
}

• • 遍历

void out(){for(int i = nxt[0]; i != -1; i = nxt[i]) cout << val[i] <<" ";cout << "\n";
}

4.3 特点

• • 全部顺序存储，无动态分配开销，极适合多组数据大规模插删。
• • add / rem 时间 O(1)，空间 O(N)，且无需垃圾回收。
• • 常见于 洛谷 P3380、AtCoder ABC链表题 等。

---

5. 小结对比

形式	插入删除	顺序遍历	随机定位	内存开销
单链表	O(1/ n )	O(n)	不支持	1 指针
双向链表	O(1)	O(n)	前驱 O(1)	2 指针
循环链表	O(1)	需哨兵	不常用	同单/双
数组模拟链表	O(1)	O(n)	不支持	2 数组

实战建议

• • 小数据 & 手写题：直接 new/delete 单链表最快写完。
• • 需要 O(1) 删除：双向 or 数组模拟。
• • 大数据连删连插：首选“数组模拟链表”，既快又无碎片。