数据结构大型实验(大整数)附源代码

数据结构大型实验实验报告（大整数运算）

主要负责人：朱镇洋

参与者：曹耀明陈华族

目录

第一部分要求与概述

一、实验目的以及准备

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印象最深刻的3个调试错误，及修正方法..............................

五、附录

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

第一部分要求与概述

1.1.1问题描述

•密码学分为两类密码：对称密码和非对称密码。对称密码主要用于数据的加/解密，而非对

称密码则主要用于认证、数字签名等场合。非对称密码在加密和解密时，是把加密的数据

当作一个大的正整数来处理，这样就涉及到大整数的加、减、乘、除和指数运算等，同时,

还需要对大整数进行输出。请采用相应的数据结构实现大整数的加、减、乘、除和指数运

算，以及大整数的输入和输出。

1.1.2基本要求

•要求采用链表来实现大整数的存储和运算，不允许使用标准模板类的链表类（list）和函

数。同时要求可以从键盘输入大整数，也可以文件输入大整数，大整数可以输出至显示器,

也可以输出至文件。大整数的存储、运算和显示，可以同时支持二进制和十进制，但至少

要支持十进制。大整数输出显示时，必须能清楚地表达出整数的位数。测试时，各种-况都

需要测试，并附上测试截图；

•要求大整数的长度可以不受限制，即大整数的十进制位数不受限制，可以为十几位的整

数，也可以为500多位的整数，甚至更长；•大整数的运算和显示时，只需要考虑正的大

整数。如果可能的话，请以秒为单位显示每次大整数运算的时间；

•要求采用类的设计路，不允许出现类以外的函数定义，但允许友元函数。主函数中只能

出现类的成员函数的调用，不允许出现对其它函数的调用。

•要求采用多文件方式：」文件存储类的声明，.cpp文件存储类的实现，主函数main存

储在另外一个单独的cpp文件中。如果采用类模板，则类的声明和实现都放在.h文件中；

•要求源程序中有相应注释；•不强制要求采用类模板，也不要求采用可视化窗口；•要

求测试例子要比较详尽，各种极限一况也要考虑到，测试的输出信。要详细易懂，表明各个

功能的执行正确；•要求采用VisualC++6.0及以上版本进行调试。

1.1.3设计思路

■根据题目要求,用链表来实现大整数的存储，用大整数类Long_Num并实现一些基本操作,

设计界面菜单类LNmenu来显示界面；然后，在main函数中来完成各种操作与检验。

第二部分具体实现

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

链表类：

List由使用指针连接的节点组成，每个节点都保存着数据，以及指向前驱和后继的指针。

每个节点中存储一个数字表示大数的一位。

源代码：

node::node()

{

next=NULL;

pre=NULL;

)

node::node(intp)〃节点构造函数

(

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;

)

•voidequal(Long_Numtemp)用equal代替了构造函数。

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

{

node*p=temp.head;

len=temp.len;

head=newnode(p->value);

back二head;

p=p->next;

while(p)

(

node*Newnode=newnode(p->value);

back->next=Newnode;

Newnode->pre=back;

back=back->next;

p=p->next;

)

}

2.1.2部分简单函数功能

•voidlength。把大整数运算过后前面的0去掉，并且更正len长度。

voidLong_Num::length()〃更正对象长度并规范大整数

(

node*p=head;

intn_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;

)

•voidequalto(Long_Numtemp)判断两大整数是否相等

boolLong_Num::equalto(Long_Numtemp)〃判断两大整数是否相等

node*pl=head,*p2=temp.head;

boolflag=true;

while(flag&&pl)

(

if(pl->value!=p2->value)

flag二false;

else

(

pl=pl->next;

p2=p2->next;

)

)

returnflag;

}

,voidprint()打印并存储十进制数据。

voidLong_Num::print()〃打印十进制数并存储

(

if(head=NULL)

(

cout<<"******数据为空!********〃<<endl;

}

else

(

ofstreamoutfile;

outfile.open(/zoutput_Num.ios::app);

node*p=head;

while(p->next)

(

if(p->value==0)

p=p->next;

else

break;

)

while(p)

(

cout<<p->value;

outfile<<p->value;

p=p->next;

)

outfile«endl;

cout«endl;

}

}

•voidprint2()打印并存储二进制数据。

voidLong_Num::print2()〃打印二进制数并存储数

据

(

if(head二二NULL)

(

cout。”******数据为空！********”<<endl;

}

else

(

ofstreamoutfile;

outfile.open(zzoutput2_Num.txt〃，ios::app);

node*p二head;

while(p->next)

(

if(p->value==0)

p=p->next;

else

break;

)

while(p)

(

cout<<p->value;

outfile«p->value;

p=p->next;

)

outfile<<endl;

cout<<endl;

)

}

•boolcompare(Long_Numtemp)实现两个长度相等的大整数的比较。

boolLong_Num::compare(Long_Numtemp)〃初级比较，只用于长度相等的

大正间的比较，大于等于返回true

boolflag二false;

node*templ=head,*temp2=temp.head;

while(tempi)

(

if(templ->value!=temp2->value)

(

flag=templ->value>temp2->value?true:false;

break;

)

else

(

templ=templ->next;

temp2=temp2->next;

)

}

if([tempi)

flag=true;

returnflag;

}

•booIcompare2(Long_Numtemp)实现两个大整数的比较。

boolLong_Num::compare2(Long_Numtemp)〃升级版比较，可比较长度不等

的大整数，大于等于返回true

(

if(len>temp.len)

returntrue;

else

(

if(len==temp.len)

returncompare(temp);

else

returnfalse;

)

)

,voidset_Long_Num(strings)创建大整数，把字符串的内容转为int赋给大

整数。

voidLong_Num::set_Long_Num(strings)〃将输入的字符串转成大整

数

intstr_len=s.length();

head二newnode((int)s[0]-48);

len++;

back=head;

if(str_len>l)

(

for(inti=l;i<str_len;i++)

(

node*Newnode=newnode((int)s[i]-48);

len++;

back->next=Newnode;

Newnode-〉pre=back;

back=back->next;

)

}

length();

}

voidLong_Num::set_Long_Num2(inttemp)〃建立大整数，将参数建立新

节点加在尾部

(

node*Newnode=newnode(temp);

if(back)

(

back->next=Newnode;

Newnode->pre=back;

back=back->next;

)

else

(

head=Newnode;

back=head;

}

len++;

)

,voidset_Long_Num2(inttemp)如果当前大整数为空，则创建大整数，并把

值赋给它，如果非空，则在后面添加节点，把值赋给节点。

voidLong_Num::set_Long_Num2(inttemp)〃建立大整数，将参数建立新

节点加在尾部

node*Newnode=newnode(temp);

if(back)

back->next=Newnode;

Newnode->pre=back;

back=back->next;

)

else

(

head=Newnode;

back二head;

)

len++;

)

LongNumLongNum::subNum(LongNumtemp,node*&p)〃截取一定长度，用于试商

法

(

Long_Numtempp;

node*pl=head,*p2=temp,head;

strings=;

while(p2)

(

s+=pl->value+，O';

pl=pl->next;

p2=p2->next;

p=p->next;

)

tempp.set_Long_Num(s);

if(!tempp.compare(temp))〃如果截取的子串还是比

参数小，再向后截一位

(

p=p->next;

tempp.setLongNum2(pl->value);

}

tempp.length();

returntempp;

)

•Long_Numsub_Num(Long_Numtemp,node*&p)截取被除数的字串，用于

除法与除数的比较，如果小，则再截取后面一位。

Long_NumLong_Num::subNum(LongNumtemp,node*&p)〃截取一定长度，用于试商

法

(

Long_Numtempp;

node*pl=head,*p2=temp,head;

,〃〃

strings二；

while(p2)

(

s+=pl->value+，O';

pl=pl->next;

p2=p2->next;

p=p->next;

}

tempp.set_Long_Num(s);

if(!tempp.compare(temp))〃如果截取的子串还是比

参数小，再向后截一位

(

p=p->next;

tempp.set_Long_Num2(pl->value);

)

tempp.length();

returntempp;

}

intLong_Num::result(Long_Numtemp)〃除法中的试商法得到当前位

的商

(

length();

intresult=0;

while(compare2(temp))

(

decrease(temp);

result++;

)

length();

returnresult;

)

,intresu11(Long_Numtemp)得到当前大整数除以除数的商。

intLong_Num::result(Long_Numtemp)〃除法中的试商法得到当前位

的商

length();

intresult=0;

while(compare2(temp))

decrease(temp);

result++;

}

length();

returnresult;

)

2.1.3加法

实现思路：

加法通过两个操作数的每一位相加，满io进位的思路设计。

代码实现：

Long_NumLong_Num::add(Long_Numtemp)〃大整数加法

(

if(temp.head==NULL||head==NULL)

cout<<〃数据为空!z/«endl;〃考虑数据的特殊情况

else

(

node*templ,*temp2;

inti=0,j;

if(len>temp.len)

(

templ=back;

temp2=temp.back;〃如果当前大整数大于后一个，则tempi为长的最后一

个节点

for(;;)

(

while(temp2!=NULL)

(

j=templ->value+temp2->value+i;

templ->value=j%10;

if(j>=10)

i=l；

else

i=0;

temp2=temp2->pre;

tempi=tempi->pre;

)〃在短的那个数还没有遍历完的情况下，实现每一位的加法，设置

一个i变量，默认设为0。如果满10则设为1,并在前一位加上，否则设为0。

if(tempi==NULL)

if(i==l)

node*Newnode=newnode(1);

Newnode->next=head;

head->pre=Newnode;

head=head->pre;

break;

)

else

break;〃如果到了长的那个数的头一位，而i仍为1,则在

大整数的前面添加值1的节点。

)

if(tempi!=NULL)

(

j=templ->value+i;

templ->value=j%10;

if(j>=10)

i=l；

else

i=0;

)

templ=templ->pre;〃如果还没到长的那个数的头一个，执行i与当前

数的加法，如果满10则i为1,否则i为0。

)

length();

return*this;〃把第一个不为0的数的前面的0去掉，并

更正大整数的长度，并返回长的那个对象。

)

if(len==temp.len)

(

i=0;

templ=back;

temp2=temp.back;

while(tempi.->pre!=NULL)

(

j=templ->value+temp2->value+i;

if(j>=10)

(

templ->value=j%10;

i=l;

)

else

templ->value=j;

i=0;

}

temp2=temp2->pre;

templ=templ->pre;

)

J=templ->value+temp2->value+i;〃两个大整数位数相同，每一位都相

加,满10进1。

if(j>=10)

(

templ->value=j%10;

node*Newnode=newnode(l);

head->pre=Newnode;

Newnode->next=head;

head=head->pre;

}

else

templ->value=j;//到了头一位时，如果i为1,则在大整

数前面添加值为1的节点。

length();

return*this;

)

if(len<temp.len)

(

tempi=temp,back;

temp2=back;

for(;;)

{

while(temp2!=NULL)

(

j=templ->value+temp2->value+i;

templ->value=j%10;

if(j>=10)

i=l；

else

i=0;

temp2=temp2->pre;

tempi二tempi->pre;

}//在短的那个数还没有遍历完的情况下，实现每一位的加法，设

置一个i变量，默认设为0。如果满10则设为1,并在前一位加上，否则设为0。

if(templ=NULL)

(

if(i==l)

(

node*Newnode=newnode(1);

Newnode->next=temp.head;

temp.head->pre=Newnode;

temp.head=temp.head->pre;

break;

}

else

break;

}

if(tempi!=NULL)

(

j=templ->value+i;

templ->value=j%10;

if(j>=10)

i=l；

else

i=0;

}

templ=templ->pre;//如果还没到长的那个数的头一个，执行i

与当前数的加法，如果满10则i为1,否则i为0。

)

equal(temp);

length();

return*this;〃把第一个不为0的数的前面的0去掉，并更正大整数

的长度，并返回长的那个对象。

)

)

2.1.4减法

实现思路：

减法通过两个操作数每一位相减，不够则借位的思路设计。

代码实现：

Long_NumLong_Num::decrease(Long_Numtemp)〃大整数减法

{

if(head==NULL||temp.head==NULL)

cout«〃数据为空!〃<<endl;〃考虑数据的特殊情况

else

(

node*templ,*temp2;

inti=0,j;

if(len>temp.len)

tempi二back;

temp2=temp.back;

while(tempi)

(

while(temp2!=NULL)

(

j=templ->value-temp2->value-i;

if(j<0)

(

templ->value=j+10;

i=l；

)

else

(

templ->value=j;

i=0;

)

templ=templ->pre;

temp2=temp2->pre;

}〃在短的那个数还没有遍历完的情况下，实现每一位

的减法，设置一个i变量，默认设为0。如果不够则设为1,并在前一位减去，否则设为0。

j=templ->value-i;

if(j<0)

{

templ->value=j+10;

i=l；

)

else

{

templ->value=j;

i=0;

)

templ=templ->pre;〃如果还没到长的那个数的头一个，执行i

与当前数的减法，如果不够则i为1,否则i为。。

)

length();

return*this;〃把第一个不为0的数的前面的0去掉,

并更正大整数的长度，并返回长的那个对象。

)

if(len==temp.len)

(

inti=0,j;

node*templ,*temp2;

if(compare(temp))

if(equalto(temp))

{

set_Long_Num(z，0，z);

return*this;

)〃两个大整数相等则直接返回0

else

(

tempi=back;

temp2=temp.back;

while(tempi)

(

j=templ->value-temp2->value-i;

if(j<0)

(

templ->value=j+10;

i=l；

)

else

(

templ->value=j;

i=0;

)

templ=templ->pre;

temp2=temp2->pre;//两个大整数位数相同，每

一位都相减，不够则把i=l,在前面一位减的时候减去，再把i=0,否则就i=0。

)

length();

return*this;〃把第一个不为0的数的前面的0去

掉，并更正大整数的长度，并返回长的那个对象。

)

)

else

(

Long_Numtempp;

tempp.equal(temp);

templ=tempp.back;

temp2=back;

while(tempi)

(

j=templ->value-temp2->value-i;

if(j<0)

(

templ->value=j+10;

i=l；

else

(

templ->value=j;

i=0;

)

tempi=tempi->pre;

temp2=temp2->pre;

)

equal(tempp);

length();

return*this;

)

)

if(len<temp.len)

(

Long_Numtempp;

tempp.equal(temp);

templ=tempp.back;

temp2=back;

while(tempi)

(

while(temp2!=NULL)

(

j=templ->value-temp2->value-i;

if(j<0)

(

templ->value=j+10;

i二1；

}

else

(

templ->value=j;

i=0;

)

tempi二tempi->pre;

temp2=temp2->pre;

}〃在短的那个数还没有遍历完的情况下，实现每一位的减法，但是用长

的那个减去短的那个，设置一个i变量，默认设为0。如果不够则设为1,并在前一位减去,

否则设为0。

j=templ->value-i;

if(j<0)

templ->value=j+10;

i二1；

)

else

(

templ->value=j;

i=0;

}

templ=templ->pre;〃如果还没到长的那个数的头一个，执行

i与当前数的减法，用长的那个数减短的，如果不够则i为1,否则i为0。

)

equal(tempp);

length();

return*this;〃把第一个不为0的数的前面的0去掉，

并更正大整数的长度，并返回长的那个对象。

)

2.1.5乘法

实验思路：

乘法通过一个操作数的每一位分别于另一个操作数的每一位相乘，得到的结果再相加设

计。

代码实现：

Long_NumLong_Num::changeO〃删除头尾节点(乘法专

用)

{

node*pl=head->next;

node*p2=head;

while(pl->next!=NULL)

(

p2->value=pl->value;

pl=pl->next;

p2=p2->next;

}

node*p=back;

p->pre->next=NULL;

back=p->pre;

p->pre=NULL;

p二back;

p->pre->next=NULL;

back=p->pre;

p->pre=NULL;

return*this;〃删除乘法一开始创建的头尾两个节点，并重新定义

头尾节点。

)

Long_Nummultiply(Long_Numtempp,Long_Numtemps)〃大整数乘法

(

Long_Numsum,ex,ex;

ex.head二newnode(0);

ex.len++;

ex.back=ex.head;

sum.head=newnode(0);

sum.len++;

sum.back=sum.head;

ex.head=newnode(0);

ex.len++;

ex.back=ex.head;

node*templ,*temp2,*tempt;

templ=tempp.back;

temp2=temps.back;

for(intw=0;temp2!=NULL;w++)〃设置w变量，从0循环到第二个大整数的长度。

(

Long_Num1;

inti=0,j;

1.head=newnode(0);

1.back=newnode(0);

1.head->next=l.back;

1.back->pre=l.head;

temptG.back;〃先创建一个大整数1,头尾结点分别为0。

for(;;)

(

while(tempi!=NULL)

(

j=templ->value*temp2->value+i;

i二j/10；

templ=templ->pre;

node*Newnode=newnode();

Newnode->pre=l.head;

Newnode->next=l.head->next;

tempt->pre=Newnode;

1.head->next=Newnode;

tempt二tempt->pre;

tempt->value=j%10;

1.len++;

}〃把一个大整数的每一位乘以另一个大整数的第一

位，设置i=0,结果加上i除以10,商赋给当前值，余数赋给i,把当前值插入到1的头结

点后，1的长度加1。

for(intww=0;w<w;ww++)

(

node*Newnode=newnode(0);

1.back->next=Newnode;

Newnode->pre=l.back;

1.back=Newnode;

1.len++;

)〃当一个大整数的每一位乘完以后，把另一个大整数的位

数往前移一位，并且移动一次，要在1后面添加一个值为0的节点，并且1的长度加1。

if(tempi二二NULL)

(

if(i!=0)

(

node*Newnode=newnode(i);

Newnode->next=l.head->next;

1.head->next->pre=Newnode;

1.head->next=Newnode;

Newnode->pre=l.head;

1.len++;

}

}//当到达第一个大整数的头一位时i仍不为0,则在1

的头结点后面插入值为i的节点，并且1的长度加lo

templ=tempp.back;

temp2=temp2->pre;

ex.len=l.len-2;

ex二1.change。；〃去掉原先创建的头尾两个值为0的节点，长度减2。

cx=sum;

ex.len=sum.len;

sum=ex.add2(ex);

break;

)

}

sum.len++;

sum.length();

returnsum;〃把第一个不为0的数的前面的0去掉，并更正大整数的长度，

并返回。

2.1.6除法

实验思路：

除法通过先在被除数中取跟除数一样的位数，进行不断的减法操作，直至小于除数，然后

再向后面取数直至位数于除数相同，重复。

代码实现：

intLong_Num::result(Long_Numtemp)〃除法中的试商法得到当前

位的商

(

length();

intresult=O;

while(compare2(temp))

(

decrease(temp);

result++;

}

length();

returnresult;

)

voidLong_Num::set_Long_Num2(inttemp)〃建立大整数，将参数建立新

节点加在尾部

(

node*Newnode=newnode(temp);

if(back)

(

back->next=Newnode;

Newnode->pre=back;

back=back->next;

)

else

(

head二Newnode;

back=head;

}

len++;

}

Long_NumLong_Num::sub_Num(Long_Numtemp,node*&p)〃截取一定长度，用于试商

法

(

LongNumtempp;

node*pl=head,*p2=temp.head;

♦〃〃

strings=;

while(p2)

(

s+=pl->value+，O';

pl=pl->next;

p2=p2->next;

p=p->next;

)

tempp.set_Long_Num(s);

if(!tempp.compare(temp))〃如果截取的子串还是比

参数小，再向后截一位

{

p=p->next;

tempp.set_Long_Num2(pl->value);

)

tempp.length();

returntempp;

)

Long_NumLong_Num::divide(Long_Numtempi,Long_Num&temp2)〃大整数除法

(

strings_result二〃〃；

intsh;

Long_Numtemp;

if(compare2(tempi))

(

if(len>templ.len)

(

node*curren=head;

temp=sub_Num(tempi,curren);//当被除数位数比除数

大，先创建一个大整数temp,存储在被除数上截取除数长度的一段值，如果不够大，则往

后面再截取一位。

sh=temp.result(tempi);//sh为一次除法得

到的商，temp为得到的余数

s_result+=sh+，;〃创建一个字符串s,

来累加商

while(curren)

(

temp.set_Long_Num2(curren->value);

sh=temp.result(tempi);

s_result+z:sh+，0，;

curren=curren->next;

)〃余数加上后一位的值构成大整数

除以除数，如果比除数小则s加上0,否则s加上商，重复直至最后。

temp2.equal(temp);

set_Long_Num(s_resu11);

length();

return*this;〃返回字符串s为总的商，把余数赋给

第二个大整数参数

)

else

sh=result(tempi);

s_result+=sh+，O';

temp2.equal(*this);

set_Long_Num(s_result);

length();

return*this;〃当被除数位数和除数相同，如上进

行一次除法操作。

)

}

else

(

temp2.equal(*this);

set_Long_Num(〃0");

return*this;〃当被除数位数比除数小，就直接返回s

为0,余数为被除数.

)

)

2.1.7幕运算

实验思路：

幕运算则通过底数自乘，累减1,结合加法，乘法，减法的方法实现。

代码实现：

boolIf_one(Long_Numtemp)〃判断对象是为1

{

boolflag=false;

node*p=temp.back;

if(p->value!=l)

returnflag;

else

{

p=p->pre;

flag=true;

while(p)

(

if(p->value!=0)

(

flag=false;

break;

)

else

p=p->pre;

)

returnflag;

boolIf_zero(Long_Numtemp)〃判断对象是否为0

(

boolflag=false;

node*p=temp.back;

if(p->value!=0)

returnflag;

else

(

p=p->pre;

flag=true;

while(p)

(

if(p->value!=0)

(