長(zhǎng)整數(shù)的四則運(yùn)算

課程名稱: 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目: 長(zhǎng)整數(shù)的四則運(yùn)算姓 名: 院系: 計(jì)算機(jī)學(xué)院專 業(yè):計(jì)算機(jī)科學(xué)與技術(shù) 年 級(jí): 學(xué) 號(hào):指導(dǎo)教師: 2014 年月 日目 錄 1 課程設(shè)計(jì)的目的32 需求分析3 3 課程設(shè)計(jì)報(bào)告內(nèi)容3 3.1概要設(shè)計(jì)33.2詳細(xì)設(shè)計(jì)3 3.3調(diào)試分析3 3.4用戶手冊(cè)4 3.5測(cè)試結(jié)果43.6程序清單5 4 小結(jié) x 5 參考文獻(xiàn) 81.課程設(shè)計(jì)的目的(1) 熟練使用 C 語(yǔ)言編寫(xiě)程序，解決實(shí)際問(wèn)題;(2) 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力;(3) 初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、測(cè)試等基本方法和技能;(4) 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力;2.需求分析問(wèn)題描述:設(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)隔開(kāi)。測(cè)試數(shù)據(jù):(1)0;0;應(yīng)輸出“0” 。(2)-;-;應(yīng)輸出“-” 。(3)-;00;應(yīng)輸出“999(4);-;應(yīng)輸出“0”。(5);-;應(yīng)輸出“1” 。(6)-9;-9;應(yīng)輸出“98” 。(7)99;1;應(yīng)輸出“00”。實(shí)現(xiàn)提示:(1)每個(gè)結(jié)點(diǎn)中可以存放的最大整數(shù)為 32767，才能保證兩數(shù)相加不會(huì)溢出，但若這樣存放，即相當(dāng)于按 32768 進(jìn)制存放，在十進(jìn)制與 32768 進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制的 4 位，即不超過(guò) 9999 的非負(fù)整數(shù)，整個(gè)鏈表表示為萬(wàn)進(jìn)制。(2)可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)點(diǎn)數(shù)目。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。3.1概要設(shè)計(jì)利用雙向循環(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é)果。3.3調(diào)試分析測(cè)試數(shù)據(jù)，測(cè)試輸出的結(jié)果，時(shí)間復(fù)雜度分析，和每個(gè)模塊設(shè)計(jì)和調(diào)試時(shí)存在問(wèn)題的思考（問(wèn)題是哪些？問(wèn)題如何解決？），算法的改進(jìn)設(shè)想。3.4用戶手冊(cè)(略)3.5測(cè)試結(jié)果(略)4總結(jié)長(zhǎng)整數(shù)用雙向循環(huán)隊(duì)列的數(shù)據(jù)結(jié)構(gòu)，用的比較少，查閱不少資料5、程序清單:(見(jiàn)附錄)#include#include#include#includeusing 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; /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ì)值大的加小的;int sum(int n);LinkList:LinkList() /構(gòu)造函數(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,*p3=result;/三個(gè)指針?lè)謩e指向三條鏈表的頭指針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(p3!=p3-pre) p3-pre-next=p3-next; p3-next-pre=p3-pre; currptr=p3; p3=p3-next; delete currptr;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)化為整數(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ù)存到雙向循環(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ù)加1 k=0; /重新初始化k和l l=0; head0-pre-data*=s; /存儲(chǔ)整數(shù)符號(hào)和節(jié)點(diǎn)數(shù)/與建第一個(gè)整數(shù)鏈表一樣，建立第二個(gè)整數(shù)鏈表head1k=0;l=0;if(am+1=-) head1-data=(-1); m+;else head1-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;void LinkList: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)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-pre&q!=head1-pre-pre) p=p-next; q=q-next; k1=p-data; k2=q-data; if(k1k2) addtwo(); else temp=head0; head0=head1; head1=temp; addtwo(); void LinkList:addtwo()/節(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;result-data=head0-pre-data; /存結(jié)果的節(jié)點(diǎn)數(shù)和符號(hào)while(q!=head1-pre)/head0存的整數(shù)絕對(duì)值比head1大，即head0的節(jié)點(diǎn)數(shù)大于或等于head1 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) /相加后超過(guò)10000，則進(jìn)位 s=currptr-data/10000; currptr-data=abs(currptr-data)%10000; else /abs(currptr-data)-10000data=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) /大于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長(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(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=result-pre; result-pre-next=currptr; result-pre=currptr; result=currptr; p=p-pre;if(s!=0) /處理相加后，進(jìn)位問(wè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 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-pre-data)-1)*FuHao;/結(jié)果記錄非0節(jié)點(diǎn)數(shù)coutdata; /首先顯示符號(hào)和第一個(gè)節(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,; /每