任意長(zhǎng)整數(shù)加法運(yùn)算

1、課程名稱: 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)課程設(shè)計(jì)題目: 任意長(zhǎng)整數(shù)加法運(yùn)算姓 名: XXX專 業(yè): 計(jì)算機(jī)科技2班 年 級(jí): 13級(jí) 學(xué) 號(hào): E11314XXX指導(dǎo)老師：XXX2015年9月17目錄1.課程設(shè)計(jì)的目的12.需求分析13任意長(zhǎng)整數(shù)加法的設(shè)計(jì)23.1概要設(shè)計(jì)23.2詳細(xì)設(shè)計(jì)33.3調(diào)試分析93.4用戶手冊(cè)103.5測(cè)試結(jié)果104總結(jié)115、程序清單:(見(jiàn)附錄)117、程序運(yùn)行結(jié)果11附錄1131.課程設(shè)計(jì)的目的(1) 熟練使用 C 語(yǔ)言編寫(xiě)程序，解決實(shí)際問(wèn)題;(2) 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力;(3) 初步掌握軟件開(kāi)發(fā)過(guò)程的問(wèn)題分析、系統(tǒng)設(shè)計(jì)、程序編碼、

2、測(cè)試等基本方法和技能;(4) 提高綜合運(yùn)用所學(xué)的理論知識(shí)和方法獨(dú)立分析和解決問(wèn)題的能力;2.需求分析(1) 設(shè)計(jì)一個(gè)實(shí)現(xiàn)任意長(zhǎng)的整數(shù)加法運(yùn)算演示程序。(2) 利用雙向鏈表實(shí)現(xiàn)長(zhǎng)整數(shù)的存儲(chǔ)，每個(gè)結(jié)點(diǎn)含一個(gè)整型變量。(3) 輸入輸出形式按中國(guó)對(duì)長(zhǎng)整數(shù)的表示習(xí)慣，每四位一組，用逗號(hào)隔開(kāi)。3任意長(zhǎng)整數(shù)加法的設(shè)計(jì)3.1概要設(shè)計(jì)(1) 主界面設(shè)計(jì)圖 1圖2主界面，如圖1所示，包含四個(gè)菜單項(xiàng)，輸入數(shù)字選擇對(duì)應(yīng)菜單，進(jìn)入子項(xiàng)。其中選項(xiàng)2包含子菜單，如圖2所示。(2) 存儲(chǔ)結(jié)構(gòu)本系統(tǒng)用結(jié)構(gòu)體linlist存儲(chǔ)數(shù)據(jù)，該結(jié)構(gòu)體由數(shù)據(jù)data、下一節(jié)點(diǎn)指針next、上一節(jié)點(diǎn)指針prior組成。data是short型變

3、量，存放每個(gè)結(jié)點(diǎn)的數(shù)據(jù)。本系統(tǒng)中data一般不超過(guò)10000。用結(jié)構(gòu)體linlist構(gòu)建鏈表，頭結(jié)點(diǎn)的data域符號(hào)代表長(zhǎng)整數(shù)的符號(hào)，絕對(duì)值表示鏈表結(jié)點(diǎn)數(shù)目。(3) 系統(tǒng)功能設(shè)計(jì)本系統(tǒng)主菜單包含四個(gè)選項(xiàng)，功能描述如下：菜單1：輸入兩個(gè)任意長(zhǎng)的整數(shù)?？砂凑諛?biāo)準(zhǔn)四位一組中間用逗號(hào)隔開(kāi)輸入，也可直接輸入，輸入的數(shù)字保存在文件中，結(jié)束后自動(dòng)返回主菜單。菜單2：實(shí)現(xiàn)兩個(gè)任意長(zhǎng)整數(shù)的加法?？芍苯虞斎雰蓚€(gè)數(shù)也可讀入一個(gè)文件，獲取兩個(gè)加數(shù)，相加結(jié)果可保存在文件中，也可不保存，結(jié)束后返回菜單2。菜單3：輸入文件名稱，查詢文件中的數(shù)字。文件中可能保存的是兩個(gè)加數(shù)，也可能保存的是某次兩個(gè)任意長(zhǎng)整數(shù)相加的結(jié)果。菜單4

4、：退出系統(tǒng)。3.2詳細(xì)設(shè)計(jì)(1) 系統(tǒng)子程序及功能設(shè)計(jì)本系統(tǒng)設(shè)置16個(gè)子程序，各程序的函數(shù)名及功能說(shuō)明如下：void append(LinList &L,Elemtype d);/以L為頭結(jié)點(diǎn)，將d加入到鏈表Lvoid Delete(LinList &L);/刪除結(jié)點(diǎn)Lvoid display(LinList L);/按照輸出標(biāo)準(zhǔn)，輸出任意長(zhǎng)整數(shù)void add(LinList &L1,LinList L2);/將L1與L2相加short StrToPosiNum(char * s);/將s轉(zhuǎn)化為一個(gè)小于32767的正整數(shù)void input(LinList &

5、L);/輸入一個(gè)很長(zhǎng)的整數(shù)到Lvoid FREE(LinList &L1);/刪除以L1為頭結(jié)點(diǎn)的整個(gè)鏈表void save(LinList L1,LinList L2);/把L1，L2寫(xiě)到文件void load(LinList &L1,LinList &L2);/讀文件到L1，L2void inputdata();/調(diào)用input函數(shù)，實(shí)現(xiàn)兩個(gè)任意長(zhǎng)整數(shù)的輸入void welcome();/輸出歡迎界面void fileadd()；/讀入文件，調(diào)用add函數(shù)，實(shí)現(xiàn)兩個(gè)任意長(zhǎng)整數(shù)的相加void directadd()；/直接輸入數(shù)字相加void calculaytead

6、d()；/實(shí)現(xiàn)兩個(gè)任意長(zhǎng)整數(shù)的相加int maincourse();/菜單選擇void search();/查詢文件中的數(shù)字(2) 數(shù)據(jù)類型定義typedef struct linlistElemtype data;linlist * next;linlist * prior; * LinList;(3) 系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)本系統(tǒng)的各個(gè)函數(shù)之間的關(guān)系如下圖：圖31) 菜單1代碼void inputdata()/調(diào)用input函數(shù)，實(shí)現(xiàn)兩個(gè)任意長(zhǎng)整數(shù)的輸入system("cls");LinList L1=NULL,L2=NULL;printf("ttt -ntt

7、tt 輸入數(shù)據(jù)nttt -n");printf("輸入第一個(gè)長(zhǎng)整數(shù):");input(L1);/調(diào)用input函數(shù)printf("輸入第二個(gè)長(zhǎng)整數(shù):");input(L2);printf("n數(shù)據(jù)將存放于文件中.");save(L1,L2);/調(diào)用save函數(shù),存儲(chǔ)L1L2FREE(L1);FREE(L2);/釋放L1，L2printf("寫(xiě)入完成!n");system("pause");void input(LinList &L)/輸入一個(gè)很長(zhǎng)的整數(shù)到Lchar s1000,

8、s25='0','0','0','0','0'unsigned i=0,j;int sign=1,num=0,flag=1;Elemtype data;while(flag)flag=0;s0=getchar();if(s0='-')/若為負(fù)數(shù)sign=-1;i=i-1;while(i=-1|si!='n')/第一個(gè)輸入負(fù)號(hào)或者輸入數(shù)字i=i+1;si=getchar();if(si=',')i=i-1;else if(si>'9'|si<

9、'0')&&si!='n')printf("非法輸入,請(qǐng)重新輸入!n");flag=1;continue;si=0;append(L,(int)(sign*ceil(strlen(s)/4.0);/第一個(gè)結(jié)點(diǎn)存放鏈表長(zhǎng)度和數(shù)據(jù)的正負(fù)號(hào)j=strlen(s)%4;i=0;if(j!=0)for(;i<j;i+)s2i=si;s2i=0;data=StrToPosiNum(s2);append(L,data);/以L為頭結(jié)點(diǎn)，添加結(jié)點(diǎn)for(;i<strlen(s);i=i+4)/每4位數(shù)放入一個(gè)結(jié)點(diǎn)for(j=0;j

10、<4;j+)s2j=si+j;s2j=0;data=StrToPosiNum(s2);append(L,data);/以L為頭結(jié)點(diǎn)，添加結(jié)點(diǎn)2) 菜單2代碼void calculayteadd()/菜單2求和while(1)system("cls");printf("ntt -ntttt 加 法 運(yùn) 算n");printf("tt -n");printf("tttt1. 直接輸入求和ntttt2. 讀入文件求和ntttt3. 返回主菜單n");printf("tt -nn");char s

11、100;int flag=0;doif(flag)printf("t 輸入非法,請(qǐng)重新輸入:");elseprintf("t 輸入數(shù)字1-3選擇:");flag=1;scanf("%s",s);while(strlen(s)>1|s0-'0'<=0|s0-'0'>3);getchar();switch(s0-'0')case 1:directadd();/直接輸入數(shù)字求和break;case 2:fileadd();/輸入文件名稱求和break;case 3:retur

12、n;break;void add(LinList &L1,LinList L2)/將L1與L2相加,結(jié)果放到L1LinList p,q,r;int cy=0;int sign1=1,sign2=1;if(!L1|L1->data=0)/若L1為空，相加結(jié)果為L(zhǎng)2L1=L2;else if(!L2|L2->data=0)/若L2為空，相加結(jié)果為L(zhǎng)1return;else/否則if(abs(L1->data)<abs(L2->data)|L1->next->data<L2->next->data)q=L1;/L1總是存放絕對(duì)值較大

13、的數(shù)字L1=L2;L2=q;p=L1->prior;q=L2->prior;if(L1->data<0)sign1=-1;if(L2->data<0)sign2=-1;if(sign1*sign2>0)/相加的為同號(hào)數(shù)字while(p!=L1&&q!=L2)p->data=q->data+p->data+cy;if(p->data>9999)cy=1;p->data=abs(p->data)-10000;elsecy=0;p=p->prior;q=q->prior;while(p!=

14、L1&&cy)p->data=p->data+cy;if(p->data>9999)cy=1;p->data=p->data-10000;elsecy=0;p=p->prior;p=p->next;if(cy)r=(LinList)malloc(sizeof(linlist);p->prior->next=r;r->prior=p->prior;r->next=p;p->prior=r;r->data=cy;L1->data=L1->data*sign1+1;L1->da

15、ta=L1->data*sign1;else/相加的為異號(hào)的數(shù)字cy=0;while(p!=L1&&q!=L2)p->data=p->data-cy;if(p->data<q->data)p->data=p->data+10000;cy=1;p->data=p->data-q->data;p=p->prior;q=q->prior;while(p!=L1&&cy)if(p->data<cy)cy=1;p->data=p->data+10000;p->dat

16、a=p->data-cy;p=p->prior;while(L1->next->data=0&&L1->next->next!=L1)/結(jié)果為0的結(jié)點(diǎn)去掉p=L1->next;p->next->prior=L1;L1->next=p->next;L1->data=L1->data*sign1-1;L1->data=L1->data*sign1;Delete(p);3) 菜單3代碼void search()/查詢文件中的數(shù)字FILE * fp;LinList L1=NULL,L2=NULL;

17、LinList p=L1;int i,length;char s100;system("cls");printf("ttt -ntttt 文件查詢nttt -");Elemtype t;printf("n文件的名稱為:");/讀取文件scanf("%s",s);fp=fopen(s,"rb");fseek(fp,0,SEEK_SET);fread(&t,sizeof(Elemtype),1,fp);length=abs(t);/第一個(gè)數(shù)字的位數(shù)append(L1,t);for(i=0;i

18、<length;i+)fread(&t,sizeof(Elemtype),1,fp);append(L1,t);fread(&t,sizeof(Elemtype),1,fp);if(!feof(fp)/讀入第二個(gè)數(shù)字length=abs(t);append(L2,t);for(i=0;i<length;i+)fread(&t,sizeof(Elemtype),1,fp);append(L2,t);printf("文件中有兩個(gè)數(shù)字,分別為:n");display(L1);putchar('n');display(L2);pu

19、tchar('n');elseprintf("文件中有一個(gè)數(shù)字:n");display(L1);putchar('n');system("pause");3.3調(diào)試分析1. 輸入數(shù)據(jù)在主菜單下輸入1并回車，進(jìn)入子項(xiàng)1，可輸入兩個(gè)任意長(zhǎng)的整數(shù)，保存于文件中，運(yùn)行結(jié)果如圖4所示。圖42. 加法運(yùn)算在主菜單下輸入2并回車，可進(jìn)入子菜單。選擇子菜單1直接輸入數(shù)字或者選擇子菜單2，讀取文件，計(jì)算文件中兩個(gè)任意長(zhǎng)整數(shù)的和，并可選擇是否將結(jié)果保存在文件中，結(jié)果如圖5所示。圖53. 文件查詢?cè)谥鞑藛蜗螺斎?并回車，可進(jìn)入子菜單，讀取文件，

20、查詢文件中的數(shù)字，結(jié)果如圖6。圖64. 退出系統(tǒng)在主菜單下輸入4并回車，退出系統(tǒng)，結(jié)果如圖7。圖73.4用戶手冊(cè)1. 本程序執(zhí)行文件為“任意長(zhǎng)整數(shù)加法.exe”。2. 用戶進(jìn)入系統(tǒng)后根據(jù)提示，輸入數(shù)字進(jìn)入相應(yīng)的子菜單，實(shí)現(xiàn)相應(yīng)功能。3. 本系統(tǒng)可實(shí)現(xiàn)任意長(zhǎng)整數(shù)加法的運(yùn)算。3.5測(cè)試結(jié)果圖 8圖9圖10圖11圖12圖13該部分給出了本系統(tǒng)的加法測(cè)試結(jié)果，如圖8到13所示。本系統(tǒng)主要函數(shù)的時(shí)間復(fù)雜度：add函數(shù)是將L1與L2相加，相加是從鏈表尾部加到鏈表頭部，時(shí)間復(fù)雜度與鏈表長(zhǎng)度相關(guān)。鏈表長(zhǎng)度與數(shù)據(jù)位數(shù)有關(guān)。鏈表長(zhǎng)度。是數(shù)據(jù)的位數(shù)。所以時(shí)間復(fù)雜度為。Input函數(shù)將數(shù)字作為字符逐個(gè)輸入，時(shí)間復(fù)雜度

21、與數(shù)字位數(shù)相關(guān)，所以時(shí)間復(fù)雜度為。save和load函數(shù)是將結(jié)點(diǎn)中data逐個(gè)保存到文件或從文件讀出，時(shí)間復(fù)雜度與鏈表長(zhǎng)度有關(guān)，加上頭結(jié)點(diǎn)，鏈表長(zhǎng)度為，對(duì)應(yīng)的時(shí)間復(fù)雜度為。4總結(jié)實(shí)驗(yàn)中，我在算法設(shè)計(jì)不太清晰時(shí)就敲代碼，到后來(lái)發(fā)現(xiàn)有點(diǎn)混亂不得不重新改，浪費(fèi)了很多時(shí)間，讓我總結(jié)到了在完成代碼部分之前要設(shè)計(jì)好算法才能更高效。這次實(shí)驗(yàn)相對(duì)于上次實(shí)驗(yàn)有所提高，代碼的冗余相對(duì)上次代碼有明顯的減少，很多功能都封裝在了函數(shù)里，比上次的代碼易讀點(diǎn)，但程序整體的設(shè)計(jì)還是有待提高，回過(guò)頭再看看發(fā)現(xiàn)整體不是很規(guī)整。下次繼續(xù)改進(jìn)。5、程序清單:(見(jiàn)附錄)7、程序運(yùn)行結(jié)果1 主界面2 輸入數(shù)據(jù)，生成文件3 加法運(yùn)算界面4

22、 直接輸入數(shù)據(jù)求和5 讀入文件求和6 查詢文件內(nèi)容7 退出系統(tǒng)附錄1（系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)給出的代碼不再詳細(xì)給出）程序清單#include <stdio.h>#include <stdlib.h>#include <math.h>#include <string.h>#define Elemtype shorttypedef struct linlistElemtype data;linlist * next;linlist * prior; * LinList;void append(LinList &L,Elemtype d)/以L

23、為頭結(jié)點(diǎn)，添加結(jié)點(diǎn)LinList p,q;if(!L)L=(LinList)malloc(sizeof(linlist);L->data=d;L->next=L;L->prior=L;elsep=L;while(p->next!=L)p=p->next;q=(LinList)malloc(sizeof(linlist);q->data=d;q->next=p->next;q->prior=p;p->next=q;q->next->prior=q;void Delete(LinList &L)/刪除結(jié)點(diǎn)Lif(!L)

24、return;else if(L->next=L)L=NULL;elseL->next->prior=L->prior;L->prior->next=L->next;free(L);void display(LinList L)/按照輸出標(biāo)準(zhǔn)，輸出任意長(zhǎng)整數(shù)if(!L)putchar('n');else if(L->next=L)printf("n");elseLinList q=L->next;if(L->data<0&&q->data!=0)printf("

25、-");printf("%d",q->data);q=q->next;while(q!=L)putchar(',');if(q->data<10)printf("000");else if(q->data<100)printf("00");else if(q->data<1000)printf("0");printf("%d",q->data);q=q->next;void add(LinList &L

26、1,LinList L2)；/將L1與L2相加,結(jié)果放到L1short StrToPosiNum(char * s)/將s轉(zhuǎn)化為一個(gè)小于32767的正整數(shù)int length=1,i=0,flag;double num1;while(i!=length)flag=1;num1=0;length=strlen(s);for(i=0;i<length;i+)if(si-'0'>-1&&si-'0'<10)num1=num1*10+si-'0'else if(si='-')flag=-1;elsepri

27、ntf("%cn字符串到整型數(shù)字出錯(cuò)!",si);exit(0);if(num1>32767)printf("輸入數(shù)字太大!,請(qǐng)重新輸入:");exit(0);return flag*(short)num1;void input(LinList &L)；/輸入一個(gè)很長(zhǎng)的整數(shù)到Lvoid FREE(LinList &L1)/刪除以L1為頭結(jié)點(diǎn)的整個(gè)鏈表LinList p;if(!L1)return;elseL1->prior->next=NULL;while(L1)p=L1;L1=L1->next;free(p);v

28、oid save(LinList L1,LinList L2)/把L1，L2寫(xiě)到文件FILE * fp;LinList p=L1;int i,length;char s100;printf("n文件的名稱為:");/將生成的數(shù)保存于文件scanf("%s",s);if(L1)length=abs(L1->data);fp=fopen(s,"wb+");for(i=0;i<length+1;i+)fwrite(&p->data,sizeof(Elemtype),1,fp);p=p->next;if(L2)

29、p=L2;for(i=0;i<length+1;i+)fwrite(&p->data,sizeof(Elemtype),1,fp);p=p->next;fclose(fp);void load(LinList &L1,LinList &L2)/讀文件到L1，L2FILE * fp;LinList p=L1;int i,length;char s100;Elemtype t;printf("n文件的名稱為:");/將生成的數(shù)保存于文件scanf("%s",s);fp=fopen(s,"rb");

30、fseek(fp,0,SEEK_SET);fread(&t,sizeof(Elemtype),1,fp);length=abs(t);append(L1,t);for(i=0;i<length;i+)fread(&t,sizeof(Elemtype),1,fp);append(L1,t);fread(&t,sizeof(Elemtype),1,fp);length=abs(t);append(L2,t);for(i=0;i<length;i+)fread(&t,sizeof(Elemtype),1,fp);append(L2,t);void inpu

31、tdata()；/調(diào)用input函數(shù)，實(shí)現(xiàn)兩個(gè)任意長(zhǎng)整數(shù)的輸入void welcome()/輸出歡迎界面printf("nt n");printf("t . .n");printf("t . 任意長(zhǎng)的整數(shù)加法運(yùn)算器 .n");printf("t . .n");printf("t n");void fileadd()/讀入文件，調(diào)用add函數(shù)，實(shí)現(xiàn)兩個(gè)任意長(zhǎng)整數(shù)的相加LinList L1=NULL,L2=NULL;int flag;char s100;system("cls")

32、;printf("ttt -ntttt 讀入文件求和nttt -n");printf("讀入文件.");load(L1,L2);/讀入到L1L2printf("(");display(L1);printf(")+");printf("(");display(L2);printf(")=");add(L1,L2);/調(diào)用add，計(jì)算L1+L2display(L1);putchar('n');flag=0;do/保存計(jì)算結(jié)果if(flag)printf("

33、;輸入非法,請(qǐng)重新輸入:");elseprintf("是否保存結(jié)果(輸入Y/N)?");flag=1;scanf("%s",s);while(strlen(s)>1|s0-'y'!=0&&s0-'Y'!=0&&s0-'N'!=0&&s0-'n'!=0);if(s0='y'|s0='Y')save(L1,NULL);printf("保存完成!n");system("pause");void directadd() /直接輸入數(shù)字相加LinList L1=NULL,L2=NULL;int flag;system("cls");printf("ttt -ntttt 直接輸入求和nttt -n");puts("輸入第一個(gè)整數(shù):");input(L1);puts("輸入第二個(gè)整數(shù):&