數(shù)據(jù)結(jié)構(gòu)長整數(shù)四則運(yùn)算

1、實(shí)習(xí)1 1.4長整數(shù)四則運(yùn)算實(shí)習(xí)報(bào)告題目：設(shè)計(jì)一個實(shí)現(xiàn)任意長的整數(shù)進(jìn)行加法運(yùn)算的演示程序。一、 需求分析1.本演示程序中，利用雙向循環(huán)鏈表實(shí)現(xiàn)長整數(shù)的存儲，每個結(jié)點(diǎn)含一個整型變量任何整型變量的范圍是-（215-1）（215-1）。在每個結(jié)點(diǎn)中僅存十進(jìn)制數(shù)的4位，即不超過9999的非負(fù)整數(shù)，整個鏈表表示為萬進(jìn)制數(shù)。輸入和輸出形式按中國對于長整數(shù)的習(xí)慣，每四位一組，組間用逗號隔開。 2.演示程序以用戶和計(jì)算機(jī)的對話方式執(zhí)行，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令；相應(yīng)的輸入數(shù)據(jù)（濾去輸入數(shù)據(jù)中的非法字符）和運(yùn)算結(jié)果顯示在其后。3.程序執(zhí)行的命令包括：（1）

2、構(gòu)造鏈表；（2）輸入數(shù)據(jù)；（3）數(shù)據(jù)處理；（4）結(jié)束4. 測試數(shù)據(jù)（1）0；0；應(yīng)輸出0。（2）-2345,6789；-7654,3211；應(yīng)輸出-1,0000,0000.（3）-9999,9999；1,0000,0000,0000；應(yīng)輸出9999,0000,0001（4）1,0001,0001；-1,0001,0001；應(yīng)輸出0。（5）1,0001,0001；-1,0001,0000；應(yīng)輸出1.（6）-9999,9999,9999；-9999,9999,9999；應(yīng)輸出-1,9999,9999,9998。（7）1,0000,9999,9999；1；應(yīng)輸出1,0001,0000,0000。二、

3、 概要設(shè)計(jì)struct LinkNode /定義結(jié)構(gòu)體LinkNodeint data; /記錄每個節(jié)點(diǎn)的整數(shù)（小于10000）LinkNode *next; /記錄下一個節(jié)點(diǎn)的地址LinkNode *pre; /記錄前一個節(jié)點(diǎn)的地址;class LinkList /定義類LinkListprivate:LinkNode *head0,*head1; /head0，head1分別記錄兩個整數(shù)鏈表的頭指針LinkNode *currptr;LinkNode *result; /result記錄結(jié)果鏈表的頭指針public:LinkList(); /構(gòu)造函數(shù)，初始化鏈表LinkList(); /析

4、構(gòu)函數(shù)，釋放空間void Creat(string a); /引入字符串，創(chuàng)立兩個鏈表，分別表示兩個整數(shù)void Add(); /實(shí)現(xiàn)兩個整數(shù)相加void Display(); /顯示結(jié)果void addtwo(); /節(jié)點(diǎn)多的作為被加數(shù)，少的作為加數(shù)，實(shí)現(xiàn)整 /數(shù)絕對值大的加小的;void main() /主函數(shù)do while(Yes_No='y'|Yes_No='Y'); /Yes_No不等于'Y'或'y'時(shí)，程序退出三、詳細(xì)設(shè)計(jì)#include<iostream>#include<string>#i

5、nclude<math.h>using namespace std;struct LinkNodeint data; /記錄每個節(jié)點(diǎn)的整數(shù)（小于10000）LinkNode *next; /記錄下一個節(jié)點(diǎn)的地址LinkNode *pre; /記錄前一個節(jié)點(diǎn)的地址;class LinkListprivate:LinkNode *head0,*head1; /head0，head1分別記錄兩個整數(shù)鏈表的頭指針LinkNode *currptr;LinkNode *result; /result記錄結(jié)果鏈表的頭指針public:LinkList(); /構(gòu)造函數(shù)，初始化鏈表LinkLis

6、t(); /析構(gòu)函數(shù)，釋放空間void Creat(string a); /引入字符串，創(chuàng)立兩個鏈表，分別表示兩個整數(shù)void Add(); /實(shí)現(xiàn)兩個整數(shù)相加void Display(); /顯示結(jié)果void addtwo(); /節(jié)點(diǎn)多的作為被加數(shù)，少的作為加數(shù)，實(shí)現(xiàn)整 /數(shù)絕對值大的加小的;/鏈表的實(shí)現(xiàn)部分int sum(int n);LinkList:LinkList() /構(gòu)造函數(shù)，初始化鏈表head0=new LinkNode; /申請一個空間記錄整數(shù)的符號和節(jié)點(diǎn)數(shù)head1=new LinkNode;head0->next=head0;head0->pre=head0

7、; /初始化鏈表，建立雙向循環(huán)鏈表head1->next=head1;head1->pre=head1; result=new LinkNode;result->next=result;result->pre=result;currptr=NULL;LinkList:LinkList() /析構(gòu)函數(shù)，釋放空間LinkNode *p1=head0,*p2=head1,*p3=result; /三個指針分別指向三條鏈表的頭指針while(p1!=p1->pre) p1->pre->next=p1->next; p1->next->pre=

8、p1->pre; currptr=p1; p1=p1->next; delete currptr;while(p2!=p2->pre) /逐個刪除節(jié)點(diǎn)，釋放空間 p2->pre->next=p2->next; p2->next->pre=p2->pre; currptr=p2; p2=p2->next; delete currptr;while(p3!=p3->pre) p3->pre->next=p3->next; p3->next->pre=p3->pre; currptr=p3; p3=

9、p3->next; delete currptr;/ delete p1;/ delete p2;/ delete p3;void LinkList:Creat(string a) /引入字符串，創(chuàng)立兩/個鏈表，分別表示兩個整數(shù)int i=0,j=0,m=0,n=0,k=0,l=0,s=0,w=0; /i記錄字符串，j記錄加數(shù)節(jié)點(diǎn)數(shù)；s記錄被加數(shù)節(jié)點(diǎn)數(shù)/w標(biāo)記字符串中的-號/k記錄字符串中的字符轉(zhuǎn)化為整數(shù)的值，l使每個節(jié)點(diǎn)記錄4位while(am!='') m+; /m記錄字符串中被加數(shù)的字符數(shù) n=m; while(an!='0') n+; /n記錄字符

10、串的總字符數(shù)if(a0='-') head0->data=(-1); /記錄整數(shù)符號 w=1;else head0->data=1;for(i=m-1;i>=w;i-) if(ai!=',') /把字符轉(zhuǎn)化為整數(shù) k+=(ai-'0')*sum(l); l+; if(ai=','|i=w) currptr=new LinkNode; /把整數(shù)存到雙向循環(huán)鏈表中 currptr->data=k; currptr->next=head0; currptr->pre=head0->pre; he

11、ad0->pre->next=currptr; head0->pre=currptr; head0=currptr; s+; /節(jié)點(diǎn)數(shù)加1 k=0; /重新初始化k和l l=0; head0->pre->data*=s; /存儲整數(shù)符號和節(jié)點(diǎn)數(shù)/與建第一個整數(shù)鏈表一樣，建立第二個整數(shù)鏈表head1k=0;l=0;if(am+1='-') head1->data=(-1); m+;else head1->data=1;for(i=n-1;i>m;i-) if(ai!=',') k+=(ai-'0')*

12、sum(l); l+; if(ai=','|i=m+1) currptr=new LinkNode; currptr->data=k; currptr->next=head1; currptr->pre=head1->pre; head1->pre->next=currptr; head1->pre=currptr; head1=currptr; j+; k=0; l=0; head1->pre->data*=j;void LinkList:Add() /實(shí)現(xiàn)兩個整數(shù)相加LinkNode *temp;if(abs(head0

13、->pre->data)>abs(head1->pre->data) /兩個整數(shù)中，絕對值大的為被加數(shù) addtwo();else if(abs(head0->pre->data)<abs(head1->pre->data) temp=head0; head0=head1; head1=temp; addtwo();else if(abs(head0->pre->data)=abs(head1->pre->data) int k1,k2; LinkNode *p=head0,*q=head1; /如果節(jié)點(diǎn)數(shù)相同

14、，則判斷節(jié)點(diǎn)中數(shù)值大小while(p->data=q->data&&p!=head0->pre->pre&&q!=head1->pre->pre) p=p->next; q=q->next; k1=p->data; k2=q->data; if(k1>k2) addtwo(); else temp=head0; head0=head1; head1=temp; addtwo(); void LinkList:addtwo() /節(jié)點(diǎn)多的作為被加數(shù)，少的作為加數(shù)，實(shí)現(xiàn)整數(shù)絕對值大的加小的/默認(rèn)hea

15、d0存的整數(shù)絕對值比head1大int s=0,m1=head0->data,m2=head1->data;m1=(head0->pre->data/abs(head0->pre->data); /head0的符號m2=(head1->pre->data/abs(head1->pre->data); /head1的符號LinkNode *p=head0->pre->pre,*q=head1->pre->pre;result->data=head0->pre->data; /存結(jié)果的節(jié)點(diǎn)數(shù)和符號

16、 while(q!=head1->pre) /head0存的整數(shù)絕對值比head1大，即head0的節(jié)點(diǎn)數(shù)大于或等于head1 currptr=new LinkNode; currptr->data=(p->data)*m1+(q->data)*m2+s; /兩整數(shù)相加 if(m1*m2)>0) /如果符號相同 if(abs(currptr->data)-10000>=0) /相加后超過10000，則進(jìn)位 s=currptr->data/10000; currptr->data=abs(currptr->data)%10000; el

17、se /abs(currptr->data)-10000<0，不進(jìn)位 s=0; currptr->data=abs(currptr->data); else if(m1>0&&m2<0) /符號不同，在此相當(dāng)于實(shí)現(xiàn)兩個正整數(shù)相減 s=0; if(currptr->data<0) /小于0，向前一位借1 currptr->data+=10000; s=-1; else if(m1<0&&m2>0) /符號不同，在此相當(dāng)于實(shí)現(xiàn)負(fù)整數(shù)加上正整數(shù) s=0; if(currptr->data>0

18、) /大于0， currptr->data=10000-currptr->data; s=1; else currptr->data=abs(currptr->data); currptr->next=result; /存入鏈表 currptr->pre=result->pre; result->pre->next=currptr; result->pre=currptr; result=currptr; p=p->pre; q=q->pre; /當(dāng)head0節(jié)點(diǎn)數(shù)比head1長時(shí)，繼續(xù)建鏈while(p!=head0-&

19、gt;pre) currptr=new LinkNode; currptr->data=p->data*m1+s; s=currptr->data/10000; if(m1*m2)>0) if(abs(currptr->data)-10000>=0) s=currptr->data/10000; currptr->data=abs(currptr->data)%10000; else s=0;currptr->data=abs(currptr->data); else if(m1>0&&m2<0) s

20、=0; if(currptr->data<0) currptr->data+=10000; s=-1; else if(m1<0&&m2>0) s=0; if(currptr->data>0) currptr->data=10000-currptr->data; s=1; else currptr->data=abs(currptr->data); currptr->data=abs(currptr->data)%10000; currptr->next=result; currptr->

21、pre=result->pre; result->pre->next=currptr; result->pre=currptr; result=currptr; p=p->pre;if(s!=0) /處理相加后，進(jìn)位問題 currptr=new LinkNode; currptr->data=abs(s); currptr->next=result; currptr->pre=result->pre; result->pre->next=currptr; result->pre=currptr; result=currpt

22、r; result->pre->data=m1*(abs(result->pre->data)+1);void LinkList:Display() /顯示結(jié)果LinkNode *p=result;int FuHao=result->pre->data/abs(result->pre->data);/結(jié)果的符號while(p->data=0&&p!=result->pre->pre) /當(dāng)運(yùn)算后前幾個節(jié)點(diǎn)的數(shù)據(jù)為0時(shí)，不輸出 p=p->next; result->pre->data=(abs(r

23、esult->pre->data)-1)*FuHao; /結(jié)果記錄非0節(jié)點(diǎn)數(shù)cout<<FuHao*p->data; /首先顯示符號和第一個節(jié)點(diǎn)中的數(shù)if(abs(result->pre->data)!=1) p=p->next; /判斷非0節(jié)點(diǎn)數(shù)是否為1while(p!=result->pre->pre) /繼續(xù)輸出 cout<<"," /每4位一組，并用，隔開 cout.width(4); cout.fill('0'); cout<<p->data; p=p->

24、;next;if(p=result->pre->pre&&abs(result->pre->data)!=1) /顯示最后一個節(jié)點(diǎn)數(shù)據(jù) cout<<"," cout.width(4); cout.fill('0'); cout<<p->data;cout<<endl;int sum(int n) /計(jì)算10的乘方int i,s=1;for(i=1;i<=n;i+) s=s*10;return s;/主函數(shù)和其他函數(shù)的實(shí)現(xiàn) void main() /主函數(shù)cout<<"*n"cout<<"*歡迎使用任意長整數(shù)加法系統(tǒng)*n"cout<<"*n""cout<<"n"cout<<"在此系統(tǒng)中，可以輸入任意長的整數(shù) 。 |n"string ch;char Yes_No;docout<<"n" cout<<"|輸入形式為：(-)*,*,*;(-)*,*,*,*|n&quo