任意长整数加法运算(C++） 一、【实验内容】【问题描述】      设计一个实现任意长的整数进行加法运算的演示程序 【基本要求】：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(215 - 1)~(215 - 1)。输入和输出形式：按中国对于长整数的表示习惯，每四位一组，组间用逗号隔开。　　　　　　【测试数据】：（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”。 二、实验目的１、熟悉掌握双向循环链表的基本操作；２、熟悉任意长字符串的输入，并实现把字符串转化为整数；３、熟悉任意长整数的加法运算；４、更进一步掌握有关类的操作   三、实验文档：                  长整数加法运算一、需求分析1、本程序实现计算任意长的整数的加法运算. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。 2、本演示程序中，集合的元素限定为数字字符[‘0’~’9’]和字符‘，’与‘；’，输入字符可以任意长，输入形式以“回车符”为结束标志，串中字符顺序不限，且允许出现重复字符。3、利用双向循环链表现实长整数的存储，每个结点含一个整形变量。输入的形式以回车结束，可以直接输入正数或负数。按中国对于长整数的表示习惯，每四位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，连续多个分隔符当一个处理。但不使用分隔符也不影响结果。4、测试数据(1)0; 0; 输出“0”; (2)-2345,6789; -7654,3211; 输出 “-1,000,000”; (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". 二、概要设计为实现上述程序功 能，应以双向循环链表表示长整数。为此，需要定义一个抽象数据类型。1. 抽象数据类型定义为：ADT OrderedList{数据对象：D={ai|ai∈int,i=1,2,...n, n≥0}数据关系：R1={|ai-1,ai∈D|=2,……n }基本操作：Creat(string a)操作结果：通过字符串a构造两个位数不限的长整数。addtwo(head0,head1，result)初始条件：head0,head1都已存在,且head0的绝对值比head1大操作结果：result等于head0和head1的和。Add(head0,head1)初始条件：head0,head1都已存在。 操作结果：判断head0与head1绝对值的大小，并使head0的绝对值比head1大Display(result)初始条件：result已存在。 操作结果：按四位一组，分隔符为","的格式，在屏幕上输出result。}ADT OrderedList   2.本程序包含三个模块：1)主程序模块：void main(){    初始化；do{   接受命令；   处理命令；}while(“命令”=”退出”)}2)、集合单元模块——实现集合的抽象数据类型3)、结点结构单元模块——定义集合的结点结构各模块之间的调用关系如下：                    主程序模块                                                               集合单元模块                                                            结点模块二、详细设计1、ZhengshuAdd.h文件，链表的定义部分#include<iostream>#include<string>#include<math.h>using namespace std;struct LinkNode{ int data;                //记录每个节点的整数（小于10000） LinkNode *next;          //记录下一个节点的地址 LinkNode *pre;           //记录前一个节点的地址};class LinkList{private: LinkNode *head0,*head1;    //head0，head1分别记录两个整数链表的头指针 LinkNode *currptr; LinkNode *result;          //result记录结果链表的头指针public: LinkList();                 //构造函数，初始化链表 ~LinkList();               //析构函数，释放空间 void Creat(string a);      //引入字符串，创立两个链表，分别表示两个整数 void Add();                //实现两个整数相加 void Display();            //显示结果 void addtwo();             //节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的};2、ZhengshuAdd.cpp文件，链表的实现部分#include"ZhengshuAdd.h"int sum(int n);LinkList::LinkList()              //构造函数，初始化链表{ head0=new LinkNode;           //申请一个空间记录整数的符号和节点数 head1=new LinkNode; head0->next=head0; head0->pre=head0;             //初始化链表，建立双向循环链表 head1->next=head1; head1->pre=head1;    result=new LinkNode; 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;  delete currptr; } while(p2!=p2->pre)                      //逐个删除节点，释放空间 {   p2->pre->next=p2->next;  p2->next->pre=p2->pre;  currptr=p2;  p2=p2->next;  delete currptr; } while(p3!=p3->pre) {  p3->pre->next=p3->next;  p3->next->pre=p3->pre;  currptr=p3;  p3=p3->next;  delete currptr; }// delete p1;// delete p2;// delete p3;} void LinkList::Creat(string a)                 //引入字符串，创立两个链表，分别表示两个整数{ int i=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=new LinkNode;           //把整数存到双向循环链表中   currptr->data=k;   currptr->next=head0;   currptr->pre=head0->pre;   head0->pre->next=currptr;   head0->pre=currptr;   head0=currptr;    s++;                             //节点数加1   k=0;                             //重新初始化k和l   l=0;                               } }    head0->pre->data*=s;                   //存储整数符号和节点数   //与建第一个整数链表一样，建立第二个整数链表head1 k=0;l=0;  if(a[m+1]=='-') {  head1->data=(-1);  m++; } else   head1->data=1; for(i=n-1;i>m;i--) {  if(a[i]!=',')  {   k+=(a[i]-'0')*sum(l);   l++;  }  if(a[i]==','||i==m+1)  {   currptr=new LinkNode;   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;} void LinkList::Add()                             //实现两个整数相加{ LinkNode *temp; if(abs(head0->pre->data)>abs(head1->pre->data))          //两个整数中，绝对值大的为被加数  addtwo(); else if(abs(head0->pre->data)<abs(head1->pre->data)) {  temp=head0;  head0=head1;  head1=temp;  addtwo(); } else if(abs(head0->pre->data)==abs(head1->pre->data)) {  int k1,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(k1>k2)   addtwo();  else   {   temp=head0;  head0=head1;  head1=temp;  addtwo();  } }}void LinkList::addtwo()         //节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的           //默认head0存的整数绝对值比head1大{ int s=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=new LinkNode;  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)-10000<0，不进位   {    s=0;    currptr->data=abs(currptr->data);   }  }  else if(m1>0&&m2<0)              //符号不同，在此相当于实现两个正整数相减  {   s=0;   if(currptr->data<0)             //小于0，向前一位借1   {    currptr->data+=10000;    s=-1;   }  }  else if(m1<0&&m2>0)           //符号不同，在此相当于实现负整数加上正整数  {    s=0;   if(currptr->data>0)         //大于0，   {    currptr->data=10000-currptr->data;    s=1;   }   else currptr->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=new LinkNode;  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;   }   else {s=0;currptr->data=abs(currptr->data);}  }  else if(m1>0&&m2<0)  {   s=0;   if(currptr->data<0)   {    currptr->data+=10000;    s=-1;   }  }  else if(m1<0&&m2>0)  {   s=0;   if(currptr->data>0)   {    currptr->data=10000-currptr->data;    s=1;   }   else currptr->data=abs(currptr->data);  }  currptr->data=abs(currptr->data)%10000;  currptr->next=result;  currptr->pre=result->pre;  result->pre->next=currptr;  result->pre=currptr;  result=currptr;  p=p->pre; } if(s!=0)                   //处理相加后，进位问题 {  currptr=new LinkNode;  currptr->data=abs(s);  currptr->next=result;  currptr->pre=result->pre;  result->pre->next=currptr;  result->pre=currptr;  result=currptr;  result->pre->data=m1*(abs(result->pre->data)+1); }}void LinkList::Display()                   //显示结果{ LinkNode *p=result; int FuHao=result->pre->data/abs(result->pre->data);//结果的符号 while(p->data==0&&p!=result->pre->pre)              //当运算后前几个节点的数据为0时，不输出 {  p=p->next;  result->pre->data=(abs(result->pre->data)-1)*FuHao;  //结果记录非0节点数 } cout<<FuHao*p->data;         //首先显示符号和第一个节点中的数 if(abs(result->pre->data)!=1) p=p->next; //判断非0节点数是否为1 while(p!=result->pre->pre)    //继续输出 {  cout<<",";               //每4位一组，并用‘，’隔开  cout.width(4);     cout.fill('0');        cout<<p->data;        p=p->next; } if(p==result->pre->pre&&abs(result->pre->data)!=1)   //显示最后一个节点数据 {  cout<<",";  cout.width(4);     cout.fill('0');        cout<<p->data; } cout<<endl;}int sum(int n)                  //计算10的乘方{ int i,s=1; for(i=1;i<=n;i++) {  s=s*10; } return s;} 3、main.cpp文件，主函数和其他函数的实现#include"ZhengshuAdd.h"                   //访问文件ZhengshuAdd.hvoid main()                    //主函数{ cout<<"|===============================================|\n"; cout<<"|***********************************************|\n"; cout<<"|**********欢迎使用任意长整数加法系统***********|\n"; cout<<"|**********************刘伟高*******************|\n"; cout<<"|***********************************************|\n"; cout<<"|在此系统中，可以输入任意长的整数 。               |\n"; string ch; char Yes_No; do{  cout<<"|输入形式为：(-)**,****,****;(-)*,****,****,****|\n";  cout<<"|即符号+数，每4位加一个','，两个数之间用';'隔开 |\n";  cout<<"|请输入你要计算的两个数:                        |\n";  cin>>ch;                                  //输入任意长字符串  LinkList List;                           //定义链表对象  List.Creat(ch);                //把字符串转化为整数，并存到链表中  List.Add();                              //实现两个整数相加  List.Display();                            //输出结果  cout<<"是否继续计算(Y/N):";                  //询问是否继续计算  cin>>Yes_No; }while(Yes_No=='y'||Yes_No=='Y');   //Yes_No不等于'Y'或'y'时，程序退出 cout<<"|===============================================|\n"; cout<<"|***********************************************|\n"; cout<<"|*****************感谢使用本系统!***************|\n"; cout<<"|***********************************************|\n";}4、函数的调用关系图反映了演示程序的层次结构：                    Main       List.Creat(ch)  List.Add()      List.Display()四、调试分析1、由于对任意长整数运算的算法推敲不足，是程序调试时费时不少2、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性3、本程序模块划分比较合理，且把指针全部封装在链表模块中，操作方便。4、算法的时空分析由于链表采用双向循环链表结构，可以从链表两头操作，各种操作的算法时间复杂度比较合理，各函数以及确定链表中的结点位置都是O（n）,n为链表长度。5、本实验采用数据抽象的程序设计方法，将程序分为3个模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。五、用户手册1、本程序的运行环境为DOS操作系统2、进入演示程序后即显示文本方式的用户界面 3、进入界面后，就会提示输入字符串的输入形式，结束符为“回车符”。4、接受其他命令后继执行相应运算和现实相应结果六、测试结果键入0；0 输出0键入y  -2345；6789；-7654，3211 输出-1，0000，0000键入y  -9999，9999；1，0000，0000，0000 输出9999，0000，0001键入y  1，0001，0001；-1，0001，0000 输出1键入y  -9999，9999，9999；-9999，9999，9999 输出-1，9999，9999，9998键入y  1，0000，9999，9999；1 输出1，0001，0000，0000键入n  (退出)七、附录源程序文件名清单：ZhengshuAdd.h                    //元素结点定义单元ZhengshuAdd.cpp                  //链表实现单元Main.cpp                          //主程序   四、实验总结（心得体会）１、进一步熟悉掌握了双向循环链表的基本操作；２、熟悉任意长字符串的输入，并实现把字符串转化为整数；３、熟悉任意长整数的加法运算；４、更进一步掌握有关类的操作5、由于对任意长整数运算的算法推敲不足，是程序调试时费时不少6、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性      五、参考文献：1、《数据结构与算法》    黄定  黄煜廉  刘贤兴  编著  广东科技出版社  2000年1月第1版2、《〈数据结构与算法〉学习与实验指导》  黄煜廉 编著   2005. 8      

评论