大数相加,大数据的数据大小已经超过系统自带的整数数据存储上限,因此采用链表存储数据;
采用的原理和平时在草稿本上算加法差不多,逐位相加,有进位则加上进位。
例如123456789和23456789相加:
利用头插法写入链表:9->8->7->6->5->4->3->2->1->NULL 和 9->8->7->6->5->4->3->2->NULL
过程:
原理很简单,因此就不细说了,直接上代码,点击此处查看Git代码,或者末尾附着代码。
注:1. 只适用于正整数和0的加法,负数和小数不适用;
2. 采用动态链表,理论上数据的大小取决于计算机能分配的内存大小;
3. 输入的格式不能0打头。如:0000123是错误格式。
运行截图:
为了直观观测结果,采用单数字重复,结尾部分分别展示输入的两位待算数据的位数。
如图,五行9和四行1相加,直接心算便知晓答案,再与运行结果对比可知代码运行结果是正确的。
使测试数据足够大,当然也是测试连续的9和连续的1,多次测试下发现,我的计算机极限便是4094位,因此我的计算机能分配的链表长度为4094。
在网上找到测试网站,测试网站有更丰富的软硬件资源。验证自己的代码,测试连续的9和连续的1,发现在达到上百万位时依然能得到正确结果。
为了防止万一,在连续的9中插入连续的1以检测结果,成功检测到插入的连续1的末尾由1变为2,证实代码的正确性。
插入连续的1以作检测:
运行结果:
代码:
#include<iostream>
#include<stdio.h>
using namespace std;
int k=0,bit=0;
struct Array
{
int a;
struct Array* next;
}Array;
struct Array CreatArray(int *n)
{
struct Array* p, * q,*head;
head = new struct Array;
head->next = NULL;
q = new struct Array;
q->next = NULL;
char ch;
int a=0;
while (1)
{
ch=getchar();
if (ch == 'n')
{
k = 0;
return *q;
}
*n=*n+1;
a = ch - '0';
if (k == 0)
{
head = new struct Array;
head->next = NULL;
head->a = a;
q = head;
k = 1;
}
else
{
p = new struct Array;
p->next = q;
p->a = a;
q = p;
}
}
}
void Add(struct Array *head, struct Array *head1, int n, int n1)
{
int bit1=0;
struct Array* p, * q, * p1, * q1;
p = head;
q = head;
p1 = head1;
q1 = head1;
if (n >= n1)
{
for (; p1; p = p->next, p1 = p1->next)
{
bit1 = p->a + p1->a + bit;
bit = 0;
p->a = bit1 % 10;
bit= bit1 / 10;
if (n == n1 && p->next == NULL && bit)
{
q = new struct Array;
q->next = NULL;
q->a = bit;
bit = 0;
p->next = q;
}
}
for (; p; p = p->next)
{
bit1 = p->a + bit;
bit = 0;
p->a = bit1 % 10;
bit = bit1 / 10;
if (bit && p->next == NULL)
{
q = new struct Array;
q->next = NULL;
q->a = bit;
bit = 0;
p->next = q;
}
}
p = head;
while (p)
{
if (k == 0)
{
head1 = new struct Array;
head1->next = NULL;
head1->a = p->a;
q1 = head1;
k = 1;
}
else
{
p1 = new struct Array;
p1->next = q1;
p1->a = p->a;
q1 = p1;
}
p = p->next;
}
k = 0;
while (p1)
{
cout << p1->a;
p1 = p1->next;
}
}
else
{
for (; p; p = p->next, p1 = p1->next)
{
bit1 = p->a + p1->a + bit;
p1->a = bit1 % 10;
bit = 0;
bit = bit1 / 10;
}
for (; p1; p1 = p1->next)
{
bit1 = p1->a + bit;
bit = 0;
p1->a = bit1 % 10;
bit = bit1 / 10;
if (bit && p1->next == NULL)
{
q1 = new struct Array;
q1->next = NULL;
q1->a = bit;
bit = 0;
p1->next = q1;
}
}
p1 = head1;
while (p1)
{
if (k == 0)
{
head = new struct Array;
head->next = NULL;
head->a = p1->a;
q = head;
k = 1;
}
else
{
p = new struct Array;
p->next = q;
p->a = p1->a;
q = p;
}
p1 = p1->next;
}
k = 0;
while (p)
{
cout << p->a;
p = p->next;
}
}
}
int main()
{
struct Array * head;
struct Array * head1;
int n=0, n1=0;
head = new struct Array;
head->next = NULL;
head1 = new struct Array;
head1->next = NULL;
*head=CreatArray(&n);
cout << "+" << endl;
*head1 = CreatArray(&n1);
cout << "=" << endl;
Add(head, head1, n, n1);
cout << endl;
cout << endl;
cout << "输入的第一位数位数:"<<n << " 输入的第二位数位数:" << n1 << endl;
return 0;
}
原文链接: https://www.cnblogs.com/darius-lee/p/12716926.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/196054
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!