任意長整數(shù)加法運算 課程設(shè)計報告

1、一、【實驗內(nèi)容】【問題描述】設(shè)計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序測試數(shù)據(jù)】：1)2)3)4)5)6)7)【基本要求】：利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲， 每個結(jié)點含一個整形變量。 任何整形變量的范圍是 -(215 - 1)(215 - 1) 。輸入和輸出形式：按中國對于 長整數(shù)的表示習慣，每四位一組，組間用逗號隔開。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 ”。二、實驗目的1、熟悉掌握雙向循環(huán)鏈表的基本操作；2、熟悉任意長字符串的輸入，并實現(xiàn)把字符串轉(zhuǎn)化為整數(shù);3、熟悉任意長整數(shù)的加法運算；4、更進一步掌握有關(guān)類的操作 三、實驗文檔：任意長整數(shù)加法運算一、需求分析1、本程序?qū)崿F(xiàn)計算任意長的整數(shù)的加法運算 . 以用戶和計算機對話的方式，即 在計算機終端上顯

3、示“提示信息”之后， 由用戶在鍵盤上輸入演示程序中規(guī)定的 運算命令，然后程序就計算并顯示出這兩個數(shù)的運算。2、本演示程序中，集合的元素限定為數(shù)字字符 09和字符， 與 ；，輸入字符可以任意長，輸入形式以“回車符”為結(jié)束標志，串中字符順 序不限，且允許出現(xiàn)重復字符。3、利用雙向循環(huán)鏈表現(xiàn)實長整數(shù)的存儲，每個結(jié)點含一個整形變量。輸入的形 式以回車結(jié)束， 可以直接輸入正數(shù)或負數(shù)。 按中國對于長整數(shù)的表示習慣， 每四 位一組，除數(shù)字和位于首位置的負號外， 其它一切字符都將作為分隔符， 連續(xù)多 個分隔符當一個處理。但不使用分隔符也不影響結(jié)果。4、測試數(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è)計 為實現(xiàn)上述程序功 象數(shù)據(jù)類型。1. 抽象數(shù)據(jù)類型定

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

6、的大小， 并使headO的絕對值比headl大Display(result) 初始條件： result 已存在。操作結(jié)果：按四位一組，分隔符為 , 的格式， ADT OrderedList在屏幕上輸出 result 。2. 本程序包含三個模塊：1)主程序模塊： void main() 初始化；do接受命令； 處理命令； 命令” =”退出”)while(2) 、集合單元模塊實現(xiàn)集合的抽象數(shù)據(jù)類型3) 、結(jié)點結(jié)構(gòu)單元模塊定義集合的結(jié)點結(jié)構(gòu) 各模塊之間的調(diào)用關(guān)系如下：主程序模塊集合單元模結(jié)點模塊二、詳細設(shè)計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);示兩個整數(shù)void Add();void Dis playO;void addtwo();/記錄每個節(jié)點的整數(shù)（小于/記

8、錄下一個節(jié)點的地址/記錄前一個節(jié)點的地址/headO ，headl分別記錄兩個整數(shù)鏈表/result記錄結(jié)果鏈表的頭指針/構(gòu)造函數(shù)，初始化鏈表 /析構(gòu)函數(shù)，釋放空間/引入字符串，創(chuàng)立兩個鏈表，分別表/實現(xiàn)兩個整數(shù)相加/顯示結(jié)果/節(jié)點多的作為被加數(shù)，少的作為加數(shù)，實現(xiàn)整數(shù)絕對值大的加小的 2、ZhengshuAdd.cpp文件，鏈表的實現(xiàn)部分#i ncludeZhe ngshuAdd.hint sum(i nt n);/構(gòu)造函數(shù)，初始化Lin kList:Li nkList()鏈表head0=new Lin kNode;/申請一個空間記錄整數(shù)的符號和節(jié)點數(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;/ 三個指針分別指向三條鏈表的頭指針 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) 個刪除節(jié)點，釋放空間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)立兩個鏈表，分別表示兩個整數(shù) int i=0,j=0,m=0,n=0,k=0,l=0,s=0,w=0;/i 記錄字符串， j 記錄加數(shù)節(jié)點數(shù)； s 記錄被加數(shù)節(jié)點數(shù)/w 標記字符串中的 - 號/k 記錄字符串中的字符轉(zhuǎn)化為整數(shù)的值， l 使每個節(jié)點記錄 4 位 while(am!=;) 符數(shù)n=m;m+;/m 記錄字符串中被加數(shù)的字while(an!=0) n+; if(a0=-)/n 記錄字符串的總字符數(shù)head0-data=(-1);w=1;/ 記錄整數(shù)符號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é)點數(shù)加 1k=0;/ 重新初始化 k 和 ll=0;/ 把字符轉(zhuǎn)化/ 把整數(shù)存到雙head0-pre-data*=s;/ 存儲整數(shù)符號和節(jié)點數(shù)/ 與建第一個整數(shù)鏈表一樣，建立第二個整數(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()/ 實現(xiàn)兩個整數(shù)相加Li

14、nkNode *temp;if(abs(head0-pre-data)abs(head1-pre-data)/ 兩個整數(shù)中，絕對值大的為被加數(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é)點數(shù)相同，則判斷節(jié)點中數(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é)點多的作為被加數(shù)，少的作為加數(shù)，實現(xiàn)整數(shù)絕對值大的加小的/ 默認 headO 存的整數(shù)絕對值比 head1 大int s=0,m1=head0-data,m2=head1-data; m1=(head0-pre-data/abs(head0-pre-data); 的符號m2=(head1-pre

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

17、則進位s=currptr-data/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)/ 符號不同，在此相當于實現(xiàn)負整數(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;/當headO節(jié)點數(shù)比headl長時，繼續(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) 題/ 處理相加后，進位問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) / 當運算后前幾個節(jié)點的數(shù)據(jù)為 0 時，不輸出/ 顯結(jié)果的符號p=p-next;result-pre-data=(abs(result-pre-data)-1)*FuHao;結(jié)果記錄非 0 節(jié)點數(shù)/ coutdata; 的數(shù) if(abs(result-pre-data)!=1) p=p-next; / while(p!=result-pre-pre)

22、/ 首先顯示符號和第一個節(jié)點中判斷非 0 節(jié)點數(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) / 顯示最后一個節(jié)點數(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+)/計算10的乘方s=s*10; return s;3、main.cpp文件，主函數(shù)和其

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

24、ayO;/輸出結(jié)果coutvv是否繼續(xù)計算/詢問是否繼續(xù)計算(Y/N):;cin Yes_No;/Yes_No不等于Y或y時,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、由于對任意長整數(shù)運算的算法推敲不足，是程序調(diào)試時費時不少2、本程序有些代碼重復出現(xiàn)，從而減少了空間的利用率和增加了程序代碼的雜 亂性3、本程序模塊劃分比較合理，且把指針全部封裝在鏈表模塊中，操作方便。4、算法的時空分析O (n) ,n為鏈表長度。3個模塊，使得設(shè)計時思由于鏈表采用雙向循環(huán)鏈表結(jié)構(gòu)，可以從鏈表兩頭操作，各種操作的算法時間復 雜度比較合理，各函數(shù)以及確定鏈表中的結(jié)點位置都是5、本實驗采用數(shù)據(jù)抽象的程序設(shè)計方法，將程序分為 路清晰，實現(xiàn)時調(diào)試順利，各模塊具有較好的可重用性