长整数的代数计算----数据结构课程设计

沈阳航空航天大学课程设计报告课程设计名称：数据结构课程设计课程设计题目：长整数的代数计算院（系）：计算机学院专业：计算机科学与技术班级：学号：姓名：指导教师：沈阳航空航天大学课程设计报告I目录1题目介绍和功能要求................................................................................................11.1题目介绍..............................................................................................................11.2功能要求..............................................................................................................11.3基本功能..............................................................................................................12系统功能模块结构图................................................................................................22.1系统功能结构框图................................................................................................22.2系统主要模块的功能说明....................................................................................23使用的数据结构的描述............................................................................................43.1数据结构设计......................................................................................................43.2数据结构用法说明..............................................................................................44函数的描述................................................................................................................54.1主要函数设计........................................................................................................54.2主要函数流程图....................................................................................................65程序测试和运行的结果..............................................................................................115.1程序测试...............................................................................................................115.2运行结果..............................................................................................................126参考文献.....................................................................................................................14附录（关键部分程序清单）..................................................................................15沈阳航空航天大学课程设计报告11题目介绍和功能要求1.1题目介绍设计数据结构完成长整数的表示和存储，并编写算法来实现两个长整数的加、减、乘、除等基本代数运算。1.2功能要求1)长整数长度在一百位以上。2）实现两长整数在同余代数下的加、减、乘、除操作。即实现算法来求解a+bmodn，a-bmodn，a*bmodn，a\bmodn。3）输入输出均在文件中。（选作）1.3基本功能1.jiafa();将一百位以上的长整数进行加法运算，计算出和。2.jianfa();将一百位以上的长整数进行减法运算，计算出差。3.chenfa();将一百位以上的长整数进行乘法运算，计算出积。4.chufa();将一百位以上的长整数进行除法运算，计算出商和余数。沈阳航空航天大学课程设计报告22系统功能模块结构图2.1系统功能结构框图主模块输入模块减法模块加法模块乘法模块除法模块输出模块图2.1系统功能结构框图2.2系统主要模块的功能说明1.主模块kongzhi()；沈阳航空航天大学课程设计报告3控制输入模块、加法模块、减法模块、乘法模块、除法模块、输出模块的循环使用。2.输入模块shuru();将输入的两组长整数分别通过转换将其转换成所需要的形式存储到两个链表（opr1、opr2）中保存起来。3.加法模块jiafa();将链表opr1、opr2中的数据进行加法运算，并且二者的将加和保存到链表oprr中。4.减法模块jianfa();将链表opr1、opr2中的数据进行减法运算，并且将二者的差保存到链表oprr中。5.乘法模块chengfa();将链表opr1、opr2中的数据进行乘法运算，并且将二者的乘积保存到链表oprr中。6.除法模块chufa();将链表opr1、opr2中的数据进行加法运算，并且将二者的商和余数分别保存到链表quti、remand中。7.输出模块shuchu();将链表oprr、quti、remand中的数据保存到字符数组中，并且将字符数组中的数据输出到屏幕上。沈阳航空航天大学课程设计报告43使用的数据结构的描述3.1数据结构设计将输入的两个长整数首先保持到字符数组中，然后将字符数组中的字符转换每四个一组，利用双向循环链表来实现每一组字符的存储，并且高位在前、低位在后。每个结点中只存储四位十进制数字，即不超过9999的非负整数。利用两个双向循环链表分别保持了两个非负长整数。加法：由低位的结点开始相加，加和大于9999时，加和除以一万取余数保存到新的双向循环链表结点中，并且加和除以一万取整数作为进位加到下两个结点相加中，依次循环相加；减法：同加法有些相似，保证第一个长整数不小于于第二个长整数，结点相减，不能相减就相前一结点借位，差保存到新的双向循环链表结点中，依次循环；乘法：由低位的结点开始相乘，乘积大于9999时，乘积除以一万取余数保存到新的双向循环链表结点中，并且乘积除以一万取整数作为进位加到下两个结点乘积中，依次循环相乘；除法：开辟两个新的链表，保存商数和差。用第一个长整数循环减去第二个长整数，没减一次计数加一，计数保存到商数链表中。直到差小于第二个长整数停止循环，最后的计数为商值，差值为余数。选择该数据结构来完成长整数的加减乘除运算是因为要对长整数进行运算，需要对长整数进行存储，所以选择用链表对长整数存储，又由于存储的顺序是从左到右，而运算的顺序则是从右到左，这样位了操作方便选择循环链表，在运算过程中有进位和借位的操作，所以最终选择双向循环链表的数据结构。3.2数据结构用法说明输入的两个长整数必须为非负长整数。加法计算时只要保证两个数都为非负数即可，减法、乘法、除法时需要保证第一个长整数大于第二个长整数。同时乘法、除法计算时第二个数不能为零，并且输入的数一定要合法，最高位不能为零，否则程序会提示输入有误。沈阳航空航天大学课程设计报告54函数的描述4.1主要函数设计1.shuru()；作用：将输入的两个长整数分别保存到两个链表中。2.jiafa()；作用：将两个长整数进行加法运算，计算出二者的和。3.jianfa();作用：将两个长整数进行减法运算，计算出二者的差。4.chengfa()；作用：将两个长整数进行乘法运算，计算出二者的积。5.chufa();作用:将两个长整数进行除法运算，计算出二者的商和余数。6.shuchu();作用:将保存到链表中的计算结果输出。沈阳航空航天大学课程设计报告64.2主要函数流程图1.kongzhi():开始判断ch输入ch调用加法函数调用减法函数调用乘法函数调用除法函数退出程序结束输出和输出差输出积输出商12345图4.2.1控制函数流程图沈阳航空航天大学课程设计报告72.jiafa();开始NodeListp1=opr1,p2=opr2,p3=oprr；将链表opr1、opr2中的对应结点中数据加和并加上进位移动指针p1、p2判断指针p1,p2是否指向头指针若p1没有指向头指针和除以一万取整保存为进位和保存到链表oprr中和大于一万是否有进位和除以一万取余保存到链表oprr中将链表opr1、opr2中的对应结点中数据加和若p2没有指向头指针将opr1中剩余结点数据保存到oprr中将opr2中剩余结点数据保存到oprr中结束YNYNYNYNNY图4.2.2加法函数流程图沈阳航空航天大学课程设计报告83.jianfa();开始NodeListp1=opr1,p2=opr2,p3=oprr；将链表opr1、opr2中的对应结点中数据作差并减去1移动指针p1、p2判断指针p2是否指向头指针若p1没有指向头指针差保存到链表oprr中是否有借位将链表opr1中结点数据加上一万后减去opr2中的对应结点中数据将opr1中剩余结点数据保存到oprr中结束YNNYNY判断链表opr1中结点的数据大于opr2中对应结点的数据将链表opr1、opr2中的对应结点中数据作差YN图4.2.3减法函数流程图沈阳航空航天大学课程设计报告94、chengfa();开始NodeListp1=opr1,p2=opr2,p3=oprr；将链表opr1、opr2中的结点中数据相乘并加上进位移动指针p1若p1没有指向头指针和除以一万取整保存为进位积保存到链表oprr中和大于一万是否有进位积除以一万取余保存到链表oprr中将链表opr1、opr2中的结点中数据相乘若p2没有指向头指针结束YNYNYNYNNY是否有进位保存进位进位为零移动指针p2图4.2.4乘法函数流程图沈阳航空航天大学课程设计报告105、chufa();开始NodeListP1=opr1,p2=opr2,quti,remand；将链表opr1结点中数据加一万后减去opr2结点数据并减借位移动指针p2链表remand中数据是否大于链表opr2中数据是否需要借位差保存到链表remand中将链表opr1、opr2中的结点中数据相减若p2没有指向头指针结束YNYNYN计数加一并将计数保存到链表quti图4.2.5除法函数流程图沈阳航