用链表实现大数相加减.docx
- 文档编号:6774946
- 上传时间:2023-05-10
- 格式:DOCX
- 页数:14
- 大小:42.36KB
用链表实现大数相加减.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; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 用链表 实现 大数 相加