《长整数加减运算.doc》由会员分享，可在线阅读，更多相关《长整数加减运算.doc（44页珍藏版）》请在三一办公上搜索。
1、 *实践教学* 兰州理工大学技术工程学院2013年春季学期 数据结构 课程设计题 目： 长整数的加减运算 专业班级：计算机科学与技术一班 姓 名： 郭利强 学 号： 11730108 指导教师： 王连相 成 绩： 计算机科学与技术专业数据结构课程设计任务书（11级）题目：长整数的加减运算学生姓名： 郭利强 学号： 11730108 班级： 11级计算机科学与技术一班 题目类型：软件工程（R） 指导教师： 王连相 一 题目简介该设计要求学生设计程序，实现两个任意长的整数求和及差的运算问题。通过该题目的设计过程，可以加深理解线性表的逻辑结构、存储结构，掌握线性表上基本运算的实现，进一步理解和熟练掌
2、握课本中所学的各种数据结构，学会如何把学到的知识用于解决实际问题，培养学生的动手能力。二 主要任务第一部分：基本算法实现1、 线性结构基本算法实现（指导老师根据题目指定）；2、 树型结构基本算法实现（指导老师根据题目指定）；3、 图型结构基本算法实现（指导老师根据题目指定）；4、 查找基本算法实现（指导老师根据题目指定）；5、 排序基本算法实现（指导老师根据题目指定）；第二部分：指定题目的设计与实现1、查阅文献资料，一般在3篇以上；2、建立数据的逻辑结构和物理结构；3、完成相应算法的设计；4、完成测试工作；5、撰写设计说明书；6、做好答辩工作。三 主要内容、功能及技术指标（1）使用双向循环链表
3、存储长整数，每个结点含一个整型变量，主要功能有：长整数输入（建立双向循环链表）、长整数的加法、长整数的减法及结果的显示输出等；（2）至少要用10组测试数据，算法对于这些合法的输入数据都能产生满足规格说明要求的结果；（3）算法对于精心选择的典型、苛刻而带有刁难性的几组输入数据能够得出满足规格说明要求的结果；对算法实现过程中的异常情况能给出有效信息；（4）任何整型变量的范围是-(215-1)（215-1）。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开，例1，0000，0000，0000；而输入为1，0001，0001和-1，0001，0000实现加法时，应输出1；（5）较
4、高要求：使程序在整型量范围是-(2n-1)(2n-1)的计算机上都能有效地运行。其中，n是由程序读入的参量。四 提交的成果1. 设计说明书一份，内容包括：1) 中文摘要100字；关键词3-5个；2) 序言；3）采用类c语言定义相关的数据类型4）各模块的伪码算法5）函数的调用关系图6）调试分析a、调试中遇到的问题及对问题的解决方法；b、算法的时间复杂度和空间复杂度。7）测试结果8）源程序（带注释）9) 设计总结、参考文献、致谢等。2. 刻制光盘一张。五 主要参考文献1严蔚敏，吴伟民.数据结构（C语言版）.清华大学出版社.2严蔚敏，吴伟民.数据结构题集（C语言版）.清华大学出版社.3 DATA S
5、TRUCTURE WITH C+. William Ford,William Topp .清华大学出版社（影印版）. 4谭浩强.c语言程序设计. 清华大学出版社. 5数据结构与算法分析（Java版） , A Practical Introduction to Data Structures and Algorithm Analysis Java Edition Clifford A. Shaffer , 张铭,刘晓丹译电子工业出版社 2001 年1月六、各阶段时间安排（共2周）周次日期内容地点第1周星期一教师讲解设计要求，准备参考资料教室星期二三分析设计要求，进行数据结构及算法设计教室、实验室
6、星期四五算法设计，编程实现实验室第2周星期一三编程上机实现、测试程序实验室星期四五检查程序，答辩实验室2013年6月28日摘要 数据结构解决实际应用中的问题，将学习的理论知识应用于实践，增强学生解决实际问题的能力。采用的基本数据结构为线性表。计算机存储的数据是有范围限制的，对于超出存储限制的数据无法直接在计算机中计算，为此需要设计相应的程序来完成这种超出范围限制的长整数间的加减运算。实现任意长的整形数进行加减运算 的程序，要求完成长整数的加、减运算。在这里长整数没有范围限制，可任意长。运算后的进位、借位等都要进行正确处理，可实现动态的输入，实时的输出。关键字：任意长整数，加、减运算序言课程设计
7、是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。数据结构是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次程序设计中我选择了长整数的代数计算这个题目，在一般的程序运算中，长整数是无法计算的，因为计算机一次能够运算的位数是有限，一旦整
8、数很长，就需要一个程序来进行多次计算，通过这个程序，可一把一个长整数分成多个普通整数来进行计算，使得长整数也可以进行运算。我编写的这个程序就可以进行加减乘除的运算，各个数据也可以是负数。目录一、概要设计1.1数据结构1.2使用函数二、流程图三、详细设计 3.1数据结构详细设计3.2链表初始化函数： 3.3计算已知的链表长度： 3.4插入函数： 3.5绝对值函数： 3.6读入数据并插入对应的链表函数： 3.7输出函数 3.8加法函数（正数加上正数） 3.9判断俩正数大小函数： 3.10减法函数： 3.11整合八种情况函数： 3.12主函数：四、调试分析 4.1调试过程中遇到的问题五、使用说明和测
9、试结果 5.1使用说明5.2测试结果附录设计总结参考文献致谢一、概要设计1.1数据结构此实验采用的数据结构是双向循环链表。这样可以很容易的找到他的前驱以及它的后继。节点采用结构体类型，代码如下：typedef struct Node / 双向链表的结构体定义 int data; struct Node *prior; struct Node *next;DLNode;1.2使用函数1) void ListInitiate(DLNode *head)操作结果：初始化一个头结点为head的双向循环链表；2) int ListLength(DLNode *head)操作结果：计算以head为头结点的
10、链表的长度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,D
11、LNode *head2,DLNode *head3)操作结果：实现正数加正数的加法操作。8) int change(DLNode *head1,DLNode *head2)操作结果：判断存在俩个链表中的数的大小，如何head1中的数大于head2中的数那么返回值为0，反之返回值为1，相等时返回值为2；9) void minus(DLNode *head1,DLNode *head2,DLNode *head3)操作结果：计算正数减正数的减法运算。10) void yunsuan(DLNode *head1,DLNode *head2,DLNode *head3,char ch)操作结果：正数
12、，负数，加法，减法。计算式共分为八种运算，在这之前我已经实现了二种运算，那么这个函数就是把这八种运算按照一定的规则转化成已经实现的二种运算来实现完整的加减法运算。11) void main()操作结果：主函数。调用以上的各个函数来引导用户进行长整数的加法运算，加法运算.二、函数流程图 输出结果两个正数相加相异判断输入两位整数第二个数减第一数两个负数相加第一个数减第二个数情况判断数字转化链表开始输出转化 三、 详细设计3.1数据结构详细设计typedef struct Node / 双向链表的结构体定义int data;struct Node *prior;struct Node *next;D
13、LNode; 双向循环链表的节点由三个部分组成，第一是数据部分data存储此节点的数据，第二是此节点的前驱指针部分*prior指向此节点的前驱，第三是此节点的后继指针部分*next指向此节点的后继。数据部分我们约定它为整形变量，前驱后继指针均为结构体Node类型。3.2链表初始化函数：void ListInitiate(DLNode *head) /双向链表的初始化if(*head=(DLNode *)malloc(sizeof(DLNode)=NULL) exit(0);(*head)-prior=*head;(*head)-next=*head; 初始化之前需要定义一个类型为Node型的头
14、结点变量，经过函数后完成链表的初始化即：头节点的前驱指针指向自己，同时他的后继指针也指向自己。3.3计算已知的链表长度：int ListLength(DLNode *head) /双向链表的表长DLNode *p=head;int size=0;while(p-next!=head) p=p-next; size+;return size; 此函数计算的是已知链表的长度。主要思想：从头结点开始寻找下一个节点，找到计数器加一。直到再次寻找到头结点时停止，计算完毕。3.4插入函数：int ListInsert(DLNode *head,int i,int x) /双向链表的数据插入,i表示是插入的
15、第几个元素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的节点。函数需要注意的是在什么位置插入才是合法的，在就是在该节点指针时的顺序不要搞错。3.5绝对值函数
16、：int abs(int x) if(x0) return -x;else return x; 此函数是实现求一个整数的绝对值。设计这么一个函数主要是考虑到在存储负数的时候头结点应该变为正整数，然后通过其他手段变相实现那种运算。3.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
17、,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; 此函数实现的是从键盘上得到数据根据三种情况进行不同的处理
18、，判断是否是头结点，判断是否是整数，判断输入的字符是否是“；”分号。并且如果是正整数它的头结点data等于1否则为0。3.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 i
19、f(r-datadata);elseprintf(,%d,r-data);r=r-next;printf(n); 此函数实现的是将最后的结果输出到显示屏上，经过判断数据的正负和数据的范围来进行不同的处理，以保证在显示屏上显示的是正确的格式。3.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
20、=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
21、;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表示最后的计算结果，这样才可以保证数据的完整性。3.9判断俩正数大
22、小函数：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-
23、data)r=1;return r;break;elsep1=p1-next;p2=p2-next;r=2;return r; 此函数实现的是判断俩个正数的大小。考虑俩正数的在链表中所占存储单元的多少，多的一定大，当他们一样长时，一位一位的比较直到找到一个节点中的data比另一个链表的对应节点的data大为止。如果最后仍是一样大那么这两个数就是一样大的。返回值为自己约定的参数r等于2表示俩数一样大，等于1表示第二个数大，等于 0表示第一个数大。3.10 减法函数：void minus(DLNode *head1,DLNode *head2,DLNode *head3)int z=0,x=-1;
24、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
25、-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(
26、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; 此函数实现的是两个正数的减法运算。整个函数分为俩大部分，第一部分处理第一个数大于第二个数，第二部分是处理第二个数大于第一个数。在这个为题上我们想了好长时间，感觉俩部分可以 结合成一部分，但是由于知识所限没有想出更好的办法，这使得代码量
27、增加了足足一倍之多。仍然模仿手算减法，先找到俩数字中最大的那个，用大的减去小的。最后判断符号位。3.11整合八种情况函数：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=
28、+) 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
29、*=-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主函数：void main()char ch,ch1;while(1)/int w
30、=-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(此版本不
31、支持%c运算,ch1);printf(要继续吗？(y/n) :);scanf(%s,&ch);if(ch=Y|ch=y) printf(n);continue;else exit(0); 此函数是主函数。主要的作用是为用户做一个提示，如何完成自己想要的运算。同时调用各个函数实现运算。 四、调试分析4.1调试过程中遇到的问题在函数编写之前我首先写出了所有函数的框架以及各个函数之间的关系，根据逐步求精的思想来完善整个程序。即使是这样我仍然遇到了不少错误。例如：在实现正数减正数时，我一开始没有分为以上所说的俩个部分，而是把俩个部分整合到一起实现一个大函数，但是在我运行调试时结果大不如人意，出现的都是
32、匪夷所思的数字，我根本就推算不出这些数字是怎么来的。没有办法我只好在另辟途径来完成函数的实现。于是我就分作两个部分来实现，这样逐步追踪可以使思绪更加清晰，所付出的代价是代码量增加。五、使用说明和测试结果5.1使用说明用户在使用该程序时，只需按照程序中的规定进行即可实现长整数的加减运算，具体使用步骤如下：1) 点击运行按钮，在DOS窗口下按照规定输入的数字需要从低位开始数四位一组用逗号隔开。输入第一个数字。2) 同上输入第二个数；3) 选择要对这两个长整数进行的运算。4) 两个操作数与运算符选择完毕后，按回车键即可得到运算结果。5.2测试结果5) 考虑边界数字，输入0和0做加法运算，输出“0”，
33、结果如下图：6) 考虑加法进位（包括低位向高位的进位以及高位仍有进位情况），结果如下图：7) 考虑减法进位并且数A小于数B，结果如下图：8) 考虑减法进位并且数A大于数B，结果如下图： 9)连续输入两次数据测试；如下图：10）较高要求附录程序的完整代码清单：#include #include #include typedef struct Node / 双向链表的结构体定义int data;struct Node *prior;struct Node *next;DLNode;void ListInitiate(DLNode *head) /双向链表的初始化if(*head=(DLNode *
34、)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&
35、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-n
