数据结构大型实验（大整数）附源代码

数据结构大型实验实验报告(大整数运算)

主要负责人： 朱镇洋

参与者： 曹耀明 陈华族

目录

第一部分 要求与概述 一、实验目的以及准备

1.1.1 问题描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.2 基本要求 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1.1.3 设计思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 第二部分 具体实现 一、代码部分

2.1.1 链表类及大数类的部分说明以及部分源码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 部分简单函数功能 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.3 加法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.4 减法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.5 乘法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.6 除法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.7 幂运算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.8 二进制和十进制的相互转化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 二、程序流程及函数间关系

2.2.1 程序流程图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2.2 函数调用关系分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 三、实验验证分析

2.3.1 输入的形式和输入值的范围 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.2 输出的形式 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.3 程序所能达到的功能. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3.4 测试数据 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 四、调试分析

2.4.1 调试过程中的主要技术问题以及具体的解决方法 . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 印象最深刻的３个调试错误，及修正方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 五、附录

2.5.1 源代码及其所属文件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

第一部分 要求与概述

1.1.1 问题描述

?密码学分为两类密码：对称密码和非对称密码。对称密码主要用于数据的加/解密，而非 对称密码则主要用于认证、数字签名等场合。非对称密码在加密和解密时，是把加密的 数据当作一个大的正整数来处理，这样就涉及到大整数的加、减、乘、除和指数运算等， 同时，还需要对大整数进行输出。请采用相应的数据结构实现大整数的加、减、乘、除 和指数运算，以及大整数的输入和输出。

1.1.2 基本要求

? 要求采用链表来实现大整数的存储和运算，不允许使用标准模板类的链表类(list)和函 数。同时要求可以从键盘输入大整数，也可以文件输入大整数，大整数可以输出至显示 器，也可以输出至文件。大整数的存储、运算和显示，可以同时支持二进制和十进制， 但至少要支持十进制。大整数输出显示时，必须能清楚地表达出整数的位数。测试时， 各种ˉ况都需要测试，并附上测试截图；

? 要求大整数的长度可以不受限制，即大整数的十进制位数不受限制，可以为十几位的整 数，也可以为500多位的整数，甚至更长； ? 大整数的运算和显示时，只需要考虑正的大整数。如果可能的话，请以秒为单位显示每 次大整数运算的时间；

? 要求采用类的设计路，不允许出现类以外的函数定义，但允许友元函数。主函数中只 能出现类的成员函数的调用，不允许出现对其它函数的调用。

? 要求采用多文件方式：.h 文件存储类的声明，.cpp 文件存储类的实现，主函数main 存 储在另外一个单独的cpp 文件中。如果采用类模板，则类的声明和实现都放在.h 文件 中； ? 要求源程序中有相应注释； ? 不强制要求采用类模板，也不要求采用可视化窗口； ? 要求测试例子要比较详尽，各种极限ˉ况也要考虑到，测试的输出信o要详细易懂，表 明各个功能的执行正确； ? 要求采用Visual C++ 6.0 及以上版本进行调试。

1.1.3 设计思路

– 根据题目要求，用链表来实现大整数的存储，用大整数类Long_Num并实现一些基本操作，设计界面菜单类LN_menu来显示界面；然后，在main函数中来完成各种操作与检验。

第二部分 具体实现

2.1.1 链表类及大数类的部分说明以及部分源码

链表类：

List由使用指针连接的节点组成，每个节点都保存着数据，以及指向前驱 和后继的指针。每个节点中存储一个数字表示大数的一位。 源代码： node::node() {

next=NULL; pre=NULL; }

node::node(int p) //节点构造函数 {

value=p; next=NULL; pre=NULL; }

大数类：

大数类有一个头节点和尾节点，分别为head和back ，而back的下一个节点为NULL。 当head与back指向同一位置时表示List为只含一个节点。Head与back都为NULL表示List为空。而且用一个int类型的变量存储大数的长度，为以后的运算提供便利。 构造函数：

?Long_Num()默认构造函数。

Long_Num::Long_Num() //构造函数 {

head=NULL; back=NULL; len=0; }

?void equal(Long_Num temp)用equal代替了构造函数。

void Long_Num::equal(Long_Num temp) //复制构造函数，将形参复制给当前对象，而非地址传递 {

node*p=temp.head; len=temp.len;

}

head=new node(p->value); back=head; p=p->next; while(p) {

node*Newnode=new node(p->value); back->next=Newnode; Newnode->pre=back; back=back->next; p=p->next; }

2.1.2 部分简单函数功能

?void length()把大整数运算过后前面的0去掉，并且更正len长度。

void Long_Num::length() //更正对象长度并规范大整数 {

node*p=head; int n_len=0; while(p->next) {

if(p->value==0) {

p=p->next;

head=head->next; head->pre=NULL; } else

break; }

while(p) {

n_len++; p=p->next; }

len=n_len; }

?void equalto（Long_Num temp)判断两大整数是否相等

bool Long_Num::equalto(Long_Num temp) //判断两大整数是否相等