11202: 【原1202】bigint

题目

题目描述

author: DS助教 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1202

Description

本题做一些简化，题目要求改为输入两个正整数，输出两个正整数的和。

Input Format

输入文件包括两行。

第一行包括一个正整数，保证位数不超过1000000。

第一行包括一个正整数，保证位数不超过1000000。

Output Format

输出文件包括一行。

第一行包括一个正整数。

Sample Input

10558
22

Sample Output

10580

Limits

1.请使用链表答题，否则代码分给0分。

2.请存储下来两个正整数的和，否则代码分给0分。

ligongzzz's solution

#include "iostream"
#include "cstring"
using namespace std;

constexpr auto maxNum = 1000001;

class myList {
public:
    short data=0;
    myList *next = nullptr;
};

class bigNum {
public:
    myList *head;
    bigNum(const char* ch) {
        head = new myList;
        auto p = head;
        for (int i = strlen(ch) - 1; i >= 0; i--) {
            //添加元素
            p->next = new myList;
            p = p->next;
            p->data = ch[i] - '0';
        }
    }
    void add(bigNum num) {
        //开始运算
        int temp = 0;
        auto p1 = head, p2 = num.head;
        while (p1->next != nullptr || p2->next != nullptr || temp != 0) {
            //判断是否需要添加
            if (p1->next == nullptr)
                p1->next = new myList;
            short addNum = p2->next == nullptr ? 0 : p2->next->data;
            if (p1->next->data + addNum + temp < 10) {
                p1->next->data = p1->next->data + addNum + temp;
                temp = 0;
            }
            else {
                p1->next->data = p1->next->data + addNum + temp - 10;
                temp = 1;
            }
            p1 = p1->next;
            p2 = p2->next == nullptr ? p2 : p2->next;
        }
    }
    void print() {
        char printString[maxNum] = { 0 }, reverseString[maxNum] = { 0 };
        int n = 0;
        for (auto p = head; p->next != nullptr; p = p->next) {
            printString[n] = p->next->data + '0';
            n++;
        }
        //倒序
        int stringSize = strlen(printString);
        for (int i = 0; i < stringSize; i++)
            reverseString[i] = printString[stringSize - i - 1];
        cout << reverseString;
    }
};

int main() {
    char num1[maxNum];
    cin >> num1;
    bigNum n1(num1);
    cin >> num1;
    bigNum n2(num1);
    n2.add(n1);
    n2.print();

    return 0;
}

Neight99's solution

#include <cstring>
#include <iostream>

using namespace std;

class String {
   private:
    struct Node {
        char data;
        Node *prev, *next;

        Node(const int &x = 0, Node *p = NULL, Node *q = NULL)
            : data(x), next(q), prev(p) {}

        ~Node() {}
    };

    Node *head, *tail;
    int Length;

    Node *move(int) const;

   public:
    String();

    String(const char *);

    String(const String &);

    ~String() {
        clear();
        delete head;
        delete tail;
        head = NULL;
        tail = NULL;
    }

    void clear();

    int length() const { return Length; }

    void insert(int, const char &);

    char visit(int) const;

    char *travel() const;

    void remove(int);

    void plus(String, String);

    String operator=(const String &);
};

String::Node *String::move(int i) const {
    Node *p = head;
    --i;
    while (i >= 0) {
        p = p->next;
        --i;
    }
    return p;
}

String::String() {
    head = new Node();
    head->next = tail = new Node();
    tail->prev = head;
    head->prev = NULL;
    tail->next = NULL;
    Length = 0;
}

String::String(const char *str) : String() {
    int len = strlen(str);

    for (int i = len - 1; i >= 0; i--) {
        this->insert(1, str[i] - '0');
    }
}

String::String(const String &right) : String() {
    if (this->head != NULL) {
        // clear();
    }
    Node *q = right.tail->prev;
    while (q->prev != NULL) {
        this->insert(1, q->data);
        q = q->prev;
    }
}

String String::operator=(const String &right) {
    if (this != &right) {
        // clear();
        Node *q = right.head->next;
        while (q->prev != NULL) {
            this->insert(1, q->data);
            q = q->prev;
        }
    }
    return *this;
}

void String::remove(int i) {
    Node *p;
    p = move(i);
    p->prev->next = p->next;
    p->next->prev = p->prev;
    delete p;
    --Length;
}

char *String::travel() const {
    char *str;
    int i = 0;
    str = new char[Length];
    Node *p = head->next;
    while (p->next != NULL) {
        str[i] = (p->data) + '0';
        i++;
        p = p->next;
    }
    str[i] = '\0';

    return str;
}

char String::visit(int x) const { return move(x)->data; }

void String::clear() {
    Node *p = head->next, *q;
    head->next = tail;
    tail->prev = head;
    while (p != tail) {
        q = p->next;
        delete p;
        p = q;
    }
    p = NULL;
    q = NULL;

    Length = 0;
}

void String::insert(int i, const char &x) {
    Node *pos, *tmp;
    pos = move(i);
    tmp = new Node(x, pos->prev, pos);
    pos->prev->next = tmp;
    pos->prev = tmp;
    Length++;
    pos = NULL;
    tmp = NULL;
}

void String::plus(String b1, String b2) {
    this->clear();
    int carry = 0, temp = 0;
    Node *p = b1.tail->prev, *q = b2.tail->prev;

    while (p->prev != NULL && q->prev != NULL) {
        temp = p->data + q->data + carry;
        carry = temp / 10;
        temp %= 10;
        this->insert(1, temp);
        temp = 0;
        p = p->prev;
        q = q->prev;
    }

    if (p->prev == NULL) {
        while (q->prev != NULL) {
            temp = q->data + carry;
            carry = temp / 10;
            temp %= 10;
            this->insert(1, temp);
            temp = 0;
            q = q->prev;
        }
    }

    if (q->prev == NULL) {
        while (p->prev != NULL) {
            temp = p->data + carry;
            carry = temp / 10;
            temp %= 10;
            this->insert(1, temp);
            temp = 0;
            p = p->prev;
        }
    }

    if (carry != 0) {
        this->insert(1, carry);
        carry = 0;
    }
}

void input(char *);

int main() {
    char str1[100001] = {'\0'}, str2[100001] = {'\0'}, *str3;
    input(str1);
    input(str2);
    String num1(str1), num2(str2), num3;
    num3.plus(num1, num2);
    str3 = num3.travel();
    cout << str3;
}

void input(char *num) {
    char ch;
    int i = 0;
    cin.get(ch);
    while (ch != '\n' && i != 100000) {
        num[i] = ch;
        i++;
        cin.get(ch);
    }
}

q4x3's solution

#include <iostream>
#include <cstdio>
using namespace std;

class LIST {
public: 
    struct NODE {
        int data;
        NODE *last;
        NODE *next;
    };

    NODE *head = NULL, *tail = NULL;
    int len = 0;

    void Pre() {
        head = new NODE;
        tail = new NODE;
        head->next = tail;
        head->last = NULL;
        tail->next = NULL;
        tail->last = head;
    }

    NODE* move(int i) {
        NODE *ith = head;
        int k = 0;
        while (k < i) {
            ++ k;
            ith = ith->next;
        }
        return ith;
    }

    void insert(int i, int x) {
        ++ len;
        NODE *ptr = new NODE;
        NODE *tmp = move(i);
        ptr->data = x;
        ptr->last = tmp;
        ptr->next = tmp->next;
        tmp->next = ptr;
        ptr->next->last = ptr;
        return;
    }

    void remove(int i) {
        --len;
        NODE *tmp = move(i);
        NODE *delptr = tmp->next;
        tmp->next = delptr->next;
        delptr->next->last = tmp;
        delete delptr;
    }

    int Get_length() {
        return len;
    }

    int Query(int i) {
        if (i >= len) return -1;
        else return move(i)->next->data;
    }

    void Print() {
        NODE *ptr;
        if (len == 0) cout << -1 << endl;
        else {
            ptr = head->next;
            while (ptr != NULL && ptr->next != NULL) {
                printf("%d", ptr->data);
                ptr = ptr->next;
            }
            cout << endl;
        }
        return;
    }

    void Clear() {
        NODE *ptr = head;
        while (ptr->next != NULL) {
            NODE *tmp = ptr;
            delete ptr;
            ptr = tmp->next;
        }
    }

};
int main() {
    LIST L1, L2, L;
    L1.Pre(); L2.Pre(); L.Pre();
    char tmp;
    while(1) {
        tmp = getchar();
        if(tmp == '\n') break;
        L1.insert(0, tmp - '0');
    }
    while(1) {
        tmp = getchar();
        if(tmp == '\n') break;
        L2.insert(0, tmp - '0');
    }
    int carry = 0;
    LIST::NODE *p1 = L1.head->next, *p2 = L2.head->next;
    for(int i = 0;i < L1.len || i < L2.len;++ i) {
        int tmp1, tmp2;
        if(p1->next == NULL) tmp1 = 0;
        else {
            tmp1 = p1->data;
            p1 = p1->next;
        }
        if(p2->next == NULL) tmp2 = 0;
        else {
            tmp2 = p2->data;
            p2 = p2->next;
        }
        int sum = tmp1 + tmp2 + carry;
        L.insert(0, sum % 10);
        carry = sum / 10;
    }
    if(carry) {
        L.insert(0, 1);
    }
    L.Print();
    L1.Clear();
    L2.Clear();
    L.Clear();
    return 0;
}

skyzh's solution

#include <iostream>
#include <string>
using namespace std;

struct Digit {
    int d;
    Digit* next;
};

int main() {
    string Na, Nb;
    getline(cin, Na);
    getline(cin, Nb);
    Digit* A = NULL;
    Digit* B = NULL;
    // C in reverse order
    Digit* C = NULL;
    for (int i = 0; i < Na.length(); i++) {
        Digit* n = new Digit;
        n->d = Na[i] - '0';
        n->next = A;
        A = n;
    }
    for (int i = 0; i < Nb.length(); i++) {
        Digit* n = new Digit;
        n->d = Nb[i] - '0';
        n->next = B;
        B = n;
    }
    Digit *a = A, *b = B;
    int carry = 0;
    for (; a && b; a = a->next, b = b->next) {
        Digit* n = new Digit;
        n->d = a->d + b->d + carry;
        carry = n->d / 10;
        n->d %= 10;
        n->next = C;
        C = n;
    }
    for(; a; a = a->next) {
        Digit* n = new Digit;
        n->d = a->d + carry;
        carry = n->d / 10;
        n->d %= 10;
        n->next = C;
        C = n;
    }
    for(; b; b = b->next) {
        Digit* n = new Digit;
        n->d = b->d + carry;
        carry = n->d / 10;
        n->d %= 10;
        n->next = C;
        C = n;
    }
    if (carry) {
        Digit* n = new Digit;
        n->d = carry;
        n->next = C;
        C = n;
    }
    Digit* c = C;
    while (c) {
        cout << c->d;
        c = c->next;
    }
    cout << endl;
    return 0;
}

victrid's solution

#include <iostream>

using namespace std;

struct uzel {
    uzel* niz;
    uzel* vys;
    char czs;
    uzel(char& cz, uzel* lf) : czs(cz), vys(lf->vys), niz(lf) {
        lf->vys = this;
    }
    uzel(char& cz, uzel* hf, int plc) : czs(cz), niz(hf->niz), vys(hf) {
        hf->niz = this;
    }
    uzel() {
        vys = nullptr;
        niz = nullptr;
        czs = '0';
    }
};
struct uzch {
    uzel* hf;
    uzel* lf;
    uzch() {
        hf      = new uzel;
        lf      = new uzel;
        hf->niz = lf;
        lf->vys = hf;
    }
    uzch* uchi(char cz) {
        new uzel(cz, lf);
        return this;
    }
    uzch* uchi(char cz, int plc) {
        new uzel(cz, hf, 1);
        return this;
    }
};
int main() {
    uzch i1, i2, i3;
    char cz;
    while (scanf("%c", &cz) && cz != '\n') {
        i1.uchi(cz);
    }
    while (scanf("%c", &cz) && cz != '\n') {
        i2.uchi(cz);
    }
    uzel *ptrf1 = i1.lf->vys, *ptrf2 = i2.lf->vys;
    bool ppf = false; // !                       |
    //! highest should not be ignored!         \ | /
    //!                                         \|/
    while (ptrf1 != i1.hf || ptrf2 != i2.hf || ppf) {
        char ans = ptrf1->czs + ptrf2->czs + ppf - '0' - '0';
        ppf      = ans / 10;
        i3.uchi('0' + ans % 10, 1);
        if (ptrf1 != i1.hf)
            ptrf1 = ptrf1->vys;
        if (ptrf2 != i2.hf)
            ptrf2 = ptrf2->vys;
    }
    bool stf = false;
    for (uzel* hff = i3.hf->niz; hff != i3.lf; hff = hff->niz) {
        if (hff->czs != '0' || stf || hff->niz == i3.lf) {
            cout << hff->czs;
            stf = true;
        }
    }
    return 0;
}

yyong119's solution

#include <iostream>
#include <cstring>
int a[1000001],b[1000001],c[1000001];
char p[1000000],q[1000000];
int i,length;
int main(){
    using namespace std;
    cin>>p>>q;
    for (i=0; i<=strlen(p)-1; i++) a[strlen(p)-i]=int(p[i]-'0');
    for (i=0; i<=strlen(q)-1; i++) b[strlen(q)-i]=int(q[i]-'0');
    if (strlen(p)>=strlen(q)) length=strlen(p);
        else length=strlen(q);
    for (i=1; i<=length; i++){
        c[i]+=a[i]+b[i];
        c[i+1]+=c[i]/10; c[i]=c[i]%10;
    }
    if (c[length+1]) length++;
    for (i=length; i>=1; i--) cout<<c[i];
    return 0;
}

Zsi-r's solution

#include <iostream>
#include <cstring>

using namespace std;

template <class elemType>
class sLinkList
{
public:
    struct node
    {
        elemType data;
        node *next;

        node(const elemType &x, node *N=NULL){
            data = x; next = N;
        }
        node ():next(NULL){};
        ~node(){};
    };

    node *head;
    int currentLength;

    node *move(int i)const;

    sLinkList();
    ~sLinkList(){clear();delete head;}

    void clear();
    int length()const {return currentLength;}
    void insert(int i,const elemType &x);
    elemType visit(int i) const;
    void traverse()const;
};

template<class elemType>
typename sLinkList<elemType>::node *sLinkList<elemType>::move(int i)const
{
    node *p = head;
    while(i-->=0)p = p->next;
    return p;
}

template<class elemType>
sLinkList<elemType>::sLinkList()
{
    head = new node;
    currentLength = 0;
}

template<class elemType>
void sLinkList<elemType>::clear()
{
    node *p = head -> next,*q;
    head ->next = NULL;
    while (p!=NULL)
    {
        q = p ->next;
        delete p;
        p = q;
    }
    currentLength =0;
}

template<class elemType>
void sLinkList<elemType>::insert(int i, const elemType &x)
{
    node *pos;

    pos = move(i -1);
    pos->next=new node(x,pos->next);
    ++currentLength;
}

template<class elemType>
elemType sLinkList<elemType>::visit(int i)const
{
    return move(i)->data;
}

template<class elemType>
void sLinkList<elemType>::traverse()const
{
    node *p = head ->next;
    while(p != NULL)
    {
        cout <<p->data;
        p = p->next;
    }
}


int main()
{
    char *l1=new char[1000001];
    char *l2=new char[1000001];
    char *resultstring=new char[1000002];
    cin >> l1>>l2;

    int i=0,j=0,len3=0,quotient,rem=0,temp,k=0,len1=strlen(l1),len2=strlen(l2);

    sLinkList<char> list1,list2,list3;
    while(i<len1)
    {
        list1.insert(0,l1[i]);
        i++;
    }

    while(j<len2)
    {
        list2.insert(0,l2[j]);
        j++;
    }

    sLinkList<char>::node *p=list1.head->next,*q=list2.head->next;

    while(len3<i&&len3<j)
    {
        temp = (p->data)+(q->data)-'0'-'0'+rem;
        quotient = temp%10;
        list3.insert(0,quotient+'0');
        rem = temp/10;
        len3++;
        p=p->next;q=q->next;
    }

    while(len3<i)
    {
        temp = (p->data)-'0'+rem;
        quotient = temp%10;
        list3.insert(0,quotient+'0');
        rem = temp/10;
        len3++;
        p=p->next;
    }

    while(len3<j)
    {
        temp = (q->data)-'0'+rem;
        quotient = temp%10;
        list3.insert(0,quotient+'0');
        rem = temp/10;
        len3++;
        q = q->next;
    }

    if (rem!=0){list3.insert(0,rem+'0');len3++;}
    p=list3.head->next;
    for (k=0;k<len3;k++){resultstring[k]=p->data;p=p->next;}
    cout<<resultstring;

    return 0;
}