长整数加减运算实验报告

实验一一、需求分析实验内容：计算机存储的数据是有范围限制的，对于超出存储限制的数据无法直接在计算机中计算，为此需要设计相应的程序来完成这种超出范围限制的长整数间的四则运算。设计一个实现任意长的整形数进行四则运算的程序，要求完成长整数的加、减运算，乘除运算可选做。在这里长整数没有范围限制，可任意长。运算后的进位、借位等都要进行正确处理，可实现动态的输入，实时的输出。实验目的：学习使用基本的数据结构解决实际应用中的问题，将学习的理论知识应用于实践，增强学生解决实际问题的能力。这里可采用的基本数据结构为线性表。测试数据：1)输入：动态输入以数字开头，可以任意长度，中间不用输入分隔符，直接输入即可。2)输出：实时输出的结果是加减运算后的结果。3)功能：实现长整数的加减运算。4)测试数据：0、0；输出“0”2345，6789、-7654，3211；输出“1，0000，0000”1，0000，0000，0000、9999，9999；输出“9999，0000，0001”1，0001，0001、；1，0001，0001；输出“0”二、概要设计1.数据结构此实验采用的数据结构是双向循环链表。这样可以很容易的找到他的前驱以及它的后继。节点采用结构体类型，代码如下：typedefstructNode//双向链表的结构体定义{intdata;structNode*prior;structNode*next;}DLNode;2.使用函数1)voidListInitiate(DLNode**head)操作结果：初始化一个头结点为head的双向循环链表；2)intListLength(DLNode*head)操作结果：计算以head为头结点的链表的长度3)intListInsert(DLNode*head,inti,intx)操作结果：将节点数据为x的节点插到第i个位置上去。4)intabs(intx)操作结果：绝对值函数，返回x的绝对值。5)intInputNumber(DLNode*head)操作结果：将从键盘中接收数据并把得到的数据存入以head为头结点的链表中。四位一存，中间以逗号区分，结束符为分号。6)voidOutputNumber(DLNode*head,intsign)操作结果：将以head为头结点的链表中的所有数据输出到显示屏上，7)voidadd(DLNode*head1,DLNode*head2,DLNode*head3)操作结果：实现正数加正数的加法操作。8)intchange(DLNode*head1,DLNode*head2)操作结果：判断存在俩个链表中的数的大小，如何head1中的数大于head2中的数那么返回值为0，反之返回值为1，相等时返回值为2；9)voidmethod(DLNode*head1,DLNode*head2,intx)操作结果：计算正数乘以正数的乘法运算。10)voidminus(DLNode*head1,DLNode*head2,DLNode*head3)操作结果：计算正数减正数的减法运算。11)voidyunsuan(DLNode*head1,DLNode*head2,DLNode*head3,charch)操作结果：正数，负数，加法，减法。计算式共分为八种运算，在这之前我已经实现了二种运算，那么这个函数就是把这八种运算按照一定的规则转化成已经实现的二种运算来实现完整的加减法运算。12)voidchengfa(DLNode*head1,DLNode*head2)操作结果：在乘法中我只是实现了正数乘以正数的运算，那么这个函数就是通过调用method函数按照一定的规则来实现完整的乘法运算。13)voidmain()操作结果：主函数。调用以上的各个函数来引导用户进行长整数的加法运算，加法运算，乘法运算。三、详细设计1.数据结构详细设计typedefstructNode//双向链表的结构体定义{intdata;structNode*prior;structNode*next;}DLNode;双向循环链表的节点由三个部分组成，第一是数据部分data存储此节点的数据，第二是此节点的前驱指针部分*prior指向此节点的前驱，第三是此节点的后继指针部分*next指向此节点的后继。数据部分我们约定它为整形变量，前驱后继指针均为结构体Node类型。2.链表初始化函数：voidListInitiate(DLNode**head)//双向链表的初始化{if((*head=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(0);(*head)-prior=*head;(*head)-next=*head;}初始化之前需要定义一个类型为Node型的头结点变量，经过函数后完成链表的初始化即：头节点的前驱指针指向自己，同时他的后继指针也指向自己。3.计算已知的链表长度：intListLength(DLNode*head)//双向链表的表长{DLNode*p=head;intsize=0;while(p-next!=head){p=p-next;size++;}returnsize;}此函数计算的是已知链表的长度。主要思想：从头结点开始寻找下一个节点，找到计数器加一。直到再次寻找到头结点时停止，计算完毕。4.插入函数：intListInsert(DLNode*head,inti,intx)//双向链表的数据插入,i表示是插入的第几个元素{DLNode*p,*s;intj;p=head-next;j=0;while(p!=head&&ji){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;}此函数是已知一双向链表实现在第i个位置插入data为x的节点。函数需要注意的是在什么位置插入才是合法的，在就是在该节点指针时的顺序不要搞错。5.绝对值函数：intabs(intx){if(x0)return-x;elsereturnx;}此函数是实现求一个整数的绝对值。设计这么一个函数主要是考虑到在存储负数的时候头结点应该变为正整数，然后通过其他手段变相实现那种运算。6.读入数据并插入对应的链表函数：intInputNumber(DLNode*head)//读入输入的数据{intinput,i=0;//第i个节点charc;scanf(%d%c,&input,&c);while(1){if(input0&&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。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-data10){printf(,000);printf(%d,r-data);}elseif(r-data100){printf(,00);printf(%d,r-data);}elseif(r-data1000){printf(,0);printf(%d,r-data);}else{printf(,%d,r-data);}r=r-next;}printf(\n);}此函数实现的是将最后的结果输出到显示屏上，经过判断数据的正负和数据的范围来进行不同的处理，以保证在显示屏上显示的是正确的格式。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表示最后的计算结果，这样才可以保证数据的完整性。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(length1length2){r=0;returnr;}elseif(length1length2){r=1;returnr;}else{inti=0;for(i=0;ilength1;i++){if(p1-datap2-data){r=0;returnr;break;}elseif(p2-datap1-data){r=1;returnr;break;}else{p1=p1-next;p2=p2-next;r=2;}}}returnr;}此函数实现的是判断俩个正数的大小。考虑俩正数的在链表中所占存储单元的多少