大数加法 C++语言

大数相加,大数据的数据大小已经超过系统自带的整数数据存储上限,因此采用链表存储数据;

采用的原理和平时在草稿本上算加法差不多,逐位相加,有进位则加上进位。

例如123456789和23456789相加:

利用头插法写入链表:9->8->7->6->5->4->3->2->1->NULL 和 9->8->7->6->5->4->3->2->NULL

过程:

大数加法 C++语言

 原理很简单,因此就不细说了,直接上代码,点击此处查看Git代码,或者末尾附着代码。

注:1. 只适用于正整数和0的加法,负数和小数不适用;

       2. 采用动态链表,理论上数据的大小取决于计算机能分配的内存大小;

 3. 输入的格式不能0打头。如:0000123是错误格式。

运行截图

为了直观观测结果,采用单数字重复,结尾部分分别展示输入的两位待算数据的位数。

如图,五行9和四行1相加,直接心算便知晓答案,再与运行结果对比可知代码运行结果是正确的。

大数加法 C++语言

使测试数据足够大,当然也是测试连续的9和连续的1,多次测试下发现,我的计算机极限便是4094位,因此我的计算机能分配的链表长度为4094。

大数加法 C++语言

在网上找到测试网站,测试网站有更丰富的软硬件资源。验证自己的代码,测试连续的9和连续的1,发现在达到上百万位时依然能得到正确结果。

大数加法 C++语言

为了防止万一,在连续的9中插入连续的1以检测结果,成功检测到插入的连续1的末尾由1变为2,证实代码的正确性。

插入连续的1以作检测:

大数加法 C++语言

 运行结果:

大数加法 C++语言

代码:

#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大佬

    大数加法 C++语言

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/342333

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年3月2日 上午1:33
下一篇 2023年3月2日 上午1:33

相关推荐