基于Java实现长整数加减法(数据结构与算法课设)【100012352】

# 长整数加减法课设 ## 1. 前言 在 Java 中正数被分为了 Integer 和长整数 long 两种类型，Integer 数据类型变量存储为 16 位的数据形式，它的范围只到-32,768 到 32，767 之间。而长整数 long 类型变量存储为 32 位，有符号的树脂形式，其范围从-2,147,483,648 到了-2,147,483,647 范围更加巨大，但是也伴随着对其进行运算时，采用内置 +-，法运算效率低下的问题，所以在本门数据算法与结构课设中，本组的成员，将探寻优化算法，提高运算效率。制作长整数加减法计算器，简化运算流程，直观展示运算结果。 ## 2. 需求分析 本产品是作为一个形如计算器的程序首先，需要考虑的就是面向用户操作，由于在使用过程中，用户可能不限于使用电脑，手机等设备进行长整数运算，并且如果用户并没有安装环境那么会照成代码无法运行的情况，为了避免这些平台兼容问题，和方便用户操作，可以采用更方便的网页方式面向用户，在美观简洁的同时，满足人际友好交互。 在解决了平台兼容问题以后，我们还需要对功能进行设计。 首先是基本功能： 1.作为长整数加减法，要实现任意唱的整数的加、减法运算。以用户和计算机对话的方式，即用户根据网页对话框显示的提示信息之后，由用户通过键盘，输入演示程序用规定的运算命令，然后返回结果提示。 2.我们的长整数计算器，的集合元素限定了用户的输入的字符只能是[‘0’~‘9’]，逗号，以及‘+’和‘-’。否则应该提示用户输入的字符串不符合程序的默认要求，并且需要重新输入。 3.对于输入的数字方面，按照中国对长整数的表示习惯，每四位是一组，组间用逗号隔开 其次是输入和输出结果: 例如： （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” ## 3. 概要设计 使用技术：数据结构-链表,JAVA 基础语法。 总设计思路:代码分为用户操作，结点类，主函数设计三个部分，图示如下：  用户操作设计:在需求分析中我们提到简便的用户操作，简单将我们所设计的长整数计算器的操作流程，归结为如下流程图： (用户操作输出结果流程图) 首先我们需要明确，两个数据之间的加法，实际上是两个所带符号相同的数据相加，而两个数据之间的减法，实际上是两个所带符号相异的数据相加，那么对于用户来说就很简单了:根据提示输入第一个数据后，如果需要运行减法，在输入第二个数据的时候将其变成相异的符号，就可以运行减法。而需要获得加法结果，只需要复制粘贴，两个输入丢进去，等待程序运算即可。当然在用户输入后，可能对长整数的分隔输入错误，或者在数中添加入了规定字符以外的字符，那么如果这个时候继续运行程序就会报错。所以我们会先对数据合法性进行判断，如果符合规范直接进入算法打印输出结果，如果不符合那么我们就需要提醒用户输错了，重新输入。当然当用户正确输入第一个数据后，应该存储到变量中，这样如果用户第二个数据输入出错，就不需要重新输入第一个数据，这样用户使用起来更加友好。 ### 链表类设计: 存储结构：顺序结构，链式存储。 我们的长整数计算器利用了数据结构中的双向循环链表，来实现长整数的存储。首先对结点类进行设计，如下图所示，双向循环链表的每一个结点，可以分为一个数据域，和两个指针域。两个指针域用来指向上一个结点，以及后续结点。而在前言中提到的整型变量的范围可以知道，我们在每一个链表结点中存放的最大的整数应该为 32767，才可以保证两个链表相加后，数字不会溢出，但这样存放相当于我们直接按 32768 进制进行存放数据，而我们常用的进制是十进制，这个时候又会多出一个进制的转换问题，所以简单处理我们在每个结点中，仅仅存放十进制的 4 位数，即每个结点的中的所存储的最大数据为不超过 9999 的非负整数。  (双向循环链表示意图) 接着是链表类的设计，在双向循环链表中，我们为每一个链表设置了，一个头指针指向首结点，一个尾指针指向最后一个结点，同时自带一个记录链表长度的参数，还有记录链表的开始符号参数，用来标识长整数的正负，当然还有一些常用内置方法： ``` TowWayCircleLinkList()用于初始化链表 Void clear()用于清空整个链表 Int length()用于返回链表长度 Boolean isEmpty()用于判断该链表是否为空 Void insert(T t)用于在链表中最后位置插入元素 Void insert(int I, T t)用于在链表中指定位置插入元素 Int indexOf(T t)找到元素在链表中第一次出现的位置 T remove(int i)用于删除链表指定位置元素 T getFirst()用于返回第一个元素 T getLast()用于返回最后一个元素 Void replace(int i, T t)用于替换指定位置元素 ``` ### 主函数设计： 作为主运行程序，不仅仅包括了对用户操作的函数，还包括了本长整数加减法的具体算法，在先前的设计中我们已经完整定义了我们所使用的数据结构，还有结点类的描述，那么在主函数的设计过程中，我们需要根据用户的操作来一步一步实现，也就是如下过程： 在用户输入之后，我们讲用户输入的长整数保存到变量，但是因为提取到的不仅仅是数字，而是包含字符的一串字符串，所以我们需要构建方法，对字符串进行拆分进双向循环链表的同时也需要进行类型转化，将字符串类型转换为整型，并且也需要对双向循环链表进行组装成字符串输出。 当提取到两个长整数并拆分成双向循环链表进入算法后，先对两个双向循环链表的正负号进行判断，并且分不同情况讨论。在用户操作设计中有涉及到，程序默认是两个长整数的加法，而减法的实现只需要通过使两个输入长整数的符号相异来实现，所以在输入两个长整数保存到主程序中之后，需要对两个链表进行判断，当两个链表符号相同时，比较两个链表大小并采用不同的算法计算，同理当两个链表符号不同时，也需要通过比较两个链表的大小来采用不同算法。因为不同大小长度，可能导致链表的长度不同，需要实现两个链表的加减，应该先保证两个链表的长度相同，但同时要保证填充的数值不影响最终结果。最后在上述过程中提到由于程序经过了字符串——> 整型——> 字符串输出的转换，所以在程序过程中需要有相应的方法在字符串和整型链表之间转换。 在经过一系列的运算过后，打印输出接下来就是与网页端相连，用户链接网页后�