任意長(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)算的演示程序測(cè)試數(shù)據(jù)】：1)2)3)4)5)6)7)【基本要求】：利用雙向循環(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)隔開。0； 0；應(yīng)輸出“ 0”。-2345,6789 ； -7654,3211 ；應(yīng)輸出“ -1,0000,0000 ”。-9999,9999 ； 1,0000,0000,0000 ；應(yīng)輸出“ 9999,0000,0001 ”。1,0001,0001 ； -1,0001,000

2、1 ；應(yīng)輸出“ 0”。1,0001,0001 ； -1,0001,0000 ；應(yīng)輸出“ 1”。-9999,9999,9999 ； -9999,9999,9999 ；應(yīng)輸出“ 1,9999,9999,9998 ”。1,0000,9999,9999 ； 1；應(yīng)輸出“ 1,0001,0000,0000 ”。二、實(shí)驗(yàn)?zāi)康?、熟悉掌握雙向循環(huán)鏈表的基本操作；2、熟悉任意長(zhǎng)字符串的輸入，并實(shí)現(xiàn)把字符串轉(zhuǎn)化為整數(shù);3、熟悉任意長(zhǎng)整數(shù)的加法運(yùn)算；4、更進(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ì)話的方式，即 在計(jì)算機(jī)終端上顯

3、示“提示信息”之后， 由用戶在鍵盤上輸入演示程序中規(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”;輸出 “ - 1,

4、000,000 ”;輸出 “9999,0000,0001 ”輸出輸出(2) -2345,6789; -7654,3211;(3) -9999,9999; 1,0000,0000,0000;“0”;”1”;輸出“ - 1,9999,9999,9998 ”(4) 1,0001,0001; -1,0001,0001;(5) 1,0001,0001; -1,0001,0000;(6) -9999,9999,9999; -9999,9999,9999;(7) 1,0000,9999,9999; 1; 輸出 1,0001,0000,0000.二、概要設(shè)計(jì) 為實(shí)現(xiàn)上述程序功 象數(shù)據(jù)類型。1. 抽象數(shù)據(jù)類型定

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

6、的大小， 并使headO的絕對(duì)值比headl大Display(result) 初始條件： result 已存在。操作結(jié)果：按四位一組，分隔符為 , 的格式， ADT OrderedList在屏幕上輸出 result 。2. 本程序包含三個(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文件，鏈表的定義部分#in cludeviostream#in

7、clude#in cludeusing n ames pace std; struct Lin kNodeint data;10000)Li nkNode *n ext;Lin kNode *pre;class Lin kListp rivate:Lin kNode *head0,*head1;的頭指針Lin kNode *cu rrptr;Lin kNode *result;public:Lin kListO;Li nkListO;void Creat(string a);示兩個(gè)整數(shù)void Add();void Dis playO;void addtwo();/記錄每個(gè)節(jié)點(diǎn)的整數(shù)（小于/記

8、錄下一個(gè)節(jié)點(diǎn)的地址/記錄前一個(gè)節(jié)點(diǎn)的地址/headO ，headl分別記錄兩個(gè)整數(shù)鏈表/result記錄結(jié)果鏈表的頭指針/構(gòu)造函數(shù)，初始化鏈表 /析構(gòu)函數(shù)，釋放空間/引入字符串，創(chuàng)立兩個(gè)鏈表，分別表/實(shí)現(xiàn)兩個(gè)整數(shù)相加/顯示結(jié)果/節(jié)點(diǎn)多的作為被加數(shù)，少的作為加數(shù)，實(shí)現(xiàn)整數(shù)絕對(duì)值大的加小的 2、ZhengshuAdd.cpp文件，鏈表的實(shí)現(xiàn)部分#i ncludeZhe ngshuAdd.hint sum(i nt n);/構(gòu)造函數(shù)，初始化Lin kList:Li nkList()鏈表head0=new Lin kNode;/申請(qǐng)一個(gè)空間記錄整數(shù)的符號(hào)和節(jié)點(diǎn)數(shù)/初始化鏈表，建立雙向循h(huán)ead仁 ne

9、w Lin kNode; head0-n ext=head0; head0-p re=head0;環(huán)鏈表head1- n ext=head1;head1- p re=head1;result=new Lin kNode;result-next=result; result-pre=result; currptr=NULL;LinkList:LinkList()/ 析構(gòu)函數(shù)，釋放空間LinkNode *p1=head0,*p2=head1,*p3=result;/ 三個(gè)指針分別指向三條鏈表的頭指針 while(p1!=p1-pre)p1-pre-next=p1-next; p1-next-pre

10、=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(p3!=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

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

12、,)為整數(shù)k+=(ai-0)*sum(l);l+;if(ai=,|i=w)currptr=new LinkNode; 向循環(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;/ 把字符轉(zhuǎn)化/ 把整數(shù)存到雙head0-pre-data*=s;/ 存儲(chǔ)整數(shù)符號(hào)和節(jié)點(diǎn)數(shù)/ 與建第一個(gè)整數(shù)鏈表一樣，建立第二個(gè)整數(shù)鏈表 head1 k=0;l=0;if(a

13、m+1=-)head1-data=(-1);m+; elsehead1-data=1;for(i=n-1;im;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-data*=j;voidLinkList:Add()/ 實(shí)現(xiàn)兩個(gè)整數(shù)相加Li

14、nkNode *temp;if(abs(head0-pre-data)abs(head1-pre-data)/ 兩個(gè)整數(shù)中，絕對(duì)值大的為被加數(shù) addtwo();else if(abs(head0-pre-data)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ù)相同，則判斷節(jié)點(diǎn)中數(shù)值大小while(p-data=q-data&p!=head0-pre-

15、pre&q!=head1-pre-pre) p=p-next;q=q-next;k1=p-data;k2=q-data; if(k1k2) addtwo();elsetemp=head0; head0=head1;head1=temp;addtwo();void LinkList:addtwo()/ 節(jié)點(diǎn)多的作為被加數(shù)，少的作為加數(shù)，實(shí)現(xiàn)整數(shù)絕對(duì)值大的加小的/ 默認(rèn) headO 存的整數(shù)絕對(duì)值比 head1 大int s=0,m1=head0-data,m2=head1-data; m1=(head0-pre-data/abs(head0-pre-data); 的符號(hào)m2=(head1-pre

16、-data/abs(head1-pre-data); 的符號(hào)LinkNode *p=head0-pre-pre,*q=head1-pre-pre; result-data=head0-pre-data;和符號(hào)while(q!=head1-pre)/headO存的整數(shù)絕對(duì)值比headl大，即headO的節(jié)點(diǎn)數(shù)大于或等于 headl/head0/head1/ 存結(jié)果的節(jié)點(diǎn)數(shù)currptr=new LinkNode;currptr-data=(p-data)*m1+(q-data)*m2+s;/ 兩整數(shù)相if(m1*m2)0)/ 如果符號(hào)相同if(abs(currptr-data)-10000=0)

17、則進(jìn)位s=currptr-data/10000; currptr-data=abs(currptr-data)%10000;else不進(jìn)位s=0;currptr-data=abs(currptr-data);else if(m10&m2datadata+=10000;s=-1;else if(m10)/ 符號(hào)不同，在此相當(dāng)于實(shí)現(xiàn)負(fù)整數(shù)加上正整數(shù)s=0;if(currptr-data0) currptr-data=10000-currptr-data; s=1;else currptr-data=abs(currptr-data);currptr-next=result;currptr-pre=

18、result-pre;/ 相加后超過10000，000data)-10/ 小于 0，向/ 大于 0，/ 存入鏈表result-pre-next=currptr; result-pre=currptr; result=currptr;p=p-pre;q=q-pre;/當(dāng)headO節(jié)點(diǎn)數(shù)比headl長(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/

19、10000; currptr-data=abs(currptr-data)%10000;else s=0;currptr-data=abs(currptr-data); else if(m10&m2datadata+=10000; s=-1;else if(m10)s=0;if(currptr-data0) currptr-data=10000-currptr-data; s=1;else currptr-data=abs(currptr-data); currptr-data=abs(currptr-data)%10000; currptr-next=result; currptr-pre=

20、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; result-pre-data=m1*(abs(result-pre-data)+1);void L

21、inkList:Display() 示結(jié)果LinkNode *p=result;int FuHao=result-pre-data/abs(result-pre-data);/ while(p-data=0&p!=result-pre-pre) / 當(dāng)運(yùn)算后前幾個(gè)節(jié)點(diǎn)的數(shù)據(jù)為 0 時(shí)，不輸出/ 顯結(jié)果的符號(hào)p=p-next;result-pre-data=(abs(result-pre-data)-1)*FuHao;結(jié)果記錄非 0 節(jié)點(diǎn)數(shù)/ coutdata; 的數(shù) if(abs(result-pre-data)!=1) p=p-next; / while(p!=result-pre-pre)

22、/ 首先顯示符號(hào)和第一個(gè)節(jié)點(diǎn)中判斷非 0 節(jié)點(diǎn)數(shù)是否為 1 / 繼續(xù)輸出cout,;，隔開cout.width(4);cout.fill(0); coutdata; p=p-next;/ 每 4 位一組，并用 if(p=result-pre-pre&abs(result-pre-data)!=1) / 顯示最后一個(gè)節(jié)點(diǎn)數(shù)據(jù)cout,;cout.width(4);cout.fill(O);coutdata;coutvve ndl;int sum(i nt n)int i,s=1;for(i=1;i=n ;i+)/計(jì)算10的乘方s=s*10; return s;3、main.cpp文件，主函數(shù)和其

23、他函數(shù)的實(shí)現(xiàn)#i ncludeZhe ngshuAdd.h 問文件 ZhengshuAdd.h void mai n()coutvv|=： cout|*|n; cout|*歡迎使用任意長(zhǎng)整數(shù)加法系統(tǒng)*|n;cout|*文 y偉高 *|n;cout|*|n;cout|在此系統(tǒng)中，可以輸入任意長(zhǎng)的整數(shù)。|n;stri ng ch;char Yes_No;do/主函數(shù)|n；/訪cout| cout| cout ch;/輸入任意長(zhǎng)字符串Lin kListList;鏈表對(duì)象List.Creat(ch);化為整數(shù)，并存到鏈表中List.Add();/定義/把字符串轉(zhuǎn)/實(shí)現(xiàn)兩個(gè)整數(shù)相加List.Dis pl

24、ayO;/輸出結(jié)果coutvv是否繼續(xù)計(jì)算/詢問是否繼續(xù)計(jì)算(Y/N):;cin Yes_No;/Yes_No不等于Y或y時(shí),while(Yes_No=y|Yes_No=Y);程序退出|n；coutvv|=： cout|*|n; cout|*感謝使用本系統(tǒng) !*|n;cout|*|n;4、函數(shù)的調(diào)用關(guān)系圖反映了演示程序的層次結(jié)構(gòu)：Mai nList.Creat(ch)List.AddOList.DisplayO四、調(diào)試分析Enter Sl= 10009999Enter S2- 151=10009999S2-1si+s2=ie0ieeQePress any key to Cont inueEnt

25、er Sl= 10009999Enter S2- 1Sl=10009999S2-151+52=10010000Press any key to ContInue1、由于對(duì)任意長(zhǎng)整數(shù)運(yùn)算的算法推敲不足，是程序調(diào)試時(shí)費(fèi)時(shí)不少2、本程序有些代碼重復(fù)出現(xiàn)，從而減少了空間的利用率和增加了程序代碼的雜 亂性3、本程序模塊劃分比較合理，且把指針全部封裝在鏈表模塊中，操作方便。4、算法的時(shí)空分析O (n) ,n為鏈表長(zhǎng)度。3個(gè)模塊，使得設(shè)計(jì)時(shí)思由于鏈表采用雙向循環(huán)鏈表結(jié)構(gòu)，可以從鏈表兩頭操作，各種操作的算法時(shí)間復(fù) 雜度比較合理，各函數(shù)以及確定鏈表中的結(jié)點(diǎn)位置都是5、本實(shí)驗(yàn)采用數(shù)據(jù)抽象的程序設(shè)計(jì)方法，將程序分為 路清晰，實(shí)現(xiàn)時(shí)調(diào)試順利，各模塊具有較好的可重用性