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

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

2、 提高綜合運用所學(xué)的理論知識和方法獨立分析和解決問題的能力;2. 需求分析問題描述 : 設(shè)計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序。 基本要求 : 利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲， 每個結(jié)點含一個整形變量。 任何整形變量的范圍是 -215 - 1 215 - 1 。輸入和輸出形式 : 按中國對于長整數(shù)的表示習(xí)慣，每四位一組，組間用逗號隔開。測試數(shù)據(jù):(1)0;0; 應(yīng)輸出“0” 。(2)-23456789;-76543211; 應(yīng)輸出“-100000000” 。應(yīng)輸出“999(4)100010001;-100010001; 應(yīng)輸出“ 0”。(5)100010001;-100010000;

3、應(yīng)輸出“1” 。(6)-999999999999;-999999999999; 應(yīng)輸出“” 。應(yīng)輸出“”。實現(xiàn)提示 :(1) 每個結(jié)點中可以存放的最大整數(shù)為 32767 ，才能保證兩數(shù)相加不會溢出，但若這樣存放， 即相當(dāng)于按 32768 進制存放，在十進制與 32768 進制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個結(jié)點中僅存十進制的4位，即不超過 9999 的非負(fù)整數(shù)，整個鏈表表示為萬進制。 (2) 可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。 用其絕對值表示元素結(jié)點數(shù)目。 相加過程中不要破壞兩個操作數(shù)鏈表。不能給長整數(shù)位數(shù)規(guī)定上限。3.1 概要設(shè)計利用雙向循環(huán)鏈表現(xiàn)實長整數(shù)的存儲， 每個結(jié)點含一

4、個整形變量。 輸入的形式以回車結(jié)束， 可以直接輸入正數(shù)或負(fù)數(shù)。 按中國對于長整數(shù)的表示習(xí)慣， 每四位一組，除數(shù)字和位于首位置的負(fù)號外， 其它一切字符都將作為分隔符， 連續(xù)多個分隔符當(dāng)一個處理 , 但不使用分隔符也不影響結(jié)果。3.3 調(diào)試分析測試數(shù)據(jù)，測試輸出的結(jié)果， 時間復(fù)雜度分析， 和每個模塊設(shè)計和調(diào)試時存在問題的思考（問題是哪些？問題如何解決？） ，算法的改進設(shè)想。-可編輯修改 -。3.4 用戶手冊 ( 略)3.5 測試結(jié)果 ( 略)4 總結(jié)長整數(shù)用雙向循環(huán)隊列的數(shù)據(jù)結(jié)構(gòu)，用的比較少，查閱不少資料5、程序清單 :( 見附錄 )#include<iostream>#include

5、<string.h>#include<stdlib.h>#include<math.h> using namespace std; struct LinkNodeint data;/記錄每個節(jié)點的整數(shù)（小于10000）LinkNode *next;/記錄下一個節(jié)點的地址LinkNode *pre;/記錄前一個節(jié)點的地址;class LinkListprivate:LinkNode *head0,*head1;/head0， head1 分別記錄兩個整數(shù)鏈表的-可編輯修改 -。頭指針LinkNode *currptr;LinkNode *result;/res

6、ult記錄結(jié)果鏈表的頭指針public:LinkList();/構(gòu)造函數(shù)，初始化鏈表LinkList();/析構(gòu)函數(shù)，釋放空間void Creat(string a);/引入字符串，創(chuàng)立兩個鏈表，分別表示兩個整數(shù)void Add();/實現(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-

7、>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;/ 三個指針分別指向三條鏈表的頭指針 while(p1!=p1->pre)p1->pre->next=p1

8、->next;p1->next->pre=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->p

9、re=p3->pre;currptr=p3;p3=p3->next;delete currptr;void LinkList: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標(biāo)記字符串中的 - 號/k記錄字符串中的字符轉(zhuǎn)化為整數(shù)的值，l 使每個節(jié)點記錄4 位while(am!='') m+;/m記錄字符串中被加數(shù)的字符數(shù)n=m;while(an!='0') n+;/n記錄字符串的總字符數(shù)if

10、(a0='-')head0->data=(-1);/記錄整數(shù)符號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-&

11、gt;next=currptr;head0->pre=currptr;head0=currptr;s+;/節(jié)點數(shù)加 1k=0;/重新初始化 k 和 ll=0;head0->pre->data*=s;/存儲整數(shù)符號和節(jié)點數(shù)/ 與建第一個整數(shù)鏈表一樣，建立第二個整數(shù)鏈表 head1 k=0;l=0;if(am+1='-')head1->data=(-1);m+;elsehead1->data=1;for(i=n-1;i>m;i-)if(ai!=',')k+=(ai-'0')*sum(l);l+;if(ai='

12、;,'|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()/實現(xiàn)兩個整數(shù)相加LinkNode *temp;if(abs(head0->pre->data)>abs

13、(head1->pre->data)/ 兩個整數(shù)中，絕對值大的為被加數(shù) addtwo();else if(abs(head0->pre->data)<abs(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-&

14、gt;data&&p!=head0->pre->pre&&q!=head1->pre->pre)p=p->next;q=q->next;k1=p->data;k2=q->data;if(k1>k2)addtwo();elsetemp=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->da

15、ta,m2=head1->data;-可編輯修改 -。m1=(head0->pre->data/abs(head0->pre->data);/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 存的整

16、數(shù)絕對值比head1 大，即 head0 的節(jié)點數(shù)大于或等于head1currptr=new LinkNode;currptr->data=(p->data)*m1+(q->data)*m2+s;/兩整數(shù)相加if(m1*m2)>0)/如果符號相同if(abs(currptr->data)-10000>=0)/相加后超過10000，則進位s=currptr->data/10000;currptr->data=abs(currptr->data)%10000;else/abs(currptr->data)-10000<0，不進位s=

17、0;currptr->data=abs(currptr->data);else if(m1>0&&m2<0)/ 符號不同，在此相當(dāng)于實現(xiàn)兩個正整數(shù)相減s=0;if(currptr->data<0)/小于 0，向前一位借1currptr->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;-

18、可編輯修改 -。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é)點數(shù)比 head1 長時，繼續(xù)建鏈 while(p!=head0->pre)currptr=new LinkNode; currptr->data=p-&

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

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

21、t;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 LinkL

22、ist:Display()/顯示結(jié)果LinkNode *p=result;int FuHao=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;

23、/首先顯示符號和第一個節(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)/ 顯示最后一個節(jié)點數(shù)據(jù)-可編輯修改 -。cout<<","cout.width(4)