长整数加减运算

长整数加减运算长整数加减运算44/44长整数加减运算*实践讲课*兰州理工大学技术工程学院2013年春天学期数据结构课程设计题目：长整数的加减运算专业班级：计算机科学与技术一班姓名：郭利强学号：11730108指导教师：王连相成绩：计算机科学与技术专业数据结构课程设计任务书（11级）题目：长整数的加减运算学生姓名：郭利强

学号：

11730108班级：

11级计算机科学与技术一班题目种类：软件工程（

R）

指导教师：

王连相一．题目简介该设计要修业生设计程序，实现两个任意长的整数乞降及差的运算问题。经过该题目的设计过程，可以加深理解线性表的逻辑结构、积蓄结构，掌握线性表上基本运算的实现，进一步理解和熟练掌握课本中所学的各种数据结构，学会怎样把学到的知识用于解决实诘责题，培育学生的着手能力。二．主要任务第一部分：基本算法实现1、线性结构基本算法实现（指导老师依据题目指定）；2、树型结构基本算法实现（指导老师依据题目指定）；3、图型结构基本算法实现（指导老师依据题目指定）；4、查找基本算法实现（指导老师依据题目指定）；5、排序基本算法实现（指导老师依据题目指定）；第二部分：指定题目的设计与实现1、查阅文件资料，一般在3篇以上；2、建立数据的逻辑结构和物理结构；3、达成相应算法的设计；4、达成测试工作；5、撰写设计说明书；6、做好争论工作。三．主要内容、功能及技术指标（1）使用双向循环链表积蓄长整数，每个结点含一个整型变量，主要功能有：长整数输入（建立双向循环链表）、长整数的加法、长整数的减法及结果的显示输出等；（2）最少要用10组测试数据，算法对于这些合法的输入数据都能产生知足规格说明要求的结果；（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据可以得出知足规格说明要求的结果；对算法实现过程中的异常状况能给出有效信息；（4）任何整型变量的范围是-(215-1)~（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号分开，例1，0000，0000，0000；而输入为1，0001，0001和-1，0001，0000实现加法时，应输出"1"；（5）较高要求：使程序在整型量范围是-(2n-1)~(2n-1)的计算机上都能有效地运转。此中，n是由程序读入的参量。四．提交的成就设计说明书一份，内容包含：中文大纲100字；重点词3-5个；序言；3）采纳类c语言定义相关的数据种类4）各模块的伪码算法5）函数的调用关系图6）调试剖析a、调试中碰到的问题及对问题的解决方法；b、算法的时间复杂度和空间复杂度。7）测试结果8）源程序（带说明）设计总结、参照文件、致谢等。刻制光盘一张。五．主要参照文件1．严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学第一版社.2．严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学第一版社.3．《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清华大学第一版社（影印版）.4．谭浩强.《c语言程序设计》.清华大学第一版社.5．数据结构与算法剖析（Java版）,APracticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionCliffordA.Shaffer,张铭,刘晓丹译电子工业第一版社2001年1月六、各阶段时间安排（共2周）周次日期内容地址礼拜一教师讲解设计要求，准备参教室考资料第1周礼拜二~剖析设计要求，进行数据结教室、实三构及算法设计验室礼拜四~算法设计，编程实现实验室五礼拜一~编程上机实现、测试程序实验室第2周三礼拜四~检查程序，争论实验室五2013年6月28日大纲数据结构解决实质应用中的问题，将学习的理论知识应用于实践，加强学生解决实诘责题的能力。采纳的基本数据结构为线性表。计算机积蓄的数据是有范围限制的，对于超出积蓄限制的数据没法直接在计算机被骗算，为此需要设计相应的程序来达成这种超出范围限制的长整数间的加减运算。实现任意长的整形数进行加减运算的程序，要求达成长整数的加、减运算。在这里长整数没有范围限制，可任意长。运算后的进位、借位等都要进行正确办理，可实现动向的输入，实时的输出。重点字：任意长整数，加、减运算序言课程设计是实践性讲课中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程以外的特别课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要修业生在数据结构的逻辑特色和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技术和科学作风方面碰到比较系统和严格的训练。在此次程序设计中我选择了长整数的代数计算这个题目，在一般的程序运算中，长整数是没法计算的，因为计算机一次可以运算的位数是有限，一旦整数很长，就需要一个程序来进行多次计算，经过这个程序，可一把一个长整数分成多个一般整数来进行计算，使得长整数也可以进行运算。我编写的这个程序就可以进行加减乘除的运算，各个数据也可以是负数。目录1.11.23.13.23.33.43.53.63.73.83.93.103.113.124.15.15.2一、大纲设计1.1数据结构此实验采纳的数据结构是双向循环链表。这样可以很简单的找到他的前驱以及它的后继。节点采纳结构体种类，代码以下：typedefstructNode//双向链表的结构体定义{intdata;structNode*prior;structNode*next;}DLNode;1.2使用函数voidListInitiate(DLNodehead)操作结果：初始化一个头结点为head的双向循环链表；intListLength(DLNode*head)操作结果：计算以head为头结点的链表的长度3)intListInsert(DLNode*head,inti,intx)操作结果：将节点数据为x的节点插到第i个地址上去。intabs(intx)操作结果：绝对值函数，返回x的绝对值。intInputNumber(DLNode*head)操作结果：将从键盘中接收数据并把获得的数据存入以head为头结点的链表中。四位一存，中间以逗号区分，结束符为分号。voidOutputNumber(DLNode*head,intsign)操作结果：将以head为头结点的链表中的全部数据输出到显示屏上，voidadd(DLNode*head1,DLNode*head2,DLNode*head3)操作结果：实现正数加正数的加法操作。intchange(DLNode*head1,DLNode*head2)操作结果：判断存在俩个链表中的数的大小，怎样head1中的数大于head2中的数那么返回值为0，反之返回值为1，相等时返回值为2；voidminus(DLNode*head1,DLNode*head2,DLNode*head3)操作结果：计算正数减正数的减法运算。10)voidyunsuan(DLNode*head1,DLNode*head2,DLNode*head3,charch)操作结果：正数，负数，加法，减法。计算式共分为八种运算，在这以前我已经实现了二种运算，那么这个函数就是把这八种运算依据必然的规则转变成已经实现的二种运算来实现圆满的加减法运算。11)voidmain()操作结果：主函数。调用以上的各个函数来指引用户进行长整数的加法运算，加法运算.二、函数流程图开始输入两位整数数字转变链表状况判断两个负数相加两个正数相加相异判断第一个数减第二个数第二个数减第一数输出转变输出结果三、详细设计3.1数据结构详细设计typedefstructNode//双向链表的结构体定义{intdata;structNode*prior;structNode*next;}DLNode;双向循环链表的节点由三个部分组成，第一是数据部分data积蓄此节点的数据，第二是此节点的前驱指针部分*prior指向此节点的前驱，第三是此节点的后继指针部分*next指向此节点的后继。数据部分我们商定它为整形变量，前驱后继指针均为结构体Node种类。3.2链表初始化函数：void

ListInitiate(DLNodehead)

//双向链表的初始化{if((*head=(DLNode*)malloc(

sizeof(DLNode)))==NULL)exit(0);(*head)->prior=*head;(*head)->next=*head;}初始化以前需要定义一个种类为Node型的头结点变量，经过函数后达成链表的初始化即：头节点的前驱指针指向自己，同时他的后继指针也指向自己。3.3计算已知的链表长度：intListLength(DLNode*head)//双向链表的表长{DLNode*p=head;intsize=0;while(p->next!=head){p=p->next;size++;}returnsize;}此函数计算的是已知链表的长度。主要思想：从头结点开始搜寻下一个节点，找到计数器加一。直到再次搜寻到头结点时停止，计算达成。3.4插入函数：intListInsert(DLNode*head,inti,intx)//双向链表的数据插入,i表示是插入的第几个元素{DLNode*p,*s;intj;p=head->next;j=0;while(p!=head&&j<i){p=p->next;j++;}if(j!=i){printf(return

"\n0;

插入地址不合法！");}if((s=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(0);s->data=x;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;return1;

//插入}此函数是已知一双向链表实现在第i个地址插入data为x的节点。函数需要注意的是在什么地址插入才是合法的，在就是在该节点指针时的序次不要搞错。3.5绝对值函数：int

abs(int

x){if(x<0)elsereturn

returnx;

-x;}此函数是实现求一个整数的绝对值。设计这么一个函数主若是考虑到在积蓄负数的时候头结点应该变成正整数，今后经过其余手段变相实现那种运算。3.6读入数据并插入对应的链表函数：intInputNumber(DLNode*head)//读入输入的数据{intinput,i=0;//第i个节点charc;scanf("%d%c",&input,&c);while(1){if(input<0&&i==0)//输入数为负且是第一个节点{head->data=0;//将长整数的符号保存在头结点中//input=abs(input);//取输入数字的绝对值ListInsert(head,i,input);//插入数据}elseif(input>=0&&i==0)//输入数为正且是第一个节点{head->data=1;//将长整数的符号保存在头结点中ListInsert(head,i,input);//插入数据}else{if(head->next->data>=0)ListInsert(head,i,input);

//非第一个节点else{//input=-1*input;ListInsert(head,i,input);}}i++;if(c==';')break;//碰到数据输入达成标记，跳出循环scanf("%d%c",&input,&c);}return1;}此函数实现的是从键盘上获得数据依据三种状况进行不同样的办理，判断是不是头结点，判断是不是整数，判断输入的字符是不是“；”分号。而且若是是正整数它的头结点data等于1不然为0。3.7输出函数voidOutputNumber(DLNode*head,intsign)//从表尾输出数据元素{DLNode*r=head->next;while(r->data==0&&r!=head->prior){r=r->next;}if(sign==1){printf("结果是:");}else{printf("结果是:-");}printf("%d",r->data);r=r->next;while(r!=head){if(r->data<10){printf(",000");printf("%d",r->data);}elseif(r->data<100){printf(",00");printf("%d",r->data);}elseif(r->data<1000){printf(",0");printf("%d",r->data);}else{printf(",%d",r->data);}r=r->next;}printf("\n");}此函数实现的是将最后的结果输出到显示屏上，经过判断数据的正负和数据的范围来进行不同样的办理，以保证在显示屏上显示的是正确的格式。3.8加法函数（正数加上正数）voidadd(DLNode*head1,DLNode*head2,DLNode*head3){intz=0;inte;DLNode*p1,*p2;p1=head1->prior;p2=head2->prior;while(p1!=head1&&p2!=head2){e=p1->data+p2->data+z;if(e>=10000){z=1;e=e%10000;}elsez=0;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;}if(p1==head1&&p2!=head2){while(p2!=head2){e=p2->data+z;if(e>=10000){z=1;e=e%10000;}elsez=0;ListInsert(head3,0,e);p2=p2->prior;}if(z==1)ListInsert(head3,0,z);}elseif(p1!=head1&&p2==head2){while(p1!=head1){e=p1->data+z;if(e>=10000){z=1;e=e%10000;}elsez=0;ListInsert(head3,0,e);p1=p1->prior;}if(z==1)ListInsert(head3,0,z);}else{if(z==1)ListInsert(head3,0,z);}}此函数实现的是两个正数之间的相加运算，主要的算法和我们手算加法是同样的，第一设置一个进位计数的变量，依据积蓄的特色从低位开始相加带进步位即可得出相应的位和，最后更新进位变量。办理界线状况：若是两个链表同样长同时他们最高位在计算达成时依旧会有进位，那么应该考虑到在数据的更高位插入一个1表示最后的计算结果，这样才可以保证数据的圆满性。3.9判断俩正数大小函数：intchange(DLNode*head1,DLNode*head2){intlength1,length2,r=2;length1=ListLength(head1);length2=ListLength(head2);DLNode*p1,*p2;p1=head1->next;p2=head2->next;if(length1>length2){r=0;returnr;}elseif(length1<length2){r=1;returnr;}else{inti=0;for(i=0;i<length1;i++){if(p1->data>p2->data){r=0;returnr;break;}elseif(p2->data>p1->data){r=1;returnr;break;}else{p1=p1->next;p2=p2->next;r=2;}}}returnr;}此函数实现的是判断俩个正数的大小。考虑俩正数的在链表中所占积蓄单元的多少，多的必然大，当他们同样长时，一位一位的比较直到找到一个节点中的data

比另一个链表的对应节点的

data

大为止。若是最后仍是同样大那么这两个数就是同样大的。返回值为自己商定的参数

r等于

2表示俩数同样大，等于

1表示第二个数大，等于

0表示第一个数大。3.10减法函数：voidminus(DLNode*head1,DLNode*head2,DLNode*head3){intz=0,x=-1;inte;DLNode*p1,*p2;p1=head1->prior;p2=head2->prior;x=change(head1,head2);if(x==0){while(p1!=head1&&p2!=head2){p1->data=p1->data+z;if(p1->data>=p2->data){e=p1->data-p2->data;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;z=0;}else{e=10000+p1->data-p2->data;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;z=-1;}}p1->data=p1->data+z;while(p1!=head1){e=p1->data;ListInsert(head3,0,e);p1=p1->prior;}}elseif(x==1){p2=head1->prior;p1=head2->prior;while(p1!=head2&&p2!=head1){p1->data=p1->data+z;if(p1->data>=p2->data){e=p1->data-p2->data;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;z=0;}else{e=10000+p1->data-p2->data;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;z=-1;}}p1->data=p1->data+z;while(p1!=head2){e=p1->data;ListInsert(head3,0,e);p1=p1->prior;}head3->next->data=-1*head3->next->data;}else{head3->next->data=0;}}此函数实现的是两个正数的减法运算。整个函数分为俩大部分，第一部分处理第一个数大于第二个数，第二部分是办理第二个数大于第一个数。在这个为题上我们想了好长时间，感觉俩部分可以结合成一部分，但是因为知识所限没有想出更好的方法，这使得代码量增添了足足一倍之多。依旧模拟手算减法，先找到俩数字中最大的那个，用大的减去小的。最后判断符号位。3.11整合八种状况函数：voidyunsuan(DLNode*head1,DLNode*head2,DLNode*head3,charch){DLNode*p1,*p2;p1=head1->next;p2=head2->next;if(head1->data==1&&head2->data==1){if(ch=='+')add(head1,head2,head3);elseminus(head1,head2,head3);}elseif(head1->data==1&&head2->data==0){if(ch=='+'){head2->next->data*=-1;minus(head1,head2,head3);}else{head2->next->data*=-1;add(head1,head2,head3);}}elseif(head1->data==0&&head2->data==1){if(ch=='+'){head1->next->data*=-1;minus(head2,head1,head3);}else{head1->next->data*=-1;head2->next->data*=-1;add(head1,head2,head3);head3->next->data*=-1;}}else{if(ch=='+'){head1->next->data*=-1;head2->next->data*=-1;add(head1,head2,head3);head3->next->data*=-1;}else{head1->next->data*=-1;head2->next->data*=-1;minus(head2,head1,head3);}}}此函数实现的是八种状况的整合。八种状况分别是正数加正数、正数加负数、正数减正数、正数减负数、负数加负数、负数加正数、负数减正数、负数减负数。此函数调用已经做好的正数加正数和正数减正数函数判断符号位，依据必然的规则实现八种运算。3.12主函数：voidmain(){charch,ch1;while(1){//intw=-1;DLNode*a,*b,*c;ListInitiate(&a);ListInitiate(&b);ListInitiate(&c);printf("请输入数A(以分号结束):");InputNumber(a);//printf("\n");printf("请输入数B(以分号结束):");InputNumber(b);//w=change(a,b);printf("请选择操作符：<+,->:\n");scanf("%s",&ch1);if(ch1=='+'||ch1=='-'){yunsuan(a,b,c,ch1);OutputNumber(c,1);}elseif(ch1=='*')chengfa(a,b);elseprintf("此版本不支持%c运算",ch1);printf("要连续吗？(y/n):");scanf("%s",&ch);if(ch=='Y'||ch=='y'){printf("\n");continue;}elseexit(0);}}此函数是主函数。主要的作用是为用户做一个提示，怎样达成自己想要的运算。同时调用各个函数实现运算。四、调试剖析4.1调试过程中碰到的问题在函数编写以前我第一写出了全部函数的框架以及各个函数之间的关系，依据渐渐求精的思想来圆满整个程序。即即是这样我依旧碰到了很多错误。比方：在实现正数减正数时，我一开始没有分为以上所说的俩个部分，而是把俩个部分整合到一起实现一个大函数，但是在我运转调试时结果大不如人意，出现的都是匪夷所思的数字，我根本就计算不出这些数字是怎么来的。没有方法我只幸好另辟路子来达成函数的实现。于是我就分作两个部分来实现，这样渐渐追踪可以使思路更加清楚，所付出的代价是代码量增添。五、使用说明和测试结果5.1使用说明用户在使用该程序时，只需依据程序中的规定进行即可实现长整数的加减运算，详细使用步骤以下：点击运转按钮，在DOS窗口下依据规定输入的数字需要从低位开始数四位一组用逗号分开。输入第一个数字。同上输入第二个数；选大纲对这两个长整数进行的运算。两个操作数与运算符选择达成后，按回车键即可获得运算结果。5.2测试结果5)考虑界线数字，输入0和0做加法运算，输出“0”，结果以以下列图：6)考虑加法进位（包含低位向高位的进位以及高位仍有进位状况），结果以以下列图：7)考虑减法进位而且数A小于数B，结果以以下列图：考虑减法进位而且数A大于数B，结果以以下列图：连续输入两次数据测试；以以下列图：10）较高要求附录程序的圆满代码清单：#include#include#includetypedef

<stdio.h><stdlib.h><malloc.h>structNode

//双向链表的结构体定义{intdata;structNode*prior;structNode*next;}DLNode;voidListInitiate(DLNodehead){

//双向链表的初始化if((*head=(DLNode*)malloc(

sizeof(DLNode)))==NULL)exit(0);(*head)->prior=*head;(*head)->next=*head;}int

ListLength(DLNode*head)

//双向链表的表长{DLNode*p=head;intsize=0;while(p->next!=head){p=p->next;size++;}return}

size;intListInsert(DLNode*head,inti,intx)//双向链表的数据插入,i表示是插入的第几个元素{DLNode*p,*s;intj;p=head->next;j=0;while(p!=head&&j<i){p=p->next;j++;}if(j!=i){printf("\n插入地址不合法！");return0;}if((s=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(0);s->data=x;s->prior=p->prior;p->prior->next=s;s->next=p;p->prior=s;return1;

//插入}int

abs(int

x){if(x<0)

return

-x;elsereturnx;}intInputNumber(DLNode*head)//读入输入的数据{intinput,i=0;//第i个节点charc;scanf("%d%c",&input,&c);while(1){if(input<0&&i==0)//输入数为负且是第一个节点{head->data=0;//将长整数的符号保存在头结点中//input=abs(input);//取输入数字的绝对值ListInsert(head,i,input);//插入数据}elseif(input>=0&&i==0)//输入数为正且是第一个节点{head->data=1;//将长整数的符号保存在头结点中ListInsert(head,i,input);

//插入数据}else{if(head->next->data>=0)ListInsert(head,i,input);

//非第一个节点else{//input=-1*input;ListInsert(head,i,input);}}i++;if(c==';')break;//碰到数据输入达成标记，跳出循环scanf("%d%c",&input,&c);}return1;}voidOutputNumber(DLNode*head,intsign)//从表尾输出数据元素{DLNode*r=head->next;while(r->data==0&&r!=head->prior){r=r->next;}if(sign==1){printf("结果是:");}else{printf("结果是:-");}printf("%d",r->data);r=r->next;while(r!=head){if(r->data<10){printf(",000");printf("%d",r->data);}elseif(r->data<100){printf(",00");printf("%d",r->data);}elseif(r->data<1000){printf(",0");printf("%d",r->data);}else{printf(",%d",r->data);}r=r->next;}printf(

"\n"

);}voidadd(DLNode*head1,DLNode*head2,DLNode*head3){intz=0;inte;DLNode*p1,*p2;p1=head1->prior;p2=head2->prior;while(p1!=head1&&p2!=head2){e=p1->data+p2->data+z;if(e>=10000){z=1;e=e%10000;}elsez=0;ListInsert(head3,0,e);p1=p1->prior;p2=p2->prior;}if(p1==head1&&p2!=head2){while(p2!=head2){e=p2->data+z;if(e>=10000){z=1;e=e%10000;}elsez=0;ListInsert(head3,0,e);p2=p2->prior;}if(z==1)ListInsert(head3,0,z);}elseif(p1!=head1&&p2==head2){while(p1!=head1){e=p1->data+z;if(e>=10000){z=1;e=e%10000;}elsez=0;ListInsert(head3,0,e);p1=p1->prior;}if(z==1)ListInsert(head3,0,z);}else{if(z==1)ListInsert(head3,0,z);}}intchange(DLNode*head1,DLNode*head2){intlength1,length2,r=2;length1=ListLength(head1);length2=ListLength(head2);DLNode*p1,*p2;p1=head1->next;p2=head2->next;if(length1>length2){r=0;returnr;}elseif(length1<length2){r=1;returnr;}else{inti=0;for(i=0;i<length1;i++){if(p1->data>p2->data){r=0;returnr;break;}elseif(p2->data>p1->data){r=1;returnr;break;}else{p1=p1->next;p2=p2->next;r=2;}}}returnr;}voidyunsuan(DLNode*head1,DLNode*head2,DLNode*head3,charch){DLNode*p1,*p2;p1=head1->next;p2=head2->next;if(head1->data==1&&head2->data==1){if(ch=='+')add(head1,head2,head3);else(head1,head2,head3);}elseif(head1->data==1&&head2->data==0){if(ch=='+'){head2->next->data*=-1;(head1,head2,head3);}else{head2->next->data*=-1;add(head1,head2,head3);}}elseif(head1->data==0&&head2->data==1){if(ch=='+'){head1->next->data*=-1;(head2,head1,head3);}else{head1->next->data*=-1;head2->next->data*=-1;add(head1,head2,head3);head3->next->data*=-1;}}else{if(ch=='+'){head1->next->data*=-1;head2->next->data*=-1;add(head1,head2,head3);head3->next->data*=-1;}else{head1->next->data*=-1;head2->next->data*=-1;(head