长整数加法运算(链表）
问题描述 :
假设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
#include <iostream>
#include <string>
#include <string.h>
#include <math.h>
#include <stdlib.h>
using namespace std;
struct DualNode
{
int data; //数据
DualNode *prior,*next; //前一个，后一个指针
};
DualNode *createDlist(string x){
DualNode *head=new DualNode,*temp;
if(x[0]=='-'){
head->data=-1;
}else{
head->data=1;
}
head->next=NULL;
head->prior=NULL;
//
int i=x.length()-1;
int weishu=0;//位数
int s=0;//记录四位数
while(i!=-1){
if(x[i]=='-'){
break;
}
if(weishu!=3){
// (int)(0.1+pow((double)temp,2.0));
s=s+(x[i]-48)*(int)(0.1+pow(10.0,(double)weishu));
weishu++;
if(x[i-1]=='-' || i==0){
temp=new DualNode;
temp->data=s;
if(head->next!=NULL){
head->next->prior=temp;
}
temp->next=head->next;
head->next=temp;
temp->prior=head;
}
}else if(weishu==3){
//前插进去
s=s+(x[i]-48)*(int)(0.1+pow(10.0,(double)weishu));
temp=new DualNode;
temp->data=s;
if(head->next!=NULL){
head->next->prior=temp;
}
temp->next=head->next;
head->next=temp;
temp->prior=head;
weishu=0;
s=0;
}
i--;
}
return head;
}
void printDList(DualNode* L)
{
DualNode *p;
p = L;
p=p->next;
while(p!=NULL && p->data==0){
p=p->next;
}
if(p==NULL){
cout<<"0"<<endl;
return;
}
if(L->data==-1){
cout<<"-";
}
int sum=0;
while(p!=NULL){
sum++;
if(sum==1){
if(p->data==0){
cout<<"0";
}else{
cout<<p->data;
}
}else{
if(p->data==0){
cout<<","<<"0000";
}else if(p->data>0 && p->data<10){
cout<<","<<"000"<<p->data;
}else if(p->data>=10 && p->data<100){
cout<<","<<"00"<<p->data;
}else if(p->data>=100 && p->data<1000){
cout<<","<<"0"<<p->data;
}else{
cout<<","<<p->data;
}
}
p=p->next;
}
cout<<endl;
}
int getLength(DualNode *head)
{
DualNode *p=head->next;
int k=0;
while(p) //while(p!=NULL)可以写成while(p)
{
k++; //这里处理每一个结点时，只是进行累加
p=p->next;
}
return k;
}
void display(DualNode *L){
DualNode *p;
p = L;
p=p->next;
while(p!=NULL && p->data==0){
p=p->next;
}
if(p==NULL){
cout<<"0";
}
int sum=0;
while(p!=NULL){
sum++;
if(sum==1){
if(p->data==0){
cout<<"0";
}else{
cout<<p->data;
}
}else{
if(p->data==0){
cout<<"->"<<"0000";
}else if(p->data>0 && p->data<10){
cout<<"->"<<"000"<<p->data;
}else if(p->data>=10 && p->data<100){
cout<<"->"<<"00"<<p->data;
}else if(p->data>=100 && p->data<1000){
cout<<"->"<<"0"<<p->data;
}else{
cout<<"->"<<p->data;
}
}
p=p->next;
}
cout<<endl;
}
DualNode *add(DualNode *X, DualNode *Y){
DualNode *head=new DualNode;
head->next=NULL;
head->prior=NULL;
//++ or --
if((X->data==1 && Y->data==1) || (X->data==-1 && Y->data==-1) ){
if(X->data==1 && Y->data==1){
head->data=1;
}else{
head->data=-1;
}
DualNode *p,*q,*temp;
p=X->next; q=Y->next;
while(p->next!=NULL){
p=p->next;
}
while(q->next!=NULL){
q=q->next;
}
int sum=0;
int carry=0;
while(p!=X && q!=Y){
sum=p->data + q->data +carry;
carry=sum/10000;
sum=sum%10000;
temp=new DualNode;
temp->data=sum;
if(head->next!=NULL){
head->next->prior=temp;
}
temp->next = head->next;
head->next = temp;
temp->prior = head;
p=p->prior;
q=q->prior;
sum=0;
}
while(p!=X){
sum=p->data + 0 +carry;
carry=sum/10000;
sum=sum%10000;
temp=new DualNode;
temp->data=sum;
if(head->next!=NULL){
head->next->prior=temp;
}
temp->next = head->next;
head->next = temp;
temp->prior = head;
p=p->prior;
sum=0;
}
while(q!=Y){
sum=q->data + 0 +carry;
carry=sum/10000;
sum=sum%10000;
temp=new DualNode;
temp->data=sum;
if(head->next!=NULL){
head->next->prior=temp;
}
temp->next = head->next;
head->next = temp;
temp->prior = head;
q=q->prior;
sum=0;
}
if(carry==1){
temp=new DualNode;
temp->data=1;
if(head->next!=NULL){
head->next->prior=temp;
}
temp->next = head->next;
head->next = temp;
temp->prior = head;
}
return head;
}
//++ or -- ~
//+-
if((X->data==1 && Y->data==-1) || (X->data==-1 && Y->data==1)){
head->data=-1;
DualNode *max,*min,*temp;
if(getLength(X)>getLength(Y)){
max=X;
min=Y;
}else if(getLength(X)<getLength(Y)){
max=Y;
min=X;
}else{
DualNode *m,*n;
m=X->next; n=Y->next;
while(m->data==n->data && m->next!=NULL && n->next!=NULL){
m=m->next;
n=n->next;
}
if(m->data>n->data){
max=X;
min=Y;
}else{
max=Y;
min=X;
}
}
head->data=max->data;
DualNode *a,*b;
a=max->next;
b=min->next;
while(a->next!=NULL){
a=a->next;
}
while(b->next!=NULL){
b=b->next;
}
int sum=0;
while(a!=max && b!=min){
if(a->data<0){
a->data=a->data+10000;
a->prior->data=a->prior->data-1;
}
// cout<<a->data<<endl;
sum=a->data - b->data;
if(sum<0){
sum=a->data+10000-b->data;
a->prior->data=a->prior->data-1;
}
temp=new DualNode;
temp->data=sum;
if(head->next!=NULL){
head->next->prior=temp;
}
temp->next = head->next;
head->next = temp;
temp->prior = head;
a=a->prior;
b=b->prior;
sum=0;
}
while(a!=max){
if(a->data<0){
a->data=a->data+10000;
a->prior->data=a->prior->data-1;
}
sum=a->data;
temp=new DualNode;
temp->data=sum;
if(head->next!=NULL){
head->next->prior=temp;
}
temp->next = head->next;
head->next = temp;
temp->prior = head;
a=a->prior;
sum=0;
}
return head;
}
//+- ~
return head;
}
int main() {
string x,y;
cin>>x>>y;
// cin>>y;
DualNode *X,*Y;
X=createDlist(x);
Y=createDlist(y);
printDList(X);
printDList(Y);
cout<<endl;
DualNode *res;
res=add(X,Y);
display(res);
printDList(res);
return 0;
}
版权声明：本文为melocarter原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。