9 长整数加法运算

作者: Turbo时间限制: 1S章节: 链表

问题描述

假设2个任意长度的整数x、y分别由双向链表A和B存储，现要求设计一个算法，实现x+y。计算结果存储在链表C中。 说明： 由于A和B输出时需要从头至尾遍历，而做加法时需要从尾至头遍历，因此使用双向链表存储。 可以从长整数的低位开始拆分（4位为一组，即不超过9999的非负整数），依次存放在链表的每个结点的数据域中；头结点的数据域存放正负数标志（正数或0：1，负数：-1）。

输入说明

第一行：长整数x 第二行：长整数y

输出说明

第一行：格式化后的长整数x（从低位到高位每4位用",“分开） 第二行：格式化后的长整数y（从低位到高位每4位用”,“分开） 第三行：空行 第四行：单链表C的遍历结果 第五行：格式化后的计算结果（从低位到高位每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

解题思路

1.首先用尾插法创建链表：其中要对字符串第一个元素进行判断，判断他是否是符号位。注意：此处将原链表做成了双向循环链表的形式，便于定位最后一个链表节点。 2.对两个链表数据进行相加操作，但是两个数据的正负可能不同，实际对应的计算效果也就不同，解决方法就是给每一个节点都成上该数据的正负号，即都乘上头结点的val值再相加； 进行加法运算时是从尾结点开始的，所以将每次存储计算结果的节点用头插法插入到新链表的头结点之后； 处理结果整体的正负号问题； 然后处理结果链表中每个节点的进位问题：如果当前节点的值大于10，则值-10，前一个节点+1,；同理值小于0，则值+10，前一个节点-1。 3.格式化处理过程：从个位开始，每四位为一组，所以判断出长整数的总长度后对4取余，余数就是余下的最高位组数字个数 4.另外，存在两个长整数相加结果是0的特殊情况，要单独讨论

代码实现

#include <iostream> #include <string.h> using namespace std; struct ListNode { int val; struct ListNode *next; struct ListNode *prior; }; //尾插法创建链表，同时将链表创建为循环的便于找到尾结点 ListNode *createByTail(string s) { struct ListNode *head=new ListNode,*p,*temp; int i; if(s[0]=='-') { i=1; head->val=-1; } else { i=0; head->val=1; } p=head; for(;i<s.length();i++) { temp=new ListNode; temp->val=s[i]-'0'; temp->next=p->next; temp->prior=p; p->next=temp; p=temp; } p->next=head; head->prior=p; return head; } ListNode *actionAdd(ListNode *headx,ListNode *heady) { struct ListNode *head=new ListNode,*temp; //做加法运算的时候要从最后一位开始 head->next=NULL; struct ListNode *x=headx->prior,*y=heady->prior; //用头插法将新创建的节点插入到新的链表中 while(x!=headx && y!=heady) { temp=new ListNode; temp->val=x->val*headx->val + y->val*heady->val; temp->next=head->next; if(temp->next) temp->next->prior=temp; temp->prior=head; head->next=temp; x=x->prior; y=y->prior; } while(x!=headx) { temp=new ListNode; temp->val=x->val*headx->val; temp->next=head->next; if(temp->next) temp->next->prior=temp; temp->prior=head; head->next=temp; x=x->prior; } while(y!=heady) { temp=new ListNode; temp->val=y->val*heady->val; temp->next=head->next; if(temp->next) temp->next->prior=temp; temp->prior=head; head->next=temp; y=y->prior; } //现在来判断进位和正负号问题 struct ListNode *p; head->val=1; p=head; if(p->next->val<0) { while(p->next) { p=p->next; p->val=(-1)*p->val; head->val=-1; } } else { while(p->next) { p=p->next; } } while(p!=head->next) { if(p->val>=10) { p->val=p->val-10; p->prior->val++; } else if(p->val<0) { p->val=p->val+10; p->prior->val--; } p=p->prior; } if(p->val>=10) { p->val=p->val-10; temp=new ListNode; temp->val=1; temp->next=p; p->prior=temp; temp->prior=head; head->next=temp; } else if(p->val<0) { p->val=p->val+10; temp=new ListNode; temp->val=1; temp->next=p; p->prior=temp; temp->prior=head; head->next=temp; } return head; } void displayx_y(ListNode *head,int len) { struct ListNode *p=head->next; int leave; if(head->val==-1) { leave=(len-1)%4; cout<<"-"; } else leave=len%4; if(leave!=0) { while(leave) { cout<<p->val; p=p->next; leave--; } if(p!=head) cout<<","; } leave=1; while(p!=head) { cout<<p->val; if(leave!=4) leave++; else { leave=1; if(p->next!=head) cout<<","; } p=p->next; } cout<<endl; } void displayc(ListNode *head) { struct ListNode *p=head->next; int len=1,leave; while(p->next) { p=p->next; len++; } //第一种输出格式 leave=len%4; p=head->next; if(leave!=0) { while(leave) { cout<<p->val; p=p->next; leave--; } if(p!=NULL) cout<<"->"; } leave=1; while(p) { cout<<p->val; if(leave!=4) leave++; else { leave=1; if(p->next) cout<<"->"; } p=p->next; } cout<<endl; //第二种输出格式 leave=len%4; p=head->next; if(head->val==-1) cout<<"-"; if(leave!=0) { while(leave) { cout<<p->val; p=p->next; leave--; } if(p!=NULL) cout<<","; } leave=1; while(p) { cout<<p->val; if(leave!=4) leave++; else { leave=1; if(p->next) cout<<","; } p=p->next; } cout<<endl; } int main() { struct ListNode *headx,*heady,*headc,*p; string x,y; cin>>x>>y; //创建两个链表 headx=createByTail(x); heady=createByTail(y); headc=actionAdd(headx,heady); //执行求和运算先求出结果链表 displayx_y(headx,x.length()); displayx_y(heady,y.length()); cout<<endl; //要判断结果链表c的结果是否为0 p=headc->next; int flag=0; while(p) { if(p->val!=0) { flag=1; break; } else p=p->next; } if(flag==0) { cout<<0<<endl<<0<<endl; } else displayc(headc); return 0; }