任意長(zhǎng)整數(shù)加法運(yùn)算-課程設(shè)計(jì)報(bào)告

1、一、【實(shí)驗(yàn)內(nèi)容】【問題描述】設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加法運(yùn)算的演示程序【基本要求】：利用雙向循環(huán)鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。任何整形變量的范圍是 -(215 - 1)(215 - 1) 。輸入和輸出形式：按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，組間用逗號(hào)隔開?！緶y(cè)試數(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,0

2、001 ；應(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 ”。二、實(shí)驗(yàn)?zāi)康?、熟悉掌握雙向循環(huán)鏈表的基本操作；、熟悉任意長(zhǎng)字符串的輸入，并實(shí)現(xiàn)把字符串轉(zhuǎn)化為整數(shù)；、熟悉任意長(zhǎng)整數(shù)的加法運(yùn)算；、更進(jìn)一步掌握有關(guān)類的操作三、實(shí)驗(yàn)文檔：任意長(zhǎng)整數(shù)加法運(yùn)算一、需求分析1、本程序?qū)崿F(xiàn)計(jì)算任意長(zhǎng)的整數(shù)的加法運(yùn)算 . 以用戶和計(jì)算機(jī)對(duì)話的方式，

3、即在計(jì)算機(jī)終端上顯示“提示信息”之后， 由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令，然后程序就計(jì)算并顯示出這兩個(gè)數(shù)的運(yùn)算。2、本演示程序中，集合的元素限定為數(shù)字字符 09 和字符，與；，輸入字符可以任意長(zhǎng)，輸入形式以“回車符”為結(jié)束標(biāo)志，串中字符順序不限，且允許出現(xiàn)重復(fù)字符。3、利用雙向循環(huán)鏈表現(xiàn)實(shí)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。輸入的形式以回車結(jié)束， 可以直接輸入正數(shù)或負(fù)數(shù)。 按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣， 每四位一組，除數(shù)字和位于首位置的負(fù)號(hào)外， 其它一切字符都將作為分隔符， 連續(xù)多個(gè)分隔符當(dāng)一個(gè)處理。但不使用分隔符也不影響結(jié)果。4、測(cè)試數(shù)據(jù)(1)0; 0;輸出“ 0”;(2)-234

4、5,6789; -7654,3211;輸出 “ - 1,000,000 ”;(3)-9999,9999; 1,0000,0000,0000;輸出 “9999,0000,0001 ”;(4)1,0001,0001; -1,0001,0001;輸出 “0”;(5)1,0001,0001; -1,0001,0000;輸出 ”1”;(6)-9999,9999,9999; -9999,9999,9999;輸出“ - 1,9999,9999,9998 ”;(7)1,0000,9999,9999; 1;輸出 "1,0001,0000,0000".二、概要設(shè)計(jì)為實(shí)現(xiàn)上述程序功 能，應(yīng)以雙向

5、循環(huán)鏈表表示長(zhǎng)整數(shù)。為此，需要定義一個(gè)抽象數(shù)據(jù)類型。1. 抽象數(shù)據(jù)類型定義為：ADT OrderedList數(shù)據(jù)對(duì)象： D=ai|aiint,i=1,2,.n, n0數(shù)據(jù)關(guān)系： R1=|ai- 1,ai D|=2,n 基本操作：Creat(string a)操作結(jié)果：通過字符串a(chǎn) 構(gòu)造兩個(gè)位數(shù)不限的長(zhǎng)整數(shù)。addtwo(head0,head1 ，result)初始條件： head0,head1 都已存在 , 且 head0 的絕對(duì)值比 head1 大操作結(jié)果： result等于 head0 和 head1 的和。Add(head0,head1)初始條件： head0,head1 都已存在。操作

6、結(jié)果：判斷head0 與 head1 絕對(duì)值的大小，并使 head0 的絕對(duì)值比 head1 大Display(result)初始條件： result已存在。操作結(jié)果：按四位一組，分隔符為"," 的格式，在屏幕上輸出result。ADT OrderedList2. 本程序包含三個(gè)模塊：1) 主程序模塊：void main()初始化；do接受命令；處理命令；while(“命令” =”退出”)2) 、集合單元模塊實(shí)現(xiàn)集合的抽象數(shù)據(jù)類型3) 、結(jié)點(diǎn)結(jié)構(gòu)單元模塊定義集合的結(jié)點(diǎn)結(jié)構(gòu)各模塊之間的調(diào)用關(guān)系如下：主程序模塊集合單元模塊結(jié)點(diǎn)模塊二、詳細(xì)設(shè)計(jì)1、ZhengshuAdd.h 文件

7、，鏈表的定義部分#include<iostream>#include<string>#include<math.h>using namespace std;struct LinkNodeint data;/ 記錄每個(gè)節(jié)點(diǎn)的整數(shù) （小于10000）LinkNode *next;/記錄下一個(gè)節(jié)點(diǎn)的地址LinkNode *pre;/記錄前一個(gè)節(jié)點(diǎn)的地址;class LinkListprivate:LinkNode *head0,*head1;/head0， head1 分別記錄兩個(gè)整數(shù)鏈表的頭指針LinkNode *currptr;LinkNode *result

8、;/result記錄結(jié)果鏈表的頭指針public:LinkList();/ 構(gòu)造函數(shù)，初始化鏈表LinkList();/析構(gòu)函數(shù)，釋放空間void Creat(string a);/ 引入字符串，創(chuàng)立兩個(gè)鏈表，分別表示兩個(gè)整數(shù)void Add();/實(shí)現(xiàn)兩個(gè)整數(shù)相加void Display();/ 顯示結(jié)果void addtwo();/ 節(jié)點(diǎn)多的作為被加數(shù)，少的作為加數(shù)，實(shí)現(xiàn)整數(shù)絕對(duì)值大的加小的;2、ZhengshuAdd.cpp 文件，鏈表的實(shí)現(xiàn)部分 #include"ZhengshuAdd.h"int sum(int n);LinkList:LinkList()/構(gòu)造函

9、數(shù)，初始化鏈表head0=new LinkNode;/ 申請(qǐng)一個(gè)空間記錄整數(shù)的符號(hào)和節(jié)點(diǎn)數(shù) head1=new LinkNode; head0->next=head0;head0->pre=head0;/初始化鏈表，建立雙向循環(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,

10、*p3=result; / 三個(gè)指針分別指向三條鏈表的頭指針 while(p1!=p1->pre)p1->pre->next=p1->next;p1->next->pre=p1->pre;currptr=p1;p1=p1->next;delete currptr;while(p2!=p2->pre)/逐個(gè)刪除節(jié)點(diǎn)，釋放空間p2->pre->next=p2->next;p2->next->pre=p2->pre;currptr=p2;p2=p2->next;delete currptr;while(p

11、3!=p3->pre)p3->pre->next=p3->next;p3->next->pre=p3->pre;currptr=p3;p3=p3->next;delete currptr;/ delete p1;/ delete p2;/ delete p3;void LinkList:Creat(string a)/引入字符串，創(chuàng)立兩個(gè)鏈表，分別表示兩個(gè)整數(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)記字符串中的 - 號(hào)/k 記錄字符串中的字符轉(zhuǎn)化為整

12、數(shù)的值， l 使每個(gè)節(jié)點(diǎn)記錄 4 位while(am!='')m+;/m記錄字符串中被加數(shù)的字符數(shù)n=m;while(an!='0') n+;/n記錄字符串的總字符數(shù)if(a0='-')head0->data=(-1);/ 記錄整數(shù)符號(hào)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ù)存

13、到雙向循環(huán)鏈表中currptr->data=k;currptr->next=head0;currptr->pre=head0->pre;head0->pre->next=currptr;head0->pre=currptr;head0=currptr;s+;/節(jié)點(diǎn)數(shù)加 1k=0;/重新初始化 k 和 ll=0;head0->pre->data*=s;/ 存儲(chǔ)整數(shù)符號(hào)和節(jié)點(diǎn)數(shù)/ 與建第一個(gè)整數(shù)鏈表一樣，建立第二個(gè)整數(shù)鏈表 head1 k=0;l=0;if(am+1='-')head1->data=(-1);m+;else

14、head1->data=1;for(i=n-1;i>m;i-)if(ai!=',')k+=(ai-'0')*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->d

15、ata*=j;voidLinkList:Add()/ 實(shí)現(xiàn)兩個(gè)整數(shù)相加LinkNode *temp;if(abs(head0->pre->data)>abs(head1->pre->data)/ 兩個(gè)整數(shù)中，絕對(duì)值大的為被加數(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-

16、>data)int k1,k2;LinkNode *p=head0,*q=head1;/ 如果節(jié)點(diǎn)數(shù)相同，則判斷節(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();elsetemp=head0;head0=head1;head1=temp;addtwo();void LinkList:ad

17、dtwo()/ 節(jié)點(diǎn)多的作為被加數(shù)，少的作為加數(shù)，實(shí)現(xiàn)整數(shù)絕對(duì)值大的加小的/ 默認(rèn) head0 存的整數(shù)絕對(duì)值比 head1 大int s=0,m1=head0->data,m2=head1->data;m1=(head0->pre->data/abs(head0->pre->data);/head0的符號(hào)m2=(head1->pre->data/abs(head1->pre->data);/head1的符號(hào)LinkNode *p=head0->pre->pre,*q=head1->pre->pre; resu

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

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

20、整數(shù)s=0;if(currptr->data>0)/ 大于 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ù)比 head

21、1 長(zhǎng)時(shí)，繼續(xù)建鏈 while(p!=head0->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

22、&&m2<0)s=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;currp

23、tr->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=currptr;res

24、ult->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é)果的符號(hào)while(p->data=0&&p!=result->pre->pre)/當(dāng)運(yùn)算后前幾個(gè)節(jié)點(diǎn)的數(shù)據(jù)為0 時(shí)，不輸出p=p->next;result->pre->data=(abs(result->

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

26、esult->pre->pre&&abs(result->pre->data)!=1)/ 顯示最后一個(gè)節(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;3、main.cpp文件，主函數(shù)和其他函數(shù)的實(shí)現(xiàn)#include"ZhengshuAdd.h&quo

27、t;/訪問文件ZhengshuAdd.hvoid main()/主函數(shù)cout<<"|=|n" cout<<"|*|n"cout<<"|*歡迎使用任意長(zhǎng)整數(shù)加法系統(tǒng)*|n"cout<<"|*劉偉高 *|n"cout<<"|*|n" cout<<"| 在此系統(tǒng)中，可以輸入任意長(zhǎng)的整數(shù) 。|n"string ch;char Yes_No;docout<<"|cout<<&qu

28、ot;|cout<<"|輸入形式為： (-)*,*,*;(-)*,*,*,*|n"即符號(hào) +數(shù)，每 4 位加一個(gè) ','，兩個(gè)數(shù)之間用請(qǐng)輸入你要計(jì)算的兩個(gè)''隔開|n"數(shù) :|n"cin>>ch;/輸入任意長(zhǎng)字符串LinkListList;/定義鏈表對(duì)象List.Creat(ch);/把字符串轉(zhuǎn)化為整數(shù)，并存到鏈表中List.Add();/ 實(shí)現(xiàn)兩個(gè)整數(shù)相加List.Display();/ 輸出結(jié)果cout<<" 是否繼續(xù)計(jì)算(Y/N):"/詢問是否繼續(xù)計(jì)算cin&g

29、t;>Yes_No;while(Yes_No='y'|Yes_No='Y');/Yes_No不等于 'Y'或 'y'時(shí)，程序退出cout<<"|=|n" cout<<"|*|n"cout<<"|* 感謝使用本系統(tǒng) !*|n" cout<<"|*|n"4、函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：MainList.Creat(ch)List.Add()List.Display()四、調(diào)試分析1、由于對(duì)任意長(zhǎng)整數(shù)運(yùn)算的算法推敲不足，是程序調(diào)試時(shí)費(fèi)時(shí)不少2、本程序有些代碼重復(fù)出現(xiàn)，從而減少了空間的利用率和增加了程序代碼的雜亂性3、本程序模塊劃分