数据结构大型实验大整数运算系统(附源代码)

1、数据结构大型实验实验报告（附源代码） 浙江工业大学 朱镇洋 曹耀明 陈华族目录第一部分 要求与概述 一、实验目的以及准备 1.1.1 问题描述 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .1.1.2 基本要求 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2、. . .1.1.3 设计思路 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .第二部分 具体实现 一、代码部分 2.1.1 链表类及大数类的部分说明以及部分源码 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.2 部分简单函数功能 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

3、. . . . . . . . . . . . . . . . . . . . 2.1.3 加法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.4 减法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4、. 2.1.5 乘法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.6 除法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.7 幂运算 . . . . . . . . . . . . .

5、. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.1.8 二进制和十进制的相互转化 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 二、程序流程及函数间关系2.2.1 程序流程图 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6、 . . . . . . . . . . . . .2.2.2 函数调用关系分析 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 三、实验验证分析2.3.1 输入的形式和输入值的范围 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.2 输出的形式 . . . . . . . . . . . . . . . . . . . . .

7、 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.3 程序所能达到的功能. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .2.3.4 测试数据 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

8、 . 四、调试分析2.4.1 调试过程中的主要技术问题以及具体的解决方法 . . . . . . . . . . . . . . . . . . . . . . . . 2.4.2 印象最深刻的个调试错误，及修正方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 五、附录2.5.1 源代码及其所属文件 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .第一部分 要求与概述 1.1.1

9、 问题描述密码学分为两类密码：对称密码和非对称密码。对称密码主要用于数据的加/解密，而非 对称密码则主要用于认证、数字签名等场合。非对称密码在加密和解密时，是把加密的 数据当作一个大的正整数来处理，这样就涉及到大整数的加、减、乘、除和指数运算等， 同时，还需要对大整数进行输出。请采用相应的数据结构实现大整数的加、减、乘、除 和指数运算，以及大整数的输入和输出。 1.1.2 基本要求 要求采用链表来实现大整数的存储和运算，不允许使用标准模板类的链表类(list)和函 数。同时要求可以从键盘输入大整数，也可以文件输入大整数，大整数可以输出至显示 器，也可以输出至文件。大整数的存储、运算和显示，可以

10、同时支持二进制和十进制， 但至少要支持十进制。大整数输出显示时，必须能清楚地表达出整数的位数。测试时， 各种况都需要测试，并附上测试截图； 要求大整数的长度可以不受限制，即大整数的十进制位数不受限制，可以为十几位的整 数，也可以为500多位的整数，甚至更长； 大整数的运算和显示时，只需要考虑正的大整数。如果可能的话，请以秒为单位显示每 次大整数运算的时间； 要求采用类的设计路，不允许出现类以外的函数定义，但允许友元函数。主函数中只 能出现类的成员函数的调用，不允许出现对其它函数的调用。 要求采用多文件方式：.h 文件存储类的声明，.cpp 文件存储类的实现，主函数main 存储在另外一个单独的

11、cpp 文件中。如果采用类模板，则类的声明和实现都放在.h 文件 中； 要求源程序中有相应注释； 不强制要求采用类模板，也不要求采用可视化窗口； 要求测试例子要比较详尽，各种极限况也要考虑到，测试的输出信o要详细易懂，表 明各个功能的执行正确； 要求采用Visual C+ 6.0 及以上版本进行调试。1.1.3 设计思路 根据题目要求，用链表来实现大整数的存储，用大整数类Long_Num并实现一些基本操作，设计界面菜单类LN_menu来显示界面；然后，在main函数中来完成各种操作与检验。第二部分 具体实现2.1.1 链表类及大数类的部分说明以及部分源码链表类：List由使用指针连接的节点组成

12、，每个节点都保存着数据，以及指向前驱 和后继的指针。每个节点中存储一个数字表示大数的一位。源代码：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() /构造函数he

13、ad=NULL;back=NULL;len=0;Long_Num()默认构造函数。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;void equal(Long_Num temp)用equ

14、al代替了构造函数。 2.1.2 部分简单函数功能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;elsebreak;while(p)n_len+;p=p-next;len=n_len;void length()把大整数运算过后前面的0去掉，并且更正len长度。bool Long_Num:equalto(Long_Num temp) /判断两大整数是否相等node*p1=head,*p2=temp

15、.head; bool flag=true;while(flag&p1)if(p1-value!=p2-value)flag=false;elsep1=p1-next;p2=p2-next;return flag;void equalto（Long_Num temp)判断两大整数是否相等void Long_Num:print() /打印十进制数并存储if(head=NULL)cout*数据为空!*next)if(p-value=0)p=p-next;elsebreak;while(p)coutvalue;outfilevalue;p=p-next;outfileendl;coutendl;vo

16、id print()打印并存储十进制数据。void Long_Num:print2() /打印二进制数并存储数据if(head=NULL)cout*数据为空!*next)if(p-value=0)p=p-next;elsebreak;while(p)coutvalue;outfilevalue;p=p-next;outfileendl;coutvalue!=temp2-value)flag=temp1-valuetemp2-value?true:false;break;elsetemp1=temp1-next;temp2=temp2-next;if(!temp1)flag=true;retur

17、n flag;bool Long_Num:compare2(Long_Num temp) /升级版比较，可比较长度的大整数，大于等于返回trueif(lentemp.len)return true;elseif(len=temp.len)return compare(temp);elsereturn false;bool compare(Long_Num temp)都是实现两个大整数的比较。void Long_Num:set_Long_Num(string s) /将输入的字符串转成大整数int str_len=s.length();head=new node(int)s0-48);len+;

18、back=head;if(str_len1)for(int i=1;inext=Newnode;Newnode-pre=back;back=back-next;length();void Long_Num:set_Long_Num2(int temp) /建立大整数，将参数建立新节点加在尾部node*Newnode=new node(temp);if(back)back-next=Newnode;Newnode-pre=back;back=back-next;elsehead=Newnode;back=head;len+;void set_Long_Num(string s) 创建大整数，把字

19、符串的内容转为int赋给大整数。void set_Long_Num2(int temp) 如果当前大整数为空，则创建大整数，并把值赋给它，如果非空，则在后面添加节点，把值赋给节点。 Long_Num Long_Num:sub_Num(Long_Num temp,node* &p) /截取一定长度，用于试商法Long_Num tempp;node*p1=head,*p2=temp.head;string s=;while(p2)s+=p1-value+0;p1=p1-next;p2=p2-next;p=p-next;tempp.set_Long_Num(s);if(!pare(

20、temp) /如果截取的子串还是比参数小，再向后截一位p=p-next;tempp.set_Long_Num2(p1-value);tempp.length();return tempp; Long_Num sub_Num(Long_Num temp,node* &p) 截取被除数的字串，用于除法与除数的比较，如果小，则再截取后面一位。int Long_Num:result(Long_Num temp) /除法中的试商法得到当前位的商length();int result=0;while(compare2(temp)decrease(temp);result+;length();return

21、result;int result(Long_Num temp)得到当前大整数除以除数的商。2.1.3 加法实现思路： 加法通过两个操作数的每一位相加，满10进位的思路设计。代码实现： Long_Num Long_Num:add(Long_Num temp) /大整数加法if(temp.head=NULL|head=NULL)cout数据为空!temp.len)temp1=back; temp2=temp.back; /如果当前大整数大于后一个，则temp1为长的最后一个节点for(;)while(temp2!=NULL)j=temp1-value+temp2-value+i; temp1-v

22、alue=j%10; if(j=10)i=1;elsei=0;temp2=temp2-pre;temp1=temp1-pre; /在短的那个数还没有遍历完的情况下，实现每一位的加法，设置一个i变量，默认设为0。如果满10则设为1，并在前一位加上，否则设为0。if(temp1=NULL)if(i=1)node*Newnode=new node(1);Newnode-next=head;head-pre=Newnode;head=head-pre;break;elsebreak; /如果到了长的那个数的头一位，而i仍为1，则在大整数的前面添加值1的节点。if(temp1!=NULL)j=temp1

23、-value+i;temp1-value=j%10;if(j=10)i=1;elsei=0;temp1=temp1-pre; /如果还没到长的那个数的头一个，执行i与当前数的加法，如果满10则i为1，否则i为0。length(); return *this; /把第一个不为0的数的前面的0去掉，并更正大整数的长度，并返回长的那个对象。if(len=temp.len)i=0;temp1=back;temp2=temp.back;while(temp1-pre!=NULL)j=temp1-value+temp2-value+i;if(j=10)temp1-value=j%10;i=1;elsete

24、mp1-value=j;i=0;temp2=temp2-pre;temp1=temp1-pre;j=temp1-value+temp2-value+i; /两个大整数位数相同，每一位都相加，满10进1。if(j=10)temp1-value=j%10;node*Newnode=new node(1);head-pre=Newnode;Newnode-next=head;head=head-pre;elsetemp1-value=j; /到了头一位时，如果i为1，则在大整数前面添加值为1的节点。length();return *this;if(lenvalue+temp2-value+i;tem

25、p1-value=j%10;if(j=10)i=1;elsei=0;temp2=temp2-pre;temp1=temp1-pre; /在短的那个数还没有遍历完的情况下，实现每一位的加法，设置一个i变量，默认设为0。如果满10则设为1，并在前一位加上，否则设为0。if(temp1=NULL)if(i=1)node*Newnode=new node(1);Newnode-next=temp.head;temp.head-pre=Newnode;temp.head=temp.head-pre;break;elsebreak;if(temp1!=NULL)j=temp1-value+i;temp1-

26、value=j%10;if(j=10)i=1;elsei=0;temp1=temp1-pre; /如果还没到长的那个数的头一个，执行i与当前数的加法，如果满10则i为1，否则i为0。equal(temp);length();return *this; /把第一个不为0的数的前面的0去掉，并更正大整数的长度，并返回长的那个对象。2.1.4 减法实现思路： 减法通过两个操作数每一位相减，不够则借位的思路设计。代码实现： Long_Num Long_Num:decrease(Long_Num temp) /大整数减法if(head=NULL|temp.head=NULL)cout数据为空!temp.

27、len)temp1=back;temp2=temp.back;while(temp1)while(temp2!=NULL)j=temp1-value-temp2-value-i;if(jvalue=j+10;i=1;elsetemp1-value=j;i=0;temp1=temp1-pre;temp2=temp2-pre; /在短的那个数还没有遍历完的情况下，实现每一位的减法，设置一个i变量，默认设为0。如果不够则设为1，并在前一位减去，否则设为0。j=temp1-value-i;if(jvalue=j+10;i=1;elsetemp1-value=j;i=0;temp1=temp1-pre;

28、 /如果还没到长的那个数的头一个，执行i与当前数的减法，如果不够则i为1，否则i为0。length();return *this; /把第一个不为0的数的前面的0去掉，并更正大整数的长度，并返回长的那个对象。if(len=temp.len)int i=0,j;node*temp1,*temp2;if(compare(temp)if(equalto(temp)set_Long_Num(0);return *this; /两个大整数相等则直接返回0elsetemp1=back;temp2=temp.back;while(temp1)j=temp1-value-temp2-value-i;if(jv

29、alue=j+10;i=1;elsetemp1-value=j;i=0;temp1=temp1-pre;temp2=temp2-pre; / 两个大整数位数相同，每一位都相减，不够则把i=1，在前面一位减的时候减去，再把i=0，否则就i=0。length();return *this; /把第一个不为0的数的前面的0去掉，并更正大整数的长度，并返回长的那个对象。elseLong_Num tempp;tempp.equal(temp);temp1=tempp.back;temp2=back;while(temp1)j=temp1-value-temp2-value-i;if(jvalue=j+1

30、0;i=1;elsetemp1-value=j;i=0;temp1=temp1-pre;temp2=temp2-pre;equal(tempp);length();return *this;if(lenvalue-temp2-value-i;if(jvalue=j+10;i=1;elsetemp1-value=j;i=0;temp1=temp1-pre;temp2=temp2-pre; /在短的那个数还没有遍历完的情况下，实现每一位的减法，但是用长的那个减去短的那个，设置一个i变量，默认设为0。如果不够则设为1，并在前一位减去，否则设为0。j=temp1-value-i;if(jvalue=j

31、+10;i=1;elsetemp1-value=j;i=0;temp1=temp1-pre; /如果还没到长的那个数的头一个，执行i与当前数的减法，用长的那个数减短的，如果不够则i为1，否则i为0。equal(tempp);length();return *this; /把第一个不为0的数的前面的0去掉，并更正大整数的长度，并返回长的那个对象。 2.1.5 乘法实验思路： 乘法通过一个操作数的每一位分别于另一个操作数的每一位相乘，得到的结果再相加设计。代码实现： Long_Num Long_Num:change() /删除头尾节点（乘法专用）node*p1=head-next;node*p2=

32、head;while(p1-next!=NULL)p2-value=p1-value;p1=p1-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_Num multiply(Long_Num tempp,Long_Num temps) /大整数乘法Long_Num sum,ex,cx;ex.head=new node(0);ex.

33、len+;ex.back=ex.head;sum.head=new node(0);sum.len+;sum.back=sum.head;cx.head=new node(0);cx.len+;cx.back=cx.head;node*temp1,*temp2,*tempt;temp1=tempp.back;temp2=temps.back; for(int w=0;temp2!=NULL;w+) /设置w变量，从0循环到第二个大整数的长度。Long_Num l;int i=0,j;l.head=new node(0); l.back=new node(0); l.head-next=l.ba

34、ck; l.back-pre=l.head;tempt=l.back; /先创建一个大整数l，头尾结点分别为0。for(;)while(temp1!=NULL)j=temp1-value*temp2-value+i; i=j/10; temp1=temp1-pre; node*Newnode=new node(); Newnode-pre=l.head;Newnode-next=l.head-next;tempt-pre=Newnode;l.head-next=Newnode;tempt=tempt-pre;tempt-value=j%10;l.len+; /把一个大整数的每一位乘以另一个大整

35、数的第一位，设置i=0，结果加上i除以10，商赋给当前值，余数赋给i，把当前值插入到l的头结点后，l的长度加1。 for(int ww=0;wwnext=Newnode; Newnode-pre=l.back; l.back=Newnode;l.len+; /当一个大整数的每一位乘完以后，把另一个大整数的位数往前移一位，并且移动一次，要在l后面添加一个值为0的节点，并且l的长度加1。if(temp1=NULL)if(i!=0) node*Newnode=new node(i); Newnode-next=l.head-next; l.head-next-pre=Newnode; l.head-

36、next=Newnode; Newnode-pre=l.head; l.len+; /当到达第一个大整数的头一位时i仍不为0，则在l的头结点后面插入值为i的节点，并且l的长度加1。temp1=tempp.back; temp2=temp2-pre;ex.len=l.len-2; ex=l.change(); /去掉原先创建的头尾两个值为0的节点，长度减2。cx=sum;cx.len=sum.len; sum=cx.add2(ex); break;sum.len+;sum.length(); return sum; /把第一个不为0的数的前面的0去掉，并更正大整数的长度，并返回。2.1.6 除法

37、实验思路： 除法通过先在被除数中取跟除数一样的位数，进行不断的减法操作，直至小于除数，然后再向后面取数直至位数于除数相同，重复。代码实现： int Long_Num:result(Long_Num temp) /除法中的试商法得到当前位的商length();int result=0;while(compare2(temp)decrease(temp);result+;length();return result;void Long_Num:set_Long_Num2(int temp) /建立大整数，将参数建立新节点加在尾部node*Newnode=new node(temp);if(back

38、)back-next=Newnode;Newnode-pre=back;back=back-next;elsehead=Newnode;back=head;len+;Long_Num Long_Num:sub_Num(Long_Num temp,node* &p) /截取一定长度，用于试商法Long_Num tempp;node*p1=head,*p2=temp.head;string s=;while(p2)s+=p1-value+0;p1=p1-next;p2=p2-next;p=p-next;tempp.set_Long_Num(s);if(!pare(temp) /如

39、果截取的子串还是比参数小，再向后截一位p=p-next;tempp.set_Long_Num2(p1-value);tempp.length();return tempp;Long_Num Long_Num:divide(Long_Num temp1,Long_Num& temp2) /大整数除法string s_result=;int sh;Long_Num temp;if(compare2(temp1)if(lentemp1.len)node*curren=head;temp=sub_Num(temp1,curren); / 当被除数位数比除数大，先创建一个大整数temp，存储在被除数上截取除数长度的一段值，如果不够大，则往后面再截取一位。sh=temp.result(temp1); /sh为一次除法得到的商，temp为得到的余数s_result+=sh+0; /创建一个字符串s，来累加商while(curren)temp.set_Long_Num2(curren-value);sh=temp.result(temp1); s_result+=sh+0;curren=curren-next; /余数加上后一位的值构成大整数除以除数，如果比除数小则s加上0，否则s加上商，重复直至最后。temp2.equal(temp);set_Long_Num