長(zhǎng)整數(shù)四則運(yùn)算加減法

1、青島理工大學(xué)數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)報(bào)告題目：長(zhǎng)整數(shù)四則運(yùn)算 院（系）：計(jì)算機(jī)工程學(xué)院 學(xué)生姓名: 班級(jí)： 學(xué)號(hào):起迄日期: 指導(dǎo)教師: 房斐斐 20122013年度 第 2 學(xué)期 一、需求分析 1.問(wèn)題描述： 設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)進(jìn)行加、減法運(yùn)算的演示程序。2.基本功能1、本程序?qū)崿F(xiàn)計(jì)算任意長(zhǎng)的整數(shù)的加、減法運(yùn)算. 以用戶和計(jì)算機(jī)對(duì)話的方式，即在計(jì)算機(jī)終端上顯示“提示信息”之后，由用戶在鍵盤上輸入演示程序中規(guī)定的運(yùn)算命令，然后程序就計(jì)算并顯示出這兩個(gè)數(shù)的運(yùn)算。 2、本演示程序中，集合的元素限定為數(shù)字字符09和字符，與；，輸入字符可以任意長(zhǎng)，輸入形式以“回車符”為結(jié)束標(biāo)志，串中字符順序不限，且允許

2、出現(xiàn)重復(fù)字符。3、利用雙向循環(huán)鏈表現(xiàn)實(shí)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整形變量。輸入的形式以回車結(jié)束，可以直接輸入正數(shù)或負(fù)數(shù)。按中國(guó)對(duì)于長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，除數(shù)字和位于首位置的負(fù)號(hào)外，其它一切字符都將作為分隔符，連續(xù)多個(gè)分隔符當(dāng)一個(gè)處理。但不使用分隔符也不影響結(jié)果。3.輸入輸出（1）0；0；加法應(yīng)輸出“0”，減法應(yīng)輸出”0”。（2）-2345,6789；-7654,3211；加法應(yīng)輸出“-1,0000,0000”，減法應(yīng)輸出”5408,6422”。（3）-9999,9999；1,0000,0000,0000；加法應(yīng)輸出“9999,0000,0001”，減法應(yīng)輸出1,0000,9999,9

3、999。（4）1,0001,0001；-1,0001,0001；加法應(yīng)輸出“0”，減法應(yīng)輸出”2,0002,0002”。（5）1,0001,0001；-1,0001,0000；加法應(yīng)輸出“1”，減法應(yīng)輸出”2,0002,0001”。（6）-9999,9999,9999；-9999,9999,9999；加法應(yīng)輸出“1,9999,9999,9998”，減法應(yīng)輸出”0”。（7）1,0000,9999,9999；1；加法應(yīng)輸出“1,0001,0000,0000”，減法應(yīng)輸出”1,0000,9999,9998”。二、 概要設(shè)計(jì)1. 設(shè)計(jì)思路：（1） 利用雙向循環(huán)鏈表現(xiàn)實(shí)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)中可以存放的

4、最大整數(shù)為32767，才能保證兩數(shù)相加不會(huì)溢出，但若這樣存放，即相當(dāng)于按32768進(jìn)制存放，在十進(jìn)制與32768進(jìn)制數(shù)之間的轉(zhuǎn)換十分不方便，故可以在每個(gè)結(jié)點(diǎn)中僅存十進(jìn)制的4位，即不超過(guò)9999的非負(fù)整數(shù)，整個(gè)鏈表表示為萬(wàn)進(jìn)制。（2）可以利用頭結(jié)點(diǎn)數(shù)據(jù)域的符號(hào)代表長(zhǎng)整數(shù)的符號(hào)。用其絕對(duì)值表示元素結(jié)點(diǎn)數(shù)目。相加過(guò)程中不要破壞兩個(gè)操作數(shù)鏈表。兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法。不能給長(zhǎng)整數(shù)位數(shù)規(guī)定上限。2. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：1) 數(shù)據(jù)類型：typedef int datatype; /定義數(shù)據(jù)類型 typedef struct doublenode /定義鏈表元素 datatype

5、 data; struct doublenode *prior; struct doublenode *next; dlnode; 2) 存儲(chǔ)結(jié)構(gòu)：順序結(jié)構(gòu)，鏈?zhǔn)酱鎯?chǔ)。采用鏈?zhǔn)酱鎯?chǔ)的方式會(huì)方便字符的讀入和操作，且算法簡(jiǎn)單易懂。3. 軟件結(jié)構(gòu)設(shè)計(jì)： 1)初始化鏈表void initnode(dlnode *head) 2) 向鏈表第n個(gè)位置插入元素x int insertnode(dlnode *head,int n,datatype x)3) 判斷整數(shù)n有幾位int digit(int n)4) 兩數(shù)相加void add(dlnode *h1,dlnode *h2) 5) 兩數(shù)相減void j

6、ian(dlnode *h1,dlnode *h2)6）打印鏈表 void printnode(dlnode *head)7）刪除鏈表void destroynode(dlnode *head)8）主函數(shù)int main()三、 詳細(xì)設(shè)計(jì) 1. 數(shù)據(jù)類型。 typedef int datatype; /定義數(shù)據(jù)類型 typedef struct doublenode /定義鏈表元素 datatype data; struct doublenode *prior; struct doublenode *next; dlnode; 2.存儲(chǔ)結(jié)構(gòu)類型：void initnode(dlnode *he

7、ad) /初始化鏈表 if(*head=(dlnode*)malloc(sizeof(dlnode)=null) exit(1); (*head)-prior=*head; (*head)-next=*head; 3.主函數(shù)和其他函數(shù)的偽碼算法；1.主函數(shù)：int main() /主函數(shù) dlnode *head1,*head2; char data1n,data2n; char d110,d210; int i,j,k; int xun;printf(提示：較長(zhǎng)的字符串?dāng)?shù)作為被加數(shù)，如果等長(zhǎng)，則第一個(gè)數(shù)加第二個(gè)數(shù)nn); while(1) printf(輸入數(shù)據(jù)：n); scanf(%s %

8、s,data1,data2); initnode(&head1); initnode(&head2); i=0;k=0; while(data1i!=;) /將數(shù)1用鏈表儲(chǔ)存 for(j=0;j10;j+) d1j=0; j=0; while(data1i!=;&data1i!=,) d1j+=data1i+; if(data1i=,) i+; if(data10=-) /處理正負(fù)數(shù) j=-(int)fabs(atoi(d1); /atoi()把字符串轉(zhuǎn)換成整型數(shù),頭文件: #include elsej=atoi(d1); insertnode(head1,k+,j); i=0; k=0; w

9、hile(data2i!=;) /將數(shù)2用鏈表儲(chǔ)存 for(j=0;j=strlen(data2) /較長(zhǎng)的數(shù)作為被加數(shù) add(head1,head2); else add(head2,head1); break; default:break; destroynode(&head1); destroynode(&head2);printf(nn); return 0; 2.初始化鏈表：void initnode(dlnode *head) /初始化鏈表 if(*head=(dlnode*)malloc(sizeof(dlnode)=null) exit(1); (*head)-prior=*

10、head; (*head)-next=*head; 3.向鏈表第n個(gè)位置插入元素x int insertnode(dlnode *head,int n,datatype x) /向鏈表第n個(gè)位置插入元素x dlnode *p,*nt; int i=0; p=head-next; while(p!=head&inext; i+; if(i!=n) printf(插入位置錯(cuò)誤n); return 0; if(nt=(dlnode *)malloc(sizeof(dlnode)=null) exit(1); nt-data=x; nt-prior=p-prior; nt-prior-next=nt;

11、 nt-next=p; p-prior=nt; return 1; 4. 判斷整數(shù)n有幾位 int digit(int n) /判斷整數(shù)n有幾位 int i; for(i=1;n/=10,i+) if(n/10=0) return i; 5.打印鏈表 void printnode(dlnode *head) /打印鏈表 printf(結(jié)果是：); dlnode *p=head-prior; int i; while(p-data=0) /去掉前面的一串0 p=p-prior; if(p=head) printf(0n); return; printf(%d,p-data); /最前面的一個(gè)數(shù)進(jìn)

12、行特殊處理,不用補(bǔ)零 p=p-prior; while(p!=head) /打印后面的數(shù)字 printf(,); if(p-data=0) printf(0000); p=p-prior; continue; for(i=0;idata);i+) /補(bǔ)零 printf(0); printf(%d,p-data); p=p-prior; printf(n); 6.刪除鏈表 void destroynode(dlnode *head) dlnode *p,*p1; p=(*head)-next; while(p!=*head) p1=p; p=p-next; free(p1); free(p);

13、head=null; 7. 兩數(shù)相加 void add(dlnode *h1,dlnode *h2) int i=0,j=0;dlnode *head3; initnode(&head3); dlnode *p1=h1-prior,*p2=h2-prior,*p3; while(p1!=h1&p2!=h2) /每個(gè)鏈表元素相加 i=p1-data+p2-data ; p1=p1-prior;p2=p2-prior; insertnode(head3,j+,i);while(p1!=h1)insertnode(head3,j+,p1-data);p1=p1-prior; p3=head3-nex

14、t; while(p3!=head3-prior) /處理鏈表元素 if(p3-data=10000) p3-next-data+=p3-data/10000; p3-data%=10000; if(p3-dataprior!=0) p3-next-data-=1; p3-data+=10000; p3-data=(int)fabs(p3-data); p3=p3-next; if(head3-prior-data=10000) /處理最前面的數(shù) insertnode(head3,j,head3-prior-data/10000); head3-prior-prior-data%=10000;

15、 if(head3-prior-dataprior-data/10000); head3-prior-prior-data%=10000; head3-prior-prior-data=(int)fabs(head3-prior-prior-data); printnode(head3); 8. 兩數(shù)相減void jian(dlnode *h1,dlnode *h2) int i=0,j=0;dlnode *head4; initnode(&head4); dlnode *p1=h1-prior,*p2=h2-prior,*p4; while(p1!=h1&p2!=h2) /每個(gè)鏈表元素相減i

16、=p1-data-p2-data ; p1=p1-prior; p2=p2-prior; insertnode(head4,j+,i);while(p1!=h1)insertnode(head4,j+,p1-data);p1=p1-prior; p4=head4-next; while(p4!=head4-prior) /處理鏈表元素 if(p4-data=10000) p4-next-data+=p4-data/10000; p4-data%=10000; if(p4-dataprior!=0&p4-datanext-data-=1; p4-data+=10000; p4-data=(int

17、)fabs(p4-data); p4=p4-next; if(head4-prior-data=10000) /處理最前面的數(shù) insertnode(head4,j,head4-prior-data/10000); head4-prior-prior-data%=10000; if(head4-prior-dataprior-data/10000); head4-prior-prior-data%=10000; head4-prior-prior-data=(int)fabs(head4-prior-prior-data); printnode(head4);4. 主函數(shù)的程序流程圖 開(kāi)始in

18、itnode(&head1)initnode(&head2)insertnode(head1,k+,j) switch(sun)insertnode(head2,k+,j)case 2jian(head2,head1)case 1add(head1,head2)defaultbreakinitnode(&head4)initnode(&head3)insertnode(head3,j+,i)insertnode(head4,j+,i)printnode(head4)printnode(head3)destroynode(&head1)destroynode(&head1)四、調(diào)試分析 1. 實(shí)

19、際完成的情況說(shuō)明程序基本功已完成，包括：輸入長(zhǎng)整型數(shù)字字符，用雙向循環(huán)鏈表儲(chǔ)存，計(jì)算兩數(shù)之和、之差，輸出值，刪除鏈表，基本符合題目要求。2. 程序的性能分析時(shí)間復(fù)雜度：o(strlen(data1)+strlen(data2)3. 上機(jī)過(guò)程中出現(xiàn)的問(wèn)題及其解決方案 1）雙向循環(huán)鏈表指針指向錯(cuò)誤 雙向循環(huán)鏈表使用錯(cuò)誤，指針順序不對(duì)，參考教課書改正。 2)打印順序錯(cuò)誤由于計(jì)算值儲(chǔ)存順序是從尾到頭，開(kāi)始誤認(rèn)為是從頭到尾，修改指針指向改正。3) 中間計(jì)算值錯(cuò)誤 中間計(jì)算值不足四位的應(yīng)用0補(bǔ)足。 4）中間值小于0處理錯(cuò)誤 中間值小于0但大于-100000的數(shù)應(yīng)取絕對(duì)值，小于-10000的數(shù)應(yīng)先借位，這個(gè)

20、數(shù)加上10000后，再取絕對(duì)值4. 程序中可以改進(jìn)的地方說(shuō)明 兩操作數(shù)的頭指針存于指針數(shù)組中是簡(jiǎn)化程序結(jié)構(gòu)的一種方法，但由于廣泛使用指針 易造成混亂，所以就放棄了，以后可以改進(jìn)。5. 程序中可以擴(kuò)充的功能及設(shè)計(jì)實(shí)現(xiàn)假想。本程序可拓展到乘除運(yùn)算，還有乘方和階乘運(yùn)算。五、測(cè)試結(jié)果l 測(cè)試方法：輸入數(shù)據(jù)l 測(cè)試數(shù)據(jù)：（1）0；0；加法應(yīng)輸出“0”，減法應(yīng)輸出”0”。（2）-2345,6789；-7654,3211；加法應(yīng)輸出“-1,0000,0000”，減法應(yīng)輸出”5408,6422”。（3）-9999,9999；1,0000,0000,0000；加法應(yīng)輸出“9999,0000,0001”，減法應(yīng)輸

21、出1,0000,9999,9999。（4）1,0001,0001；-1,0001,0001；加法應(yīng)輸出“0”，減法應(yīng)輸出”2,0002,0002”。（5）1,0001,0001；-1,0001,0000；加法應(yīng)輸出“1”，減法應(yīng)輸出”2,0002,0001”。（6）-9999,9999,9999；-9999,9999,9999；加法應(yīng)輸出“1,9999,9999,9998”，減法應(yīng)輸出”0”。（7）1,0000,9999,9999；1；加法應(yīng)輸出“1,0001,0000,0000”，減法應(yīng)輸出”1,0000,9999,9998”。六、用戶手冊(cè)本程序使用起來(lái)簡(jiǎn)單方便，只要按照菜單提示進(jìn)行即可。1.加法1. 輸入0；0；2. 輸入-2345,6789；-7654,3211；3. 輸入-9999,9999；1,0000,0000,0000；4. 輸入1,0001,0001；-1,0001,0001；5. 輸入1,0001,0001；-1,0001,0000；6. 輸入-9999,9999,9999；-9999,9999,9999；7. 輸入1,0000,9999,9999；1；2. 減法1. 輸入0；0；2. 輸入-2345,6789；-7654,3211；3. 輸入-9999,9999；1