数据结构长整数四则运算

实习11.4长整数四则运算实习报告题目：设计一个实现任意长的整数进行加法运算的演示程序。一、需求分析1.本演示程序中，利用双向循环链表实现长整数的存储，每个结点含一个整型变量任何整型变量的范围是-（215-1）—（215-1）。在每个结点中仅存十进制数的4位，即不超过9999的非负整数，整个链表表示为万进制数。输入和输出形式按中国对于长整数的习惯，每四位一组，组间用逗号隔开。2.演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令；相应的输入数据（滤去输入数据中的非法字符）和运算结果显示在其后。3.程序执行的命令包括：（1）构造链表；（2）输入数据；（3）数据处理；（4）结束4.测试数据（1）0；0；应输出0。（2）-2345,6789；-7654,3211；应输出-1,0000,0000.（3）-9999,9999；1,0000,0000,0000；应输出9999,0000,0001（4）1,0001,0001；-1,0001,0001；应输出0。（5）1,0001,0001；-1,0001,0000；应输出1.（6）-9999,9999,9999；-9999,9999,9999；应输出-1,9999,9999,9998。（7）1,0000,9999,9999；1；应输出1,0001,0000,0000。二、概要设计structLinkNode//定义结构体LinkNode{intdata;//记录每个节点的整数（小于10000）LinkNode*next;//记录下一个节点的地址LinkNode*pre;//记录前一个节点的地址};classLinkList//定义类LinkList{private:LinkNode*head0,*head1;//head0，head1分别记录两个整数链表的头指针LinkNode*currptr;LinkNode*result;//result记录结果链表的头指针public:LinkList();//构造函数，初始化链表~LinkList();//析构函数，释放空间voidCreat(stringa);//引入字符串，创立两个链表，分别表示两个整数voidAdd();//实现两个整数相加voidDisplay();//显示结果voidaddtwo();//节点多的作为被加数，少的作为加数，实现整//数绝对值大的加小的};voidmain()//主函数｛……do{}while(Yes_No=='y'||Yes_No=='Y');//Yes_No不等于'Y'或'y'时，程序退出}三、详细设计#includeiostream#includestring#includemath.husingnamespacestd;structLinkNode{intdata;//记录每个节点的整数（小于10000）LinkNode*next;//记录下一个节点的地址LinkNode*pre;//记录前一个节点的地址};classLinkList{private:LinkNode*head0,*head1;//head0，head1分别记录两个整数链表的头指针LinkNode*currptr;LinkNode*result;//result记录结果链表的头指针public:LinkList();//构造函数，初始化链表~LinkList();//析构函数，释放空间voidCreat(stringa);//引入字符串，创立两个链表，分别表示两个整数voidAdd();//实现两个整数相加voidDisplay();//显示结果voidaddtwo();//节点多的作为被加数，少的作为加数，实现整//数绝对值大的加小的};//链表的实现部分intsum(intn);LinkList::LinkList()//构造函数，初始化链表{head0=newLinkNode;//申请一个空间记录整数的符号和节点数head1=newLinkNode;head0-next=head0;head0-pre=head0;//初始化链表，建立双向循环链表head1-next=head1;head1-pre=head1;result=newLinkNode;result-next=result;result-pre=result;currptr=NULL;}LinkList::~LinkList()//析构函数，释放空间{LinkNode*p1=head0,*p2=head1,*p3=result;//三个指针分别指向三条链表的头指针while(p1!=p1-pre){p1-pre-next=p1-next;p1-next-pre=p1-pre;currptr=p1;p1=p1-next;deletecurrptr;}while(p2!=p2-pre)//逐个删除节点，释放空间{p2-pre-next=p2-next;p2-next-pre=p2-pre;currptr=p2;p2=p2-next;deletecurrptr;}while(p3!=p3-pre){p3-pre-next=p3-next;p3-next-pre=p3-pre;currptr=p3;p3=p3-next;deletecurrptr;}//deletep1;//deletep2;//deletep3;}voidLinkList::Creat(stringa)//引入字符串，创立两//个链表，分别表示两个整数{inti=0,j=0,m=0,n=0,k=0,l=0,s=0,w=0;//i记录字符串，j记录加数节点数；s记录被加数节点数//w标记字符串中的‘-’号//k记录字符串中的字符转化为整数的值，l使每个节点记录4位while(a[m]!=';')m++;//m记录字符串中被加数的字符数n=m;while(a[n]!='\0')n++;//n记录字符串的总字符数if(a[0]=='-'){head0-data=(-1);//记录整数符号w=1;}else{head0-data=1;}for(i=m-1;i=w;i--){if(a[i]!=',')//把字符转化为整数{k+=(a[i]-'0')*sum(l);l++;}if(a[i]==','||i==w){currptr=newLinkNode;//把整数存到双向循环链表中currptr-data=k;currptr-next=head0;currptr-pre=head0-pre;head0-pre-next=currptr;head0-pre=currptr;head0=currptr;s++;//节点数加1k=0;//重新初始化k和ll=0;}}head0-pre-data*=s;//存储整数符号和节点数//与建第一个整数链表一样，建立第二个整数链表head1k=0;l=0;if(a[m+1]=='-'){head1-data=(-1);m++;}elsehead1-data=1;for(i=n-1;im;i--){if(a[i]!=','){k+=(a[i]-'0')*sum(l);l++;}if(a[i]==','||i==m+1){currptr=newLinkNode;currptr-data=k;currptr-next=head1;currptr-pre=head1-pre;head1-pre-next=currptr;head1-pre=currptr;head1=currptr;j++;k=0;l=0;}}head1-pre-data*=j;}voidLinkList::Add()//实现两个整数相加{LinkNode*temp;if(abs(head0-pre-data)abs(head1-pre-data))//两个整数中，绝对值大的为被加数addtwo();elseif(abs(head0-pre-data)abs(head1-pre-data)){temp=head0;head0=head1;head1=temp;addtwo();}elseif(abs(head0-pre-data)==abs(head1-pre-data)){intk1,k2;LinkNode*p=head0,*q=head1;//如果节点数相同，则判断节点中数值大小while(p-data==q-data&&p!=head0-pre-pre&&q!=head1-pre-pre){p=p-next;q=q-next;}k1=p-data;k2=q-data;if(k1k2)addtwo();else{temp=head0;head0=head1;head1=temp;addtwo();}}}voidLinkList::addtwo()//节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的//默认head0存的整数绝对值比head1大{ints=0,m1=head0-data,m2=head1-data;m1=(head0-pre-data/abs(head0-pre-data));//head0的符号m2=(head1-pre-data/abs(head1-pre-data));//head1的符号LinkNode*p=head0-pre-pre,*q=head1-pre-pre;result-data=head0-pre-data;//存结果的节点数和符号while(q!=head1-pre)//head0存的整数绝对值比head1大，即head0的节点数大于或等于head1{currptr=newLinkNode;currptr-data=(p-data)*m1+(q-data)*m2+s;//两整数相加if((m1*m2)0)//如果符号相同{if(abs(currptr-data)-10000=0)//相加后超过10000，则进位{s=currptr-data/10000;currptr-data=abs(currptr-data)%10000;}else//abs(currptr-data)-100000，不进位{s=0;currptr-data=abs(currptr-data);}}elseif(m10&&m20)//符号不同，在此相当于实现两个正整数相减{s=0;if(currptr-data0)//小于0，向前一位借1{currptr-data+=10000;s=-1;}}elseif(m10&&m20)//符号不同，在此相当于实现负整数加上正整数{s=0;if(currptr-data0)//大于0，{currptr-data=10000-currptr-data;s=1;}elsecurrptr-data=abs(currptr-data);}currptr-next=result;//存入链表currptr-pre=result-pre;result-pre-next=currptr;result-pre=currptr;result=currptr;p=p-pre;q=q-pre;}//当head0节点数比head1长时，继续建链while(p!=head0-pre){currptr=newLinkNode;currptr-data=p-data*m1+s;s=currptr-data/10000;if((m1*m2)0){if(abs(currptr-data)-10000=0){s=currptr-data/10000;currptr-data=abs(currptr-data)%10000;}els