大数相加（不开辟额外空间）

本文主要是介绍大数相加（不开辟额外空间），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大数相加可以借助多种方法来实现，这里提供了一种链表节点的数据域为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 100char *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);elseprintf("Wrong\n");return 0;
}

测试结果：