1、数据结构长整数四则运算精品实习1 1.4长整数四则运算实习报告题目:设计一个实现任意长的整数进行加法运算的演示程序。一、需求分析1.本演示程序中,利用双向循环链表实现长整数的存储,每个结点含一个整型变量任何整型变量的范围是-(215-1)(215-1)。在每个结点中仅存十进制数的4位,即不超过9999的非负整数,整个链表表示为万进制数。输入和输出形式按中国对于长整数的习惯,每四位一组,组间用逗号隔开。 2.演示程序以用户和计算机的对话方式执行,即在计算机终端上显示“提示信息”之后,由用户在键盘上输入演示程序中规定的运算命令;相应的输入数据(滤去输入数据中的非法字符)和运算结果显示在其后。3.程
2、序执行的命令包括:(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,0
3、000,0000。二、 概要设计struct LinkNode /定义结构体LinkNodeint data; /记录每个节点的整数(小于10000)LinkNode *next; /记录下一个节点的地址LinkNode *pre; /记录前一个节点的地址;class LinkList /定义类LinkListprivate:LinkNode *head0,*head1; /head0,head1分别记录两个整数链表的头指针LinkNode *currptr;LinkNode *result; /result记录结果链表的头指针public:LinkList(); /构造函数,初始化链表Lin
4、kList(); /析构函数,释放空间void Creat(string a); /引入字符串,创立两个链表,分别表示两个整数void Add(); /实现两个整数相加void Display(); /显示结果void addtwo(); /节点多的作为被加数,少的作为加数,实现整 /数绝对值大的加小的;void main() /主函数do while(Yes_No=y|Yes_No=Y); /Yes_No不等于Y或y时,程序退出三、详细设计#include#include#includeusing namespace std;struct LinkNodeint data; /记录每个节点的
5、整数(小于10000)LinkNode *next; /记录下一个节点的地址LinkNode *pre; /记录前一个节点的地址;class LinkListprivate:LinkNode *head0,*head1; /head0,head1分别记录两个整数链表的头指针LinkNode *currptr;LinkNode *result; /result记录结果链表的头指针public:LinkList(); /构造函数,初始化链表LinkList(); /析构函数,释放空间void Creat(string a); /引入字符串,创立两个链表,分别表示两个整数void Add(); /实
6、现两个整数相加void Display(); /显示结果void addtwo(); /节点多的作为被加数,少的作为加数,实现整 /数绝对值大的加小的;/链表的实现部分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-nex
7、t=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; cu
8、rrptr=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
9、记录字符串中的字符转化为整数的值,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; /把整数存到双向循环链表中 currptr-data=k; currptr-next=head0; currp
10、tr-pre=head0-pre; head0-pre-next=currptr; head0-pre=currptr; head0=currptr; s+; /节点数加1 k=0; /重新初始化k和l l=0; head0-pre-data*=s; /存储整数符号和节点数/与建第一个整数链表一样,建立第二个整数链表head1k=0;l=0;if(am+1=-) head1-data=(-1); m+;else head1-data=1;for(i=n-1;im;i-) if(ai!=,) k+=(ai-0)*sum(l); l+; if(ai=,|i=m+1) currptr=new Lin
11、kNode; 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)pre-d
12、ata) 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(k1k2) addtwo(); else temp=head0; head0=head
13、1; 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-d
14、ata; /存结果的节点数和符号 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)-10
15、000data=abs(currptr-data); else if(m10&m2datadata+=10000; s=-1; else if(m10) /符号不同,在此相当于实现负整数加上正整数 s=0; if(currptr-data0) /大于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; r
16、esult=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(m10
17、&m2datadata+=10000; s=-1; else if(m10) s=0; if(currptr-data0) 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) /处
18、理相加后,进位问题 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);/结
19、果的符号while(p-data=0&p!=result-pre-pre) /当运算后前几个节点的数据为0时,不输出 p=p-next; result-pre-data=(abs(result-pre-data)-1)*FuHao; /结果记录非0节点数coutdata; /首先显示符号和第一个节点中的数if(abs(result-pre-data)!=1) p=p-next; /判断非0节点数是否为1while(p!=result-pre-pre) /继续输出 cout,; /每4位一组,并用,隔开 cout.width(4); cout.fill(0); coutdata; p=p-nex
20、t;if(p=result-pre-pre&abs(result-pre-data)!=1) /显示最后一个节点数据 cout,; cout.width(4); cout.fill(0); coutdata;coutendl;int sum(int n) /计算10的乘方int i,s=1;for(i=1;i=n;i+) s=s*10;return s;/主函数和其他函数的实现void main() /主函数cout*n;cout*欢迎使用任意长整数加法系统*n;cout*n;coutn;cout在此系统中,可以输入任意长的整数 。 |n;string ch;char Yes_No;do co
21、utn; cout|输入形式为:(-)*,*,*;(-)*,*,*,*|n; cout即符号+数,每4位加一个,,两个数之间用;隔开 |n; coutch; /输入任意长字符串 LinkList List; /定义链表对象 List.Creat(ch); /把字符串转化为整数,并存到链表中 List.Add(); /实现两个整数相加 List.Display(); /输出结果 coutYes_No;while(Yes_No=y|Yes_No=Y); /Yes_No不等于Y或y时,程序退出cout*n;cout *感谢使用本系统!*n;cout *n;四 调试分析在设计初期采用C语言设计,在编译
22、上出现了好多问题,导致了代码利用率不高并且结构松散,进而采用C+的思想,利用类之后,不仅代码量减少,效率也提高了不少。在编译的时候,程序不能很好地检测出输入形式,如果输入格式不正确,就不能很好地计算出正确结果,对于这一问题,没找到很好地解决办法。总体来说,这个程序相对简单,但在指针的利用方面,编程的时候出现了一些问题。经过仔细检查与多次修改,成功的解决了指针问题。五、用户手册1、本程序的运行环境为DOS操作系统,执行文件为长整数四则运算.exe。2、进入演示程序后即显示文本方式的用户界面:3、按照上面要求输入要计算的两个数即可。输入完成后按回车键,将输出计算结果。继续计算请按Y或y,否则请按N或n。六、测试结果七、附录该程序在同一个文件,即只在.cpp文件里的以实现。【感谢您的阅览,下载后可自由编辑和修改,关注我 每天更新】