長整數(shù)的四則運算(共12頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上課程名稱: 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計課程設(shè)計題目: 長整數(shù)的四則運算姓 名: 院系: 計算機學(xué)院專 業(yè):計算機科學(xué)與技術(shù) 年 級: 學(xué) 號:指導(dǎo)教師: 2014 年月 日目 錄 1 課程設(shè)計的目的32 需求分析3 3 課程設(shè)計報告內(nèi)容3 3.1概要設(shè)計33.2詳細(xì)設(shè)計3 3.3調(diào)試分析3 3.4用戶手冊4 3.5測試結(jié)果43.6程序清單5 4 小結(jié) x 5 參考文獻(xiàn) 81.課程設(shè)計的目的(1) 熟練使用 C 語言編寫程序，解決實際問題;(2) 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力;(3) 初步掌握軟件開發(fā)過程的問題分析、系統(tǒng)設(shè)計、程序編碼、測試等基

2、本方法和技能;(4) 提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力;2.需求分析問題描述:設(shè)計一個實現(xiàn)任意長的整數(shù)進(jìn)行加法運算的演示程序?；疽?利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整形變量。任何整形變量的范圍是 -215 - 1 215 - 1。輸入和輸出形式:按中國對于長整數(shù)的表示習(xí)慣，每四位一組，組間用逗號隔開。測試數(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”。實現(xiàn)提示:(1)每個結(jié)點中可以存

3、放的最大整數(shù)為 32767，才能保證兩數(shù)相加不會溢出，但若這樣存放，即相當(dāng)于按 32768 進(jìn)制存放，在十進(jìn)制與 32768 進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個結(jié)點中僅存十進(jìn)制的 4 位，即不超過 9999 的非負(fù)整數(shù)，整個鏈表表示為萬進(jìn)制。(2)可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。不能給長整數(shù)位數(shù)規(guī)定上限。3.1概要設(shè)計利用雙向循環(huán)鏈表現(xiàn)實長整數(shù)的存儲，每個結(jié)點含一個整形變量。輸入的形式以回車結(jié)束，可以直接輸入正數(shù)或負(fù)數(shù)。按中國對于長整數(shù)的表示習(xí)慣，每四位一組，除數(shù)字和位于首位置的負(fù)號外，其它一切字符都將作為分隔符，

4、連續(xù)多個分隔符當(dāng)一個處理,但不使用分隔符也不影響結(jié)果。3.3調(diào)試分析測試數(shù)據(jù)，測試輸出的結(jié)果，時間復(fù)雜度分析，和每個模塊設(shè)計和調(diào)試時存在問題的思考（問題是哪些？問題如何解決？），算法的改進(jìn)設(shè)想。3.4用戶手冊(略)3.5測試結(jié)果(略)4總結(jié)長整數(shù)用雙向循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)，用的比較少，查閱不少資料5、程序清單:(見附錄)#include<iostream>#include<string.h>#include<stdlib.h>#include<math.h>using namespace std;struct LinkNodeint data; /

5、記錄每個節(jié)點的整數(shù)（小于10000）LinkNode *next; /記錄下一個節(jié)點的地址LinkNode *pre; /記錄前一個節(jié)點的地址;class LinkListprivate:LinkNode *head0,*head1; /head0，head1分別記錄兩個整數(shù)鏈表的頭指針LinkNode *currptr;LinkNode *result; /result記錄結(jié)果鏈表的頭指針public:LinkList(); /構(gòu)造函數(shù)，初始化鏈表LinkList(); /析構(gòu)函數(shù)，釋放空間void Creat(string a); /引入字符串，創(chuàng)立兩個鏈表，分別表示兩個整數(shù)void Ad

6、d(); /實現(xiàn)兩個整數(shù)相加void Display(); /顯示結(jié)果void addtwo();/節(jié)點多的作為被加數(shù)，少的作為加數(shù)，實現(xiàn)整數(shù)絕對值大的加小的;int sum(int n);LinkList:LinkList() /構(gòu)造函數(shù)，初始化鏈表head0=new LinkNode;/申請一個空間記錄整數(shù)的符號和節(jié)點數(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;/三個指針分別指向三條鏈表的頭指針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、個刪除節(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;void LinkList:Creat(string a) /引入字符串，創(chuàng)立兩個鏈表，分別表示兩個整

9、數(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標(biāo)記字符串中的-號 /k記錄字符串中的字符轉(zhuǎn)化為整數(shù)的值，l使每個節(jié)點記錄4位while(am!='') m+; /m記錄字符串中被加數(shù)的字符數(shù) n=m;while(an!='0') n+; /n記錄字符串的總字符數(shù)if(a0='-') head0->data=(-1); /記錄整數(shù)符號 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é)點數(shù)加1 k=0; /重新初始化k和l l=0; head0->pre->

11、;data*=s; /存儲整數(shù)符號和節(jié)點數(shù)/與建第一個整數(shù)鏈表一樣，建立第二個整數(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() /實現(xiàn)兩個整數(shù)相加LinkNode *temp;if(abs(head0->pre->data)>abs(head1->pre->data) /兩個整數(shù)中，絕對值大的為被加數(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é)點數(shù)相同，則判斷節(jié)點中數(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é)點多的作為被加數(shù)，少的作為加數(shù)，實現(xiàn)整數(shù)絕對值大的加小的 /默認(rèn)head0存的整數(shù)絕對值比head1大int s=0,m1=head0->data,m2=head1->data;m1=(head0->pre->data/abs(head0->pre->data); /

15、head0的符號m2=(head1->pre->data/abs(head1->pre->data); /head1的符號LinkNode *p=head0->pre->pre,*q=head1->pre->pre;result->data=head0->pre->data; /存結(jié)果的節(jié)點數(shù)和符號while(q!=head1->pre)/head0存的整數(shù)絕對值比head1大，即head0的節(jié)點數(shù)大于或等于head1 currptr=new LinkNode; currptr->data=(p->data)*

16、m1+(q->data)*m2+s; /兩整數(shù)相加 if(m1*m2)>0) /如果符號相同 if(abs(currptr->data)-10000>=0) /相加后超過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、/符號不同，在此相當(dāng)于實現(xiàn)兩個正整數(shù)相減 s=0; if(currptr->data<0) /小于0，向前一位借1 currptr->data+=10000; s=-1; else if(m1<0&&m2>0)/符號不同，在此相當(dāng)于實現(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é)點數(shù)比head1長時，繼續(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)位問題 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é)果的符號while(p->data=0&&p!=result->pre->pre)/當(dāng)運算后前幾個節(jié)點的數(shù)據(jù)為0時，不輸出 p=p->next; result->pre->data=(abs(result->pre->data)-1)*FuHao;/結(jié)果記錄非0節(jié)點數(shù)cout<<FuHao*p->data; /首先顯示符號和第一個節(jié)點中的數(shù)if(abs(result->pre->data)!=1) p=p->next; /判斷非0節(jié)點數(shù)是否為1while(p!=result->pre->pre) /繼續(xù)輸出 cout<<"," /每4位一組，并用，隔開 cout.width(4); cout.fill('0'); cout<<p->data; p=p->next;if(p=result->pre->pre&&abs(result->pre->data)!=1)/