大数相加c语言实现

yalewoo 最后修改于 2015-01-01 发表于 2014-11-14 5,582 views 0

C/C++ c语言

c语言中int类型是有一定的范围的，例如在32位的情况下可以表示的最大整数是2^31 – 1 = 2147483647 。

如果想要进行更多位数的整数加法，可以用数组，分别对每个位进行计算。

合法数字检查

输入的时候应检查输入的是否是合法的数字，若不是则应进行处理。

分配空间

本文中的程序可以接收任意多位数的输入，因为采用的是运行时根据输入的位数分配空间的。

存放结果的数组，比两个数组中位数最多的那个位数还要多2，一个用来保存可能的进位（例如9+9 两个一位数结果是二位数），另一个用来保存表示字符串结束的空字符’\0′

输入54321和192后，在内存中是这样表示的

个位对齐

数字按照字符的形式存入数组后，进行运算的时候还需要从个位开始算起，所以应该将num2向右移动，让个位对齐。

也可以将各个位数字逆序，这样从下标0开始，就是对齐的个位数字。

逆序的过程可以顺便把字符变为对应十进制数字，只需要减去’0’即可。

本程序中对齐后效果如下

n1和n2分配空间大小是最长数字的位数+1 ，最高位后面全部置0.这样是为了计算时候的方便。

这样下标0是个位下标1是十位下标2是百位……

计算

c语言代码

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
#include <string.h>

#define INIT_LENGTH 20	//数字位数的起始大小

char * inputBigNum(void);	//接收标准输入的数字 存入内存后返回地址 返回的地址需要free
char * bigNumAdd(const char *num1, const char *num2);	//计算num1+num2 结果是一个指针 用完后需要free

int main(void)
{
	char *num1;	//数字1指针
	char *num2;	//数字2指针
	char *res;	//存放结果的指针

printf("Input the first num:\n");
	num1 = inputBigNum();
	while (num1 == NULL)	//判断非法数字
	{
		printf("Invalid num, please input again:\n");
		num1 = inputBigNum();
	}

printf("Input the second num:\n");
	while ((num2 = inputBigNum()) == NULL)	//判断非法数字
	{
		printf("Invalid num, please input again:\n");
		num2 = inputBigNum();
	}

res = bigNumAdd(num1, num2);	//计算

printf("num1: %s\n", num1);
	printf("num2: %s\n", num2);
	printf("res: %s\n", res);

free(num1);
	free(num2);
	free(res);

return 0;
}

/*
 * 根据输入数字个数分配内存（采用翻倍增加空间的方式 有效利用率大于50%）
 * 如果输入中有非数字 返回NULL
 * 如果输入是合法数字 返回一个存放该数字字符串的指针 
 * 返回有效指针时，记得用完后释放内存
*/
char * inputBigNum(void)
{
	char *p;
	int i = 0;
	int current_capacity = INIT_LENGTH;
	char ch;
	int ok = 1;

if ((p = (char *)malloc(INIT_LENGTH * sizeof(char))) == NULL)
		exit(-1);

while ((ch = getchar()) != '\n')
	{
		p[i++] = ch;
		if (ch < '0' || ch > '9')
		{
			ok = 0;
		}
		//已经写入了i个数字
		if (i+1 == current_capacity)
		{
			if ((p = (char *)realloc(p, current_capacity * 2 * sizeof(char))) == NULL)
				exit(-1);
			current_capacity *= 2;
		}
	}
	p[i] = '\0';

if (ok == 0)
	{
		free(p);
		return NULL;
	}
	else
	{
		return p;
	}
}

/*
 * 计算num1 + num2 结果是字符串形式 
 * 返回存放结果的字符串地址，记得用完后free
*/
char * bigNumAdd(const char *num1, const char *num2)
{
	int i;

int num1_len;	//num1的数字位数
	int num2_len;	//num2的数字位数
	int res_len;	//计算结果的数字位数 包括最后的空字符'\0'

char *n1;	//临时存放num1
	char *n2;	//临时存放num2
	char *res;	//存放结果

int c = 0;	//每一位上的进位 个位上的进位初始时是0

//计算长度
	num1_len = strlen(num1);
	num2_len = strlen(num2);
	res_len = num1_len > num2_len ? num1_len : num2_len;

//分配内存 两个加数最高位的更高一位设置为0 结果包含可能的进位和空字符'\0'
	if ((n1 = (char *)malloc(res_len * sizeof(char) + 1)) == NULL)
		exit(-1);
	if ((n2 = (char *)malloc(res_len * sizeof(char) + 1)) == NULL)
		exit(-1);
	if ((res = (char *)malloc(res_len * sizeof(char) + 2)) == NULL)
		exit(-1);
	memset(n1, 0, res_len * sizeof(char) + 1);
	memset(n2, 0, res_len * sizeof(char) + 1);
	memset(res, 0, res_len * sizeof(char) + 2);
	
	//将原加数按照逆序存入n1和n2 同时转换为数字
	for (i = 0; i < num1_len; ++i)
	{
		n1[i] = num1[num1_len-i-1] - '0';
	}
	for (i = 0; i < num2_len; ++i)
	{
		n2[i] = num2[num2_len-i-1] - '0';
	}

//按位进行加运算
	for (i = 0; i < res_len + 1; ++i)
	{
		res[res_len-i] = ((n1[i] + n2[i] + c) % 10) + '0';	//结果最高位是个位
		c = (n1[i] + n2[i] + c) / 10;	//进位
	}
	res[res_len+1] = '\0';	//设置末尾的空字符

//释放临时内存
	free(n1);
	free(n2);

return res;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

#include <stdio.h>

#include <stdlib.h>

#include <malloc.h>

#include <string.h>

#define INIT_LENGTH 20 //数字位数的起始大小

char * inputBigNum(void); //接收标准输入的数字存入内存后返回地址返回的地址需要free

char * bigNumAdd(const char *num1, const char *num2); //计算num1+num2 结果是一个指针用完后需要free

int main(void)

{

char *num1; //数字1指针

char *num2; //数字2指针

char *res; //存放结果的指针

printf("Input the first num:\n");

num1 = inputBigNum();

while (num1 == NULL) //判断非法数字

{

printf("Invalid num, please input again:\n");

num1 = inputBigNum();

}

printf("Input the second num:\n");

while ((num2 = inputBigNum()) == NULL) //判断非法数字

{

printf("Invalid num, please input again:\n");

num2 = inputBigNum();

}

res = bigNumAdd(num1, num2); //计算

printf("num1: %s\n", num1);

printf("num2: %s\n", num2);

printf("res: %s\n", res);

free(num1);

free(num2);

free(res);

return 0;

}

* 根据输入数字个数分配内存（采用翻倍增加空间的方式有效利用率大于50%）

* 如果输入中有非数字返回NULL

* 如果输入是合法数字返回一个存放该数字字符串的指针

* 返回有效指针时，记得用完后释放内存

char * inputBigNum(void)

{

char *p;

int i = 0;

int current_capacity = INIT_LENGTH;

char ch;

int ok = 1;

if ((p = (char *)malloc(INIT_LENGTH * sizeof(char))) == NULL)

exit(-1);

while ((ch = getchar()) != '\n')

{

p[i++] = ch;

if (ch < '0' || ch > '9')

{

ok = 0;

}

//已经写入了i个数字

if (i+1 == current_capacity)

{

if ((p = (char *)realloc(p, current_capacity * 2 * sizeof(char))) == NULL)

exit(-1);

current_capacity *= 2;

}

p[i] = '\0';

if (ok == 0)

{

free(p);

return NULL;

}

else

{

return p;

}

* 计算num1 + num2 结果是字符串形式

* 返回存放结果的字符串地址，记得用完后free

char * bigNumAdd(const char *num1, const char *num2)

{

int i;

int num1_len; //num1的数字位数

int num2_len; //num2的数字位数

int res_len; //计算结果的数字位数包括最后的空字符'\0'

char *n1; //临时存放num1

char *n2; //临时存放num2

char *res; //存放结果

int c = 0; //每一位上的进位个位上的进位初始时是0

//计算长度

num1_len = strlen(num1);

num2_len = strlen(num2);

res_len = num1_len > num2_len ? num1_len : num2_len;

//分配内存两个加数最高位的更高一位设置为0 结果包含可能的进位和空字符'\0'

if ((n1 = (char *)malloc(res_len * sizeof(char) + 1)) == NULL)

exit(-1);

if ((n2 = (char *)malloc(res_len * sizeof(char) + 1)) == NULL)

exit(-1);

if ((res = (char *)malloc(res_len * sizeof(char) + 2)) == NULL)

exit(-1);

memset(n1, 0, res_len * sizeof(char) + 1);

memset(n2, 0, res_len * sizeof(char) + 1);

memset(res, 0, res_len * sizeof(char) + 2);

//将原加数按照逆序存入n1和n2 同时转换为数字

for (i = 0; i < num1_len; ++i)

{

n1[i] = num1[num1_len-i-1] - '0';

}

for (i = 0; i < num2_len; ++i)

{

n2[i] = num2[num2_len-i-1] - '0';

}

//按位进行加运算

for (i = 0; i < res_len + 1; ++i)

{

res[res_len-i] = ((n1[i] + n2[i] + c) % 10) + '0'; //结果最高位是个位

c = (n1[i] + n2[i] + c) / 10; //进位

}

res[res_len+1] = '\0'; //设置末尾的空字符

//释放临时内存

free(n1);

free(n2);

return res;

}

雅乐网

计算机技术、学习成长