用链表实现大数相加减.docx
《用链表实现大数相加减.docx》由会员分享，可在线阅读，更多相关《用链表实现大数相加减.docx（14页珍藏版）》请在冰点文库上搜索。
用链表实现大数相加减
《高级语言程序设计》作业报告
作业名称:
大整数相加减
学院计算机科学与工程学院
专业计算机软件
学生姓名awell
任课教师xxx
提交日期
一、问题描述
实现两个大整数的相加减
二、系统设计
1、结构说明
建立结构类型node：
structnode{
intnum;//每个位数用一个int类型表示，其中num>=0&&num<=9;
node*next;//建立单向链表，连接相邻的数字；
};
2、函数说明
建立链表（将输入的两个数中较大的保存在fir表头的链表中）：
voidcreatlist（）{
boolfalg=false;//标记输入的两个整数是否需要进行互换；
if（）-falg1>（）-falg2）//falg1表示输入的第一个整数前面的符号；
falg=true;
if（）-falg2==（）-falg1）{
for（inti=0;i<（）-falg2;i++）{
if（opration=='+'）{//如果是实现加法，不用管建链表时的整数互换
falg=true;
break;
}
if（arr1[i+falg1]>arr2[i+falg2]）{
falg=true;
break;
}
if（i==（）-falg1-1）falg=false;
}
}
if（falg）
{
for（inti=（）-1;i>=falg1;i--）{
node*s;
s=newnode;
s->num=arr1[i]-'0';//从输入的整数尾部逆向建立链表
if（fir==NULL）fir=s;
elseefir->next=s;
efir=s;
}
efir->next=NULL;//尾结点的next一定要赋NULL,不然会出现错误
for（inti=（）-1;i>=falg2;i--）{
node*s;
s=newnode;
s->num=arr2[i]-'0';
if（sec==NULL）sec=s;
elseesec->next=s;
esec=s;
}
esec->next=NULL;
}
else{
for（inti=（）-1;i>=falg2;i--）{
node*s;
s=newnode;
s->num=arr2[i]-'0';
if（fir==NULL）fir=s;
elseefir->next=s;
efir=s;
}
efir->next=NULL;
for（inti=（）-1;i>=falg1;i--）{
node*s;
s=newnode;
s->num=arr1[i]-'0';
if（sec==NULL）sec=s;
elseesec->next=s;
esec=s;
}
esec->next=NULL;
}
if（opration=='+'）return;
if（!
falg）f=!
f;//f表示整个运算结果的正负
}
voidadd（）{//实现加法
boolfalg=false;//标记是否进位
intnum2=sec->num;
for（node*head1=fir,*head2=sec;head1;head1=head1->next）{//因为以fir为表头建立的链表所保存的整数较大，所以，以sec为表头建立的链表会先或者同时遍历到表位
intnum1=head1->num;
head1->num=（falg+num1+num2）%10;
falg=（falg+num1+num2）/10;
if（head2->next）{//判断以sec为表头的链表是否达到表尾
head2=head2->next;
num2=head2->num;
}
elsenum2=0;
}
if（f）cout<<"-";
if（falg）cout<<1;
inti=0;
char*ans=newchar[sizeof（arr1）+sizeof（arr2）];
for（node*head1=fir;head1;head1=head1->next）{
ans[i]=head1->num+'0';
i++;
}
for（i--;i>=0;i--）
cout<}
voidsub（）{//实现两整数相减
intnum2=sec->num;
boolfalg=false;//判是否退位
for（node*head1=fir,*head2=sec;head1;head1=head1->next）{
intnum1=head1->num;
head1->num=num1-num2-falg;
if（num1-falg-num2<0）{
falg=true;
head1->num=head1->num+10;
}
elsefalg=false;
if（head2->next）{
head2=head2->next;
num2=head2->num;
}
elsenum2=0;
}
inti=0;
char*ans=newchar[sizeof（arr1）+sizeof（arr2）];
for（node*head1=fir;head1;head1=head1->next）{
ans[i]=head1->num+'0';
i++;
}
i--;
falg=false;
for（intj=0;j<=i;j++）{
if（ans[j]!
='0'）break;
if（j==i）{
falg=true;
cout<<0;
return;
}
}
if（f）cout<<"-";
if（ans[i]=='0'）i--;
for（;i>=0;i--）
cout<}
voiddele（）{//回收内存
node*tem;
for（;fir;）{
tem=fir;
fir=fir->next;
deletetem;
}
for（;sec;）{
tem=sec;
sec=sec->next;
deletetem;
}
tem=fir=efir=sec=esec=NULL;
}
程序流程图
三、程序测试
1、设计测试用例
0+0
1+1
10+1
1+10
000000000+
-1+1
1+-1
-10+100
100+-10
-1000000+-0000000000000000000000000000000
10-10
1-10
10-1
1-7
7-1
5-5
-10--10
-11--1
-1--15515
-1--8
-8--1
-66--6
2、程序测试结果
0+0=0
1+1=2
10+1=11
1+10=11
000000000+=
-1+1=0
1+-1=0
-10+100=90
100+-10=90
-1000000+-0000000000000000000000000000000=-0000000000000000000000001000000
10-10=0
1-10=-9
10-1=9
1-7=-6
7-1=6
5-5=
000000000000000000000000000000000
-10--10=0
-11--1=-10
-1--15515=15514
-1--8=7
-8--1=-7
-66--6=-000000000000000000
四、使用说明
能正确实现两个大整数（包括正负）相加减的运算
五、收获体会及建议
完整代码：
#include
#include
#include
#include
usingnamespacestd;
structnode{
intnum;
node*next;
};
boolf,falg1,falg2;
stringarr1,arr2;
charopration;
node*fir=NULL,*efir=NULL,*sec=NULL,*esec=NULL;
voidcreatlist（）{
boolfalg=false;
if（）-falg1>（）-falg2）
falg=true;
if（）-falg2==（）-falg1）{
for（inti=0;i<（）-falg2;i++）{
if（opration=='+'）{
falg=true;
break;
}
if（arr1[i+falg1]>arr2[i+falg2]）{
falg=true;
break;
}
if（i==（）-falg1-1）falg=false;
}
}
if（falg）
{
for（inti=（）-1;i>=falg1;i--）{
node*s;
s=newnode;
s->num=arr1[i]-'0';
if（fir==NULL）fir=s;
elseefir->next=s;
efir=s;
}
efir->next=NULL;
for（inti=（）-1;i>=falg2;i--）{
node*s;
s=newnode;
s->num=arr2[i]-'0';
if（sec==NULL）sec=s;
elseesec->next=s;
esec=s;
}
esec->next=NULL;
}
else{
for（inti=（）-1;i>=falg2;i--）{
node*s;
s=newnode;
s->num=arr2[i]-'0';
if（fir==NULL）fir=s;
elseefir->next=s;
efir=s;
}
efir->next=NULL;
for（inti=（）-1;i>=falg1;i--）{
node*s;
s=newnode;
s->num=arr1[i]-'0';
if（sec==NULL）sec=s;
elseesec->next=s;
esec=s;
}
esec->next=NULL;
}
if（opration=='+'）return;
if（!
falg）f=!
f;
}
voidadd（）{
boolfalg=false;
intnum2=sec->num;
for（node*head1=fir,*head2=sec;head1;head1=head1->next）{
intnum1=head1->num;
head1->num=（falg+num1+num2）%10;
falg=（falg+num1+num2）/10;
if（head2->next）{
head2=head2->next;
num2=head2->num;
}
elsenum2=0;
}
if（f）cout<<"-";
if（falg）cout<<1;
inti=0;
char*ans=newchar[sizeof（arr1）+sizeof（arr2）];
for（node*head1=fir;head1;head1=head1->next）{
ans[i]=head1->num+'0';
i++;
}
for（i--;i>=0;i--）
cout<}
voidsub（）{
intnum2=sec->num;
boolfalg=false;
for（node*head1=fir,*head2=sec;head1;head1=head1->next）{
intnum1=head1->num;
head1->num=num1-num2-falg;
if（num1-falg-num2<0）{
falg=true;
head1->num=head1->num+10;
}
elsefalg=false;
if（head2->next）{
head2=head2->next;
num2=head2->num;
}
elsenum2=0;
}
inti=0;
char*ans=newchar[sizeof（arr1）+sizeof（arr2）];
for（node*head1=fir;head1;head1=head1->next）{
ans[i]=head1->num+'0';
i++;
}
i--;
falg=false;
for（intj=0;j<=i;j++）{
if（ans[j]!
='0'）break;
if（j==i）{
falg=true;
cout<<0;
return;
}
}
if（f）cout<<"-";
if（ans[i]=='0'）i--;
for（;i>=0;i--）
cout<}
voiddele（）{//回收内存
node*tem;
for（;fir;）{
tem=fir;
fir=fir->next;
deletetem;
}
for（;sec;）{
tem=sec;
sec=sec->next;
deletetem;
}
tem=fir=efir=sec=esec=NULL;
}
intmain（）{
cout<<"输入算式，形如：
"<cout<<"a+bora-b"<while（cin>>arr1>>opration>>arr2）{
chartem=opration;
f=false,falg1=false,falg2=false;
if（arr1[0]=='-'）falg1=true;
if（arr2[0]=='-'）falg2=true;
if（opration=='-'&&falg2）{
opration='+';
if（falg1）{
f=true;
opration='-';
}
}
if（falg1）
if（!
（opration=='-'&&falg2））{
f=true;
if（opration=='+'&&!
falg2）opration='-';
elseopration='+';
}
if（!
falg1&&opration=='+'&&falg2）{
opration='-';
}
if（!
falg1&&tem=='-'&&falg2）opration='+';
creatlist（）;
if（opration=='+'）
add（）;
elsesub（）;
dele（）;
cout<}
return0;
}
升级会员 