长整数加减运算实验报告.doc

长整数加减的运算一、需求分析问题描述：设计一个实现任意长的整数进行加法运算的演示程序基本要求：利用双向循环链表实现长整数的存储，每个结点含一个整型变量。任何整型变量的范围是（2 15 1）（2 15 1） 。输入输出形式：按照中国对于长整数的表示习惯，每四位是一组，组间用逗号隔开更高要求：（1）长整数的减法（2）多个长整数的连续加减法，并带括号等。具体方式可以参见表达式的求值部分，利用栈测试数据：（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” 一、 概要设计1. 数据结构此实验采用的数据结构是双向循环链表。这样可以很容易的找到他的前驱以及它的后继。节点采用结构体类型，代码如下：typedef struct Node / 双向链表的结构体定义 int data; struct Node *prior;struct Node *next;DLNode;2. 使用函数1) void ListInitiate(DLNode *head)操作结果：初始化一个头结点为head的双向循环链表；2) int ListLength(DLNode *head)操作结果：计算以head为头结点的链表的长度3) int ListInsert(DLNode *head,int i,int x)操作结果：将节点数据为x的节点插到第i个位置上去。4) int abs(int x)操作结果：绝对值函数，返回x的绝对值。5) int InputNumber(DLNode *head)操作结果：将从键盘中接收数据并把得到的数据存入以head为头结点的链表中。四位一存，中间以逗号区分，结束符为分号。6) void OutputNumber(DLNode *head,int sign)操作结果：将以head为头结点的链表中的所有数据输出到显示屏上，7) void add(DLNode *head1,DLNode *head2,DLNode *head3)操作结果：实现正数加正数的加法操作。8) int change(DLNode *head1,DLNode *head2)操作结果：判断存在俩个链表中的数的大小，如何head1中的数大于head2中的数那么返回值为0，反之返回值为1，相等时返回值为2；9) void method(DLNode *head1,DLNode *head2,int x)操作结果：计算正数乘以正数的乘法运算。10) void minus(DLNode *head1,DLNode *head2,DLNode *head3)操作结果：计算正数减正数的减法运算。11) void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch)操作结果：正数，负数，加法，减法。计算式共分为八种运算，在这之前我已经实现了二种运算，那么这个函数就是把这八种运算按照一定的规则转化成已经实现的二种运算来实现完整的加减法运算。12) void chengfa(DLNode *head1,DLNode *head2)操作结果：在乘法中我只是实现了正数乘以正数的运算，那么这个函数就是通过调用method函数按照一定的规则来实现完整的乘法运算。13) void main()操作结果：主函数。调用以上的各个函数来引导用户进行长整数的加法运算，加法运算，乘法运算。二、 详细设计1. 数据结构详细设计typedef struct Node / 双向链表的结构体定义int data;struct Node *prior;struct Node *next;DLNode;双向循环链表的节点由三个部分组成，第一是数据部分data存储此节点的数据，第二是此节点的前驱指针部分*prior指向此节点的前驱，第三是此节点的后继指针部分*next指向此节点的后继。数据部分我们约定它为整形变量，前驱后继指针均为结构体Node类型。2. 链表初始化函数：void ListInitiate(DLNode *head) /双向链表的初始化if(*head=(DLNode *)malloc(sizeof(DLNode)=NULL) exit(0);(*head)-prior=*head;(*head)-next=*head;初始化之前需要定义一个类型为Node型的头结点变量，经过函数后完成链表的初始化即：头节点的前驱指针指向自己，同时他的后继指针也指向自己。3. 计算已知的链表长度：int ListLength(DLNode *head) /双向链表的表长DLNode *p=head;int size=0;while(p-next!=head) p=p-next; size+;return size; 此函数计算的是已知链表的长度。主要思想：从头结点开始寻找下一个节点，找到计数器加一。直到再次寻找到头结点时停止，计算完毕。4. 插入函数：int ListInsert(DLNode *head,int i,int x) /双向链表的数据插入,i表示是插入的第几个元素DLNode *p,*s;int j;p=head-next;j=0;while(p!=head&jnext;j+;if(j!=i) printf(n插入位置不合法！);return 0;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;return 1;此函数是已知一双向链表实现在第i个位置插入data为x的节点。函数需要注意的是在什么位置插入才是合法的，在就是在该节点指针时的顺序不要搞错。5. 绝对值函数：int abs(int x) if(x0) return -x;else return x;此函数是实现求一个整数的绝对值。设计这么一个函数主要是考虑到在存储负数的时候头结点应该变为正整数，然后通过其他手段变相实现那种运算。6. 读入数据并插入对应的链表函数：int InputNumber(DLNode *head) /读入输入的数据int input,i=0;/第i个节点char c;scanf(%d%c,&input,&c);while(1)if(inputdata=0;/将长整数的符号保存在头结点中/input=abs(input);/取输入数字的绝对值ListInsert(head,i,input);/插入数据else if(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);return 1;此函数实现的是从键盘上得到数据根据三种情况进行不同的处理，判断是否是头结点，判断是否是整数，判断输入的字符是否是“；”分号。并且如果是正整数它的头结点data等于1否则为0。7. 输出函数void OutputNumber(DLNode *head,int sign) /从表尾输出数据元素DLNode *r=head-next;while(r-data=0&r!=head-prior)r=r-next;if(sign=1) printf(结果是:);elseprintf(结果是: -);printf(%d,r-data);r=r-next;while(r!=head)if(r-datadata);else if(r-datadata);else if(r-datadata);elseprintf(,%d,r-data);r=r-next;printf(n);此函数实现的是将最后的结果输出到显示屏上，经过判断数据的正负和数据的范围来进行不同的处理，以保证在显示屏上显示的是正确的格式。8. 不完整加法函数（只可实现正数加上正数）void add(DLNode *head1,DLNode *head2,DLNode *head3) int z=0;int e;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;else z=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;else z=0;ListInsert(head3,0,e);p2=p2-prior; if(z=1) ListInsert(head3,0,z); else if(p1!=head1&p2=head2) while(p1!=head1) e=p1-data+z;if(e=10000)z=1;e=e%10000; else z=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. 判断俩正数大小函数：int change(DLNode *head1,DLNode *head2)int length1,length2,r=2;length1=ListLength(head1); length2=ListLength(head2);DLNode *p1,*p2;p1=head1-next;p2=head2-next;if(length1length2)r=0;return r;else if(length1length2)r=1;return r;elseint i=0;for(i=0;idatap2-data)r=0;return r;break;else if(p2-datap1-data)r=1;return r;break;elsep1=p1-next;p2=p2-next;r=2;return r;此函数实现的是判断俩个正数的大小。考虑俩正数的在链表中所占存储单元的多少，多的一定大，当他们一样长时，一位一位的比较直到找到一个节点中的data比另一个链表的对应节点的data大为止。如果最后仍是一样大那么这两个数就是一样大的。返回值为自己约定的参数r等于2表示俩数一样大，等于1表示第二个数大，等于 0表示第一个数大。10. 乘法函数：void method(DLNode *head1,DLNode *head2,int x)void minus(DLNode *head1,DLNode *head2,DLNode *head3);DLNode *temp1;DLNode *temp2;DLNode *temp3;DLNode *temp4;DLNode *temp5;int e,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;idata*p2-data+z;if(e9999)z=e/10000;e=e-z*10000;else z=0;ListInsert(temp1,0,e);p1=p1-prior;if(z!=0) ListInsert(temp1,0,z);for(j=0;jprior;p2=p2-prior;OutputNumber(temp2,x);此函数实现的是俩个整数的乘法运算。模仿手算乘法，乘数的每一位分别和被乘数相乘得到的结果相加，注意的是在每次乘完相加时注意把低位的空缺补上0，以保证数据可以按位相加。在每一位乘法时需要注意一定要加上低位的进位以及改变进位的值，这样才能保证每一位诚出来的结果是正确的。11. 减法函数：void minus(DLNode *head1,DLNode *head2,DLNode *head3)int z=0,x=-1;int e;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; else if(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;elsehead3-next-data=0;此函数实现的是两个正数的减法运算。整个函数分为俩大部分，第一部分处理第一个数大于第二个数，第而部分是处理第二个数大于第一个数。在这个为题上我自己想了好长时间，感觉俩部分可以 结合成一部分，但是由于本人的知识所限没有想出更好的办法，这使得代码量增加了足足一倍之多。仍然模仿手算减法，先找到俩数字中最大的那个，用大的减去小的。最后判断符号位。12. 整合八种情况函数：void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch) DLNode *p1,*p2;p1=head1-next;p2=head2-next;if(head1-data=1&head2-data=1) if(ch=+) add(head1,head2,head3);else minus(head1,head2,head3);else if(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);else if(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;elseif(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);此函数实现的是八种情况的整合。八种情况分别是正数加正数、正数加负数、正数减正数、正数减负数、负数加负数、负数加正数、负数减正数、负数减负数。此函数调用已经做好的正数加正数和正数减正数函数判断符号位，根据一定的规则实现八种运算。13. 整合乘法运算函数：void chengfa(DLNode *head1,DLNode *head2)int i;if(head1-next-data*head2-next-data)next-data=abs(head1-next-data);head2-next-data=abs(head2-next-data);i=0;method(head1,head2,i);elsehead1-next-data=abs(head1-next-data);head2-next-data=abs(head2-next-data);i=1;method(head1,head2,i);此函数实现的是乘法运算的完整运算。调用已经实现的正数乘以正数的函数来计算函数值，在判断最终的函数符号，得到最和的结果。14. 主函数：void main()char ch,ch1;while(1)/int w=-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);else if(ch1=*) chengfa(a,b);else printf(此版本不支持%c运算,ch1);printf(要继续吗？(y/n) :);scanf(%s,&ch);if(ch=Y|ch=y) printf(n);continue;else exit(0); 此函数是主函数。主要的作用是为用户做一个提示，如何完成自己想要的运算。同时调用各个函数实现运算。三、 调试分析1. 调试过程中遇到的问题在函数编写之前我首先写出了所有函数的框架以及各个函数之间的关系，根据逐步求精的思想来完善整个程序。即使是这样我仍然遇到了不少错误。例如：在实现正数减正数时，我一开始没有分为以上所说的俩个部分，而是把俩个部分整合到一起实现一个大函数，但是在我运行调试时结果大不如人意，出现的都是匪夷所思的数字，我根本就推算不出这些数字是怎么来的。没有办法我只好在另辟途径来完成函数的实现。于是我就分作两个部分来实现，这样逐步追踪可以使思绪更加清晰，所付出的代价是代码量增加。四、 使用说明和测试结果1. 使用说明用户在使用该程序时，只需按照程序中的规定进行即可实现长整数的加减运算，具体使用步骤如下：1) 点击运行按钮，在DOS窗口下按照规定输入的数字需要从低位开始数四位一组用逗号隔开。输入第一个数字。2) 同上输入第二个数；3) 选择要对这两个长整数进行的运算。4) 两个操作数与运算符选择完毕后，按回车键即可得到运算结果。2. 测试结果1) 考虑边界数字，输入0和0做加法运算，输出“0”，结果如下图：2) 考虑加法进位（包括低位向高位的进位以及高位仍有进位情况），结果如下图：3) 考虑减法进位并且数A小于数B以及数A大于数B，结果如下图：4) 乘法结果为正数以及负数两种情况，结果如下图：5) 本试验要求的数据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 #include #include typedef struct Node / 双向链表的结构体定义int data;struct Node *prior;struct Node *next;DLNode;void ListInitiate(DLNode *head) /双向链表的初始化if(*head=(DLNode *)malloc(sizeof(DLNode)=NULL) exit(0);(*head)-prior=*head;(*head)-next=*head;int ListLength(DLNode *head) /双向链表的表长DLNode *p=head;int size=0;while(p-next!=head) p=p-next; size+;return size;int ListInsert(DLNode *head,int i,int x) /双向链表的数据插入,i表示是插入的第几个元素DLNode *p,*s;int j;p=head-next;j=0;while(p!=head&jnext;j+;if(j!=i) printf(n插入位置不合法！);return 0;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;return 1;int abs(int x) if(x0) return -x;else return x;int InputNumber(DLNode *head) /读入输入的数据int input,i=0;/第i个节点char c;scanf(%d%c,&input,&c);while(1)if(inputdata=0;/将长整数的符号保存在头结点中/input=abs(input);/取输入数字的绝对值ListInsert(head,i,input);/插入数据else if(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);return 1;void OutputNumber(DLNode *head,int sign) /从表尾输出数据元素DLNode *r=head-next;while(r-data=0&r!=head-prior)r=r-next;if(sign=1) printf(结果是:);elseprintf(结果是: -);printf(%d,r-data);r=r-next;while(r!=head)if(r-datadata);else if(r-datadata);else if(r-datadata);elseprintf(,%d,r-data);r=r-next;printf(n); void add(DLNode *head1,DLNode *head2,DLNode *head3) int z=0;int e;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;else z=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;else z=0;ListInsert(head3,0,e);p2=p2-prior; if(z=1) ListInsert(head3,0,z); else if(p1!=head1&p2=head2) while(p1!=head1) e=p1-data+z;if(e=10000)z=1;e=e%10000; else z=0; ListInsert(head3,0,e); p1=p1-prior; if(z=1) ListInsert(head3,0,z); else if(z=1) ListInsert(head3,0,z); int change(DLNode *head1,DLNode *head2)int length1,length2,r=2;length1=ListLength(head1); length2=ListLength(head2);DLNode *p1,*p2;p1=head1-next;p2=head2-next;if(length1length2)r=0;return r;else if(length1length2)r=1;return r;elseint i=0;for(i=0;idatap2-data)r=0;return r;break;else if(p2-datap1-data)r=1;return r;break;elsep1=p1-next;p2=p2-next;r=2;return r;void method(DLNode *head1,DLNode *head2,int x)void minus(DLNode *head1,DLNode *head2,DLNode *head3);DLNode *temp1;DLNode *temp2;DLNode *temp3;DLNode *temp4;DLNode *temp5;int e,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;idata*p2-data+z;if(e9999)z=e/10000;e=e-z*10000;else z=0;ListInsert(temp1,0,e);p1=p1-prior;if(z!=0) ListInsert(temp1,0,z);for(j=0;jprior;p2=p2-prior;OutputNumber(temp2,x);void minus(DLNode *head1,DLNode *head2,DLNode *head3)int z=0,x=-1;int e;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; else if(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!=he