任意长整数加法运算

1、课程名称: 数据结构课程设计课程设计题目: 任意长整数加法运算姓 名: XXX专 业: 计算机科技2班 年 级: 13级 学 号: E11314XXX指导老师：XXX2015年9月17目录1.课程设计的目的12.需求分析13任意长整数加法的设计23.1概要设计23.2详细设计33.3调试分析93.4用户手册103.5测试结果104总结115、程序清单:(见附录)117、程序运行结果11附录1131.课程设计的目的(1) 熟练使用 C 语言编写程序，解决实际问题;(2) 了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力;(3) 初步掌握软件开发过程的问题分析、系统设计、程序编码、

2、测试等基本方法和技能;(4) 提高综合运用所学的理论知识和方法独立分析和解决问题的能力;2.需求分析(1) 设计一个实现任意长的整数加法运算演示程序。(2) 利用双向链表实现长整数的存储，每个结点含一个整型变量。(3) 输入输出形式按中国对长整数的表示习惯，每四位一组，用逗号隔开。3任意长整数加法的设计3.1概要设计(1) 主界面设计图 1图2主界面，如图1所示，包含四个菜单项，输入数字选择对应菜单，进入子项。其中选项2包含子菜单，如图2所示。(2) 存储结构本系统用结构体linlist存储数据，该结构体由数据data、下一节点指针next、上一节点指针prior组成。data是short型变

3、量，存放每个结点的数据。本系统中data一般不超过10000。用结构体linlist构建链表，头结点的data域符号代表长整数的符号，绝对值表示链表结点数目。(3) 系统功能设计本系统主菜单包含四个选项，功能描述如下：菜单1：输入两个任意长的整数。可按照标准四位一组中间用逗号隔开输入，也可直接输入，输入的数字保存在文件中，结束后自动返回主菜单。菜单2：实现两个任意长整数的加法。可直接输入两个数也可读入一个文件，获取两个加数，相加结果可保存在文件中，也可不保存，结束后返回菜单2。菜单3：输入文件名称，查询文件中的数字。文件中可能保存的是两个加数，也可能保存的是某次两个任意长整数相加的结果。菜单4

4、：退出系统。3.2详细设计(1) 系统子程序及功能设计本系统设置16个子程序，各程序的函数名及功能说明如下：void append(LinList &L,Elemtype d);/以L为头结点，将d加入到链表Lvoid Delete(LinList &L);/删除结点Lvoid display(LinList L);/按照输出标准，输出任意长整数void add(LinList &L1,LinList L2);/将L1与L2相加short StrToPosiNum(char * s);/将s转化为一个小于32767的正整数void input(LinList &

5、L);/输入一个很长的整数到Lvoid FREE(LinList &L1);/删除以L1为头结点的整个链表void save(LinList L1,LinList L2);/把L1，L2写到文件void load(LinList &L1,LinList &L2);/读文件到L1，L2void inputdata();/调用input函数，实现两个任意长整数的输入void welcome();/输出欢迎界面void fileadd()；/读入文件，调用add函数，实现两个任意长整数的相加void directadd()；/直接输入数字相加void calculaytead

6、d()；/实现两个任意长整数的相加int maincourse();/菜单选择void search();/查询文件中的数字(2) 数据类型定义typedef struct linlistElemtype data;linlist * next;linlist * prior; * LinList;(3) 系统主要子程序详细设计本系统的各个函数之间的关系如下图：图31) 菜单1代码void inputdata()/调用input函数，实现两个任意长整数的输入system("cls");LinList L1=NULL,L2=NULL;printf("ttt -ntt

7、tt 输入数据nttt -n");printf("输入第一个长整数:");input(L1);/调用input函数printf("输入第二个长整数:");input(L2);printf("n数据将存放于文件中.");save(L1,L2);/调用save函数,存储L1L2FREE(L1);FREE(L2);/释放L1，L2printf("写入完成!n");system("pause");void input(LinList &L)/输入一个很长的整数到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='-')/若为负数sign=-1;i=i-1;while(i=-1|si!='n')/第一个输入负号或者输入数字i=i+1;si=getchar();if(si=',')i=i-1;else if(si>'9'|si<

9、'0')&&si!='n')printf("非法输入,请重新输入!n");flag=1;continue;si=0;append(L,(int)(sign*ceil(strlen(s)/4.0);/第一个结点存放链表长度和数据的正负号j=strlen(s)%4;i=0;if(j!=0)for(;i<j;i+)s2i=si;s2i=0;data=StrToPosiNum(s2);append(L,data);/以L为头结点，添加结点for(;i<strlen(s);i=i+4)/每4位数放入一个结点for(j=0;j

10、<4;j+)s2j=si+j;s2j=0;data=StrToPosiNum(s2);append(L,data);/以L为头结点，添加结点2) 菜单2代码void calculayteadd()/菜单2求和while(1)system("cls");printf("ntt -ntttt 加 法 运 算n");printf("tt -n");printf("tttt1. 直接输入求和ntttt2. 读入文件求和ntttt3. 返回主菜单n");printf("tt -nn");char s

11、100;int flag=0;doif(flag)printf("t 输入非法,请重新输入:");elseprintf("t 输入数字1-3选择:");flag=1;scanf("%s",s);while(strlen(s)>1|s0-'0'<=0|s0-'0'>3);getchar();switch(s0-'0')case 1:directadd();/直接输入数字求和break;case 2:fileadd();/输入文件名称求和break;case 3:retur

12、n;break;void add(LinList &L1,LinList L2)/将L1与L2相加,结果放到L1LinList p,q,r;int cy=0;int sign1=1,sign2=1;if(!L1|L1->data=0)/若L1为空，相加结果为L2L1=L2;else if(!L2|L2->data=0)/若L2为空，相加结果为L1return;else/否则if(abs(L1->data)<abs(L2->data)|L1->next->data<L2->next->data)q=L1;/L1总是存放绝对值较大

13、的数字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)/相加的为同号数字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/相加的为异号的数字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)/结果为0的结点去掉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()/查询文件中的数字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);/第一个数字的位数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)/读入第二个数字length=abs(t);append(L2,t);for(i=0;i<length;i+)fread(&t,sizeof(Elemtype),1,fp);append(L2,t);printf("文件中有两个数字,分别为:n");display(L1);putchar('n');display(L2);pu

19、tchar('n');elseprintf("文件中有一个数字:n");display(L1);putchar('n');system("pause");3.3调试分析1. 输入数据在主菜单下输入1并回车，进入子项1，可输入两个任意长的整数，保存于文件中，运行结果如图4所示。图42. 加法运算在主菜单下输入2并回车，可进入子菜单。选择子菜单1直接输入数字或者选择子菜单2，读取文件，计算文件中两个任意长整数的和，并可选择是否将结果保存在文件中，结果如图5所示。图53. 文件查询在主菜单下输入3并回车，可进入子菜单，读取文件，

20、查询文件中的数字，结果如图6。图64. 退出系统在主菜单下输入4并回车，退出系统，结果如图7。图73.4用户手册1. 本程序执行文件为“任意长整数加法.exe”。2. 用户进入系统后根据提示，输入数字进入相应的子菜单，实现相应功能。3. 本系统可实现任意长整数加法的运算。3.5测试结果图 8图9图10图11图12图13该部分给出了本系统的加法测试结果，如图8到13所示。本系统主要函数的时间复杂度：add函数是将L1与L2相加，相加是从链表尾部加到链表头部，时间复杂度与链表长度相关。链表长度与数据位数有关。链表长度。是数据的位数。所以时间复杂度为。Input函数将数字作为字符逐个输入，时间复杂度

21、与数字位数相关，所以时间复杂度为。save和load函数是将结点中data逐个保存到文件或从文件读出，时间复杂度与链表长度有关，加上头结点，链表长度为，对应的时间复杂度为。4总结实验中，我在算法设计不太清晰时就敲代码，到后来发现有点混乱不得不重新改，浪费了很多时间，让我总结到了在完成代码部分之前要设计好算法才能更高效。这次实验相对于上次实验有所提高，代码的冗余相对上次代码有明显的减少，很多功能都封装在了函数里，比上次的代码易读点，但程序整体的设计还是有待提高，回过头再看看发现整体不是很规整。下次继续改进。5、程序清单:(见附录)7、程序运行结果1 主界面2 输入数据，生成文件3 加法运算界面4

22、 直接输入数据求和5 读入文件求和6 查询文件内容7 退出系统附录1（系统主要子程序详细设计给出的代码不再详细给出）程序清单#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、为头结点，添加结点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)/删除结点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)/按照输出标准，输出任意长整数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相加,结果放到L1short StrToPosiNum(char * s)/将s转化为一个小于32767的正整数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字符串到整型数字出错!",si);exit(0);if(num1>32767)printf("输入数字太大!,请重新输入:");exit(0);return flag*(short)num1;void input(LinList &L)；/输入一个很长的整数到Lvoid FREE(LinList &L1)/删除以L1为头结点的整个链表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写到文件FILE * fp;LinList p=L1;int i,length;char s100;printf("n文件的名称为:");/将生成的数保存于文件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文件的名称为:");/将生成的数保存于文件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()；/调用input函数，实现两个任意长整数的输入void welcome()/输出欢迎界面printf("nt n");printf("t . .n");printf("t . 任意长的整数加法运算器 .n");printf("t . .n");printf("t n");void fileadd()/读入文件，调用add函数，实现两个任意长整数的相加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);/调用add，计算L1+L2display(L1);putchar('n');flag=0;do/保存计算结果if(flag)printf("

33、;输入非法,请重新输入:");elseprintf("是否保存结果(输入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() /直接输入数字相加LinList L1=NULL,L2=NULL;int flag;system("cls");printf("ttt -ntttt 直接输入求和nttt -n");puts("输入第一个整数:");input(L1);puts("输入第二个整数:&