用链表实现大数相加减

高级语言程序设计作业报告作业名称: 大整数相加减 学 院 计算机科学与工程学院 专 业 计算机软件 学生姓名 awell 任课教师 xxx 提交日期 2012.6.28 1、 问题描述 实现两个大整数的相加减二、系统设计 1、结构说明建立结构类型 node：struct nodeint num;/每个位数用一个int类型表示，其中num=0&numarr2.size()-falg2)/falg1表示输入的第一个整数前面的符号；falg=true;if(arr2.size()-falg2=arr1.size()-falg1)for(int i=0;iarr2i+falg2) falg=true;break;if(i=arr1.size()-falg1-1) falg=false;if(falg)for(int i=arr1.size()-1;i=falg1;i-)node *s;s=new node;s-num=arr1i-0;/从输入的整数尾部逆向建立链表if(fir=NULL) fir=s;else efir-next=s;efir=s;efir-next=NULL;/尾结点的next一定要赋NULL,不然会出现错误for(int i=arr2.size()-1;i=falg2;i-)node *s;s=new node;s-num=arr2i-0;if(sec=NULL) sec=s;else esec-next=s;esec=s;esec-next=NULL;elsefor(int i=arr2.size()-1;i=falg2;i-)node *s;s=new node;s-num=arr2i-0;if(fir=NULL) fir=s;else efir-next=s;efir=s;efir-next=NULL;for(int i=arr1.size()-1;i=falg1;i-)node *s;s=new node;s-num=arr1i-0;if(sec=NULL) sec=s;else esec-next=s;esec=s;esec-next=NULL;if(opration=+) return;if(!falg) f=!f;/f表示整个运算结果的正负void add()/实现加法bool falg=false;/标记是否进位int num2=sec-num;for(node *head1=fir,*head2=sec;head1;head1=head1-next)/因为以fir为表头建立的链表所保存的整数较大，所以，以sec为表头建立的链表会先或者同时遍历到表位int num1=head1-num;head1-num=(falg+num1+num2)%10;falg=(falg+num1+num2)/10;if(head2-next) /判断以sec为表头的链表是否达到表尾head2=head2-next;num2=head2-num;else num2=0;if(f) cout-;if(falg) coutnext)ansi=head1-num+0;i+;for(i-;i=0;i-)coutnum;bool falg=false;/判是否退位for(node *head1=fir,*head2=sec;head1;head1=head1-next)int num1=head1-num;head1-num=num1-num2-falg;if(num1-falg-num2num=head1-num+10;else falg=false;if(head2-next)head2=head2-next;num2=head2-num;else num2=0;int i=0;char *ans=new charsizeof(arr1)+sizeof(arr2);for(node *head1=fir;head1;head1=head1-next)ansi=head1-num+0;i+;i-;falg=false;for(int j=0;j=i;j+)if(ansj!=0) break;if(j=i)falg=true;cout0;return;if(f) cout=0;i-)coutnext;delete tem;for(;sec;)tem=sec;开始sec=sec-next;delete tem;tem=fir=efir=sec=esec=NULL;输入式子判操作程序流程图实现加法实现减法输出结果结束三、程序测试 1、设计测试用例0 + 01 + 110 + 11 + 101000000000000000000000 + 1111111111111111111111111111111111-1 + 11 + -1-10 + 100100 + -10-1000000 + -1000000000000000000000000000000000000000000010 - 101 - 1010 - 11 - 77 - 155555555555555555555555555555555555555555 - 555555555555555555555555555555555-10 - -10-11 - -1-1 - -15515-1 - -8-8 - -1-6666666666666666666666666666666666 - -6666666666666666666666666 2、程序测试结果0 + 0 = 01 + 1 = 210 + 1 = 111 + 10 = 111000000000000000000000 + 1111111111111111111111111111111111 = 1111111111112111111111111111111111 -1 + 1 = 01 + -1 = 0-10 + 100 = 90100 + -10 = 90-1000000 + -10000000000000000000000000000000000000000000 = -1000000000000000000000000000000000000100000010 - 10 = 01 - 10 = -910 - 1 = 91 - 7 = -67 - 1 = 655555555555555555555555555555555555555555 - 555555555555555555555555555555555 = 55555555000000000000000000000000000000000-10 - -10 = 0-11 - -1 = -10-1 - -15515 = 15514-1 - -8 = 7-8 - -1 = -7-6666666666666666666666666666666666 - -6666666666666666666666666 = -6666666660000000000000000000000000四、使用说明 能正确实现两个大整数（包括正负）相加减的运算5、 收获体会及建议完整代码：#include #include #include #include using namespace std;struct nodeint num;node * next;bool f,falg1,falg2;string arr1,arr2;char opration;node *fir=NULL,*efir=NULL,*sec=NULL,*esec=NULL;void creatlist()bool falg=false;if(arr1.size()-falg1arr2.size()-falg2)falg=true;if(arr2.size()-falg2=arr1.size()-falg1)for(int i=0;iarr2i+falg2) falg=true;break;if(i=arr1.size()-falg1-1) falg=false;if(falg)for(int i=arr1.size()-1;i=falg1;i-)node *s;s=new node;s-num=arr1i-0;if(fir=NULL) fir=s;else efir-next=s;efir=s;efir-next=NULL;for(int i=arr2.size()-1;i=falg2;i-)node *s;s=new node;s-num=arr2i-0;if(sec=NULL) sec=s;else esec-next=s;esec=s;esec-next=NULL;elsefor(int i=arr2.size()-1;i=falg2;i-)node *s;s=new node;s-num=arr2i-0;if(fir=NULL) fir=s;else efir-next=s;efir=s;efir-next=NULL;for(int i=arr1.size()-1;i=falg1;i-)node *s;s=new node;s-num=arr1i-0;if(sec=NULL) sec=s;else esec-next=s;esec=s;esec-next=NULL;if(opration=+) return;if(!falg) f=!f;void add()bool falg=false;int num2=sec-num;for(node *head1=fir,*head2=sec;head1;head1=head1-next)int num1=head1-num;head1-num=(falg+num1+num2)%10;falg=(falg+num1+num2)/10;if(head2-next) head2=head2-next;num2=head2-num;else num2=0;if(f) cout-;if(falg) coutnext)ansi=head1-num+0;i+;for(i-;i=0;i-)coutnum;bool falg=false;for(node *head1=fir,*head2=sec;head1;head1=head1-next)int num1=head1-num;head1-num=num1-num2-falg;if(num1-falg-num2num=head1-num+10;else falg=false;if(head2-next)head2=head2-next;num2=head2-num;else num2=0;int i=0;char *ans=new charsizeof(arr1)+sizeof(arr2);for(node *head1=fir;head1;head1=head1-next)ansi=head1-num+0;i+;i-;falg=false;for(int j=0;j=i;j+)if(ansj!=0) break;if(j=i)falg=true;cout0;return;if(f) cout=0;i-)coutnext;delete tem;for(;sec;)tem=sec;sec=sec-next;delete tem;tem=fir=efir=sec=esec=NULL;int main() cout输入算式，形如：endl;couta + b or a - barr1oprationarr2)char tem=opration;f=false,falg1=false,falg2=false;if(arr10=-) falg1=true;if(arr20=-) falg2=true;if(opration=-&falg2)opration=