數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-長整數(shù)運算

上傳人：奔*** IP屬地：河北更新時間：2024-04-02 格式：doc 頁數(shù)：13 大小：177.00KB 人氣指數(shù)：12 舉報 版權(quán)申訴

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-長整數(shù)運算_第1頁

已閱讀1頁，還剩12頁未讀，繼續(xù)免費閱讀

版權(quán)說明：本文檔由用戶提供并上傳，收益歸屬內(nèi)容提供方，若內(nèi)容存在侵權(quán)，請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、　　數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告　　題目：長整數(shù)四則運算　　一、需求分析　　1.問題描述：　　由于工程上有時候需要對很大的數(shù)進(jìn)行計算，但是計算機(jī)本身提供的數(shù)據(jù)類型無法保存幾百位甚至幾千位

2、的數(shù)字，所以需要設(shè)計專門的算法對數(shù)據(jù)進(jìn)行相應(yīng)的計算。此程序的設(shè)計任務(wù)是：設(shè)計一個程序能夠?qū)崿F(xiàn)長整數(shù)運算的程序，而且能夠?qū)σ恍╁e誤異常進(jìn)行辨別調(diào)整，計算出正確的結(jié)果。程序輸入格式是字符串，保存時需要用雙向循環(huán)鏈表將字符串每四位保存在循環(huán)鏈表中的一個節(jié)點中，然后再計算后運行出結(jié)果。　　2.基本功能　　功能一：建立雙向循環(huán)

3、鏈表,計算鏈表個數(shù)，對鏈表的數(shù)據(jù)進(jìn)行修改，能在鏈表中插入結(jié)點。　　功能二：將字符串轉(zhuǎn)換成相應(yīng)的數(shù)字存儲在雙向循環(huán)鏈表中　　功能三：對存入雙向循環(huán)鏈表的長整數(shù)進(jìn)行相加，相減，相除。　　3.輸入輸出　　程序輸入以字符串的形式輸入，數(shù)據(jù)的類

4、型是字符串，包含元素的范圍是數(shù)字，逗號，負(fù)號。　　輸入時用字符串輸入，輸出時以一鏈表結(jié)點輸出，而且每個結(jié)點表示四位。　　二、概要設(shè)計　　1.設(shè)計思路：　　由于計算機(jī)無法完成位數(shù)很大的數(shù)字計算，設(shè)計

5、思路就是將很長的數(shù)據(jù)進(jìn)行分割，一部分一部分的用計算機(jī)固有數(shù)據(jù)類型進(jìn)行計算。將各部分的結(jié)果整合起來。由于計算機(jī)固有的整數(shù)類型存數(shù)的對大整數(shù)是2＾15-1，所以為了方便，且符合中國人對長整數(shù)的表示習(xí)慣，建立一個雙向循環(huán)鏈表，每個結(jié)點存儲四位數(shù)字，以萬為進(jìn)制。從最低位開始加法，超過一萬向上進(jìn)位，所以每次加法應(yīng)該是對應(yīng)兩個結(jié)點和進(jìn)位數(shù)相加，進(jìn)位值初始為0；減法也是一個結(jié)點計算一次，每次計算應(yīng)該是第一個鏈表對應(yīng)的結(jié)點值減去第二個結(jié)點的值和借位值的

6、和，借位值初始值為0；除法的計算可以借助減法，被減數(shù)被減數(shù)減一次則最終結(jié)果加一；直至被減數(shù)比減數(shù)小。　　2.數(shù)據(jù)結(jié)構(gòu)設(shè)計：　　因為計算的是一個連續(xù)的數(shù)字，需要桉順序一次計算，所以采用的數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是線性表。因為要求每一個結(jié)點只存儲四位數(shù)字，為了將數(shù)字連接起來，采用的數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)是鏈?zhǔn)健?lt;/p>

7、　　1．雙向循環(huán)鏈表的抽象數(shù)據(jù)類型定義為：　　ADT Link　　{　　數(shù)據(jù)對象：D={ai | ai∈CharSet，i=1，2，……，n，n≥0}　　數(shù)據(jù)關(guān)系; R={&

8、lt;ai-1,ai> | ai-1,ai∈D,i=2，……，n}　　}　　基本操作：　　InitLinkList(&L,a) 　　操作結(jié)果：構(gòu)造一個雙向循環(huán)鏈表L ，用a判斷是正數(shù)

9、還是負(fù)數(shù) 　　DestroyList(&L) 　　初始條件：雙向循環(huán)兩已經(jīng)存在　　操作結(jié)果：銷毀有序表L　　Insert(&L,a)　　初始條件：雙向循環(huán)鏈表已經(jīng)存在

10、操作結(jié)果：在循環(huán)鏈表的末尾插入一個結(jié)點，且此結(jié)點的數(shù)據(jù)值為a　　HeadInsert(&L,a)　　初始條件：雙向循環(huán)鏈表已經(jīng)存在　　操作結(jié)果：在循環(huán)鏈表的頭結(jié)點后插入一個結(jié)點，且此結(jié)點的數(shù)據(jù)值為a　　CountNode(&L)&l

11、t;p>　　初始條件：雙向循環(huán)鏈表存在　　操作結(jié)果：計算出鏈表中結(jié)點的個數(shù)，并返回個數(shù)　　Compare(&L1, &L2)　　初始條件：L1和L2存在　　操作結(jié)果：比較兩個雙向循環(huán)鏈表的大小，用返回值1表示L1大于L2,返回值-1標(biāo)志L1小于L2,

12、返回值0標(biāo)志L1和L2相等　　ToNum(*s,i,&e) 　　初始條件：s為字符串中指向某個字符的指針　　操作結(jié)果：將s的前i個字符轉(zhuǎn)換為數(shù)字，存入e中　　CreatNum(&L,&s)　　初始條件：s

13、為某個字符串，雙向循環(huán)鏈表L存在　　操作結(jié)果：將字符串s轉(zhuǎn)換成數(shù)字存入到循環(huán)鏈表L中　　Add(L1，L2, op) 　　初始條件：雙向循環(huán)鏈表L1和L2存在，op為結(jié)果的標(biāo)識符　　操作結(jié)果：兩個鏈表相加，求出結(jié)果。　　Sub(

14、L1,L2, op) 　　初始條件：雙向循環(huán)鏈表L1和L2存在　　操作結(jié)果：L1減去L2,求出結(jié)果，op為結(jié)果的標(biāo)識符　　EraseZero(Link &L)　　初始條件：雙向循環(huán)鏈表L存在　　操作結(jié)果：刪去L鏈表頭結(jié)

15、點后，第一個數(shù)據(jù)不為零結(jié)點前的所有數(shù)據(jù)為零的結(jié)點。　　如果結(jié)點數(shù)據(jù)都為零，則保存一個結(jié)點。　　print(L)　　初始條件：雙向循環(huán)鏈表L存在　　操作結(jié)果：從L頭結(jié)點開始順此打印每個結(jié)點中的數(shù)據(jù)

16、;　　3.軟件結(jié)構(gòu)設(shè)計：　　本程序包含四個模塊：　　1.主程序模塊　　Int main()　　{

17、　接受命令　　While(“命令”!=“退出”)　　{　　輸入字符串　　建立雙向循環(huán)鏈表　　將字

18、符串轉(zhuǎn)換為要求的格式存入鏈表的每個結(jié)點　　對鏈表中數(shù)據(jù)進(jìn)行即興操作數(shù)理　　再次接受命令　　}　　}　　2.雙向鏈表操

19、作模塊------實現(xiàn)結(jié)點的插入、刪除、修改　　3.字符串轉(zhuǎn)換存儲模塊----實現(xiàn)將字符串轉(zhuǎn)換為數(shù)字按格式存儲在鏈表中　　4.數(shù)據(jù)計算模塊—--------對存儲在鏈表中的數(shù)據(jù)進(jìn)行計算，得到最終期望的結(jié)果　　各個模塊調(diào)用的關(guān)系如下：　　主程序模塊中的函數(shù)原型：</p

20、>　　void Interface()-------------------操作界面函數(shù)　　Status CreatNum(Link &L,char*s)----創(chuàng)建數(shù)字鏈表函數(shù)　　Link Compute(Link &L1,Link &L2,char Ope)----數(shù)據(jù)計算函數(shù)

21、　　數(shù)據(jù)運算模塊：　　Link Add(Link &L1,Link &L2,char op) ----加法計算　　Link Sub(Link &L1,Link &L2,char op) ----減法運算<

22、;b>　　雙向鏈表操作模塊　　void InitLinkList(Link &L,char a)　　Status DestroyList(Link &L)　　Status Insert(Link &L,Elemtype a)

23、;　　int CountNode(Link L)　　BOOL Compare(Link &L1,Link &L2)　　void EraseZero(Link &L)　　Status HeadInsert(Link &L,Elemtype a) <p&

24、gt;　　字符串轉(zhuǎn)換模塊　　Status CreatNum(Link &L,char*s)　　Status ToNum(char*s,int i,long &e)　　人機(jī)界面：&l

25、t;b>　　三、詳細(xì)設(shè)計 　　1..根據(jù)分析和鏈表操作的特點，采用雙向循環(huán)鏈表實現(xiàn)，這里頭結(jié)點存儲數(shù)字的符號。　　typedef long Elemtype ;　　typedef int Status;　　typedef int BOOL;&

26、lt;/p>　　typedef struct LNode{　　Elemtype data;　　LNode *next;　　LNode *prior;　　}Node,*Link;　　void InitLi

27、nkList(Link &L,char a){　　//對一個雙向循環(huán)鏈表進(jìn)行初始化，分配頭結(jié)點　　L = (Link)malloc(sizeof(Node));//動態(tài)分配存儲空間　　If(!L) return FALSE;　　if(a == '-'

28、;) L->data = -1;//L->data存放符號節(jié)點，如果是‘-’則為，否則為0　　else L->data = 1;　　L->prior = L;　　L->next = L;　　}</p

29、>　　Status DestroyList(Link &L){　　//銷毀鏈表L　　if(!L)return ERROR;//鏈表不存在　　p = L->prior;//p指向鏈表頭節(jié)點的前驅(qū)

30、　　while(p!=L)//刪除節(jié)點節(jié)點p　　{　　q = p->prior;　　free(p);//釋放節(jié)點p的空間　　p = q;<b&

31、gt;　　}　　free(L);//釋放鏈表L的存儲空間　　return OK;　　}　　Status Insert(Link &L,Elemtype a){　　/

32、/分配一個結(jié)點，并將其數(shù)據(jù)值存為a,插入到鏈表的末尾　　p=(Link)malloc(sizeof(LNode));　　if(!p)　　exit(OVERFLOW);　　p->next=p->prior=NULL;<

33、/p>　　p->data=a;　　Link q=L->prior;　　q->next=p;　　p->prior=q;　　p->next=L;　　L->prior=p;

34、　　return OK;　　}　　Status HeadInsert(Link &L,Elemtype a){ 　　//分配一個結(jié)點，并將其數(shù)據(jù)值存為a，按頭插入法插入　　p=(Li

35、nk)malloc(sizeof(LNode));　　if(!p)　　exit(OVERFLOW);　　p->data=a; 　　Link q=L->next;<

36、p>　　q->prior=p;　　p->next=q;　　L->next=p;　　p->prior=L;　　return OK;　　}&l

37、t;p>　　Status ToNum(char*s,int i,long &e){　　//將字符串s的前i位轉(zhuǎn)換為正數(shù)，并由e保存　　sum=0;　　for(m=1,n=1;m<=i;n=n*10) //n的值每次是原來的10倍&l

38、t;p>　　{　　sum+=(*(s-m)-'0')*n; //轉(zhuǎn)換成相應(yīng)的數(shù)字　　m++;　　}　　e

39、=sum;　　return OK;　　Status CreatNum(Link &L,char*s){　　//將字符串轉(zhuǎn)分割成很多部分，每部分轉(zhuǎn)換為數(shù)字后存在一個鏈表結(jié)點中。　　InitLinkList(L,s[0]);

40、　　if(*s=='-')　　{ InitLinkList(L,s[0]); s++;　　}　　else　　InitLinkList(L,s[0]);<

41、;/p>　　while(*s!='\0')　　{　　if(*s==',')　　{ ToNum(s,i,e);　　Insert(L,e);<

42、p>　　i=-1; //因為這是已經(jīng)將某一個逗號前i個字符變成數(shù)字加入 　　} //數(shù)字鏈表中，逗號不算本次　　i++;　　s++;&l

43、t;b>　　}　　ToNum(s,i,e); 　　Insert(L,e);　　}　　int CountNode(Link L){　　//計算鏈表L的結(jié)點數(shù)</

44、p>　　Link p=L->next;　　while(p!=L)　　{　　i++;　　p=p->next;<

45、b>　　}　　return i;　　}　　BOOL Compare(Link &L1,Link &L2){　　//比較鏈表L1和L2的大小，如果L1大于L

46、2,返回1,如果L2大于L1,返回-1,如果相等，返回0　　{　　if(CountNode(L1)>CountNode(L2))　　// L1大于L2　　else if(CountNode(

47、L1)<CountNode(L2))　　L2大于L1　　else{　　p1=L1->next,p2=L2->next;　　while(p1!=L1&&p2!=L2

48、)　　{　　if(p1->data>p2->data)　　// L1大于L2　　if(p1->data<p2->data)<p&g

49、t;　　return -1;　　p1=p1->next;　　p2=p2->next;　　}　　}　　L1和L2相等</

50、b>　　}　　Link Add(Link &L1,Link &L2,char op) 主要函數(shù)　　//將字符串L1和L2的數(shù)據(jù)相加，得到的結(jié)果鏈表頭結(jié)點指針返回　　Link Sub(L

51、ink L1,Link L2,char op) 主要函數(shù)　　//將字符串L1和L2的數(shù)據(jù)相減，得到的結(jié)果鏈表的頭結(jié)點指針返回　　void EraseZero(Link &L)　　{//刪除鏈表L的無效零元素結(jié)點　　p=L->

52、;next,q;　　while(p->data==0&&p->next!=L)　　{　　q=p;　　p=p->next;

53、　　p->prior=q->prior;　　free(q);　　}　　L->next=p;　　}

54、　Link Compute(Link &L1,Link &L2,char Ope) //主要函數(shù)　　//對鏈表L1和鏈表L2進(jìn)行計算，即相加，相減等等　　void Interface() 　　//界面函數(shù),顯示操作的主界面　　Sta

55、tus print(Link L){　　//順次打印鏈表L中的數(shù)據(jù)　　EraseZero(L);　　if(*s<48&&*s!='-'||*s>57) //第一個不是數(shù)字也不是-，則出錯　　return

56、ERROR;　　if(*s=='-') k=0;　　else k=1;　　i=1;　　while(*(s+i)!='\0')<b

57、>　　{　　if(*(s+i)!=','&&(*(s+i)>57||*(s+i)<48))　　return ERROR;　　i++;　　}<

58、/b>　　i=1;　　while(*(s+i)!=','&&*(s+i)!='\0') {　　i++;　　k++;</

59、b>　　}　　if(k>5)　　return ERROR;　　if(*(s+i)=='\0')　　return OK;<

60、/p>　　k=4;　　while(*(s+i)!='\0')　　{　　if(*(s+i)==',')　　{</b

61、>　　if(k!=4)　　return ERROR;　　k=-1; //此時逗號字符不能在四個數(shù)字的計算之中　　}&

62、lt;p>　　k++;　　i++;　　}　　if(k!=4) //最后一個逗號后必須有四個數(shù)<p&g

63、t;　　return ERROR;　　return OK;　　函數(shù)調(diào)用關(guān)系圖：　　調(diào)試分析 　　1.實際完成的功能有：長整數(shù)的加法和減法，支持的數(shù)據(jù)類型是整形，能夠?qū)Ξ惓］斎脒M(jìn)行判斷，打印和計算的

64、時候能夠消除可能出現(xiàn)的前置零。　　2.程序的主要函數(shù)compute時間復(fù)雜度為O(n)，其實n為計算的兩個鏈表的結(jié)點個數(shù)的較大值。物理存儲使用的是雙向鏈表，有兩個指針域，空間消耗在合理范圍之內(nèi)　　3.調(diào)試中由于是雙向鏈表，在插入時應(yīng)該注意將prior域進(jìn)行考慮，剛開始寫程序時忘記，導(dǎo)致輸出結(jié)果錯誤。清楚前置零的時候開始沒有考慮輸入數(shù)據(jù)全是零的時候，結(jié)果將

65、全部的數(shù)據(jù)結(jié)點都給刪除，最后沒有結(jié)果輸出，調(diào)試中發(fā)現(xiàn)這個問題，應(yīng)該將每個鏈表至少保存一個數(shù)據(jù)結(jié)點。　　4.由于時間倉促，而且長整數(shù)四則運算的乘法一直沒有想到好的辦法，如果再有幾天時間，乘法這個功能完全可以加上。隨之就可以完成乘方的計算　　5.本程序還有很大的擴(kuò)充地方，應(yīng)該可以將程序由正數(shù)擴(kuò)充為浮點數(shù)，能夠運行更復(fù)雜的數(shù)據(jù)，如求階乘，開方等功能。如果實現(xiàn)了

66、，則這個計算器的功能方面就可以和windows系統(tǒng)自帶的計算器媲美了。　　五、測試結(jié)果　　列出你的測試結(jié)果，包括輸入和輸出。注意測試數(shù)據(jù)應(yīng)該完整和嚴(yán)格，至少給出2組測試結(jié)果（含合法數(shù)據(jù)與非法數(shù)據(jù)）。　　輸入0;0，輸出0

67、;　　輸入1,0001,0001;-1,0001,0001；輸出0　　輸入1,0001,0001；-1,0001,0000；輸出1　　輸入-9999,9999；-9999；9999；輸出-1,9999,9998　　非法數(shù)據(jù)<

68、p>　　1,000；000,1；輸出“輸入錯誤”　　六、用戶手冊　　說明如何使用你編寫的程序，詳細(xì)列出每一步的具體操作步驟。這里可以有適當(dāng)?shù)倪\行結(jié)果抓圖。用戶手冊與開發(fā)過程無關(guān)，只與使用有關(guān)，必須是Step by Step的。 　　所有運行結(jié)果截圖均要求有實際數(shù)據(jù)的內(nèi)容

69、，截圖尺寸要求按頁寬排版兩張大小，且要求有每張圖下面有規(guī)范的標(biāo)題說明如何使用你編寫的程序，詳細(xì)列出每一步的操作步驟。　　1.進(jìn)入操作主界面　　2．按照命令提示操作　?、胚x1，進(jìn)入加法運算　?、佥斎氲谝粋€操作數(shù)：并且按照提示格式輸入&l

70、t;/p>　　如果輸入錯誤，比如1,000，則程序會提示錯誤，重新輸入　?、谌绻斎胝_，比如輸入1,0000，輸入下一個數(shù)　?、圯斎胝_，如輸入9999,9999 則計算出結(jié)果　?、茌敵雒總€鏈表中的結(jié)點值，便于觀察比較　　⑤輸出結(jié)果1,000

71、0,9999　　⑵選2，進(jìn)入減法運算　?、佥斎氲谝粋€操作數(shù)，并按照提示的格式輸入　　如果輸入錯誤，比如，10,000，程序會提示輸入錯誤，重新輸入　?、谌绻斎胝_，比如9999,9999，輸入下一個數(shù)。　　③第二個數(shù)也輸入正確，

72、比如輸入10,0000，輸出結(jié)果　　④提示是否繼續(xù)計算，選擇Y或者y退出，其他任意鍵繼續(xù)操作　　七、體會與自我評價 　　長整數(shù)四則運算的一些思考　　這次的課程設(shè)計中，長整數(shù)四則運算這個實驗給了我很大的挑戰(zhàn)，在設(shè)計中遇到了很多的困難，比如如何用如何將字符數(shù)據(jù)分割成很多部分存

73、儲進(jìn)雙向循環(huán)鏈表，如何判斷輸入的字符串是否是正確的；在輸入特殊數(shù)據(jù)買比如0000,00000時，程序能夠消除無用的前置零得出正確的結(jié)果，我在這些問題上都考慮的很久，一點點的攻破難題，　　而在這次實驗中我對長正數(shù)的各種運算也有了一定的認(rèn)識，對于特別長的數(shù)的計算，只能先求局部結(jié)果，最后將局部結(jié)果綜合起來，得到最終結(jié)果。比如加法就是從最低位開始計算，判斷進(jìn)位后再一次向高位計算，最終得到結(jié)果。計算加法的

74、時候，由于是每四位一個結(jié)點，所以是以萬位為進(jìn)制。輸出時如果一個結(jié)點中數(shù)據(jù)是以為，則前面輸出三個零，如果是兩位，則輸出兩個零，如果是三位，則輸出一個零，四位數(shù)直接輸出。如果節(jié)點數(shù)據(jù)為零，則按第一種情況輸出是前面加三個零即可。為了程序的健壯性，應(yīng)該考慮負(fù)數(shù)和正數(shù)相加的情況，如果一個較大的正數(shù)加上一個數(shù)值較小的負(fù)數(shù)，應(yīng)該是大數(shù)減去去掉振幅符號的小數(shù)，即可。如果是一個較小的正數(shù)加上一個數(shù)值較大的負(fù)數(shù)，則應(yīng)該是去掉正負(fù)號的負(fù)數(shù)減去正數(shù)，最后在結(jié)果

75、里加上一個負(fù)號即可。　　乘法的基本思想是相加，但是在雙向循環(huán)鏈表中，如果乘數(shù)很大的時候，單純的相加要進(jìn)行很多次，效率上完全不夠滿足要求，一般是用字符串直接按位相乘，按豎式結(jié)構(gòu)計算。　　除法的實現(xiàn)可以用減法，但是問題還是和乘法一樣，如果數(shù)字太大的話，用雙向循環(huán)鏈表，要進(jìn)行的減法次數(shù)也是很龐大的。　　以上是我對長整數(shù)

眾賞文庫> 全部分類> 畢業(yè)設(shè)計

溫馨提示

1. 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2. 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3. 本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 眾賞文庫僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-長整數(shù)運算

文檔簡介

溫馨提示

最新文檔

評論

數(shù)據(jù)結(jié)構(gòu)課程設(shè)計報告-長整數(shù)運算

文檔簡介

溫馨提示

最新文檔

評論

免費下載