# 11202: 【原1202】bigint

### 题目描述

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

## 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:
bigNum(const char* ch) {
for (int i = strlen(ch) - 1; i >= 0; i--) {
//添加元素
p->next = new myList;
p = p->next;
p->data = ch[i] - '0';
}
}
//开始运算
int temp = 0;
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.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() {}
};

int Length;

Node *move(int) const;

public:
String();

String(const char *);

String(const String &);

~String() {
clear();
delete tail;
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 {
--i;
while (i >= 0) {
p = p->next;
--i;
}
return p;
}

String::String() {
head->next = tail = new Node();
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() {
// 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();
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];
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() {
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() {
tail = new NODE;
tail->next = NULL;
}

NODE* move(int i) {
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 {
while (ptr != NULL && ptr->next != NULL) {
printf("%d", ptr->data);
ptr = ptr->next;
}
cout << endl;
}
return;
}

void Clear() {
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;
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>
{
public:
struct node
{
elemType data;
node *next;

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

int currentLength;

node *move(int i)const;

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>
{
while(i-->=0)p = p->next;
return p;
}

template<class elemType>
{
currentLength = 0;
}

template<class elemType>
{
node *p = head -> next,*q;
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>
{
return move(i)->data;
}

template<class elemType>
{
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);

while(i<len1)
{
list1.insert(0,l1[i]);
i++;
}

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

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++;}