9 长整数加法运算
问题描述 :
假设2个任意长度的整数x、y分别由双向链表A和B存储，现要求设计一个算法，实现x+y。计算结果存储在链表C中。
说明：
由于A和B输出时需要从头至尾遍历，而做加法时需要从尾至头遍历，因此使用双向链表存储。 可以从长整数的低位开始拆分（4位为一组，即不超过9999的非负整数），依次存放在链表的每个结点的数据域中；头结点的数据域存放正负数标志（正数或0：1，负数：-1）。
输入说明 :
第一行：长整数x 第二行：长整数y
输出说明 :
第一行：格式化后的长整数x（从低位到高位每4位用",“分开） 第二行：格式化后的长整数y（从低位到高位每4位用”,“分开） 第三行：空行 第四行：单链表C的遍历结果 第五行：格式化后的计算结果（从低位到高位每4位用”,"分开） （输入与输出之间用一空行分隔）
这题写麻烦了，感觉下次还是要分几个程序写看着清楚一点。 思路：可以将负号乘给每一个元素，用head3链表来接收新的结果，再对head3->next->value结果进行判断，如果是负数，那整体都乘以-1，如果是正数，就直接从最后一位进行进位处理。 注意点：有一个例子比较特殊：当两个数字加起来是0的时候，要分类讨论。
#include <iostream> #include <vector> using namespace std; struct Listnode{ Listnode *prior; Listnode *next; int value; }; Listnode* createlist(vector<char>v){ Listnode *head = new Listnode;//头节点 Listnode *cur = new Listnode; cur = head; head->value = 1; int len = v.size(); for(int i = 0 ; i < len ; i++){ if(i == 0 && v[i] == '-'){ head->value = -1; continue; } Listnode *temp = new Listnode; temp->value = v[i]-'0'; cur->next = temp; temp->prior = cur; cur = cur->next; temp->next = NULL; } return head; } int countnum(Listnode* head){ Listnode *cur = new Listnode; cur = head; int sum; if(head->next && head->next->value >= 10){ head->next->value = head->next->value - 10; Listnode *p = new Listnode; p->value = 1; p->next = head->next; p->prior = head; p->next->prior = p; head->next = p; } else{ sum = 0; } while(cur->next != NULL){ sum++; cur = cur->next; } return sum; } void printlist1(Listnode* head){ Listnode *fin = new Listnode; fin = head; int key = 0; while(fin->next && fin->next->value == 0){ fin = fin->next; key = 1; } if(key == 1){ head = fin->prior; } int test = 0; int c = countnum(head); int cc = c%4; Listnode *q = head->next; while(cc){ if(q->value < 0){ cout<<(-1) * q->value; }else{ cout<<q->value; } q = q->next; cc--; } if(c%4 != 0 && c>=4){ cout<<"->"; } while(q != NULL){ if(q == NULL){ cout<<endl; break; } if(test == 4){ test = 0; cout<<"->"; } test++; cout<<q->value; q = q->next; } cout<<endl; } void printlist2(Listnode* head,int flag){ if(flag == 1){ cout<<'-'; } Listnode *fin = new Listnode; fin = head; int key = 0; while(fin->next && fin->next->value == 0){ fin = fin->next; key = 1; } if(key == 1){ head = fin->prior; } int test = 0; int c = countnum(head); int cc = c%4; Listnode *q = head->next; while(cc){ cout<<q->value; q = q->next; cc--; } if(c%4 != 0 && c>=4){ cout<<","; } while(q != NULL){ if(q == NULL){ cout<<endl; break; } if(test == 4){ test = 0; cout<<","; } test++; cout<<q->value; q = q->next; } } int main(){ string s1; string s2; cin>>s1>>s2; int len1 = s1.size(); int len2 = s2.size(); vector <char> v1; vector <char> v2; for(int i = 0;i < len1 ; i++){ v1.push_back(s1[i]); } for(int i = 0;i < len2 ; i++){ v2.push_back(s2[i]); } Listnode *head1 = createlist(v1); Listnode *head2 = createlist(v2); int temp1 = len1; int temp2 = len2; if(s1[0] == '-'){ temp1--; } if(s2[0] == '-'){ temp2--; } while(temp1 >= 4){ temp1 = temp1 - 4; } while(temp2 >= 4){ temp2 = temp2 - 4; } if(head1->value == -1){ cout<<'-'; } Listnode *cur1 = head1->next; Listnode *cur2 = head2->next; for(int i = 0;i < temp1; i++){ cout<<cur1->value; cur1 = cur1->next; } if(temp1 != 0 && len1 >= 4){ cout<<','; } int sum = 0; while(cur1 !=NULL){ if(sum == 4){ cout<<','; sum = 0; } sum++; cout<<cur1->value; cur1 = cur1->next; } cout<<endl; if(head2->value == -1){ cout<<'-'; } for(int i = 0;i < temp2; i++){ cout<<cur2->value; cur2 = cur2->next; } if(temp2 != 0 && len2 >= 4){ cout<<','; } sum = 0; while(cur2){ if(sum == 4){ cout<<','; sum = 0; } sum++; cout<<cur2->value; cur2 = cur2->next; } cout<<endl<<endl; Listnode *end1 = new Listnode; Listnode *end2 = new Listnode; end1 = head1; end2 = head2; while(end1->next != NULL){ end1 = end1->next; }//end1指向尾部 while(end2->next != NULL){ end2 = end2->next; }//end2指向尾部 Listnode *head3 = new Listnode; head3->next = NULL; if(s1[0] == '-'){ Listnode *ss = new Listnode; ss = head1; while(ss->next){ ss = ss->next; ss->value = (-1) * ss->value; } } if(s2[0] == '-'){ Listnode *ss = new Listnode; ss = head2; while(ss->next){ ss = ss->next; ss->value = (-1) * ss->value; } } while(end1 != head1 && end2 != head2){ int cc = end1->value + end2->value; Listnode *c = new Listnode; c->value = cc; c->next = head3->next; c->prior = head3; if(c->next){ c->next->prior = c; } head3->next = c; end1 = end1->prior; end2 = end2->prior; } while(end1 != head1){ int cc = end1->value; Listnode *c = new Listnode; c->value = cc; c->next = head3->next; c->prior = head3; if(c->next){ c->next->prior = c; } head3->next = c; end1 = end1->prior; } while(end2 != head2){ int cc = end2->value; Listnode *c = new Listnode; c->value = cc; c->next = head3->next; c->prior = head3; if(c->next){ c->next->prior = c; } head3->next = c; end2 = end2->prior; } Listnode *last = new Listnode; last = head3; int flag = 0; if(head3->next->value < 0){ while(last->next){ last = last->next; last->value = (-1) * last->value; flag = 1; } } else{ while(last->next){ last = last->next; } } while(last != head3->next){ if(last->value >= 10){ last->value = last->value - 10; last->prior->value++; } if(last->value <0){ last->value = last->value + 10; last->prior->value--; } last = last->prior; } printlist1(head3); printlist2(head3,flag); }