用鏈表實現(xiàn)大數(shù)相加減

1、高級語言程序設計作業(yè)報告作業(yè)名稱: 大整數(shù)相加減 學 院 計算機科學與工程學院 專 業(yè) 計算機軟件 學生姓名 awell 任課教師 xxx 提交日期 1、 問題描述 實現(xiàn)兩個大整數(shù)的相加減二、系統(tǒng)設計 1、結構說明建立結構類型 node：struct nodeint num;/每個位數(shù)用一個int類型表示，其中num>=0&&num<=9;node * next;/建立單向鏈表，連接相鄰的數(shù)字；; 2、函數(shù)說明建立鏈表（將輸入的兩個數(shù)中較大的保存在fir表頭的鏈表中）：void creatlist()bool falg=false;/標記輸入的兩個整數(shù)是否需要進行互

2、換；if(arr1.size()-falg1>arr2.size()-falg2)/falg1表示輸入的第一個整數(shù)前面的符號；falg=true;if(arr2.size()-falg2=arr1.size()-falg1)for(int i=0;i<arr2.size()-falg2;i+)if(opration='+') /如果是實現(xiàn)加法，不用管建鏈表時的整數(shù)互換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'/從輸入的整數(shù)尾部逆向建立鏈表if(fir=NULL) fir=s;else efir->next=s;efir=s;efir->next=NULL;/尾結點的next一定要賦NULL,不然會出現(xiàn)錯誤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()/實現(xiàn)加法bool falg=false;/標記是否進位int num2=sec->num;for(node *head1=fir,*head2=sec;head1;head1=head1->next)/因為以fir為表頭建立的鏈表所保存的整數(shù)較大，所以，以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()/實現(xiàn)兩整數(shù)相減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()/回收內(nèi)存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;輸入式子判操作程序流程圖實現(xiàn)加法實現(xiàn)減法輸出結果結束三、程序測試 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四、使用說明 能正確實現(xiàn)兩個大整數(shù)（包括正負）相加減的運算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()/回收內(nèi)存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