1、 韶關學院計算機科學學院數據結構課程設計題 目：大數運算器學生姓名：學 號：專 業：班 級： 指導教師姓名及職稱： 講師 起止時間： 年 月 年 月1.需求分析1.1課題背景及意義大數運算，顧名思義，就是很大的數值的數進行一系列的運算。隨著社會的發展，數據出現了指數般爆炸性增長，而在天文學，數學，遺傳學等傳統學科，所研究的數字往往幾百位甚至上千位，要求的精度也很高。但是在計算機中，由于字長的限制，計算機所能表示的范圍是有限的，當我們對比較小的數進行運算時，這樣的數值并沒有超出計算機的表示范圍，所以可以運算。但是當我們在實際的應用中進行大量的數據處理時，會發現參與運算的數往往超過計算機的基本數據

2、類型的表示范圍，比如在天文學時常運用到的“光年”這一單位，如果求距地球幾十光年的星球航天器所要到達的時間，計算機將無法對其進行運算。由于編程語言提供的基本數值數據類型表示的數值范圍有限，不能滿足較大規模的高精度數值計算，因此需要利用其他方法實現高精度數值的計算，于是產生了大數運算。大數運算主要有加、減、乘三種方法。既然在計算機中無法直接表示，那么大數到底如何進行運算呢，學習過數據結構的都知道線性表，將大數拆分然后存儲在線性表中，不失為一個很好的辦法。1.2課題要求基本要求： 實現一個大整數（要求允許絕對值232）的運算程序。要求程序讀入操作數A和B，選擇相應的加、減法或乘法運算符，然后計算結果

3、并輸出到屏幕上。選做內容：（1）實現整除運算； （2）求出運算時間； （3）實現乘方運算； （4）圖形化操作界面。1.2.1程序規定格式（1）輸入的形式：正數的不同輸入符號位，輸入數為整型數，數位理論上為無限位。（2）程序所能達到的功能：能進行理論上無限位的數值之間所有整型數的四則運算。（3）輸出的形式：整型數據1.2.2測試的數據(1)正確的輸入以下是對兩個大數進行加減乘運算所得的正確結果：大數A：999888777666555444333222111000大數B：111222333444555666777888999000正確的運算結果：A+B：1111111111111111111111

4、111110000A-B：888666444221999777555333112000A*B：111209963037098814851876554444456814851901296370456889000000以下是對兩個大數進行除法運算所得的正確結果：大數A：999888777666555444333222111000大數B：1234567890正確的運算結果A/B：809909917280090157158(2)錯誤的輸入數A：999999999999.9數B：3錯誤的結果：33333333333332概要設計2.1問題解決的思路概述 首先是確定結構化程序設計的流程圖，利用字符串來進行

5、比較數的大小，把程序主要分為五個部分：實現加法的模塊，實現減法的模塊，實現乘法的模塊，實現除法的模塊，實現求余的模塊，通過函數的嵌套調用來實現其功能，并通過編寫main主函數來實現大整數的正確輸入與正確輸出，最后通過調試程序來修改不足和優化程序界面。2.2相關函數的的介紹與說明int sign=1; /sign 為符號位inline int compare(string str1,string str2)/定義比較兩個函數大小string ADD_INT(string str1,string str2) /加法string:size_type L1,L2;/定義L1，L2的類型int int1

6、=0,int2=0; /int2 記錄進位string:size_type tempint;/自定義tempintstring MUL_INT(string str1,string str2)/高精度乘法string DIVIDE_INT(string str1,string str2,int flag) /除法，flag=1時,返回商; flag=0時,返回余數string quotient,residue; /定義商和余數string tempstr/字符串變量string DIV_INT(string str1,string str2) return DIVIDE_INT(str1,st

7、r2,1);/除法,返回商string MOD_INT(string str1,string str2) return DIVIDE_INT(str1,str2,0);/除法,返回余數printf()/顯示內容2.3主程序的流程圖3調試分析4用戶使用說明程序運行操作步驟：(1) 運行66666.exe應用程序后出現主界面；(2) 首先，按下數字鍵輸入數A，按下回車鍵。在輸入數的過程中，如果發現輸入的某個數錯誤了，可按“退格”鍵從后往前一個個刪除掉；（3）輸入將要運算的運算符，如“加”是“+”，“減”是“-”，“乘”是“*”，“除”是“/”,“求余”是“%”；（4)輸入數B，按下回車鍵，結果就會

8、顯示在屏幕上。5測試結果 圖1程序主界面 圖2加法測試結果 圖3減法測試結果 圖4乘法測試結果 圖5除法測試結果參考文獻1嚴蔚敏，李冬梅，吳偉民 .數據結構(C語言版) M.北京:人民郵電出版社，2011.2譚浩強 .C+面向對象程序設計(第二版) M.北京：中國鐵道出版社，2009.附錄:程序源碼#include #include using namespace std;inline int compare(string str1,string str2) /相等返回0，大于返回1，小于返回-1 if (str1.size()str2.size() return 1; /長度長的整數大于長度

9、小的整數 else if (str1.size()str2.size() return -1; else return pare(str2); /若長度相等，則頭到尾按位比較string SUB_INT(string str1,string str2);string ADD_INT(string str1,string str2) /高精度加法 int sign=1; /sign 為符號位 string str; if (str10=-) if (str20=-) sign=-1; str=ADD_INT(str1.erase(0,1),str2.erase(0,1); else str=SU

10、B_INT(str2,str1.erase(0,1); else if (str20=-) str=SUB_INT(str1,str2.erase(0,1); else /把兩個整數對齊，短整數前面加0補齊 string:size_type L1,L2; int i; L1=str1.size(); L2=str2.size(); if (L1L2) for (i=1;i=L2-L1;i+) str1=0+str1; else for (i=1;i=0;i-) int1=(int(str1i)-0+int(str2i)-0+int2)%10; int2=(int(str1i)-0+int(st

11、r2i)-0+int2)/10; str=char(int1+0)+str; if (int2!=0) str=char(int2+0)+str; /運算后處理符號位 if (sign=-1)&(str0!=0) str=-+str; return str;string SUB_INT(string str1,string str2) /高精度減法 int sign=1; /sign 為符號位 string str; int i,j; if (str20=-) str=ADD_INT(str1,str2.erase(0,1); else int res=compare(str1,str2);

12、if (res=0) return 0; if (res=0;i-) if (str1i+tempint=0;i-) str=str1i+str; /去除結果中多余的前導0 str.erase(0,str.find_first_not_of(0); if (str.empty() str=0; if (sign=-1) & (str0!=0) str =-+str; return str;string MUL_INT(string str1,string str2) /高精度乘法 int sign=1; /sign 為符號位 string str; if (str10=-) sign*=-1;

13、 str1 =str1.erase(0,1); if (str20=-) sign*=-1; str2 =str2.erase(0,1); int i,j; string:size_type L1,L2; L1=str1.size(); L2=str2.size(); for (i=L2-1;i=0;i-) /模擬手工乘法豎式 string tempstr; int int1=0,int2=0,int3=int(str2i)-0; if (int3!=0) for (j=1;j=0;j-) int1=(int3*(int(str1j)-0)+int2)%10; int2=(int3*(int(

14、str1j)-0)+int2)/10; tempstr=char(int1+0)+tempstr; if (int2!=0) tempstr=char(int2+0)+tempstr; str=ADD_INT(str,tempstr); /去除結果中的前導0 str.erase(0,str.find_first_not_of(0); if (str.empty() str=0; if (sign=-1) & (str0!=0) str=-+str; return str;string DIVIDE_INT(string str1,string str2,int flag) /高精度除法。fla

15、g=1時,返回商; flag=0時,返回余數 string quotient,residue; /定義商和余數 int sign1=1,sign2=1; if (str2 = 0) /判斷除數是否為0 quotient= ERROR!; residue = ERROR!; if (flag=1) return quotient; else return residue ; if (str1=0) /判斷被除數是否為0 quotient=0; residue =0; if (str10=-) str1 = str1.erase(0,1); sign1 *= -1; sign2 = -1; if

16、(str20=-) str2 = str2.erase(0,1); sign1 *= -1; int res=compare(str1,str2); if (res0) quotient=0; residue =str1; else if (res = 0) quotient=1; residue =0; else string:size_type L1,L2; L1=str1.size(); L2=str2.size(); string tempstr; tempstr.append(str1,0,L2-1); for (int i=L2-1;i=0;ch-) /試商 string str; str=str+ch; if (compar