大整數(shù)的運算 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計

1、目 錄 一、題目概述（內(nèi)容及要求）3二、功能分析4三、設(shè)計5四、運行與測試6五、總結(jié)22六、參考文獻23一、 題目概述（內(nèi)容及要求）內(nèi)容： 請設(shè)計一個有效的算法，可以進行兩個n位大整數(shù)的四則運算。 長整數(shù)長度在二十位以上。 實現(xiàn)兩長整數(shù)的加、減、乘、除操作。要求： 1.設(shè)計數(shù)據(jù)結(jié)構(gòu)，存儲結(jié)構(gòu)； 2.在c兼容環(huán)境完成上述題目的代碼編寫與調(diào)試； 3.程序運行界面交互性好； 4.軟件運行，給出測試數(shù)據(jù)。二、功能分析1. 設(shè)計一個實現(xiàn)長整數(shù)進行四則運算的程序，長整數(shù)長度在二十位以上，有正負數(shù)的區(qū)別。2. 輸入每四位一組，組間用逗號隔開，長整數(shù)位數(shù)沒有上限，以分號結(jié)束長整型數(shù)據(jù)的輸入。用lnode結(jié)點數(shù)

2、據(jù)結(jié)構(gòu)存儲數(shù)據(jù)。每一個數(shù)據(jù)有一個頭結(jié)點，它的data域用來放數(shù)據(jù)的正負數(shù)。其余結(jié)點的數(shù)都為正整數(shù)。3. 程序包含數(shù)據(jù)的輸入，判斷，運算,輸出和主函數(shù)。4. 具體程序執(zhí)行的命令包括:a) 輸入函數(shù)：inputa();inputb();/的輸入并建立雙向循環(huán)鏈表b) 判斷函數(shù)：compare();/比較數(shù)據(jù)的大小c) 運算函數(shù)：unsigndeadd();/無符號的加法a) unsigndesub();/無符號的減法b) add();sub();mul();div();/加減乘除四則運算d) 輸出函數(shù)：divput();/除法結(jié)果的輸出函數(shù)a) putoutc();/其余結(jié)果的輸出函數(shù)e) 主函數(shù)

3、：main()；5. 系統(tǒng)功能結(jié)構(gòu)框圖圖2.1 系統(tǒng)功能結(jié)構(gòu)框圖三、設(shè)計首先要考慮的是如何表示長整型數(shù)?？梢?位數(shù)形成1組，而一個長整型數(shù)可能會有很多組這種4位數(shù)，而每節(jié)之間是有先后順序的，因此我們可以考慮用數(shù)組和鏈表來存儲數(shù)據(jù)。(1)再考慮到每個長整型數(shù)的長度在輸入之間是無法預(yù)知的，因此使用鏈表在存儲空間的分配上更方便一些。(2)在輸入數(shù)據(jù)時總是從高位到低位地存儲，而計算時總是從低位向高位運算，因此采用雙向鏈表更方便，而為了從頭結(jié)點方便地轉(zhuǎn)到尾結(jié)點可以采用循環(huán)鏈表。綜上考慮，應(yīng)以雙向循環(huán)鏈表表示長整數(shù)，每個結(jié)點含一個整型變量，且僅絕對值不超過9999的整數(shù)，整個鏈表用十進制數(shù)表示。(3)對于

4、每一個長整型數(shù)可以設(shè)置一個頭結(jié)點，其中的數(shù)據(jù)域用來表示該長整型數(shù)的正負號及組數(shù)，該值的符號則表示該長整型數(shù)的符號，該數(shù)的絕對值表示該長整型數(shù)包含的4位數(shù)的組數(shù)。第一個存儲4位數(shù)據(jù)組的結(jié)點稱為首結(jié)點，而最后一個4位數(shù)據(jù)組結(jié)點稱為尾結(jié)點。為此需要結(jié)構(gòu)數(shù)據(jù)類型：雙向循環(huán)鏈表：typedef struct lnode/結(jié)點結(jié)構(gòu)體int data;struct lnode *next;struct lnode *prior;lnode,*lnodelist主要的模塊可分為： 輸入函數(shù)：inputa();inputb();/的輸入并建立雙向循環(huán)鏈表 判斷函數(shù)：compare();/比較兩個數(shù)據(jù)的大小，進行

5、相應(yīng)的的計算。 運算函數(shù)：add();sub();mul();div();/運算 輸出函數(shù)：divput();putoutc();/除法的輸出及其他運算的輸出。 主函數(shù)：main()；四、運行與測試 圖4.1長整數(shù)加法運行結(jié)果圖實現(xiàn)以上加法操作的程序如下：int add(lnodelist &ahead,lnodelist &bhead)int e,acount=0,bcount=0,q;e=ahead-data*bhead-data;cout輸出運算結(jié)果為:data=-1)coutdata=-1)coutdata=1)coutdata*bhead-data;cout輸出運算結(jié)果為:data=

6、-1)coutdata=-1)coutdata=1)coutdata*bhead-data;cout輸出運算結(jié)果為:endl;if(e=-1)coutnext;pb=bhead-next;p=chead=new lnode;/頭結(jié)點p-data=0;p-next=p;p-prior=p;pc=cnow=chead;while(pb!=bhead)carry=0;while(pa!=ahead)multi=pa-data*pb-data+carry;carry = multi/10000;if(pc-prior=chead)p=new lnode; p-data=multi%10000; p-n

7、ext=chead-next; chead-next-prior=p; chead-next=p; p-prior=chead;elsemulti=pc-prior-data+multi%10000;pc-prior-data=multi%10000;carry=carry+multi/10000;pc=pc-prior; pa=pa-next;if(carry!=0)p=new lnode; p-data=carry; p-next=chead-next; chead-next-prior=p; chead-next=p; p-prior=chead;cnow=cnow-prior;pc=c

8、now;pa=ahead-next;pb=pb-next;putoutc(chead);return OK;圖4.4長整數(shù)除法運行結(jié)果圖實現(xiàn)以上除法操作的程序如下：int divput(lnode *chead)lnode *s,*pr;pr=chead-prior; if(pr!=chead) coutdata;pr=pr-prior;while(pr!=chead)if(pr-data=0)coutdata0&pr-data10)coutdata=10&pr-data100)coutdata=100&pr-data1000)cout0;coutdata;s=pr;pr=pr-prior;d

9、elete s;coutendl;return 0;int div(lnodelist &ahead,lnodelist &bhead)cout輸出運算結(jié)果為:data*bhead-data;cout輸出運算結(jié)果為:endl; cout商為;if(e=-1)cout-;while(borrow=0)compare(ahead,bhead,q);if(q=0)borrow=1;cout+count，余數(shù)為0endl;else if(q=-1)borrow=1;coutcountnext;pb=bhead-next;while(pa!=ahead&pb!=bhead)diffe=pa-data-b

10、orrow-pb-data;if(diffedata=diffe;pa = pa-next;pb = pb-next;if(pa!=ahead)while(pa!=ahead)diffe=pa-data-borrow;if (diffedata=diffe;pa=pa-next;p=pa-prior;while(p-data=0&p-prior!=ahead)s=p;p=p-prior;ahead-prior=p;p-next=ahead;delete s;return 0;附錄（其它代碼實現(xiàn)）：第一部分：#includeusing namespace std;#define OK 1;#de

11、fine FALSE 0;typedef struct lnode /結(jié)點結(jié)構(gòu)體int data;struct lnode *next;struct lnode *prior;lnode,*lnodelist;int compare(lnodelist &ahead,lnodelist &bhead,int &q)/比較a和b的大小lnode *pa,*pb;int bcount=0,acount=0;pa=ahead-next;pb=bhead-next;while(pa!=ahead)acount+;pa=pa-next;while(pb!=bhead)bcount+;pb=pb-next

12、;if(acountbcount)q=1;else if(acountprior;pb=bhead-prior;while(pa-data=pb-data)&(pa-prior!=ahead)pa=pa-prior; pb=pb-prior;if(pa-datapb-data)q=1;else if(pa-datadata)q=-1;else q=0;return 0;int inputa(lnodelist &ahead)/輸入長整數(shù)alnode *p;char ch; int afirst;cout請輸入第一個無符號長整型數(shù)，要求每四位用逗號隔開末尾為分號:data=0;p-next=p;

13、p-prior=p;cinafirstch;/輸入第一個結(jié)點數(shù)據(jù)if(afirstdata=-1;afirst=-afirst;else ahead-data=1;p=new lnode;p-data=afirst;p-next=ahead;ahead-prior=p; ahead-next=p;p-prior=ahead; while(ch!=;)cinafirstch;p=new lnode; p-data=afirst; p-next=ahead-next;ahead-next-prior=p;ahead-next=p;p-prior=ahead;return OK;int inputb

14、(lnodelist &bhead)/輸入長整數(shù)blnode *p;char ch; int bfirst;cout請輸入第二個無符號長整型數(shù)，要求每四位用逗號隔開末尾為分號:data=0;p-next=p;cinbfirstch;/輸入第一個結(jié)點數(shù)據(jù)if(bfirstdata=-1; bfirst=-bfirst;else bhead-data=1;p=new lnode;p-data=bfirst;p-next=bhead; bhead-prior=p;bhead-next=p;p-prior=bhead;while(ch!=;)cinbfirstch;p=new lnode; p-dat

15、a=bfirst; p-next=bhead-next;bhead-next-prior=p;bhead-next=p;p-prior=bhead;return OK;void putoutc(lnode *chead)/輸出結(jié)果lnode *s,*pr;pr=chead-next;if(pr!=chead)coutdata; pr=pr-next;while(pr!=chead)if(pr-data=0)coutdata0&pr-data10)coutdata=10&pr-data100)coutdata=100&pr-data1000)cout0;coutdata;s=pr;pr=pr-n

16、ext;delete s;coutnext;pb=bhead-next;p=chead=new lnode;/頭結(jié)點p-data=0;p-next=p;p-prior=p;while(pa!=ahead&pb!=bhead)sum=pa-data+pb-data+carry;p=new lnode;p-data=sum%10000;carry = sum/10000; p-next=chead-next;chead-next-prior=p;chead-next=p;p-prior=chead;pa=pa-next;pb=pb-next;if(pa!=ahead)/a還沒有處理完，把a剩下的數(shù)

17、字加到和上while(pa!=ahead)sum=pa-data+carry;p=new lnode;p-data=sum%10000; p-next=chead-next;chead-next-prior=p;chead-next=p;p-prior=chead;carry = sum/10000;pa=pa-next;if(pb!=bhead)/b還沒有處理完，把b剩下的數(shù)字加到和上while(pb!=bhead)sum=pb-data+carry;p=new lnode;p-data=sum%10000; p-next=chead-next; chead-next-prior=p; ch

18、ead-next=p; p-prior=chead; carry = sum/10000; pb=pb-next;if(carry)/如果最后一位有進位，就申請一個結(jié)點存儲p=new lnode;p-data=carry;p-next=chead-next;chead-next-prior=p;chead-next=p;p-prior=chead;putoutc(chead);return OK;int unsigndesub(lnodelist &ahead,lnodelist &bhead)/無符號長整數(shù)的減法a比b大。int diffe,borrow=0; /借位lnode *pa,*p

19、b,*chead;lnode *p;pa=ahead-next;pb=bhead-next;p=chead=new lnode;/頭結(jié)點p-data=0;p-next=p;p-prior=p;while(pa!=ahead&pb!=bhead)diffe=pa-data-borrow-pb-data;if (diffedata=diffe; p-next=chead-next;chead-next-prior=p;chead-next=p;p-prior=chead;pa = pa-next;pb = pb-next;if(pa!=ahead)while(pa!=ahead)diffe=pa-data-borrow; if (diffedata=diffe; p-next=chead-next; chead-next-prior=p; chead-next=p; p-prior=chead; pa=pa-next;while (p-data=0&p-next!=chead)lnode *s;s=p;p=p-next;chead-next=p;p-prior=chead;delete s;putoutc(chead);return OK;第二部分：int xuan(int &c) cout 開始菜單 endl;cout*請選擇要進行的操作:*