長整數(shù)的加減運算系統(tǒng)說明文檔11003601

1、桂林電子科技大學綜合設(shè)計說明書用紙 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計說明書題 目： 長整數(shù)的加減運算 學 院： 計算機科學與工程學院 專 業(yè)： 信 息 安 全 姓 名： xxxxxxxx 學 號： 11003601xx 指導教師： 張 瑞 霞 老 師 2013年 9 月 13 日桂林電子科技大學綜合設(shè)計說明書用紙 第 21 頁 成績評定標準及成績1、 能按照格式進行寫作，無抄襲現(xiàn)象（10分）2、 報告內(nèi)容行文通暢，有條理性，無錯別字，結(jié)構(gòu)嚴謹。（10分）3、 能夠按照數(shù)據(jù)結(jié)構(gòu)課設(shè)的格式要求、排版要求和字數(shù)要求等，有需求分析，系統(tǒng)分析，詳細設(shè)計，關(guān)鍵技術(shù)的介紹和參考文獻。（10分）4、 在驗收過程中，能合

2、理的回答問題（20分）5、 軟件能正常運行，實現(xiàn)所提出的功能（40分）6、 軟件代碼規(guī)范性較好（5分）7、 具有自己的創(chuàng)新或特色（5分） 總成績： 目 錄1、前言22、需求分析32.1.問題描述：32.2.基本要求：42.3.更高要求：42.4.測試數(shù)據(jù)：42.5.開發(fā)環(huán)境 Visual C+6.0(完整綠色版）43、系統(tǒng)概述53.1.關(guān)鍵技術(shù)。53.2.相關(guān)的函數(shù)接口63.3.功能設(shè)計64、系統(tǒng)分析75、系統(tǒng)的調(diào)試與結(jié)果165.1.調(diào)試過程出現(xiàn)的問題以及解決方法165.2.成功的測試數(shù)據(jù)截圖176、課設(shè)小結(jié)197、參考文獻：201、前言本系統(tǒng)主要內(nèi)容是為數(shù)據(jù)結(jié)構(gòu)長整數(shù)加法的實現(xiàn)，所以整個程序

3、是為了實現(xiàn)長整數(shù)的加減法運算。設(shè)計一個實現(xiàn)任意長的整數(shù)間進行四則運算的程序，要求完成長整數(shù)的加運算和減運算。長整數(shù)的長度沒有限制，可以是任意長，正確處理好運算之后的進位和借位。每個結(jié)點中可以存放的最大整數(shù)為215-1=32767，才能保證兩數(shù)相加不會溢出。但若這樣存，即相當于按32768進制數(shù)存，在十進制數(shù)與32768進制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個結(jié)點中僅存十進 制數(shù)4位，即不超過9999的非負整數(shù)，整個鏈表視為萬進制數(shù)?？梢岳妙^結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不

4、能給長整數(shù)位數(shù)規(guī)定上限。由于在某些工程上進行加減運算時，有時候需要對很大的長整數(shù)進行計算，但是計算機本身提供的數(shù)據(jù)類型無法保證存在幾百位甚至幾千位的數(shù)字，所以需要設(shè)計專門的算法系統(tǒng)對數(shù)據(jù)進行相應(yīng)的計算。因此本系統(tǒng)的設(shè)計主要任務(wù)是：設(shè)計一個程序能夠?qū)崿F(xiàn)任意長整數(shù)的加減運算的程序，而且能夠?qū)σ恍╁e誤異常進行辨別調(diào)整，從而迅速計算出正確無誤的結(jié)果。程序輸入格式是字符串，包含元素的范圍是數(shù)字，都好，負號以及分號，保存時需要用到雙鏈表將字符串每四位保存在循環(huán)鏈表中的一個結(jié)點中，然后在計算出運行結(jié)果。雖然程序有些復(fù)雜，但使用方法十分簡單，只需按照相關(guān)提示進行操作即可，能夠為用戶的學習和工作帶來快捷與方便。

5、2、需求分析 本系統(tǒng)主要內(nèi)容是為數(shù)據(jù)結(jié)構(gòu)長整數(shù)加法的實現(xiàn)，所以整個程序是為了實現(xiàn)長整數(shù)的加減法運算。設(shè)計一個實現(xiàn)任意長的整數(shù)間進行四則運算的程序，要求完成長整數(shù)的加運算和減運算。長整數(shù)的長度沒有限制，可以是任意長，正確處理好運算之后的進位和借位。2.1.問題描述：首先最初的目的是設(shè)計一個實現(xiàn)任意長的整數(shù)進行加法運算的演示程序。2.2.基本要求：利用雙向循環(huán)鏈表實現(xiàn)長整數(shù)的存儲，每個結(jié)點含一個整型變量。任何整型變量的范圍是（2151）（2151）。輸入輸出形式：按照中國對于長整數(shù)的表示習慣，每四位是一組，組間用逗號隔開。2.3.更高要求：（1） 僅僅是能運行長整數(shù)的加法，還是不能達到我們運算的需

6、求，因此，對于長整數(shù)的減法運算的設(shè)計將是對我們系統(tǒng)更高的一次挑戰(zhàn)。（2）多個長整數(shù)的連續(xù)加減法，并帶括號等。具體方式可以參見表達式的求值部分，利用棧。2.4.測試數(shù)據(jù)：（1）0；0；應(yīng)輸出“0”。（2）2345，6789；7654，3211；應(yīng)輸出“1，0000，0000”。（3）9999，9999；1，0000，0000，0000；應(yīng)輸出“9999，0000，0001”。（4）1，0001，0001；1，0001，0001；應(yīng)輸出“0”。（5）1，0001，0001；1，0001，0000；應(yīng)輸出“1”。（6）9999，9999，9999；9999，9999，9999；應(yīng)輸出“1，9999，

7、9999，9998”。（7）1，0000，9999，9999；1；應(yīng)輸出“1，0001，0000，0000”。注：實現(xiàn)提示：（1）每個結(jié)點中可以存放的最大整數(shù)為215132767，才能保證兩數(shù)相加不會溢出。但若這樣存，即相當于按32768進制數(shù)存，在十進制數(shù)與32768進制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個結(jié)點中僅存十進制數(shù)的4位，即不超過9999的非負整數(shù)。整個鏈表是為萬進制數(shù)。（2） 可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。2.5.開發(fā)環(huán)境

8、Visual C+6.0(完整綠色版） Visual C+ 6.0 （完整綠色版）使用說明： 1、軟件安裝后，在桌面和開始菜單里分別建立快捷方式。2、此版本適用于計算機等級考試上機環(huán)境及一般的C+應(yīng)用。3、此版本為默認安裝后對安裝文件夾完整打包，并安裝windowssystem32下的相應(yīng)文件。4、系統(tǒng)默認安裝在：C:Program FilesMicrosoft Visual Studio 。5、VC6.0通用補?。禾貏e適合于解決錯誤信息：“Compiling. , Error spawning cl.exe” 使用方法：退出VC，運行此文件，單擊"是"，再啟動VC，可解決

9、大部分問題。6、 系統(tǒng)安裝后，如果考試系統(tǒng)提示沒有安裝VC，不影響使用，自行從桌面的快捷方式啟動vc， 然后打開需要調(diào)試的程序，調(diào)試即可，不影響考試系統(tǒng)評分。3、系統(tǒng)概述3.1.關(guān)鍵技術(shù)。3.1.1存儲結(jié)構(gòu)：循環(huán)雙向鏈表。 循環(huán)鏈表是將單鏈表的形式稍作改變，不讓最后一個結(jié)點的指針指為NULL，而讓它指向頭一個結(jié)點；雙鏈表給運算帶來的最大好處是可以很容易地找到結(jié)點的前驅(qū)和后繼。將雙鏈表的頭一個結(jié)點和最后一個結(jié)點連接起來，這樣不增加額外存儲卻給某些運算帶來方便。 圖3.1.1.加入頭結(jié)點的循環(huán)雙鏈表3.1.2.主要算法的基本思想： 每個結(jié)點中可以存放的最大整數(shù)為215-1=32767，才能保證兩數(shù)

10、相加不會溢出。但若這樣存，即相當于按32768進制數(shù)存，在十進制數(shù)與32768進制數(shù)之間的轉(zhuǎn)換十分不方便。故可以在每個結(jié)點中僅存十進 制數(shù)4位，即不超過9999的非負整數(shù)，整個鏈表視為萬進制數(shù)。 可以利用頭結(jié)點數(shù)據(jù)域的符號代表長整數(shù)的符號。用其絕對值表示元素結(jié)點數(shù)目。相加過程中不要破壞兩個操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡化程序結(jié)構(gòu)的一種方法。不能給長整數(shù)位數(shù)規(guī)定上限。3.1.3.數(shù)據(jù)結(jié)構(gòu)設(shè)計： 因為計算的事一個連續(xù)的數(shù)字，需要按順序一次計算，所以采用的數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)是線性表。根據(jù)用戶需求每一個結(jié)點只存儲四位數(shù)字，為了將數(shù)字連接起來，采用的數(shù)據(jù)結(jié)構(gòu)的存儲結(jié)構(gòu)是鏈式。3.2.相關(guān)

11、的函數(shù)接口3.2.1.結(jié)構(gòu)體：struct dl_nodeint x;dl_node *pre;dl_node *next;3.2.2.初始化：void list_init(dl_node * h) 3.2.3.插入元素：void list_insert(dl_node *h,int x)3.2.4.輸出鏈表：void prin(dl_node *h)3.2.5.實現(xiàn)相加：void list_add(dl_node *h1,dl_node *h2)3.2.6.實現(xiàn)相減：void list_sub(dl_node *h1,dl_node *h2)3.3.功能設(shè)計3.3.1.輸入兩個數(shù)，用鏈表來存

12、儲。鏈表的頭結(jié)點的數(shù)據(jù)的值為1時，表示的是輸入的數(shù)非負；為-1時表示輸入的數(shù)是負數(shù)。3.3.2.在創(chuàng)建鏈表時，讓高位在鏈表的尾部，低位在鏈表的頭部。3.3.3.在做加法時，先判斷兩個數(shù)的符號是否相同，如果相同，在根據(jù)加數(shù)的符號，決定和數(shù)的符號，取兩個數(shù)的絕對值做加法，但是的處理進位。3.3.4.如果異號，用一函數(shù)來判斷和的符號，判斷異號的兩個數(shù)相加和的符號，當兩個數(shù)的長度不相等時，取較長數(shù)的符號作為和的符號，否則比兩個數(shù)的大小，再決定和的符號。3.3.5.異號的兩個數(shù)想加時，先去兩個數(shù)的絕對值，用較大的數(shù)減去較小的數(shù)，差作為和的絕對值。如果相應(yīng)的位夠減時，直接做減法，否則借位，但是要注意被借位

13、的值是否為零，如果為零，則繼續(xù)借位。3.3.6.輸出最終結(jié)果，輸出數(shù)時，要去掉大數(shù)最前面的零，直到數(shù)的首位不是零時為止。在輸出地位的數(shù)時，有可能某些單元的數(shù)低于四位，必須要在四位數(shù)的高位補零，即四位一個單元輸出?？杖碧幱昧阊a齊。4、系統(tǒng)分析 對于本系統(tǒng)而言： 如果是兩個長整數(shù)相加，每個加數(shù)都需要一個循環(huán)鏈表存儲，則必須定義兩個循環(huán)鏈表h1、h2，即：循環(huán)雙鏈表；while(p!=h) 循環(huán)雙向鏈表一直往右找，直到找到頭結(jié)點為止printf(",%04d",p->x);%04d為對齊方式，當一個結(jié)點值不足4位則補齊p=p->next;puts("&quo

14、t;);元素值相加，已處理好h1比h2的長度大于等于h1的長度最后結(jié)果保存在h1（即長串中）void list_add(dl_node *h1,dl_node *h2)dl_node *p=h1->pre,*q=h2->pre;int e=0;while(q!=h2)每次相加，如果有進位則保存到e變量中int tmp=p->x+q->x+e;if(tmp>9999)p->x=tmp%10000;e=tmp/10000;elsep->x=tmp; p=p->pre; q=q->pre;當h1長度大于h2的時候，還要對未相加的部分進行操作whi

15、le(p!=h1)int tmp=p->x+e;if(tmp>9999)p->x=tmp%10000;e=tmp/10000;else p->x=tmp; p=p->pre;p=h1->next;如果最高位得到的結(jié)果還有進位，那么就要再創(chuàng)建一個結(jié)點if(e!=0)dl_node *s;s=(dl_node *)malloc(sizeof(dl_node);s->x=e;s->pre=p->pre;p->pre->next=s;s->next=p;p->pre=s;元素值相減 方法同相加類似最后結(jié)果保存在h1（即長串中

16、）void list_sub(dl_node *h1,dl_node *h2)dl_node *p=h1->pre,*q=h2->pre;此處flag的值即位借位的值，借位的值為0或者為1，因為減0無關(guān)緊要int flag=0;while(q!=h2)if(p->x-flag>=q->x)p->x-=q->x+flag;flag=0;elsep->x=p->x+10000-q->x-flag;flag=1;p=p->pre;q=q->pre;同樣的，如果h1的長度大于h2的長度，那么對剩下的操作while(p!=h1)if

17、(p->x-flag<0)p->x=p->x+10000-flag;flag=1;elsep->x=p->x-flag;flag=0;p=p->pre;如果最高位為0的話，那么就要刪除最高位的結(jié)點了p=h1->next;while(p->x=0)p->pre->next=p->next;p->next->pre=p->pre;p=h1->next;打印輸入提示int main()cout<<"-"<<endl;cout<<"桂林電子科

18、技大學 計算機科學與工程學院 信息安全 "<<endl;cout<<""<<endl;cout<<""<<endl;cout<<" 11003601班 羅宗聰 "<<endl;cout<<""<<endl;cout<<"-"<<endl;cout<<" 歡迎使用-長整數(shù)的加減運算-系統(tǒng) "<<endl<&l

19、t;endl;cout<<"請輸入兩個任意長整數(shù)，并以 ; 隔開，然后Enter"<<endl;cout<<""<<endl; cout<<"如：1314,5210 + 5210,1314"<<endl;cout<<" 1314,5210；"<<endl;cout<<" 5210,1314；"<<endl;cout<<" 6524,6524"&l

20、t;<endl;cout<<"-"<<endl; / freopen("大數(shù)求和.txt","r",stdin);while(1)puts("");char c;int a;dl_node *h1,*h2;list_init(&h1);輸入元素，直到讀入 " ; "則停止輸入第一個鏈表值while(1) /cout<<"asdfa"scanf("%d%c",&a,&c);/cout<&

21、lt;c<<endl;list_insert(h1,a);if(c='') break;如果第一個元素小于0，則取負值，并在頭結(jié)點當中保存信息if(h1->next->x<0)h1->x=-h1->x;h1->next->x=-h1->next->x;/prin(h1);list_init(&h2);int r=0;相同方法輸入第二個鏈表，碰到 " ; "則停止，并且讀到文件結(jié)束while(1)if(scanf("%d%c",&a,&c)=EOF)

22、r=1;break;list_insert(h2,a);if(c='')break;/cout<<r<<endl;如果第一個元素小于0，則取正值，并在頭結(jié)點當中保存信息if(h2->next->x<0)h2->x=-h2->x;h2->next->x=-h2->next->x;/h1_num和h2_num分別表示長度int h1_num=h1->x,h2_num=h2->x;把長的放到h1里面，是為了后面的加減操作更順利if(abs(h1_num)<abs(h2_num)dl_nod

23、e *tmp=h1;h1=h2;h2=tmp;h1_num=h1->x,h2_num=h2->x;/cout<<h1_num<<" "<<h2_num<<endl;此處為重點部分，分為兩個部分，如果h1大于h2四種情況如果h1等于h2也有四種情況如果他們的長度不相等，即h1大于 h2了if(abs(h1_num)!=abs(h2_num)如果都為正數(shù)if(h1_num>0&&h2_num>0)/prin(h1);list_add(h1,h2);prin(h1);continue;如果都為

24、負數(shù)elseif(h1_num<0&&h2_num<0)list_add(h1,h2);cout<<"-"prin(h1);continue;如果h1為正而h2為負else if(h1_num>0&&h2_num<0)list_sub(h1,h2);prin(h1);continue;如果h1為負而h2為正elseif(h1_num<0&&h2_num>0)cout<<"-"list_sub(h1,h2);prin(h1);否則，如果他們長度都相等

25、的話：else如果都為正數(shù)if(h1_num>0&&h2_num>0)list_add(h1,h2);prin(h1);continue;如果都為負數(shù)else if(h1_num<0&&h2_num<0)list_add(h1,h2);cout<<"-"prin(h1);continue;如果h1為正而h2為負else if(h1_num>0&&h2_num<0)這種情況，如果h1最高結(jié)點元素大于h2的最高元素，那么交換鏈表if(h1->next->x<h2-&

26、gt;next->x)dl_node *tmp=h1;h1=h2;h2=tmp;/h1_num=h1->x,h2_num=h2->x;/prin(h1);/prin(h2);這種情況得先輸出一個負號cout<<"-"交換之后加法還是一樣list_sub(h1,h2);prin(h1);continue;如果h1為負而h2為正elseif(h1_num<0&&h2_num>0)if(h1->next->x<h2->next->x)dl_node *tmp=h1;h1=h2;h2=tmp;/

27、cout<<"-"否則為負值，要輸出負號else cout<<"-"list_sub(h1,h2);prin(h1); 5、系統(tǒng)的調(diào)試與結(jié)果5.1.調(diào)試過程出現(xiàn)的問題以及解決方法 由于對編程的熟練度不是很高，所以在編程的過程中往往很容易出現(xiàn)錯誤。比如說，本系統(tǒng)同時應(yīng)用了多個函數(shù)接口，有些接口可能嘗試了很多次也不一定能夠成功；調(diào)試中由于使用了數(shù)據(jù)結(jié)構(gòu)的循環(huán)雙鏈表，在插入時缺乏考慮，剛開始寫程序是忘記，導致輸入、輸出結(jié)果錯誤。這是最好的解決方法好了嘗試還是嘗試，是在不行的話，就請教老師和同學。 5.2.成功的測試數(shù)據(jù)截圖5.2.1以下

28、是用戶界面： 圖5.2.15.2.2測試數(shù)據(jù)（1）0；0；應(yīng)輸出“0”。（2）2345，6789；7654，3211；應(yīng)輸出“1，0000，0000”。（3）9999，9999；1，0000，0000，0000；應(yīng)輸出“9999，0000，0001”。（4）1，0001，0001；1，0001，0001；應(yīng)輸出“0”。（5）1，0001，0001；1，0001，0000；應(yīng)輸出“1”。（6）9999，9999，9999；9999，9999，9999；應(yīng)輸出“1，9999，9999，9998”。（7）1，0000，9999，9999；1；應(yīng)輸出“1，0001，0000，0000”。 圖5.2.26、課設(shè)小結(jié)通過這次學習，讓我認識到自己在學習上的諸多不足。從剛拿到題目到完成整個編程，從理論到實踐，雖然學到很多的的東西，但是也因為自己知識的不足，不能考慮周全，完全成功的完成此次課程設(shè)計。在認識自己的不足后，我便開始認真復(fù)習書本知識，同時與動手能力強的同學互相交流，讓自己