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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課程名稱: 數(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ǔ)言編寫程序，解決實(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è)試等基

2、本方法和技能;(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)中可以存

3、放的最大整數(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)外，其它一切字符都將作為分隔符，

4、連續(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<iostream>#include<string.h>#include<stdlib.h>#include<math.h>using namespace std;struct LinkNodeint data; /

5、記錄每個(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 Ad

6、d(); /實(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

7、;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) /逐

8、個(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è)整

9、數(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!=',&

10、#39;) /把字符轉(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->

11、;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;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->p

12、re=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)<a

13、bs(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ù)相同，則判斷節(jié)點(diǎn)中數(shù)值大小while(p->data=q->data&&p!=head0->pre->pre&&q!=head1->pre->pre) p=p->n

14、ext; 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ù)絕對(duì)值大的加小的 /默認(rèn)head0存的整數(shù)絕對(duì)值比head1大int s=0,m1=head0->data,m2=head1->data;m1=(head0->pre->data/abs(head0->pre->data); /

15、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)*

16、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)-10000<0，不進(jìn)位 s=0; currptr->data=abs(currptr->data); else if(m1>0&&m2<0)

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

18、t; /存入鏈表 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-

19、>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=0; if(currptr->data<0) currptr->data+=10000; s=-1; else if(m1<0&&m2>0) s=0; if(currptr->data&g

20、t;0) 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) /處理相加后，

21、進(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=

22、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ù)cout<<FuHao*p->data; /首先顯示符號(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<<"," /每4位一組，并用，隔開(kāi) cout.width(4); cout.fill('0'); cout<<p->data; p=p->next;if(p=result->pre->pre&&abs(result->pre->data)!=1)/