初等高精度计算（链表实现）-创新互联

  我们都知道加法，1+1=2.c语言实现一个加法也是初学者的必修课。但是你有没有想过如果两个超过long long 类型的数据在c语言中要怎么实现加减乘除？比如一个一百位的数加上另一个一百位的数。好接下来先介绍高精度算法的处理方式。大家如果有发现什么BUG请私信告诉我谢谢。（我现在也不能保证我的屎山代码是正确的hh）

创新互联是一家网站设计公司，集创意、互联网应用、软件技术为一体的创意网站建设服务商，主营产品：成都响应式网站建设公司、高端网站设计、全网整合营销推广。我们专注企业品牌在网站中的整体树立，网络互动的体验，以及在手机等移动端的优质呈现。成都做网站、成都网站制作、成都外贸网站建设、移动互联产品、网络运营、VI设计、云产品.运维为核心业务。为用户提供一站式解决方案，我们深知市场的竞争激烈，认真对待每位客户，为客户提供赏析悦目的作品，网站的价值服务。

警告：使用链表处理需要保持数据结构的高度一致！！！（不然就会像我一样一大堆的段错误）

  处理方式

  既然不能直接用整形进行处理，那么我们就用长度不限的数组来进行处理，但是这个数组比较特别，它的元素代表它在一个数的各位。比如：

  大数：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 有什么用。

 1——>高精度加法 思想        

  让我们想想自己是怎么计算两个数的和的，比如9876987+999999。我们先会把他们对齐对吧？按地位对齐。

然后再各位先加，逢10进1，在计算机里我们仿照人对加法的操作。首先解决第一个问题--->按低位对齐。然后是第二个问题，逢十进一。

按低位对齐

  我们这里用链表实现，所以之后的所有语言都是基于链表的。如果链表不熟悉的小伙伴可以先看看链表专题。（传送门）

初学者的链表总结_zhywyt的博客-博客链表c语言实现https://blog.csdn.net/weixin_73620289/article/details/127691181?spm=1001.2014.3001.5502如果一个数在存进链表的时候是倒序存入的，那么链表的第一个元素就是这个大数的最低位对。所以我们在处理大数的时候把他们都用倒序储存。倒序储存很简单，只需要写一个insert函数就行。这里我的insert函数考虑到插入后头节点里的位数信息需要更新，那么每次创建头节点时必须给它 的data初始化，不然在调用insert的时候就会出现段错误。

这样我们就能得到一个倒序输入的大数了。也就是说我们已经达到了按低位对齐的目的了。

逢十进一

  在我们把两个数的个位加起来之后，需要对各位的数字进行处理，从低位开始，逢十进一。这个操作也很简单，只需要用一个变量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;
}

 2——>高精度减法 思想

  和加法不同，如果说加法是在进位的话，减法就是在退位了。我们这里只想处理a>b的情况。所以在减之前，先判断 a 和 b 的大小关系，如果 b 大于 a 那么就交换 a 和 b 并且给ans添上负的记号。也就是ans的头节点里的 id 了。id 为-1表示这个数是负数，我们在输出的时候判断头节点里的记号是否是-1，如果是的话先输出一个负号。减法和加法在操作上是差不多的，只不过减法是判断得到的数是不是负数，如果是负数的话就借十。从高位借十。这就是高位借十的操作。

比较函数compare()

写一个比较函数，来判断 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;
}

  3——>高精度乘法（十进制） 思想

  乘法也是遵循我们对两个数竖式相乘的步骤， 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;
}

  4——>高精度除法 思想

  想象一下竖式计算，比如 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元起，快前往官网查看详情吧

新闻名称：初等高精度计算（链表实现）-创新互联
本文地址：http://cqcxhl.cn/article/gdjih.html