搜索
您的当前位置：首页正文

纯C语言实现大数基本运算

来源：易榕旅网

开发环境visual studio 2010

仅限正整数之间的运算

使用的是字符串数组代表一个大数，并整体封装成一个结构体。

如果有时间的话，我会重新写一份代码，这份代码写完后有点不忍细看，就是一坨，不过通过复制粘贴代码是能够直接运行的，代码菜鸡一个，欢迎大家批评指正。

large_number.h文件代码
/**
Elmist

大数运算（支持2^32位十进制数的大数基本运算）
仅限正整数之间的运算
算法效率一般
可读性一般
若遇到bug请联系
开发者qq：2115007207
*/

#define NEW(obj) (obj *)malloc(sizeof(obj))
#define NEWR(obj,n) (obj *)malloc(sizeof(obj)*n);

typedef struct {
	char *num;
	unsigned int len;
	unsigned int cap;
}Lager;
//大数左移
void lar_lefit(Lager *p_lar,unsigned int n);
//大数右移
void lar_rigit(Lager *p_lar,unsigned int n);
//创建大数对象
Lager *lar_create();
//随机创建n位十进制数
Lager *lar_creadom(int n);
//整理格式不正确的大数
int lar_detect(Lager *p_lar);
//销毁大数对象
int lar_delete(Lager *p_lar);
//大数对象赋值
Lager *lar_assign(Lager *p_lar,char *num);
//比较num1是否小于num2
int lar_less(Lager *num1,Lager *num2);
//将大数转换为字符串对象
char *lar_tostring(Lager *p_lar);
//计算大数相加，函数内部会创建一个新的大数对象，并返回。
Lager* lar_add(Lager *num1,Lager *num2);
//计算大数相乘
Lager* lar_multip(Lager *num1,Lager *num2);
//计算大数的幂，num1的num次方
Lager* lar_power(Lager *num1,unsigned int num);
//计算机大数相减，num1-num2，num1需要大于num2
Lager* lar_minus(Lager *num1,Lager *num2);
//计算机大数相除，num1/num2,remainder是余数，num1需要大于num2
Lager* lar_divby(Lager *num1,Lager *num2,Lager *remainder);
large_number.c文件代码
#define  _CRT_SECURE_NO_WARNINGS
#include<stdlib.h>
#include<string.h>
#include<errno.h>
#include<stdio.h>
#include<time.h>
#include<limits.h>
#include"large_number.h"

//2^32位内的大数运算


Lager *lar_create(){
	Lager *p_lar=NEW(Lager);
	p_lar->num=NEWR(char,16);
	p_lar->len=0;
	p_lar->cap=16;
	//printf("创建主：%p 次：%p 量：%d\n",p_lar,p_lar->num,p_lar->cap);
	return p_lar;
}
int lar_delete(Lager *p_lar){
	//printf("即将释放主：%p 次：%p 量：%d\n",p_lar,p_lar->num,p_lar->cap);
	free(p_lar->num);
	p_lar->num=0;
	p_lar->len=0;
	p_lar->cap=0;
	free(p_lar);
	return 0;
}

char* str_reverse(char *str){
	char *buff;
	int n=strlen(str);
	int i;
	buff=NEWR(char,n+1);
	for(i=0;i<n;i++)
		buff[n-i-1]=str[i];
	buff[i]='\0';
	return buff;
}
int str_reverse_1(char *str){
	char *p,*q,t;
	p=str;
	q=str+strlen(str)-1;
	while(p<q){
		t=*p;
		*p=*q;
		*q=t;
		p++;
		q--;
	}
	return 0;
}
Lager *lar_assign(Lager *p_lar,char *num){
	char *buff=str_reverse(num);
	while(strlen(num)+1>p_lar->cap){
		free(p_lar->num);
		p_lar->cap*=2;
		p_lar->num=NEWR(char,p_lar->cap);
	}
	strcpy(p_lar->num,buff);
	free(buff);
	p_lar->len=strlen(num);
	return p_lar;
}
int lar_detect(Lager *p_lar){
	if(p_lar==NULL){
		printf("lar_detect:p_lar is NULL");
		system("pause");
		return -1;
	}
	while(p_lar->num[p_lar->len-1]=='0'&&p_lar->len>1){
		p_lar->num[p_lar->len-1]='\0';
	}
	p_lar->len=strlen(p_lar->num);
	return 0;
}
char *lar_tostring(Lager *p_lar){
	char *buff;
	unsigned int i;
	buff=NEWR(char,p_lar->len+1);
	for(i=0;i<p_lar->len;i++){
		buff[i]=p_lar->num[p_lar->len-i-1];
	}
	buff[i]='\0';
	return buff;
}

void lar_append(Lager *p_lar,char ch){
	while(p_lar->len>=p_lar->cap-1){
		char *new_num;
		p_lar->cap*=2;
		new_num=NEWR(char,p_lar->cap);
		strncpy(new_num,p_lar->num,p_lar->len);
		free(p_lar->num);
		p_lar->num=new_num;
	}
	p_lar->num[p_lar->len]=ch;
	p_lar->len++;
}
Lager *lar_creadom(int n){
	Lager *num;
	num=lar_create();

	while(n--){
		lar_append(num,(char)(rand()%10+'0'));
	}
	lar_append(num,'\0');
	num->len--;
	return num;
}
Lager* lar_add(Lager *num1,Lager *num2){
	Lager *res=lar_create();
	unsigned int n=num1->len<num2->len?num1->len:num2->len;
	int x1=0;//进位数

	unsigned int i=0;
	for(i=0;i<n;i++){
		int x2;
		x2=num1->num[i]+num2->num[i]+x1-2*'0';
		lar_append(res,x2%10+'0');
		x1=(x2/10)?1:0;
	}
	while(i<num1->len){
		int x2;
		x2=num1->num[i]+x1-'0';
		lar_append(res,x2%10+'0');
		x1=(x2/10)?1:0;
		i++;
	}
	while(i<num2->len){
		int x2;
		x2=num2->num[i]+x1-'0';
		lar_append(res,x2%10+'0');
		x1=(x2/10)?1:0;
		i++;
	}
	if(x1==1)
		lar_append(res,1+'0');
	lar_append(res,'\0');
	res->len--;
	return res;
}
void lar_lefit(Lager *p_lar,unsigned int n){
	while(p_lar->len+n>p_lar->cap){
		char *new_num;
		p_lar->cap*=2;
		new_num=NEWR(char,p_lar->cap);
		strncpy(new_num,p_lar->num,p_lar->len);
		free(p_lar->num);
		p_lar->num=new_num;
	}
	{
		unsigned int i;
		for(i=p_lar->len+n-1;i<UINT_MAX;i--){
			if(i<n)
				p_lar->num[i]='0';
			else
				p_lar->num[i]=p_lar->num[i-n];
		}
	}
	p_lar->len+=n;
}
void lar_rigit(Lager *p_lar,unsigned int n){
	unsigned int i;
	for(i=0;i<p_lar->len-n;i++){
		p_lar->num[i]=p_lar->num[i+n];
	}
	p_lar->len-=n;
}
Lager* lar_multip_part(Lager *num,char ch){
	Lager *res=lar_create();
	unsigned int adds=0;
	unsigned int i;
	for(i=0;i<num->len;i++){
		adds+=(num->num[i]-'0')*(ch-'0');
		lar_append(res,adds%10+'0');
		adds/=10;
	}
	if(adds!=0){
		lar_append(res,adds%10+'0');
	}
	return res;
}
Lager* lar_multip(Lager *num1,Lager *num2){
	Lager *res,*temp;
	unsigned int i;
	if(lar_less(num1,num2)){
		void *p=num1;
		num1=num2;
		num2=p;
	}
	temp=res=lar_create();
	lar_assign(res,"0");
	for(i=0;i<num2->len;i++){
		Lager *temp1=lar_multip_part(num1,num2->num[i]);
		lar_lefit(temp1,i);
		res=lar_add(res,temp1);
		lar_delete(temp);
		lar_delete(temp1);
		temp=res;
	}
	return res;
}
Lager* lar_power(Lager *num1,unsigned int num){
	Lager *res,*temp;
	temp=res=lar_create();
	lar_assign(res,"1");
	while(num--){
		res=lar_multip(res,num1);
		lar_delete(temp);
		temp=res;
	}
	return res;
}
int lar_less(Lager *num1,Lager *num2){
	char ins1 = num1->len<num2->len;	//长度比较小
	char ins2 = num1->len==num2->len;	//长度相等
	char ins3,*p1,*p2;
	p1=num1->num+num1->len-1;
	p2=num2->num+num2->len-1;
	while(*p1==*p2&&p1!=num1->num){
		p1--;
		p2--;
	}
	ins3=*p1<*p2;
	return ins1||(ins2&&ins3);
}
int lar_equal_0(Lager *num){
	if(num!=NULL&&num->len==1)
		return num->num[0]=='0';
	if(num==NULL){
		printf("lar_equal_0:num is NULL\n");
		system("pause");
	}
	return 0;
}
Lager* lar_minus(Lager *num1,Lager *num2){
	Lager *res;
	unsigned int i,x=0;//x:进位数
	signed char ch;
	if(lar_less(num1,num2)){
		puts("num1<num2");
		system("pause");
		return NULL;
	}
	res=lar_create();
	for(i=0;i<num1->len;i++){
		ch=num1->num[i] -x- (i<num2->len?num2->num[i]:'0');
		if(ch<0){
			ch+=10;
			x=1;
		}else{
			x=0;
		}
		lar_append(res,ch+'0');
	}
	if(ch==0){
		res->len--;
	}
	if(res->len==0){
		res->num[0]='0';
		res->len++;
	}
	res->num[res->len]='\0';
	lar_detect(res);
	return res;
}
Lager* lar_divby(Lager *num1,Lager *num2,Lager *remainder){
	Lager *quotient;
	Lager *t_num1,*t_num2,*temp1,*temp2,*temp3;
	Lager *v_10,*v_1;
	if(lar_equal_0(num2)){
		printf("The dividend 'num2' is zero.");
		system("pause");
		return NULL;
	}
	v_10=lar_create();
	v_1=lar_create();
	lar_assign(v_10,"10");
	lar_assign(v_1,"1");

	t_num1=lar_create();
	t_num2=lar_create();
	quotient=lar_create();
	lar_assign(t_num1,num1->num);
	lar_assign(t_num2,num2->num);
	str_reverse_1(t_num1->num);
	str_reverse_1(t_num2->num);
	lar_assign(quotient,"0");
	while(!lar_less(t_num1,num2)){
		temp1=t_num2;
		temp3=lar_power(v_10,t_num1->len-num2->len);
		t_num2=lar_multip(num2,temp3);
		if(lar_less(t_num1,t_num2)){
			lar_delete(temp3);
			temp3=lar_power(v_10,t_num1->len-num2->len-1);
			t_num2=lar_multip(num2,temp3);
		}
		lar_delete(temp1);
		while(!lar_less(t_num1,t_num2)){
			temp1=t_num1;
			t_num1=lar_minus(t_num1,t_num2);
			temp2=quotient;
			quotient=lar_add(quotient,temp3);
			lar_delete(temp1);
			lar_delete(temp2);
		}		
		lar_delete(temp3);
	}
	if(remainder!=NULL){
		lar_assign(remainder,t_num1->num);
		str_reverse_1(remainder->num);
	}
	lar_delete(t_num1);
	lar_delete(t_num2);
	return quotient;
}
主函数：main.c
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include"large_number.h"
//大数相加测试
int test1(){
	Lager *num1,*num2,*num3;
	num1=lar_create();
	num2=lar_create();
	
	lar_assign(num1,"13");
	lar_assign(num2,"41");
	num3=lar_add(num1,num2);
	printf("%s + %s = %s \n",lar_tostring(num1),lar_tostring(num2),lar_tostring(num3));

	getchar();
}
//大数相减测试
int test2(){
	Lager *num1,*num2,*num3;
	num1=lar_create();
	num2=lar_create();
	
	lar_assign(num1,"12");
	lar_assign(num2,"4");
	num3=lar_minus(num1,num2);
	printf("%s - %s = %s \n",lar_tostring(num1),lar_tostring(num2),lar_tostring(num3));

	getchar();
}
//大数相乘测试
int test3(){
	Lager *num1,*num2,*num3;
	num1=lar_create();
	num2=lar_create();
	
	lar_assign(num1,"12");
	lar_assign(num2,"4");
	num3=lar_multip(num1,num2);
	printf("%s * %s = %s \n",lar_tostring(num1),lar_tostring(num2),lar_tostring(num3));

	getchar();
}
//大数的幂运算
int test4(){
	Lager *num1,*num2,*num3;
	num1=lar_create();
	num2=lar_create();
	
	lar_assign(num1,"12");
	lar_assign(num2,"4");
	num3=lar_power(num1,2);
	printf("%s ^ %s = %s \n",lar_tostring(num1),2,lar_tostring(num3));

	getchar();
}
//大数整除与求余运算
int test5(){
	Lager *num1,*num2,*res,*rem;
	num1=lar_creadom(6);
	num2=lar_creadom(2);
	lar_detect(num1);
	lar_detect(num2);
	rem=lar_create();
	res=lar_divby(num1,num2,rem);
	if(res==NULL)
		return 0;
	printf("%s 整除 %s = %s ，余：%s\n",lar_tostring(num1),lar_tostring(num2),lar_tostring(res),lar_tostring(rem));
	{
		//将大数转换为长整型验证计算结果
		long n1,n2;
		n1=atol(lar_tostring(num1));
		n2=atol(lar_tostring(num2));
		//printf("%ld 整除 %ld = %ld ，余：%ld\n",n1,n2,n1/n2,n1%n2);
	}
	return 0;
}
int main(){
	test1();
}

因篇幅问题不能全部显示，请点此查看更多更全内容

查看全文

Copyright © 2019- 版权所有

Top