189 8069 5689
我们都知道加法，1+1=2.c语言实现一个加法也是初学者的必修课。但是你有没有想过如果两个超过long long 类型的数据在c语言中要怎么实现加减乘除？比如一个一百位的数加上另一个一百位的数。好接下来先介绍高精度算法的处理方式。大家如果有发现什么BUG请私信告诉我谢谢。（我现在也不能保证我的屎山代码是正确的hh）
警告：使用链表处理需要保持数据结构的高度一致！！！（不然就会像我一样一大堆的段错误）
既然不能直接用整形进行处理，那么我们就用长度不限的数组来进行处理，但是这个数组比较特别，它的元素代表它在一个数的各位。比如：
大数：123456789101112131415161718
数组：{1,2,3,4,5,6,7,8,9,1,0,1,1,1,2,1,3,1,4,1,5,1,6,1,7,1,8}
接下来的高精度操作都是这样处理的。（我的链表里存的都不是ASCII都是整形数字，所以输出也用的%d）
对链表的此链表的规定因为我想用单链表加单结构体解决掉高精度计算，所以在如何储存大数的长度的时候犯了难。但是看到头节点还没有好好利用起来时，我把大数的位数存进了头节点的数据域，在后面讲减法的时候会用到这个，快速比较两个数的大小关系。这里先放一个结构体的定义。因为在高精度乘法里有一个权值的思想，所以我规定结构体里的 id 代表各位数的权值，后面会讲到 id 有什么用。
让我们想想自己是怎么计算两个数的和的，比如9876987+999999。我们先会把他们对齐对吧？按地位对齐。
然后再各位先加，逢10进1，在计算机里我们仿照人对加法的操作。首先解决第一个问题--->按低位对齐。然后是第二个问题，逢十进一。
按低位对齐我们这里用链表实现，所以之后的所有语言都是基于链表的。如果链表不熟悉的小伙伴可以先看看链表专题。（传送门）
初学者的链表总结_zhywyt的博客-博客链表c语言实现
这样我们就能得到一个倒序输入的大数了。也就是说我们已经达到了按低位对齐的目的了。
逢十进一在我们把两个数的个位加起来之后，需要对各位的数字进行处理，从低位开始，逢十进一。这个操作也很简单，只需要用一个变量temp来保存进位就行。初始化temp位0表示没有进位。
图中的 at , bt 表示本次循环中 a 的数字大小，bt 同理。因为两个数的长度很可能不一样，也就是说在短的数遍历完之后，长的数还有元素需要加到结果里，这时候需要设置短的那个大数的本次循环数字大小为零。
两个数相加，得到的结果长度大是max(lena,lenb)+1，最小是max(lena,lenb)所以我们只需要先循环max(lena,lenb)次，为结果插入元素，然后在循环外面判断是否有进位，进位的数由整型data保存，于是有：
我们从逆序输入加数，然后逆序插入到结果中，那么结果其实已经是正序了，设想一下，如果我们要连加的话，那么输入的格式和输出的格式一定不能是相反的，所以我们最后把得到的链表reverse一下，得到逆序的链表然后返回。还有就是对数据的处理方面，输入的大数需要去除前导零。注意！去除前导零的函数要记得让头节点的 data 减小相应的大小。
代码展示node* add(node* a, node* b){
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
a = inzero(a), b = inzero(b);//inzero()是一个去除前导零的函数，在输入的时候，如果输入001+002，没有这个操作是很危险的。
int lena = a->data,lenb=b->data;
int at, bt, lenans = max(lena, lenb);
int data = 0;
for (int i = 0; i< lenans; i++){
if (a->next != NULL){
at = a->next->data;
a = a->next;
}
else at = 0;
if (b->next != NULL){
bt = b->next->data;
b = b->next;
}
else bt = 0;
int temp = at + bt + data;
data = temp % 10;
temp /= 10;
insert(ans, data);
data = temp;
}
if (data)insert(ans, data);
reverse(ans);
return ans;
}和加法不同，如果说加法是在进位的话，减法就是在退位了。我们这里只想处理a>b的情况。所以在减之前，先判断 a 和 b 的大小关系，如果 b 大于 a 那么就交换 a 和 b 并且给ans添上负的记号。也就是ans的头节点里的 id 了。id 为-1表示这个数是负数，我们在输出的时候判断头节点里的记号是否是-1，如果是的话先输出一个负号。减法和加法在操作上是差不多的，只不过减法是判断得到的数是不是负数，如果是负数的话就借十。从高位借十。这就是高位借十的操作。
写一个比较函数，来判断 a 和 b 谁大。首先比较 a 和 b 的长度关系，这里就用到之前存在头节点里的data了。当长度不一样的时候，可以直接判断出大小关系。当长度一样的时候，从高位开始比较，直到出现不一样的或者到达最后。这里要注意，因为传进来的链表是逆序的，所以在逐位比较的时候需要先reverse。
int compare(node* a, node* b){
int lena = a->data,lenb=b->data;
if (lena != lenb)return lena - lenb;
else {
reverse(a), reverse(b);
node* q = a, * p = b;
while (a->next && b->next && a->next->data == b->next->data)a = a->next, b = b->next;
if (a->next && b->next){
int at = a->next->data;
int bt = b->next->data;
reverse(q), reverse(p);
return (at - bt);
}
else{
reverse(q), reverse(p);
return 0;
}
}
}减法得到的结果是有可能出现前导零的，所以在返回答案之前需要去除前导零。
代码展示node* mins(node* a, node* b){
//考虑b大于a
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
ans->data = 0;
int lena = a->data, lenb = b->data;
int flag=compare(a,b);
if (flag< 0){
swap(&a, &b);
int temp = lena;
lena = lenb;
lenb = temp;
ans->id = -1;
}
else if (flag == 0){
insert(ans, 0);
ans->data = 1;
return ans;
}
int at, bt,lenans = max(lena, lenb);
int data = 0;
for (int i = 0; i< lenans; i++){
if (a->next != NULL){
at = a->next->data;
a = a->next;
}
else at = 0;
if (b->next != NULL){
bt = b->next->data;
b = b->next;
}
else bt = 0;
int temp = at - bt + data;
data = temp;
if (temp< 0){
data += 10;
temp = -1;
}
else temp = 0;
insert(ans, data);
data = temp;
}
reverse(ans);
ans=inzero(ans);
return ans;
} 乘法也是遵循我们对两个数竖式相乘的步骤， a , b 两个数比如12345 和 6789看其中一个数，12345中第一位1它的权值是4 也就是看成1*10e4, 第二位数2 看成2*10e3，后面的同理。再看6789=6*10e3+7*10e2+8*10e1+9*10e0。先给数加上权值，然后再进行乘法操作。对 a 中的每一位数都需要和 b 中的每一位数进行乘法操作。得到的数放在 ans 的 a->id+b->id中。我们需要一个find函数，来找到ans 中对应权值的所在位置。为了减少find 函数的使用，我们借助循环的线性性质，对于 a 中的每一位数，我们遍历 b 这个过程对应 ans 中的权值就是连续的，对于 a 中的各位数我们只需要调用一次find函数。find函数是很简单的。 
node* multiplication(node* a, node* b){
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
a = inzero(a), b = inzero(b);
int lena = a->data, lenb = b->data;
int lenans = (lena + lenb-1);//最小是这个长度，大是它加一
node* am = a->next, * bm = b->next;
int i = 0;
//添加权值
while (am){
am->id = i++;
am = am->next;
}
i = 0;
while (bm){
bm->id = i++;
bm = bm->next;
}
for (int i = 0; i< lenans; i++)insert(ans, 0);//先插入空节点
a = a->next, b = b->next;
for(node*i=a;i;i=i->next){
node* p;
p = find(ans, (i->id));//只需要找一次
for(node*j=b;j;j=j->next){
p->data += (i->data) * (j->data);
p = p->next;
}
}
int data = 0;
node* p=ans;
ans = ans->next;
while (ans){
int temp = ans->data+data;
ans->data = temp % 10;
temp /= 10;
data = temp;
ans = ans->next;
}
ans = p;
reverse(ans);
if (data)insert(ans, data),ans->data++;
//去前导零套装
reverse(ans);
ans=inzero(ans);
return ans;
}想象一下竖式计算，比如 16 / 2 我们的做法是，先从较大的那个数的高位取一位数，这里是 1 ，然后比较 1 和 2 的大小，发现 1 小了，那么给答案链表加一个 0，再在16 里取下一位，得到 16和 2 比较，发现比 2 大，就用 16减去 2，得到 14 存下来，答案链表中的该位加一，重复这个操作，直到 16 变成小于 2.最后再去除答案链表中的前导零，就结束操作了。
注：这些图片来组b站up主SherlockGn，她对高精度的讲解非常到位，大家也可以去看他的视频。高精度计算除法，计算大数相除、求余再也不用求人了！_哔哩哔哩_bilibili
一个视频带你了解高精度计算！再也不用担心数据溢出了！_哔哩哔哩_bilibili
细节处理 前面讲高精度减法的时候有提到compare函数，使用compare函数就需要严格的遵守长度设置规则，不能出现有一个数的长度未初始化，不然会出现奇怪的事情。（我甚至有一次把电脑跑黑屏了，任务管理器直接罢工）那么去除前导零就极为重要。写除法的时候，我两次推翻了前面构建好的加减乘体系，全部重写了两次，才把这几个东西统一起来。各位写的时候一定要小心，多留一个心眼。
node* devide(node* a, node* b){
node* ans = NewNode(), * leave = NewNode();
ans->next = NULL,leave->next=NULL;
ans->data = 0, leave->data = 0;
ans->id = 1,leave->id=1;//先做最简单的十进制算法
int flag = compare(a, b);
if (flag< 0){
printf("0 ****** ");
RPrint(a);
printf("\n");
insert(ans, 0);
return ans;
}
else if (flag == 0){
insert(ans, 1);
printf("1 ****** 0");
return ans;
}//a要用到正序所以转回来
reverse(a);
node * q = leave;
a = a->next;
while (a){
insert(leave, a->data);
insert(ans, 0);
inzero(leave);//如果leave是0 的话，再插入一个零就需要去除前导零了，所以这部不能删
int flag;
while ((flag=compare(leave, b)) >= 0){
if (flag >0) {
leave = mins(leave, b);
destroy(q);
q = leave;
ans->next->data++;
}
else if (flag == 0){
leave = NewNode();
leave->data = 0,leave->id=1,leave->next=NULL;
insert(leave, 0);
free(q);
q = leave;
ans->next->data++;
}
}
a = a->next;
}
inzero(ans);
RPrint(ans);
printf(" ****** ");
RPrint(q);
printf("\n");
printf("The ans has %d digit.\n", ans->data);
return ans;
}最后是我的屎山代码。（建议在VS2022下运行）
#include#include#include#ifndef max(a,b) ((a)>(b)?(a):(b))
#define max(a,b) ((a)>(b)?(a):(b))
#endif
//头节点里的data是数字位数 id 是数字正负 1为非负 -1为负
struct node {
int data;
int id;
node* next;
};
typedef struct node node;
node* NewNode();
//在头节点之后倒序插入数据
void SetColor(unsigned short ForeColor, unsigned short BackGroundColor)
{
HANDLE hCon = GetStdHandle(STD_OUTPUT_HANDLE);
SetConsoleTextAttribute(hCon, (ForeColor % 16) | (BackGroundColor % 16 * 16));
}
void insert(node* la, int data);
//倒序打印链表
void RPrint(node* la);
//逆序输入，返回逆序
node* add(node* a, node* b);
//逆序输入，返回逆序
node* mins(node* a, node* b);
//逆序输入，返回逆序
node* multiplication(node* a, node* b);
//逆序输入，返回逆序
node* devide(node* a, node* b);
void destroy(node* la);
//带头节点
void reverse(node* la);
void swap(node* a, node* b);
//比较逆序的两个数
int compare(node* a, node* b);
//去除后导零
node* inzero(node* la);
node* find(node* la, int a);
int main(){
while (1){
system("cls"),printf("######## Author is zhywyt. ########\n");
printf("Please input a line of claculation.\nLike a+b or a-b or a*b or a/b without space!\n");
SetColor(4, 0),printf("Please not input space between data!\n"), SetColor(15, 0);
node* a = NewNode(), * b = NewNode(), * ans=NewNode();
char c;
a->next = NULL, b->next = NULL,a->data=0,b->data=0,ans->data=0,ans->next=NULL;
while ((c = getchar()) >= '0' && c<= '9')insert(a, c - '0');
char m;
m = c;
if (c!='+'&&c!='-'&&c!='*'&&c!='/'){
SetColor(4, 0), system("cls"), printf("Format Error !\a\a\a\n");
SetColor(15, 0), printf("Plaese input true format!!\n\n"), printf("Enter to continue.\n");
getchar();
continue;
}
while ((c = getchar()) >= '0' && c<= '9')insert(b, c - '0');
while (!a->data){
printf("Please input a!\a\na = ");
while ((c = getchar()) >= '0' && c<= '9')insert(a, c - '0');
}
while (!b->data){
printf("Please input b!\a\nb = ");
while ((c = getchar()) >= '0' && c<= '9')insert(b, c - '0');
}
a = inzero(a), b = inzero(b);
switch (m){
case('+'): {
RPrint(a), printf(" + "), RPrint(b), printf(" = ");
ans=add(a, b), RPrint(ans);
printf("\nThe answer have %d digits.\n",ans->data);
break;
}
case('-'): {
RPrint(a), printf(" - "), RPrint(b), printf(" = ");
ans=mins(a, b), RPrint(ans);
printf("\nThe answer have %d digits.\n", ans->data);
break;
}
case('*'): {
RPrint(a), printf(" * "), RPrint(b), printf(" = ");
ans=multiplication(a, b), RPrint(ans);
printf("\nThe answer have %d digits.\n", ans->data);
break;
}
case('/'): {
if (b->data == 1 && b->next->data == 0) {
printf("0 is not to be the fenmu!\a\a\a\n");
insert(ans, 0);
break;
}
RPrint(a), printf(" / "), RPrint(b), printf(" = ");
ans=devide(a, b);
break;
}
}
destroy(ans);
destroy(a);
destroy(b);
printf("\nPlease input a 'enter' to continue or '0' to exit.\n");
char n;
scanf("%c", &n);
if (n == '\n')continue;
getchar();
if (n == '0')break;
}
return 0;
}
node* NewNode(){
node* la = (node*)malloc(sizeof(node));
if (la == NULL){
printf("memory error!\a");
exit(-1);
}
return la;
}
void insert(node* la, int data){
la->data++;
node* p = NewNode();
p->next = la->next;
la->next = p;
p->data = data;
}
void destroy(node* la){
node* p;
while (la){
p = la->next;
free(la);
la = p;
}
}
void RPrint(node*la){
node* p = la;
reverse(la);
if (la->id == -1)printf("-");
la = la->next;
while (la){
printf("%d", la->data);
la = la->next;
}
reverse(p);
}
void reverse(node* la){
node* p = la->next;
la->next = NULL;
while (p){
node* q = p;
p = p->next;
q->next = la->next;
la->next = q;
}
}
void swap(node** a, node** b){
node* temp =* a;
*a = *b;
*b = temp;
}
node* inzero(node* la){
node* p = (node*)malloc(sizeof(node));
if (!p){
printf("Eroor!\a");
exit(-1);
}
p=la;
reverse(la);
la = la->next;
while (la && !la->data && la->next){
node* q = la;
la = la->next;
free(q);
(p->data)--;
}
p->next = la;
reverse(p);
return p;
}
node* find(node* la, int a){
for (int i = 0; i<=a; i++)la = la->next;
return la;
}
int compare(node* a, node* b){
int lena = a->data,lenb=b->data;
if (lena != lenb)return lena - lenb;
else {
reverse(a), reverse(b);
node* q = a, * p = b;
while (a->next && b->next && a->next->data == b->next->data)a = a->next, b = b->next;
if (a->next && b->next){
int at = a->next->data;
int bt = b->next->data;
reverse(q), reverse(p);
return (at - bt);
}
else{
reverse(q), reverse(p);
return 0;
}
}
}
node* devide(node* a, node* b){
node* ans = NewNode(), * leave = NewNode();
ans->next = NULL,leave->next=NULL;
ans->data = 0, leave->data = 0;
ans->id = 1,leave->id=1;//先做最简单的十进制算法
int flag = compare(a, b);
if (flag< 0){
printf("0 ****** ");//6个
RPrint(a);
printf("\n");
insert(ans, 0);
return ans;
}
else if (flag == 0){
insert(ans, 1);
printf("1 ****** 0");
return ans;
}//a要用到正序所以转回来
reverse(a);
node * q = leave;
a = a->next;
while (a){
insert(leave, a->data);
insert(ans, 0);
inzero(leave);//
int flag;
while ((flag=compare(leave, b)) >= 0){
if (flag >0) {
leave = mins(leave, b);
destroy(q);
q = leave;
ans->next->data++;
}
else if (flag == 0){
leave = NewNode();
leave->data = 0,leave->id=1,leave->next=NULL;
insert(leave, 0);
free(q);
q = leave;
ans->next->data++;
}
}
a = a->next;
}
inzero(ans);
RPrint(ans);
printf(" ****** ");
RPrint(q);
printf("\n");
printf("The ans has %d digit.\n", ans->data);
return ans;
}
node* add(node* a, node* b){
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
a = inzero(a), b = inzero(b);//inzero()是一个去除前导零的函数，在输入的时候，如果输入001+002，没有这个操作是很危险的。
int lena = a->data,lenb=b->data;
int at, bt, lenans = max(lena, lenb);
int data = 0;
for (int i = 0; i< lenans; i++){
if (a->next != NULL){
at = a->next->data;
a = a->next;
}
else at = 0;
if (b->next != NULL){
bt = b->next->data;
b = b->next;
}
else bt = 0;
int temp = at + bt + data;
data = temp % 10;
temp /= 10;
insert(ans, data);
data = temp;
}
if (data)insert(ans, data);
reverse(ans);
return ans;
}
node* mins(node* a, node* b){
//考虑b大于a
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
ans->data = 0;
int lena = a->data, lenb = b->data;
int flag=compare(a,b);
if (flag< 0){
swap(&a, &b);
int temp = lena;
lena = lenb;
lenb = temp;
ans->id = -1;
}
else if (flag == 0){
insert(ans, 0);
ans->data = 1;
return ans;
}
int at, bt,lenans = max(lena, lenb);
int data = 0;
for (int i = 0; i< lenans; i++){
if (a->next != NULL){
at = a->next->data;
a = a->next;
}
else at = 0;
if (b->next != NULL){
bt = b->next->data;
b = b->next;
}
else bt = 0;
int temp = at - bt + data;
data = temp;
if (temp< 0){
data += 10;
temp = -1;
}
else temp = 0;
insert(ans, data);
data = temp;
}
reverse(ans);
ans=inzero(ans);
return ans;
}
node* multiplication(node* a, node* b){
node* ans = NewNode();
ans->next = NULL;
ans->id = 1;
a = inzero(a), b = inzero(b);
int lena = a->data, lenb = b->data;
int lenans = (lena + lenb-1);
node* am = a->next, * bm = b->next;
int i = 0;
//添加权值
while (am){
am->id = i++;
am = am->next;
}
i = 0;
while (bm){
bm->id = i++;
bm = bm->next;
}
for (int i = 0; i< lenans; i++)insert(ans, 0);
a = a->next, b = b->next;
for(node*i=a;i;i=i->next){
node* p;
p = find(ans, (i->id));
for(node*j=b;j;j=j->next){
p->data += (i->data) * (j->data);
p = p->next;
}
}
int data = 0;
node* p=ans;
ans = ans->next;
while (ans){
int temp = ans->data+data;
ans->data = temp % 10;
temp /= 10;
data = temp;
ans = ans->next;
}
ans = p;
reverse(ans);
if (data)insert(ans, data),ans->data++;
//去前导零套装
reverse(ans);
ans=inzero(ans);
return ans;
} 你是否还在寻找稳定的海外服务器提供商？创新互联www.cdcxhl.cn海外机房具备T级流量清洗系统配攻击溯源，准确流量调度确保服务器高可用性，企业级服务器适合批量采购，新人活动首月15元起，快前往官网查看详情吧