中国石油大学《数据结构》任意长的整数加减法运算

中国石油大学《数据结构》任意长的整数加减法运算1.课程设计题目任意长的整数加减法运算题目要求：设计算法，实现一个任意长的整数进行加法、减法运算的演示程序。例如：1234，5123，4512，3451，2345与-1111，1111，1111，1111，1111的加法结果为：0123，4012，3401，2340，1234。基本要求如下：利用链表实现长整数的存储，每个节点含一个整型变量；整型变量的范围：-（2^15-1）~（2^15-1）；输入与输出形式每四位一组，组间用逗号分隔开。如：1986,8213,1935,2736,3299；界面友好，每步给出适当的操作提示，并且系统具有一定的容错能力。至少给出下面的测试数据：（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题目要求：设计算法，实现一个任意长的整数进行加法、减法运算的演示程序。例如：1234，5123，4512，3451，2345与-1111，1111，1111，1111，1111的加法结果为：0123，4012，3401，2340，1234。基本要求如下：利用链表实现长整数的存储，每个节点含一个整型变量；整型变量的范围：-（2^15-1）~（2^15-1）；输入与输出形式每四位一组，组间用逗号分隔开。如：1986,8213,1935,2736,3299；界面友好，每步给出适当的操作提示，并且系统具有一定的容错能力。至少给出下面的测试数据：（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一、需求分析1.1问题描述：设计算法，实现一个任意长的整数进行加法、减法运算的演示程序。1.2基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是－（215－1）～（215－1）。输入输出形式：按照中国对于长整数的表示习惯，每四位是一组，组间用逗号隔开（1）长整数的减法（2）多个长整数的连续加减法，并带括号等。具体方式可以参见表达式的求值部分，利用栈1.3测试数据：（1）0；0；应输出“0”（2）－2345，6789；－7654，3211；应输出“－1，0000，0000”（3）－9999，9999；1，0000，0000，0000；应输出“9999，0000，0001”（4）1，0001，0001；－1，0001，0001；应输出“0”（5）1，0001，0001；－1，0001，0000；应输出“1”（6）－9999，9999，9999；－9999，9999，9999；应输出“－1，9999，9999，9998”（7）1，0000，9999，9999；1；应输出“1，0001，0000，0000”二、概要设计此实验采用的数据结构是双向循环链表。这样可以很容易的找到他的前驱以及它的后继。节点采用结构体类型，代码如下：typedefstructNode//双向链表的结构体定义{ intdata; structNode*prior; structNode*next;}DLNode;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)

操作结果：实现正数加正数的加法操作。

voidminus(DLNode*head1,DLNode*head2,DLNode*head3)

操作结果：计算正数减正数的减法运算。

voidyunsuan(DLNode*head1,DLNode*head2,DLNode*head3,charch)

操作结果：正数，负数，加法，减法。计算式共分为八种运算，在这之前我已经实现了二种运算，那么这个函数就是把这八种运算按照一定的规则转化成已经实现的二种运算来实现完整的加减法运算。voidmain()

操作结果：主函数。调用以上的各个函数来引导用户进行长整数的加法运算，加法运算，乘法运算。详细设计3.1数据结构详细设计typedefstructNode//双向链表的结构体定义{ intdata; structNode*prior; structNode*next;}DLNode;双向循环链表的节点由三个部分组成，第一是数据部分data存储此节点的数据，第二是此节点的前驱指针部分*prior指向此节点的前驱，第三是此节点的后继指针部分*next指向此节点的后继。数据部分我们约定它为整形变量，前驱后继指针均为结构体Node类型。3.2链表初始化函数：voidListInitiate(DLNode**head)//双向链表的初始化{ 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("\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的节点。函数需要注意的是在什么位置插入才是合法的，在就是在该节点指针时的顺序不要搞错。3.5绝对值函数intabs(intx){ if(x<0)return-x; elsereturnx;}此函数是实现求一个整数的绝对值。设计这么一个函数主要是考虑到在存储负数的时候头结点应该变为正整数，然后通过其他手段变相实现那种运算。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减法函数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.10整合八种情况函数：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.11主函数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); }}此函数是主函数。主要的作用是为用户做一个提示，如何完成自己想要的运算。同时调用各个函数实现运算。四、调试分析在函数编写之前我首先写出了所有函数的框架以及各个函数之间的关系，根据逐步求精的思想来完善整个程序。即使是这样我仍然遇到了不少错误。例如：在实现正数减正数时，我一开始没有分为以上所说的两个部分，而是把两个部分整合到一起实现一个大函数，但是在我运行调试时结果大不如人意，出现的都是匪夷所思的数字，我根本就推算不出这些数字是怎么来的。没有办法我只好在另辟途径来完成函数的实现。于是我就分作两个部分来实现，这样逐步追踪可以使思绪更加清晰，所付出的代价是代码量增加。五、使用说明和测试结果5.1使用说明用户在使用该程序时，只需按照程序中的规定进行即可实现长整数的加减运算，具体使用步骤如下：点击运行按钮，在DOS窗口下按照规定输入的数字需要从低位开始数四位一组用逗号隔开。输入第一个数字。同上输入第二个数；选择要对这两个长整数进行的运算。两个操作数与运算符选择完毕后，按回车键即可得到运算结果。5.2测试结果考虑边界数字，输入0和0做加法运算，输出“0”，结果如下图：考虑加法进位（包括低位向高位的进位以及高位仍有进位情况），结果如下图：考虑减法进位并且数A小于数B以及数A大于数B，结果如下图：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”六、心得体会本次试验是我感觉到了理论应用与实践的意义，以前我们也做过类似的题目，所以在试验中我感觉还是比较顺利的但是还是花了我两天时间才完成。根据模块化思想来把握整体结构会使自己的思路更加清晰，更加明了。得到的东西往往是说不出来的只有自己心理面最清楚。 七、附录程序的完整代码清单：#include<stdio.h>#include<stdlib.h>#include<malloc.h>typedefstructNode//双向链表的结构体定义{ intdata; structNode*prior; structNode*next;}DLNode;voidListInitiate(DLNode**head)//双向链表的初始化{ if((*head=(DLNode*)malloc(sizeof(DLNode)))==NULL)exit(0); (*head)->prior=*head; (*head)->next=*head;}intListLength(DLNode*head)//双向链表的表长{ DLNode*p=head; intsize=0; while(p->next!=head) { p=p->next; size++; }returnsize;}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;}intabs(intx){ 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;}voidmethod(DLNode*head1,DLNode*head2,intx){ voidminus(DLNode*head1,DLNode*head2,DLNode*head3); DLNode*temp1; DLNode*temp2; DLNode*temp3; DLNode*temp4; DLNode*temp5; inte,z=0,i,j; ListInitiate(&temp1); ListInitiate(&temp2); ListInitiate(&temp3); ListInsert(temp2,0,0); DLNode*p1,*p2; p1=head1->prior; p2=head2->prior; for(i=0;i<ListLength(head2);i++){ ListInitiate(&temp4); ListInitiate(&temp5); ListInsert(temp4,0,0); while(p1!=head1) { e=p1->data*p2->data+z; if(e>9999) { z=e/10000; e=e-z*10000; } elsez=0; ListInsert(temp1,0,e); p1=p1->prior; } if(z!=0)ListInsert(temp1,0,z); for(j=0;j<i-1;j++) { ListInsert(temp1,ListLength(temp1),0); } add(temp1,temp2,temp3); temp1=temp4; temp2=temp3; temp3=temp5; z=0; p1=head1->prior; p2=p2->prior; }OutputNumber(temp2,x);}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; }}voidyunsuan(DLNode*head1,DLNode*head2,DLNode*head3,charch){ DLNode*p1,*p2; p1=head1->next; p2=head2->next; if(head1-