任意长整数加法运算(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、熟悉任意长字符串的输入,并实现把字符串转化为整数; 3、熟悉任意长整数的加法运算; 4、更进一步掌握有关类的操作
三、实验文档: 长整数加法运算 一、需求分析 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+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.h void 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 //主程序
四、实验总结(心得体会) 1、进一步熟悉掌握了双向循环链表的基本操作; 2、熟悉任意长字符串的输入,并实现把字符串转化为整数; 3、熟悉任意长整数的加法运算; 4、更进一步掌握有关类的操作 5、由于对任意长整数运算的算法推敲不足,是程序调试时费时不少 6、本程序有些代码重复出现,从而减少了空间的利用率和增加了程序代码的杂乱性
五、参考文献: 1、《数据结构与算法》 黄定 黄煜廉 刘贤兴 编著 广东科技出版社 2000年1月第1版 2、《〈数据结构与算法〉学习与实验指导》 黄煜廉 编著 2005. 8
|