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

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