大数相加可以借助多种方法来实现,这里提供了一种链表节点的数据域为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/C++实现的大数相加和大数相乘,可以拿来当工具用。
java实现大数相加,在不使用BigInteger工具的前提下实现大数相加
该文件为C/C++课程对于大数相加问题的解决, /*大数相加*/ /*在一般语言中对整型数都有个最大限制, 先给出两个超出正常范围的十进制数 对其进行求和,带进位的加法*/
用c++编写的大数相加,可以实现任意两个长度的大数相加求和。
很通用的大数相加模版, 使用做ACM超出数范围情况下使用
大数相乘算法,java代码,包含独立大数相加算法 其中bigNumberPlus(String s1,String s2)为大数相加方法 bigNumberMultiply(String s1,String s2)为大数相乘方法
用C语言和链表编写的大数相加程序,想学链表的不要错过,程序里的不足请多指教
大数相加的算法,很不错,是用字符串的方法
字符串实现大数相加,首先两个数是用计算机的位数不能表示出来的,然后我们用字符数组进行操作!
大数相乘大数相加大数阶乘代码 完全解决代码简易 容易理解 有什么缺点欢迎评论 交流
用面向对象及链表编写的C++大数相加、减源代码
描述一种大数相加的算法,简单清晰。 使用string 作为主要操作对象。 欧拉13题。
使用string类型实现大数相加。先将两个加数存为String类型,再从两个加数的末尾开始,一个数一个数的相加,跟做普通加法一个原理,只是这里需要注意的是,两个加数的类型为字符串,需要相应的转换才能相加,在代码有...
C++实现的大数相加,有很好的类的封装性
利用链表实现大数相加
大数相加
一个关于大数相乘和大数相加的c语言源代码
该文件夹是用vs2017实现的整个项目文件,作为数据结构的第一次上机实习,用的也只是一些数据结构中较为基础的知识,仅仅用到最简单的链表就能实现大数的相加,该代码仅供参考,代码还是自己动手实现才有意义。
利用字符串实现大数相加,代码在VS2005 中可用