任意长整数加法运算-课程设计报告

1、一、【实验内容】【问题描述】设计一个实现任意长的整数进行加法运算的演示程序【基本要求】：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(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,0

2、001 ；应输出“ 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、本程序实现计算任意长的整数的加法运算 . 以用户和计算机对话的方式，

3、即在计算机终端上显示“提示信息”之后， 由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。2、本演示程序中，集合的元素限定为数字字符 09 和字符，与；，输入字符可以任意长，输入形式以“回车符”为结束标志，串中字符顺序不限，且允许出现重复字符。3、利用双向循环链表现实长整数的存储，每个结点含一个整形变量。输入的形式以回车结束， 可以直接输入正数或负数。 按中国对于长整数的表示习惯， 每四位一组，除数字和位于首位置的负号外， 其它一切字符都将作为分隔符， 连续多个分隔符当一个处理。但不使用分隔符也不影响结果。4、测试数据(1)0; 0;输出“ 0”;(2)-234

4、5,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".二、概要设计为实现上述程序功 能，应以双向

5、循环链表表示长整数。为此，需要定义一个抽象数据类型。1. 抽象数据类型定义为：ADT OrderedList数据对象： D=ai|aiint,i=1,2,.n, n0数据关系： 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 都已存在。操作

6、结果：判断head0 与 head1 绝对值的大小，并使 head0 的绝对值比 head1 大Display(result)初始条件： result已存在。操作结果：按四位一组，分隔符为"," 的格式，在屏幕上输出result。ADT OrderedList2. 本程序包含三个模块：1) 主程序模块：void main()初始化；do接受命令；处理命令；while(“命令” =”退出”)2) 、集合单元模块实现集合的抽象数据类型3) 、结点结构单元模块定义集合的结点结构各模块之间的调用关系如下：主程序模块集合单元模块结点模块二、详细设计1、ZhengshuAdd.h 文件

7、，链表的定义部分#include<iostream>#include<string>#include<math.h>using namespace std;struct LinkNodeint data;/ 记录每个节点的整数 （小于10000）LinkNode *next;/记录下一个节点的地址LinkNode *pre;/记录前一个节点的地址;class LinkListprivate:LinkNode *head0,*head1;/head0， head1 分别记录两个整数链表的头指针LinkNode *currptr;LinkNode *result

8、;/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()/构造函

9、数，初始化链表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,

10、*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(p

11、3!=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 记录字符串中的字符转化为整

12、数的值， l 使每个节点记录 4 位while(am!='')m+;/m记录字符串中被加数的字符数n=m;while(an!='0') n+;/n记录字符串的总字符数if(a0='-')head0->data=(-1);/ 记录整数符号w=1;else head0->data=1;for(i=m-1;i>=w;i-)if(ai!=',')/ 把字符转化为整数k+=(ai-'0')*sum(l);l+;if(ai=','|i=w)currptr=new LinkNode;/ 把整数存

13、到双向循环链表中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;/ 存储整数符号和节点数/ 与建第一个整数链表一样，建立第二个整数链表 head1 k=0;l=0;if(am+1='-')head1->data=(-1);m+;else

14、head1->data=1;for(i=n-1;i>m;i-)if(ai!=',')k+=(ai-'0')*sum(l);l+;if(ai=','|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->d

15、ata*=j;voidLinkList: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-

16、>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();elsetemp=head0;head0=head1;head1=temp;addtwo();void LinkList:ad

17、dtwo()/ 节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的/ 默认 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; resu

18、lt->data=head0->pre->data;/存结果的节点数和符号while(q!=head1->pre)/head0 存的整数绝对值比head1 大，即 head0 的节点数大于或等于head1currptr=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;currpt

19、r->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，向前一位借 1currptr->data+=10000;s=-1;else if(m1<0&&m2>0)/符号不同，在此相当于实现负整数加上正

20、整数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 节点数比 head

21、1 长时，继续建链 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

22、&&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;currp

23、tr->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;res

24、ult->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->

25、;pre->data)-1)*FuHao;/ 结果记录非 0 节点数cout<<FuHao*p->data;/首先显示符号和第一个节点中的数if(abs(result->pre->data)!=1) p=p->next; / while(p!=result->pre->pre)判断非/继续输出0 节点数是否为1cout<<","/每4 位一组，并用，隔开cout.width(4);cout.fill('0');cout<<p->data;p=p->next;if(p=r

26、esult->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&quo

27、t;/访问文件ZhengshuAdd.hvoid main()/主函数cout<<"|=|n" cout<<"|*|n"cout<<"|*欢迎使用任意长整数加法系统*|n"cout<<"|*刘伟高 *|n"cout<<"|*|n" cout<<"| 在此系统中，可以输入任意长的整数 。|n"string ch;char Yes_No;docout<<"|cout<<&qu

28、ot;|cout<<"|输入形式为： (-)*,*,*;(-)*,*,*,*|n"即符号 +数，每 4 位加一个 ','，两个数之间用请输入你要计算的两个''隔开|n"数 :|n"cin>>ch;/输入任意长字符串LinkListList;/定义链表对象List.Creat(ch);/把字符串转化为整数，并存到链表中List.Add();/ 实现两个整数相加List.Display();/ 输出结果cout<<" 是否继续计算(Y/N):"/询问是否继续计算cin&g

29、t;>Yes_No;while(Yes_No='y'|Yes_No='Y');/Yes_No不等于 'Y'或 'y'时，程序退出cout<<"|=|n" cout<<"|*|n"cout<<"|* 感谢使用本系统 !*|n" cout<<"|*|n"4、函数的调用关系图反映了演示程序的层次结构：MainList.Creat(ch)List.Add()List.Display()四、调试分析1、由于对任意长整数运算的算法推敲不足，是程序调试时费时不少2、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性3、本程序模块划分