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

1、数据结构大型实验实验报告（附源代码）浙江工业大学朱镇洋 曹耀明 陈华族目录第一部分 要求与概述 一、实验目的以及准备 第二部分 具体实现 一、代码部分 二、程序流程及函数间关系三、实验验证分析四、调试分析五、附录第一部分 要求与概述密码学分为两类密码：对称密码和非对称密码。对称密码主要用于数据的加/解密，而非 对称密码则主要用于认证、数字签名等场合。非对称密码在加密和解密时，是把加密的 数据当作一个大的正整数来处理，这样就涉及到大整数的加、减、乘、除和指数运算等， 同时，还需要对大整数进行输出。请采用相应的数据结构实现大整数的加、减、乘、除 和指数运算，以及大整数的输入和输出。基本要求 要求采

2、用链表来实现大整数的存储和运算，不允许使用标准模板类的链表类(list和函 数。同时要求可以从键盘输入大整数，也可以文件输入大整数，大整数可以输出至显示 器，也可以输出至文件。大整数的存储、运算和显示，可以同时支持二进制和十进制， 但至少要支持十进制。大整数输出显示时，必须能清楚地表达出整数的位数。测试时， 各种况都需要测试，并附上测试截图； 要求大整数的长度可以不受限制，即大整数的十进制位数不受限制，可以为十几位的整 数，也可以为500多位的整数，甚至更长； 大整数的运算和显示时，只需要考虑正的大整数。如果可能的话，请以秒为单位显示每 次大整数运算的时间； 要求采用类的设计路，不允许出现类以

3、外的函数定义，但允许友元函数。主函数中只 能出现类的成员函数的调用，不允许出现对其它函数的调用。 要求采用多文件方式：.h 文件存储类的声明，.cpp 文件存储类的实现，主函数main 存储在另外一个单独的cpp 文件中。如果采用类模板，则类的声明和实现都放在.h 文件 中； 要求源程序中有相应注释； 不强制要求采用类模板，也不要求采用可视化窗口； 要求测试例子要比较详尽，各种极限况也要考虑到，测试的输出信o要详细易懂，表 明各个功能的执行正确； 要求采用Visual C+ 6.0 及以上版本进行调试。设计思路 根据题目要求，用链表来实现大整数的存储，用大整数类Long_Num并实现一些基本操

4、作，设计界面菜单类LN_menu来显示界面；然后，在main函数中来完成各种操作与检验。第二部分 具体实现链表类及大数类的部分说明以及部分源码链表类：List由使用指针连接的节点组成，每个节点都保存着数据，以及指向前驱 和后继的指针。每个节点中存储一个数字表示大数的一位。源代码：node:node(next=NULL;pre=NULL;node:node(int p /节点构造函数value=p;next=NULL;pre=NULL;大数类： 大数类有一个头节点和尾节点，分别为head和back ，而back的下一个节点为NULL。 当head与back指向同一位置时表示List为只含一个节点

5、。Head与back都为NULL表示List为空。而且用一个int类型的变量存储大数的长度，为以后的运算提供便利。构造函数：Long_Num:Long_Num( /构造函数head=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(pnode*Newnode=new node(p-value;back-

6、next=Newnode;Newnode-pre=back;back=back-next;p=p-next;void equal(Long_Num temp用equal代替了构造函数。 void Long_Num:length( /更正对象长度并规范大整数node*p=head;int n_len=0;while(p-nextif(p-value=0p=p-next;head=head-next;head-pre=NULL;elsebreak;while(pn_len+;p=p-next;len=n_len;void length(把大整数运算过后前面的0去掉，并且更正len长度。bool L

7、ong_Num:equalto(Long_Num temp /判断两大整数是否相等node*p1=head,*p2=temp.head;bool flag=true;while(flag&p1if(p1-value!=p2-valueflag=false;elsep1=p1-next;p2=p2-next;return flag;void equalto（Long_Num temp判断两大整数是否相等void Long_Num:print( /打印十进制数并存储if(head=NULLcout*数据为空!*nextif(p-value=0p=p-next;elsebreak;while(pco

8、ut value; outfilenext;outfile cout void print(打印并存储十进制数据。void Long_Num:print2( /打印二进制数并存储数据if(head=NULLcout*数据为空!*nextif(p-value=0p=p-next;elsebreak;while(pcout value; outfilenext;outfile coutvalue!=temp2-valueflag=temp1-valuetemp2-value?true:false;break;elsetemp1=temp1-next;temp2=temp2-next;if(!tem

9、p1flag=true;return flag;bool Long_Num:compare2(Long_Num temp /升级版比较，可比较长度的大整数，大于等于返回trueif(lentemp.lenreturn true;elseif(len=temp.lenreturn 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(ints0-

10、48;len+;back=head;if(str_len1for(int i=1;i node*Newnode=new node(intsi-48;len+;back-next=Newnode;Newnode-pre=back;back=back-next;length(;void Long_Num:set_Long_Num2(int temp /建立大整数，将参数建立新节点加在尾部node*Newnode=new node(temp;if(backback-next=Newnode;Newnode-pre=back;back=back-next;elsehead=Newnode;back=h

11、ead;len+;void set_Long_Num(string s 创建大整数，把字符串的内容转为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(p2s+=p1-value+0;p1=p1-next;p2=p2-next;p=p-next

12、;tempp.set_Long_Num(s;if(!pare(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(tempdecrease(temp;r

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

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

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

16、value=j;i=0;temp2=temp2-pre;temp1=temp1-pre;j=temp1-value+temp2-value+i; /两个大整数位数相同，每一位都相加，满10进1。if(j=10temp1-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(len temp1=temp.back;temp2=back;fo

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

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

19、LL|temp.head=NULLcout数据为空!temp.lentemp1=back;temp2=temp.back;while(temp1while(temp2!=NULLj=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-

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

21、ue-temp2-value-i;if(jvalue=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(temp1j=temp1-value-temp2-va

22、lue-i;if(jvalue=j+10;i=1;elsetemp1-value=j;i=0;temp1=temp1-pre;temp2=temp2-pre;equal(tempp;length(;return *this;if(len Long_Num tempp;tempp.equal(temp;temp1=tempp.back;temp2=back;while(temp1while(temp2!=NULLj=temp1-value-temp2-value-i;if(jvalue=j+10;i=1;elsetemp1-value=j;i=0;temp1=temp1-pre;temp2=te

23、mp2-pre; /在短的那个数还没有遍历完的情况下，实现每一位的减法，但是用长的那个减去短的那个，设置一个i变量，默认设为0。如果不够则设为1，并在前一位减去，否则设为0。j=temp1-value-i;if(jvalue=j+10;i=1;elsetemp1-value=j;i=0;temp1=temp1-pre; /如果还没到长的那个数的头一个，执行i与当前数的减法，用长的那个数减短的，如果不够则i为1，否则i为0。equal(tempp;length(;return *this; /把第一个不为0的数的前面的0去掉，并更正大整数的长度，并返回长的那个对象。实验思路：乘法通过一个操作数的

24、每一位分别于另一个操作数的每一位相乘，得到的结果再相加设计。代码实现：Long_Num Long_Num:change( /删除头尾节点（乘法专用）node*p1=head-next;node*p2=head;while(p1-next!=NULLp2-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; /删除乘法一开始创建的头尾两个节点，并重新定义头尾节点

25、。 Long_Num multiply(Long_Num tempp,Long_Num temps /大整数乘法Long_Num sum,ex,cx;ex.head=new node(0;ex.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变

26、量，从0循环到第二个大整数的长度。Long_Num l;int i=0,j;l.head=new node(0;l.back=new node(0;l.head-next=l.back;l.back-pre=l.head;tempt=l.back; /先创建一个大整数l，头尾结点分别为0。for(;while(temp1!=NULLj=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=Newn

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

28、长度加1。if(temp1=NULLif(i!=0node*Newnode=new node(i;Newnode-next=l.head-next;l.head-next-pre=Newnode;l.head-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

29、;sum=cx.add2(ex; break; sum.len+;sum.length(; return sum; /把第一个不为0的数的前面的0去掉，并更正大整数的长度，并返回。实验思路：除法通过先在被除数中取跟除数一样的位数，进行不断的减法操作，直至小于除数，然后再向后面取数直至位数于除数相同，重复。代码实现：int Long_Num:result(Long_Num temp /除法中的试商法得到当前位的商length(;int result=0;while(compare2(tempdecrease(temp;result+;length(;return result;void Long

30、_Num:set_Long_Num2(int temp /建立大整数，将参数建立新节点加在尾部node*Newnode=new node(temp;if(backback-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(p2s+=p1-value+0;p

31、1=p1-next;p2=p2-next;p=p-next;tempp.set_Long_Num(s;if(!pare(temp /如果截取的子串还是比参数小，再向后截一位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(temp1if(lentemp1.lennode*curren=head;

32、temp=sub_Num(temp1,curren; / 当被除数位数比除数大，先创建一个大整数temp，存储在被除数上截取除数长度的一段值，如果不够大，则往后面再截取一位。sh=temp.result(temp1; /sh为一次除法得到的商，temp为得到的余数s_result+=sh+0; /创建一个字符串s，来累加商while(currentemp.set_Long_Num2(curren-value;sh=temp.result(temp1; s_result+=sh+0;curren=curren-next; /余数加上后一位的值构成大整数除以除数，如果比除数小则s加上0，否则s加上

33、商，重复直至最后。temp2.equal(temp;set_Long_Num(s_result;length(;return *this; /返回字符串s为总的商，把余数赋给第二个大整数参数elsesh=result(temp1;s_result+=sh+0;temp2.equal(*this;set_Long_Num(s_result;length(;return *this; /当被除数位数和除数相同，如上进行一次除法操作。 elsetemp2.equal(*this;set_Long_Num(0;return *this; /当被除数位数比除数小，就直接返回s为0，余数为被除数.实验思路

34、：幂运算则通过底数自乘，幂减1，结合加法，乘法，减法的方法实现。代码实现：bool If_one(Long_Num temp /判断对象是为1bool flag=false;node*p=temp.back;if(p-value!=1return flag;elsep=p-pre;flag=true;while(pif(p-value!=0flag=false;break;elsep=p-pre;return flag;bool If_zero(Long_Num temp /判断对象是否为0bool flag=false;node*p=temp.back;if(p-value!=0return

35、 flag;elsep=p-pre;flag=true;while(pif(p-value!=0flag=false;break;elsep=p-pre;return flag;Long_Num Long_Num:power(Long_Num temp /大整数乘方Long_Num sum,tempp,one;one.set_Long_Num(1;tempp.equal(temp;sum.equal(*this;if(If_one(temppsum.length(;return sum; /指数为1则直接返回底数elseif(If_zero(temppreturn one; /指数为0则直接返

36、回0elsewhile(!If_one(temppsum=multiply(sum,*this;tempp=tempp.decrease(one; /底数自乘，指数减1，直至指数为1。sum.length(;return sum;实验思路：十进制转二进制则通过不断除二，取余放入栈中，再输出的方法实现。二进制转十进制则通过每一位乘以2(n-1再相加的方法实现。代码实现：十进制转二进制Long_Num Long_Num:tranform1( /十进制转二进制if(If_one(*this|If_zero(*thisreturn *this; / 如果当前值为0或1则直接返回。elsestack s

37、t; Long_Num yushu,two;two.set_Long_Num(2;while(!If_one(*thisdivide(two,yushu;st.push(yushu.get_value(; /商不断除2，把余数放入栈中，直到商为1。set_Long_Num(1;while(!st.empty(set_Long_Num2(st.top(;st.pop(; /把栈中的元素输出，就为二进制。return *this;二进制转十进制Long_Num Long_Num:tranform2( /二进制转十进制if(len=0cout*数据为空!value=0set_Long_Num(0;r

38、eturn *this;elseset_Long_Num(1;return *this; /如果长度为1，直接输出。if(len1Long_Num cx,sum,ex,one;sum.set_Long_Num(0;one.set_Long_Num(1;cx.set_Long_Num(2;int t_len=len-1,t;node*p=head;while(p-nextif(p-value=1string s=;s=t_len+0;ex.set_Long_Num(s;sum.add(cx.power(ex;t_len-;p=p-next; /每一位乘以2(n-1,相加，直到最后一位。if(p-

39、value=1sum.add(one; /如果最后一位为1，则再加1。equal(sum;return *this;加法调用length函数，equal函数。减法调用length函数，compare函数，equal函数，equalto函数，set_Long_Num函数。乘法调用change函数，add函数，length函数。除法调用compare函数，comepare2函数，sub_Num函数，result函数，set_Long_Num2函数，set_Long_Num函数，equal函数，length函数，decrease函数。幂运算调用set_Long_Num函数，equal函数，lengt

40、h函数，If_one函数 ，If_zero函数，multiply函数，decrease函数。十进制转二进制调用If_one函数 ，If_zero函数，set_Long_Num函数，divide函数，get_value函数，set_Long_Num2函数。二进制转十进制调用set_Long_Num函数，add函数，power函数，equal函数。理论上可输入无限大的数程序会出现菜单，输入的形式需跟菜单一致。只能输入正数。支持十进制和二进制。键盘输入：文件读入： 指令识别 读写文本 检查错误 算式运算 输出结果正确输入：错误输入：一开始创建链表是只有向后的一个指针，结果在写运算时发现很不方便，所以

41、后面把它改成了双向链表。一开始写除法时，采取了重复减法的方法，结果发现时间复杂度较高，运算时间太长，后来就采取另外算法。运算后前面有0残留的问题，后面又写了一个length把长度更正和去0的的功能，就能正确的输出了。一开始把两个大整数直接用等号相等，结果出现了错误。两个大整数直接用等号相等为地址传递，若一个改变，另一个也会改变。后来写了一个equal函数，仅仅把一个大整数的每个值传给另一个大整数。一开始发现结果不对，但是找了好久也不知道哪里错误。后面发现因为在运算的时候len没有改变，导致在条件判断中出错。一开始在写length函数时仅仅移动了head节点，而没有head节点的pre指针设为N

42、ULL，导致有些运算通过back往前移的时候又出现了0,结果错误。node.h#ifndef NODE_H#define NODE_Hclass nodepublic:node(;node(int p;int value;node*next;node*pre;#endiflong_num.h#ifndef LONG_NUM#define LONG_NUM#includenode.h#include #include using namespace std;class Long_Numprivate:node*head;node*back;int len;public:Long_Num(;voi

43、d length(; /更正一个数的长度bool equalto(Long_Num temp; /判断两个数是否相等void equal(Long_Num temp; /复制函数void print(; /打印并存储数据void print2(; /打印并存储二进制数据friend bool If_one(Long_Num temp; /判断是否为1friend bool If_zero(Long_Num temp; /判断是否为0bool compare(Long_Num temp; /比较长度相等的两数void set_Long_Num(string s; /建立大整数void set_L

44、ong_Num2(int temp; /建立大整数2Long_Num add(Long_Num temp; /加法Long_Num add2(Long_Num temp; /加法2（乘法专用）Long_Num decrease(Long_Num temp; /减法Long_Num change(; /除去乘法计算中的头尾节点（乘法专用）friend Long_Num multiply(Long_Num tempp,Long_Num temps; /友元乘法Long_Num divide(Long_Num temp1,Long_Num& temp2; /除法Long_Num power(Long

45、_Num temp; /乘方Long_Num tranform1(; /十进制转二进制Long_Num tranform2(; /二进制转十进制bool If_even(; /判断是否为偶数Long_Num sub_Num(Long_Num temp,node* &p; /截取子串（除法专用）int result(Long_Num temp; /试商法获取子串的商（除法专用）bool compare2(Long_Num temp; /compare函数的更新，可比较长度不等的大整数int get_value(; /返回节点数值（除法专用）;#endifd_timer.h#ifndef TIMER_CLASS#define TIMER_CLASS#include / declares clock_t type, function clock(, / and constant CLOCKS_PER_SECclass timerprivate:/ starting and ending time measured in clock ticksclock_t startTime, endTime;public:timer(;/ initialize the timer./ Postconditions: set the starting and e