`
testcs_dn
  • 浏览: 113863 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

大数相加(不开辟额外空间)

 
阅读更多

大数相加可以借助多种方法来实现,这里提供了一种链表节点的数据域为int型(用char型也可以,这样更省空间)的思路。这篇文章采用常用的转变为字符串进行处理的方法,下面说下我用字符串实现大数相加的思路:

假设输入了如下两个字符串(其中上面的红色部分表示数组的下标,下面的绿色和黄色部分表示各字符):

s1:


s2:

很明显,s1的实际长度为4,s2的实际长度为7,将二者在最低位出对齐,并将前面空出来的高位用0替换,最高位留出来,以备相加到最左边有进位时,可以保存进位1。移位后如下所示:

s1:


s2:


这里没有了'\0',是因为移动的时候覆盖掉了,暂且不管,接下来我们就要执行相加的操作,由于每个字符的ASCII值均在0-255之间,因此我们没必要在另外开辟int数组,可以直接在char数组上进行移位、相加等操作,只要注意不要将还没移动或者相加的数据覆盖掉就行。

我们假设二者相加后的结果存放到s1中,则相加后,s1如下:


这是次高位没有进位,因此最高位还是0,最后我们将s1中的各int值再转化为字符,如果s1[0]为1,则直接转化,如果s1[0]为0,则转化后,需要将字符依次向前移动一位,最后,在最后一个字符的后面加上'\0',表示字符串的结束。这边得到了结果。


完整实现代码如下:

/******************
字符串实现大数相加
Author:兰亭风雨
Date:2014-05-11
******************/
#include<stdio.h>
#include<string.h>

#define MAX 100

char *BigDataAdd(char *s1,char *s2)
{
	if(s1==NULL || s2==NULL)
		return NULL;

	int len1 = strlen(s1);
	int len2 = strlen(s2);
	int Maxlen = (len1>len2)?len1:len2;
	
	//将对应的字符转化为整数,并使二者对齐到Maxlen处,
	//前面的字符通过memset用ASCII值为0的字符替换,
	//最高位留出来,如果次高位发生进位,则可以保存进位1,
	//这里s1和s2相当于变为了整数数组,由于字符的ASCII值在0-255之间,
	//因此这里不用开辟int数组,直接用自身的char数组即可
	int i,k;
	for(i=len1-1,k=Maxlen;i>=0;i--,k--)
		s1[k] = s1[i] - '0';
	if(k>=0)
		memset(s1,0,(k+1)*sizeof(char));
	for(i=len2-1,k=Maxlen;i>=0;i--,k--)
		s2[k] = s2[i] - '0';
	if(k>=0)
		memset(s2,0,(k+1)*sizeof(char));

	//整数数组相加到s1中
	for(i=Maxlen;i>=1;i--)
	{
		s1[i] += s2[i];
		if(s1[i]>=10)
		{
			s1[i] -= 10;
			s1[i-1] += 1;
		}
	}
	
	//将s1转换为为相加后的字符串
	if(s1[0] == 0)
	{	//如果次高位没有进位
		for(i=1;i<=Maxlen;i++)
			s1[i-1] = s1[i] +'0';
		s1[i-1] = '\0';
	}
	else
	{	//如果次高位有进位
		for(i=0;i<=Maxlen;i++)
			s1[i] = s1[i] +'0';
		s1[i] = '\0';
	}
	return s1;
}

int main()
{
	char s1[MAX];
	char s2[MAX];
	gets(s1);
	gets(s2);
	char *result = BigDataAdd(s1,s2);
	if(result != NULL)
		puts(result);
	else
		printf("Wrong\n");
	return 0;
}
测试结果:

原文:http://blog.csdn.net/ns_code/article/details/25555743
分享到:
评论

相关推荐

    C++大数相加减

    C++标准库并未提供内置的大数支持,因此要实现大数相加减的功能,通常需要自定义数据结构和算法。这个项目"BigNumberAdd"显然是关于如何用C++来实现大数加法和减法的示例。 首先,我们要创建一个表示大数的数据结构...

    大数运算 大数相加 大数相乘

    C和C++这两种编程语言虽然原生不支持大数运算,但可以通过自定义数据结构和算法来实现。本篇文章将详细介绍如何用C/C++实现大数相加和大数相乘。 首先,我们要理解大数的概念。在计算机内部,基本的数据类型如int、...

    两个大数相加-字符串实现

    2. 对齐:如果两个大数的位数不一致,可以在较短的大数前面添加零,使得两个大数的位数相同,以便进行逐位相加。 3. 逐位相加:从最低位开始,对两个大数的对应位进行相加,同时考虑进位。每一位的计算遵循小学数学...

    大数相加通用模版

    因此,掌握大数运算技巧对于软件开发人员而言是必不可少的技能。 ### 大数相加通用模板解析 #### 模板代码概览 给定的部分内容展示了如何通过字符串操作实现大数相加的算法。该方法将两个大数(以字符串形式存储...

    java大数相加代码

    java实现大数相加,在不使用BigInteger工具的前提下实现大数相加

    大数相加.cpp

    该文件为C/C++课程对于大数相加问题的解决, /*大数相加*/ /*在一般语言中对整型数都有个最大限制, 先给出两个超出正常范围的十进制数 对其进行求和,带进位的加法*/

    用c++编写的大数相加

    用c++编写的大数相加,可以实现任意两个长度的大数相加求和。

    大数相乘算法,java代码,包含独立大数相加算法

    大数相乘算法,java代码,包含独立大数相加算法 其中bigNumberPlus(String s1,String s2)为大数相加方法 bigNumberMultiply(String s1,String s2)为大数相乘方法

    大数相乘大数相加大数阶乘代码

    同样,如果C++标准库不提供支持,我们需要创建一个大数类,包含存储数字的数组和处理进位的逻辑。 3. **大数阶乘**: 阶乘运算涉及到大量的乘法和加法。为了计算大数阶乘,首先需要实现大数相乘和相加的功能,然后...

    用C语言和链表编写的大数相加程序

    用C语言和链表编写的大数相加程序,想学链表的不要错过,程序里的不足请多指教

    c++实现大数相加

    C++实现大数相加 C++作为一门功能强大且灵活的编程语言,在实现大数相加时提供了多种方法。下面我们将探讨使用C++实现大数相加的方法。 大数相加的定义 大数相加是指将两个或多个大整数相加,得到一个新的大整数...

    数据结构课设一:链表实现大数相加

    在这个课设“数据结构课设一:链表实现大数相加”中,我们主要关注的是链表这一基本数据结构以及如何利用它来解决实际问题,即进行大数的相加运算。 链表是一种线性数据结构,与数组不同,它不连续存储元素,而是...

    大数相加的经典算法))

    大数相加的算法,很不错,是用字符串的方法

    面向对象版大数相加、减源代码

    用面向对象及链表编写的C++大数相加、减源代码

    大数相加算法

    描述一种大数相加的算法,简单清晰。 使用string 作为主要操作对象。 欧拉13题。

    【c++】大数相加

    使用string类型实现大数相加。先将两个加数存为String类型,再从两个加数的末尾开始,一个数一个数的相加,跟做普通加法一个原理,只是这里需要注意的是,两个加数的类型为字符串,需要相应的转换才能相加,在代码有...

    C++实现大数相加

    总的来说,使用`std::string`实现大数相加是一种直观且易于理解的方法,尤其在不依赖特定的大数库的情况下。然而,在实际应用中,为了获得更好的性能和更完善的功能,可能会选择使用如GMP(GNU Multiple Precision ...

    实现大数相加功能

    这个过程需要考虑如何处理进位,并确保正确处理两个大数长度不一致的情况。 5. **内存管理**:在大数操作中,需要对动态分配的内存进行管理。在创建大数、添加新元素或合并大数后,可能需要调整字符数组的大小。别...

    C++大数相加

    C++实现的大数相加,有很好的类的封装性

    利用链表实现大数相加

    在编程领域,大数相加是一项常见的操作,特别是在处理金融计算、加密算法或者高精度数学问题时。在C#中,由于内置的数据类型如int、long等存在数值范围限制,当我们需要处理超过这些范围的大整数时,就需要自定义...

Global site tag (gtag.js) - Google Analytics