大数相加,大数据的数据大小已经超过系统自带的整数数据存储上限,因此采用链表存储数据;
采用的原理和平时在草稿本上算加法差不多,逐位相加,有进位则加上进位。
例如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】免费获取数百本计算机经典书籍;
也有高质量的技术群,里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/342333
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!