数据结构课程设计-大数运算-实现大数加法、大数减法、大数乘法、大数除法、大数乘方、大数取模、同时支持十进制大数和二进制大数运算
相关代码见本人上传的资源点这里
实验题目和要求
大整数的运算
【问题描述】
密码学分为两类密码：对称密码和非对称密码。对称密码主要用于数据的加解密，而非对称密码则主要用于认证、数字签名等场合。非对称密码在加密和解密时，是把加密的数据当作一个大的正整数来处理，这样就涉及到大整数的加、减、乘、除和指数运算等，同时，还需要对大整数进行输出。请采用相应的数据结构实现大整数的加、减、乘、除和指数运算，以及大整数的输入和输出。
【基本要求】
- 要求采用链表来实现大整数的存储和运算，不允许使用标准模板类的链表类(list)和函数。同时要求可以从键盘输入大整数，也可以文件输入大整数，大整数可以输出至显示器，也可以输出至文件。大整数的存储、运算和显示，可以同时支持二进制和十进制，但至少要支持十进制。大整数输出显示时，必须能清楚地表达出整数的位数。测试时，各种情况都需要测试，并附上测试截图；要求测试例子要比较详尽，各种极限情况也要考虑到，测试的输出信息要详细易懂，表明各个功能的执行正确；
- 要求大整数的长度可以不受限制，即大整数的十进制位数不受限制，可以为十几位的整数，也可以为 500 多位的整数，甚至更长；大整数的运算和显示时，只需要考虑正的大整数。如果可能的话，请以秒为单位显示每次大整数运算的时间；
- 要求采用类的设计思路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能出现类的成员函数的调用，不允许出现对其它函数的调用。
- 要求采用多文件方式：.h 文件存储类的声明，.cpp 文件存储类的实现，主函数 main 存储在另外一个单独的 cpp 文件中。如果采用类模板，则类的声明和实现都放在.h 文件中。
- 不强制要求采用类模板，也不要求采用可视化窗口；要求源程序中有相应注释；
【实现提示】 - 大整数的加减运算可以分解为普通整数的运算来实现；而大整数的乘、除和指数运算，可以分解为大整数的加减运算。
- 大整数的加、减、乘、除和指数运算，一般是在求两大整数在取余操作下的加、减、乘、除和指数运算，即分别求 (a +b) mod n, (a - b) mod n, (a * b) mod n, (a / b) mod n 和(a ^ b) mod n。其中 a ^ b 是求 a 的 b 次方，而 n 称之为模数。
说明：取余操作(即 mod 操作)是计算相除之后所得的余数，不同于除法运算的是，取余操作得到的是余数，而不是除数。如 7 mod 5 = 2。模数 n 的设定，可以为 2m 或 10m，m 允许每次计算时从键盘输入。模数 n 的取值一般为 2^512(相当于十进制 150 位左右),2^1024(相当于十进制 200~300位),2^2048(相当于十进制 300~500 位)。为了测试，模数 n 也可以为 2^256, 2^128等值。 - 需要设计主要类有：链表类和大整数类。链表类用于处理链表的相关操作，包括缺省构造函数、拷贝构造函数、赋值函数、析构函数、链表的创建、插入、删除和显示等；而大整数类则用于处理大整数的各种运算和显示等。
【运行结果要求】
要求能实现大整数的加、减、乘、除和指数运算，以及大整数的输入和输出，实验报告要求有详细的设计思路、功能测试截图。
设计思路
2.1 系统总体设计
根据上述任务的要求，可以知道，需要设计系统是一个基于链表数据结构的大整数的运算系统。首先讨论用于存储大整数的链表数据结构，容易知道，如果想要将一个大整数存入一个链表，那么首先要解决的问题是链表的各个位置所代表的含义。一个很自然的想法就是，将一个很长的大整数看作一个链表，链表的每一个节点存储的数据就是一个大整数的某一位上的数值。如果我们假设这个位上的值是x，那么容易知道存在一下关系：
x∈{x|0≤x≤9,x∈Z}
考虑到一个大整数的首位不能够为0，因此再之后的程序当中需要对大整数的首位数字做特殊的处理。
在处理好如何将一个大整数存入链表的问题之后，需要考虑这种用来存储大整数的链表结构应当有哪些方法成员。首先是对于链表的基本成员方法，这种结构应当都有，除此之外，考虑到大整数运算时的顺序，一般是从低位开始计算。因此需要在上述结构中加入链表的反转操作。考虑到任务要求，需要输出大整数的长度，因此在链表的数据成员中需要加入一个用于记录链表长度的数据成员，这个问题会在之后的程序中具体讲述。另外，链表的输出需要时需要考虑到前导零的问题，因此该类型的链表结构中的输出函数应当对于大整数的前导零的问题有着一个特殊的处理。大体上来看，上述类型的链表结构已经能够满足所有任务的基本要求了。
接下来考虑程序的主体，大整数类。这个类的私有数据成员只需要一个大整数链表成员即可。对于大整数类的函数成员的设计而言相对复杂，需要设计的主要函数成员应当包括：大整数的加法、大整数的减法、大整数的乘法、大整数的除法、大整数的取模运算、大整数的乘方运算、大整数的输出方法、大整数的读入方法等。除此之外，为了让上述大整数类有更好的使用体验，还需要C++的标准运算符进行重载，使得大整数的运算更为接近于一般的整数的运算，通过运算符的重载，用户可以像处理标准整形数据一样处理大整数数据。上述函数成员在之后的程序中会进行进一步的讨论。
最后需要考虑的就是如何对程序进行测试。为此，我们可以考虑设计一个专门用来对大整数类进行测试的一个类。对于这个用于测试的类，其私有数据私有数据成员不需要，主要是对其函数成员的设计。按照上述大整数类的设计思路来看，需要设计的函数成员应当包括：对大整数的加法运算的测试、对大整数减法的测试、对大整数的乘法的测试、对大整数的除法的测试、对大整数的取模运算的测试、对大整数乘方的测试，以及需要测试二进制下的大整数的处理的情况。在每一个函数成员的具体的设计时需要考虑各种边界情况和极限情况，同时需要对上述大整数运算的时间进行相应的测量，最后通过一个相对与用户用好的方式呈现给用户。
各个类之间的关系图如下：
图1 系统中各个元素之间的关系
2.2 系统功能设计
大整数运算系统的功能主要包括一下几个方面：
1.能够进行大整数的基本运算包括大整数的加法，大整数的减法，大整数的乘法，大整数的除法，大整数的取模运算，大整数的乘方运算，二进制下的大整数的加减乘除运算以及二进制下的大整数的取模和乘方的运算。
2.能够在实现上述基本要求的基础之上，给出一个相对合理的用户体验相对友好的输出界面。
3.系统能够进行较好的自我验证，即验证运算结果的正确性。
4.系统能够有较好的性能，即能够再合理的时间内给出大整数的运算结果，通过当程序运行完成之后能够给出一个相对合理的时间结果，以便于用户进行相应的比较。
相关代码见本人上传的资源点这里
2.3 类的设计
首先作为一个用于大整数运算系统，其基本的功能是进行大整数的运算。在上一小节中我们已经对于大整数运算系统的基本功能的大体设计进行了相应的讨论，因此在本小节中将对其中涉及到的所有具体的功能进行具体的讨论。
首先是用于存储大整数的链表类，这个类在上一小节中已经有了一些简要的讨论。除了上一小节中涉及到的链表的创建，大整数的前导零的特殊情况的讨论等功能，其他需要添加的函数成员以及其相应的解释如下表所示：
函数名称 函数说明
LinkList() 链表的构造函数
LinkList(const LinkList&) 链表的拷贝构造函数
~LinkList() 链表的析构函数
Node* front() 供外接访问的入口，返回链表的头部指针
Node* getpreback() 获取尾部的前一个指针，便于进行后续的处理
Node* getback() 获取链表的尾部指针
void deleteback() 删除链表的最后一个元素，用于后续的处理
Ulong getlength() 获取链表的长度，也就是大整数的位数
void push_back(int) 向链表尾部插入一个节点，用于链表的创建
void push_front(int) 向链表的头部插入一个节点，用于链表的创建
void earse() 删除链表中的所有前缀0
bool isempty() 判断链表是否为空
void tofile() 输出到文件
void toconsole() 输出到控制台
void revise() 反转链表，用于之后的大整数的处理
void clear() 清空链表，用于之后程序的
void operator =(std::string) 重载使得能够读入字符串
void operator =(const LinkList&) 重载赋值运算符，使得两个不同的链表能够进行深度拷贝
表1 大整数链表类的函数成员列表
系统中使用到的第二个类，也是系统中的核心类，这个类的函数成员相对复杂，需要对大整数链表进行各种各样的操作，处了在上一小节中提到过的几个方法成员之外，大整数类的其他主要的函数成员如下表所示，表中给出了每一个函数成员的定义以及其相应的函数说明：
函数名称 函数说明
bigint() 大整数类的默认构造函数
bigint(const bigint&) 大整数赋值构造函数
~bigint() 大整数类的析构函数
void read(std::string) 以字符串的形式读入一个大整数
void read(int) 以整数的方式读入一个大整数
void readfromfile(std::string) 从文件中读取一个大数，其中的字符串的参数是文件的地址
void display() 显示一个大整数，需要进行去前导零的处理
void writeTofile() 将一个大整数写入到文件中
void process() 处理最终结果的进位
bigint process(LinkList&) 以链表为参数的处理函数，便于之后的程序中类与类之间的交互
void tobinary() 将一个十进制的大整数转化为二进制大整数
void todec() 将一个二进制的大整数转化成为一个十进制的大整数
int compare(bigint&) 大整数的比较函数
bigint add(bigint&) 大整数加运算
bigint operator +(bigint&) 重载运算符+
bigint operator ++(int) 重载运算符++
bigint subtract(bigint&) 大整数的减运算
bigint operator -(bigint&) 重载运算符-
bigint multiple(bigint&) 大整数的乘运算
bigint operator (bigint&) 重载运算符
bigint divide(bigint&) 大整数的除运算
bigint operator /(bigint&) 重载运算符/
bigint pow(bigint&) 大整数的乘方运算
bigint operator ^(bigint&) 重载运算符^
bigint mod(bigint&) 大整数的取模运算
bigint operator %(bigint&) 重载运算符%
bool operator ==(bigint&) 重载运算符
bool operator >(bigint&) 重载运算符>
bool operator <(bigint&) 重载运算符<，类似于>
表2 大整数类的函数成员列表
其中大整数类的主要成员函数包括大整数的基本运算函数，以乘方运算为例，下图给出了基于快速幂优化之后的程序运行流程图：
图2 基于快速幂优化的大整数乘方运算流程图
系统中最后一个类是用于对系统中各个部分的功能是否正常运转进行测试的类，由于在实现第二个大整数类的过程中，已经使用到了大整数链表中的所有函数成员，这也就是说，在第二个类的实现的过程中已经实现了对链表类的所有函数的成员的测试，因此在测试类中不必再一次对大整数链表类中的函数成员进行测试。程序测试类中的函数成员以及其作用和解释如下表所示：
函数名称 函数说明
void TestAdd() 验证加法的正确性
void TestSubtract() 验证减法的正确性
void TestMultiple() 验证乘法的正确性
void TestDivide() 验证除法的正确性
void TestMod() 验证取模运算的正确性
void TestPow() 验证乘方运算的正确性
void TestBinary() 验证二进制运算的正确性
void TestFileToFile() 验证从文件中读取数据并进行运算，并将运算结果输出到文件中功能是否正常运转
表3 程序测试类的函数成员列表
各个类之间的相互关系已经在小节一中提到了，在此不在赘述。
2.4 主程序的设计
由于本系统中已经设计了用于程序测试的专用类，因此，主程序中只需要依次调用各个类即可。主程序的运行流程图如下图所示：
图3 主程序的运行流程图
调试分析
3.1 技术难点分析
在大整数系统的实现的过程中，遇到的技术难点主要有以下几点：
1.大整数的加法中的实现的方式，由于本系统采用了链表的数据结构来对大整数进行存储，这样的方式的优点是，对于大整数的长度没有限制，但是同时也带来了另外一个问题，对于大整数各个位上的数字进行访问就得花大力气进行解决。针对大整数的加法运算，本系统采用的方式是将大整数的各个位进行相加，最后通过对最终的结果链表进行进位处理来达到大数加法的目的。
2.在处理大整数的除法运算时，可能会出现大整数访问出现错误的地方，需要针对不同的情况做出不同的处理。利用试除法对大整数进行处理如何进行相应的优化等。
3.大整数的乘方运算，如果采用一个一个相乘，最后达到指定指数后停止的方法的话，会带来大量的不必要的时间消耗，如何对上述过程进行相应的优化也是一个技术上的难点。
4.在处理大整数的减法的过程之中，如果采用和加法类似的做法，最终的结果链表中可能会出现带有大量的前导零的大整数，如何在处理的过程中将上述问题避免也是一个技术上的难点。
5.在处理将十进制的大整数转化成为二进制的大整数时会出现大量的除法，但是容易知道，除法在所有运算中是最消耗时间的，如何通过一定的处理将上述大量的除法运算转化为一个相对时间常数较低的运算也是一个技术上的难点。
6.在对链表进行“=”的赋值操作时，如果不进行任何的处理，会出现两个链表指向同一块内存的问题，如何处理来避免这种问题也是一个技术上的难点。
3.2 调试错误分析
在上述系统的调试的过程中，出现了很多的错误，这里选取了其中几个错误来做说明。
调试错误1：链表类没有实现赋值构造函数和重载赋值运算符，但是调用了赋值运算符。
图4 调试错误1
解决方案：实现链表的复制构造函数和赋值运算符的重载。相关的解决代码截图如下。
图5 实现链表的复制构造函数
图6 重载赋值运算符
调试错误2：进行减法的相关测试时出现了前导零的输出问题。图示是1000 – 1000的结果。
图7 调试错误2
解决方案：在链表的函数成员中加入清除前导零的函数方法。在减法运行结束时候对返回的结果调用该方法，该方法的实现代码如下。
图8 实现清除链表前导零的函数
调试错误3：进行运算之后，原本参与运算的两个大整数发生了变化。
图9 调试错误3
解决方案：在各个实现运算的函数中，以临时变量的方式对传入函数中的大整数进行处理。具体解决代码如下图所示。
图10 以临时变量的方式进行处理
调试错误4：参与运算之后的结果链表虽然去除了前导零，但是长度没有发生改变，在进行大数比较时出现了错误。
图11 调试错误4
解决方案：在去除前导零的函数中加入以下代码。每次去除一个前导零时使得总长度减少1。
图12 调试错误4的解决方案截图
调试分析
在主程序中对各个功能模块进行测试测试的结果截图如下，对于结果的验证，我们采用了python的大数对运行结果进行验证。对每一个测试，都给出了相应的python运算结果，以供对照。
加法测试：
图13 大整数加法测试
图14 大整数加法python验证结果
减法测试：
图15 大整数减法测试
图16 大整数减法python验证结果
乘法测试：
图17 大整数乘法测试
图18 大整数乘法python验证结果
除法测试：
图19 大整数除法测试
图20 大整数除法python验证结果
取模运算测试：
图21 大整数取模测试
图22 大整数取模运算python验证结果
乘方运算测试：
图23 大整数乘方测试
图24 大整数乘方运算python验证结果
图25 大整数二进制运算测试1
图26 大整数二进制运算测试2
对于二进制运算，只需要验证程序是否正确的将10进制转化为了2进制，这里我们仍然使用python进行测试。
图27 大整数转二进制结果
图28 python程序的验证结果
文件读取并计算测试：
图29 从本地文件中读取数据并进行计算测试
对于运算结果的验证，可以采用python对文件进行求和，得到一个resultPython.data的文件，然后再利用Windows自带的文件对比命令对结果进行对比，最终对比结果如下：
图30 Windows命令对比结果
从结果中可以看出，上述两个文件的内容完全一致，这说明大数运算的结果是正确的。
除了上述的验证方法之外，还可以通过OJ网站对算法的正确性进行验证，本次验证采用的OJ系统是51nod，下面的截图给出了乘法的验证的结果:
图31 大整数乘法验证
从OJ系统的判定来看，大整数乘法的实现是成功的。
由于OJ系统上没有大数加法的题目，因此对于大数加法的验证，采用了python程序进行，具体的方法为：通过python程序生成两千个1-10000位的大整数，然后分别通过python和上述系统对这两个文件中的大整数一一求和，通过python程序，生成的结果文件是res.txt，通过上述系统运算生成的结果文件是resC++.txt，在上述程序运行结束后，通过命令行对生成的结果进行比对，比对的结果如下：
图32 文件比对结果1
从上述结果截图结果中可以知道，上述大整数加法运算的验证是正确的。
利用同样的方法，对大整数的减法也进行了验证，数据量为2000个大整数，每个大整数的长度范围是1-10000，通过python运算，得到的结果文件为resSub.txt，通过本系统进行计算，得到的结果文件为resSubc++.txt，之后调用命令行对结果进行比对，比对结果如下：
图33 文件比对结果2
同样的，利用相同的方法，分别再对除法，乘方进行验证。对于除法的验证，数据个数为2000，大整数长度为1-500位，测试结果如下：
图34 文件比对结果3
对于乘方的验证，数据个数为2000，大整数范围为1-5位，测试结果如下：
图35 文件比对结果4