长整数的加减运算

*******************实践教学*******************兰州理工大学技术工程学院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是由程序读入的参量。四．提交的成果1.设计说明书一份，内容包括：1)中文摘要100字；关键词3-5个；2)序言；3）采用类c语言定义相关的数据类型4）各模块的伪码算法5）函数的调用关系图6）调试分析a、调试中遇到的问题及对问题的解决方法；b、算法的时间复杂度和空间复杂度。7）测试结果8）源程序（带注释）9)设计总结、参考文献、致谢等。2.刻制光盘一张。五．主要参考文献1．严蔚敏，吴伟民.《数据结构（C语言版）》.清华大学出版社.2．严蔚敏，吴伟民.《数据结构题集（C语言版）》.清华大学出版社.3．《DATASTRUCTUREWITHC++》.WilliamFord,WilliamTopp.清华大学出版社（影印版）.4．谭浩强.《c语言程序设计》.清华大学出版社.5．数据结构与算法分析（Java版）,APracticalIntroductiontoDataStructuresandAlgorithmAnalysisJavaEditionCliffordA.Shaffer,张铭,刘晓丹译电子工业出版社2001年1月六、各阶段时间安排（共2周）周次日期内容地点第1周星期一教师讲解设计要求，准备参考资料教室星期二~三分析设计要求，进行数据结构及算法设计教室、实验室星期四~五算法设计，编程实现实验室第2周星期一~三编程上机实现、测试程序实验室星期四~五检查程序，答辩实验室2013年6月28日摘要数据结构解决实际应用中的问题，将学习的理论知识应用于实践，增强学生解决实际问题的能力。采用的基本数据结构为线性表。计算机存储的数据是有范围限制的，对于超出存储限制的数据无法直接在计算机中计算，为此需要设计相应的程序来完成这种超出范围限制的长整数间的加减运算。实现任意长的整形数进行加减运算的程序，要求完成长整数的加、减运算。在这里长整数没有范围限制，可任意长。运算后的进位、借位等都要进行正确处理，可实现动态的输入，实时的输出。关键字：任意长整数，加、减运算序言课程设计是实践性教学中的一个重要环节，它以某一课程为基础，可以涉及和课程相关的各个方面，是一门独立于课程之外的特殊课程。课程设计是让同学们对所学的课程更全面的学习和应用，理解和掌握课程的相关知识。《数据结构》是一门重要的专业基础课，是计算机理论和应用的核心基础课程。数据结构课程设计，要求学生在数据结构的逻辑特性和物理表示、数据结构的选择和应用、算法的设计及其实现等方面，加深对课程基本内容的理解。同时，在程序设计方法以及上机操作等基本技能和科学作风方面受到比较系统和严格的训练。在这次程序设计中我选择了长整数的代数计算这个题目，在一般的程序运算中，长整数是无法计算的，因为计算机一次能够运算的位数是有限，一旦整数很长，就需要一个程序来进行多次计算，通过这个程序，可一把一个长整数分成多个普通整数来进行计算，使得长整数也可以进行运算。我编写的这个程序就可以进行加减乘除的运算，各个数据也可以是负数。目录一、概要设计……………………………………………………………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调试过程中遇到的问题…………………………………………五、使用说明和测试结果…………………………………………………5.1使用说明…………………………………………………………5.2测试结果…………………………………………………………附录…………………………………………………………………………设计总结……………………………………………………………………参考文献……………………………………………………………………致谢…………………………………………………………………………一、概要设计1.1数据结构此实验采用的数据结构是双向循环链表。这样可以很容易的找到他的前驱以及它的后继。节点采用结构体类型，代码如下：typedefstructNode//双向链表的结构体定义{intdata;structNode*prior;structNode*next;}DLNode;1.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)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链表初始化函数：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&&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的节点。函数需要注意的是在什么位置插入才是合法的，在就是在该节点指针时的顺序不要搞错。3.5绝对值函数：intabs(intx){if(x0)re