用链表实现大数相加减

1、高级语言程序设计作业报告作业名称: 大整数相加减 学 院 计算机科学与工程学院 专 业 计算机软件 学生姓名 awell 任课教师 xxx 提交日期 1、 问题描述 实现两个大整数的相加减二、系统设计 1、结构说明建立结构类型 node：struct nodeint num;/每个位数用一个int类型表示，其中num>=0&&num<=9;node * next;/建立单向链表，连接相邻的数字；; 2、函数说明建立链表（将输入的两个数中较大的保存在fir表头的链表中）：void creatlist()bool falg=false;/标记输入的两个整数是否需要进行互

2、换；if(arr1.size()-falg1>arr2.size()-falg2)/falg1表示输入的第一个整数前面的符号；falg=true;if(arr2.size()-falg2=arr1.size()-falg1)for(int i=0;i<arr2.size()-falg2;i+)if(opration='+') /如果是实现加法，不用管建链表时的整数互换falg=true;break;if(arr1i+falg1>arr2i+falg2) falg=true;break;if(i=arr1.size()-falg1-1) falg=false;i

3、f(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=

4、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

5、) 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->

6、;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) cout<<1;int i=0;char *ans=new charsizeof(arr1)+sizeof(arr2);for(node *head1=fir;head1;head1=head1-&g

7、t;next)ansi=head1->num+'0'i+;for(i-;i>=0;i-)cout<<ansi;void sub()/实现两整数相减int num2=sec->num;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-num2<0)falg=true;head1->num=head1-&

8、gt;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)

9、falg=true;cout<<0;return;if(f) cout<<"-"if(ansi='0') i-;for(;i>=0;i-)cout<<ansi;void dele()/回收内存node *tem;for(;fir;)tem=fir;fir=fir->next;delete tem;for(;sec;)tem=sec;开始sec=sec->next;delete tem;tem=fir=efir=sec=esec=NULL;输入式子判操作程序流程图实现加法实现减法输出结果结束三、程序测试 1

10、、设计测试用例0 + 01 + 110 + 11 + 10-1 + 11 + -1-10 + 100100 + -1010 - 101 - 1010 - 11 - 77 - 155555555555555555555555555555555555555555 - 555555555555555555555555555555555-10 - -10-11 - -1-1 - -15515-1 - -8-8 - -1-6666666666666666666666666666666666 - -6666666666666666666666666 2、程序测试结果0 + 0 = 01 + 1 = 210

11、 + 1 = 111 + 10 = 11-1 + 1 = 01 + -1 = 0-10 + 100 = 90100 + -10 = 9010 - 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

12、- -1 = -7-6666666666666666666666666666666666 - -6666666666666666666666666 = -6666666660000000000000000000000000四、使用说明 能正确实现两个大整数（包括正负）相加减的运算5、 收获体会及建议完整代码：#include <cstdio>#include <string>#include <cstring>#include <iostream>using namespace std;struct nodeint num;node * next

13、;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()-falg1>arr2.size()-falg2)falg=true;if(arr2.size()-falg2=arr1.size()-falg1)for(int i=0;i<arr2.size()-falg2;i+)if(opration='+') falg=true;break;

14、if(arr1i+falg1>arr2i+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

15、;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=ne

16、w 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+

17、num2)%10;falg=(falg+num1+num2)/10;if(head2->next) head2=head2->next;num2=head2->num;else num2=0;if(f) cout<<"-"if(falg) cout<<1;int i=0;char *ans=new charsizeof(arr1)+sizeof(arr2);for(node *head1=fir;head1;head1=head1->next)ansi=head1->num+'0'i+;for(i-;i&

18、gt;=0;i-)cout<<ansi;void sub()int num2=sec->num;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-num2<0)falg=true;head1->num=head1->num+10;else falg=false;if(head2->next)head2=head2->nex

19、t;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;cout<<0;return;if(f) cout<<"-"if(ansi='0') i-;for(;i>=0;i-)cout<<ansi;void dele()/回收内存node *tem;for(;fir;)tem=fir;fir=fir->next;delete tem;for(;sec;)tem=sec;sec=sec->next;delete tem;tem=fir=efir=sec=esec=NULL;int main() cout<<"输入算式，形如："<<endl;cout<<"a + b o