暑假OJ练习——9长整数加法运算

1.问题描述

假设2个任意长度的整数x、y分别由双向链表A和B存储，现要求设计一个算法，实现x+y。计算结果存储在链表C中。

说明：

由于A和B输出时需要从头至尾遍历，而做加法时需要从尾至头遍历，因此使用双向链表存储。

可以从长整数的低位开始拆分（4位为一组，即不超过9999的非负整数），依次存放在链表的每个结点的数据域中；头结点的数据域存放正负数标志（正数或0：1，负数：-1）。

2.输入说明

假设2个任意长度的整数x、y分别由双向链表A和B存储，现要求设计一个算法，实现x+y。计算结果存储在链表C中。

说明：

由于A和B输出时需要从头至尾遍历，而做加法时需要从尾至头遍历，因此使用双向链表存储。

可以从长整数的低位开始拆分（4位为一组，即不超过9999的非负整数），依次存放在链表的每个结点的数据域中；头结点的数据域存放正负数标志（正数或0：1，负数：-1）。

3.输出说明

第一行：格式化后的长整数x（从低位到高位每4位用","分开）

第二行：格式化后的长整数y（从低位到高位每4位用","分开）

第三行：空行

第四行：单链表C的遍历结果

第五行：格式化后的计算结果（从低位到高位每4位用","分开）

（输入与输出之间用一空行分隔）

4.范例

输入

-53456467576846547658679870988098
435643754856985679

输出

-5345,6467,5768,4654,7658,6798,7098,8098
43,5643,7548,5698,5679

5345->6467->5768->4611->2014->9250->1400->2419
-5345,6467,5768,4611,2014,9250,1400,2419

5.代码

#include
#include <string> //cin>>s1>>s2;
#include
#include //使用reverse()函数
using namespace std;
//头结点的数据域存放正负数标志（正数或0：1，负数：-1） head->num=1(0或者正数)
struct node {
int num;
struct node* pre;
struct node* next;
};
struct node* create(string s) { //由于链表从尾部到头部相加，所以结果采用头插法插入
//1.新建头结点并初始化
struct node* head = new node;
head->next = NULL;
head->pre = NULL;
//2.计算链表真正长度
int len=s.length();
if (s[len - 1] == '-') {
len = s.length() - 1;
head->num = -1;
}
else {
len = s.length();
head->num = 1;
}
//3.进行相加工作，num保存结果数值，cnt用于控制每四位相加
int cnt = 0;
int num = 0;
for (int i = 0; i ) {
//num += (int)(s[i] - '0') * (pow(10, cnt) + 0.1);//此处改成num +=(s[i] - '0') * pow(10, cnt);
num += (s[i] - '0') * pow(10, cnt);
cnt++;
if (cnt == 4 || i == len - 1) { //当读取4个数时重置
struct node* p = new node;
struct node* q = head->next;
p->num = num;//p所指为新建结点

head->next = p;
p->pre = head;
p->next = q;
//链表中除了头结点，还有其他结点
if (q)
q->pre = p;
cnt = 0;
num = 0;
}
}
return head;
}
void display(struct node* head) {
if (head->next) { //存在数据时
if (head->num == -1)
cout <<'-';
struct node* p = head->next;
cout <num;
p = p->next;
while (p) {
printf(",%04d", p->num);
p = p->next;
}
}
else
cout <<0; //注意这里要考虑到没有数据的情况
}
struct node* add(struct node* num1, struct node* num2) { //两个链表相加情况 ，类似于合并链表操作
struct node* head = new node;
head->next = NULL;
head->pre = NULL;
struct node* p = num1;
struct node* q = num2;
while (p->next)
p = p->next;
while (q->next)
q = q->next;
//1.链表num1,num2均非空
while (p != num1 && q != num2) { //从尾部到头部进行遍历
struct node* t = new node;
struct node* f = head->next;
t->num = num1->num*p->num + num2->num*q->num; //num1->num代表链表L1的符号 ， num2->num代表链表L2的符号
//t->num = p->num + q->num;这应该不行，因为Line ：155处开始有关于符号的处理

head->next = t;
t->pre = head;
t->next = f;
if (f)
f->pre = t;
p = p->pre;
q = q->pre;
}
//2.链表num1非空，num2已空
while (p != num1) { //类似于合并有序表，对没有运算的结点采用头部插入的方法
struct node* t = new node;
struct node* h = head->next;
t->num = num1->num * p->num;
head->next = t;
t->pre = head;
t->next = h;
if (h)
h->pre = t;
p = p->pre;
}
//3.链表num2非空，num1已空
while (q != num2) {
struct node* t = new node;
struct node* o = head->next;
t->num = num2->num * q->num;
head->next = t;
t->pre = head;
t->next = o;
if (o)
o->pre = t;
q = q->pre;
}
//4.判断最后的取值是正是负
if (head->next->num > 0)
head->num = 1;
else
head->num = -1;
p = head;
while (p->next)
p = p->next;
q = p;//q指向链表尾部结点
/*接下来部分理解很重要！！！*/
//5.处理进位情况 p指向链表尾部，逐步向前遍历
while (p != head) { //p指向链表尾部结点
//关键：处理有进位的情况
if (p->num * head->num <0) { //正数借位减一，负数借位加1
if (head->num > 0) { //正数
p->num += 10000;
p->pre->num -= 1;
}
else {
p->num -= 10000;
p->pre->num += 1;
}
}
p = p->pre; //从尾部到前部进行遍历
}
//6.将原先带符号的各个数据结点都恢复为处理为正常形式，即只有头结点head->num==1||head->num==-1代表正负数或0
p = head->next;
while (p) {
p->num = abs(p->num);
p = p->next;
}
//7.处理进位情况，注意和5进行区分
//q==head->next指代链表第一个数据结点（非头结点）
while (q != head->next) { //进行进位处理
if (q->num >= 10000) {
q->num -= 10000;
q->pre->num += 1;
}
q = q->pre;
}
if (q && q->num >= 10000) { //产生进位情况时
struct node* t = new node;
t->next = q;
q->pre = t;
head->next = t;
t->pre = head;
t->num = q->num / 10000;
q->num = q->num % 10000;
}
//8.删除前面为0的结点
p = head->next;
//当前边出现0时删除该结点
while (p && p->num == 0) {
p->pre->next = p->next; //p结点指向数据为0 ，使P结点的前驱结点指向P的后继结点 处理P的前驱结点的next指向
if (p->next)
p->next->pre = p->pre; //处理P的后继结点的pre指针指向

p = p->next;
}
return head;
};
void display_2(struct node* head) {
if (head->next) {
struct node* p = head->next;
cout <num;
p = p->next;
while (p) {
printf("->%04d", p->num); //%04d保证数据输出为四位数形式，若不足则在左边补零
p = p->next;
}
cout << endl;
}
else
cout <<0 << endl;
}
int main() {
string s1, s2;
struct node *num1, *num2, *c;
cin >> s1;
cin >> s2;
reverse(s1.begin(), s1.end());
num1 = create(s1);
display(num1);
cout << endl;
reverse(s2.begin(), s2.end());
num2 = create(s2);
display(num2);
cout < endl;
c = add(num1, num2);
display_2(c);
display(c);
return 0;
}