数据结构长整数四则运算

1、实习 1 1.4 长整数四那么运算 实习报告 题目： 设计一个实现任意长的整数进行加法运算的演示程序。一、 需求分析1. 本演示程序中， 利用双向循环链表实现长整数的存储， 每个结点含一个整型变量任何整型 变量的范围是 - 215-1 215-1 。在每个结点中仅存十进制数的 4位，即不超过 9999 的非负整数， 整个链表表示为万进制数。 输入和输出形式按中国对于长整数的习惯， 每四位 一组，组间用逗号隔开。2. 演示程序以用户和计算机的对话方式执行，即在计算机终端上显示“提示信息之后， 由用户在键盘上输入演示程序中规定的运算命令； 相应的输入数据 滤去输入数据中的非法 字符和运算结果显示在

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,00014) 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,99987)1,0000,9999

3、,9999； 1；应输出 1,0001,0000,0000概要设计struct LinkNode /定义结构体 LinkNodeint data; /LinkNode *next;/LinkNode *pre;/记录每个节点的整数小于 10000记录下一个节点的地址记录前一个节点的地址;class LinkList /定义类 LinkListprivate:LinkNode *head0,*head1; /head0， head1 分别记录两个整数链表的头指针public:LinkList();/LinkList();/void Creat(string a); / void Add();/L

4、inkNode *currptr;记录结果链表的头指针LinkNode *result; /result构造函数，初始化链表析构函数，释放空间 引入字符串，创立两个链表，分别表示两个整数 实现两个整数相加void Display(); /显示结果void addtwo(); /节点多的作为被加数，少的作为加数，实现整 / 数绝对值大的加小的;void main() / 主函数do while(Yes_No='y'|Yes_No='Y'); /Yes_No不等于 'Y' 或 'y' 时，程序退出三、详细设计 #include<

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

6、表的头指针public:LinkList();/LinkList();/void Creat(string a); / void Add();/void Display();/void addtwo();/构造函数，初始化链表析构函数，释放空间 引入字符串，创立两个链表，分别表示两个整数实现两个整数相加显示结果 节点多的作为被加数，少的作为加数，实现整 / 大的加小的数绝对值;/ 链表的实现局部int sum(int n);LinkList:LinkList() /构造函数，初始化链表head0=new LinkNode;/ 申请一个空间记录整数的符号和节点数head1=new LinkNod

7、e;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-&

8、gt;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->

9、;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 记录加数节点数；/w 标记字符串中的 - '号/k 记录字符串中的字符转化为整数的值， while(am!='') m+;/mn=m;while(an!='0') n+;/nif(a0='-')hea

10、d0->data=(-1); /w=1;elsehead0->data=1;for(i=m-1;i>=w;i-)引入字符串，创立两/ 个链表，分别表示两个整数s 记录被加数节点数l 使每个节点记录 4 位记录字符串中被加数的字符数记录字符串的总字符数记录整数符号if(ai!=',')/把字符转化为整数k+=(ai-'0')*sum(l);l+;if(ai=','|i=w)currptr=new LinkNode;/currptr->data=k;currptr->next=head0;currptr->pre=

11、head0->pre;head0->pre->next=currptr;head0->pre=currptr;head0=currptr;s+;/k=0;/l=0;head0->pre->data*=s; /把整数存到双向循环链表中节点数加 1 重新初始化 k 和 l存储整数符号和节点数/ 与建第一个整数链表一样，建立第二个整数链表 head1 k=0;l=0;if(am+1='-')head1->data=(-1);m+;else head1->data=1;for(i=n-1;i>m;i-)if(ai!=',&#

12、39;)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->data*=j;实现两个整数相加void LinkList:Add() /LinkNode *temp;i

13、f(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;/ 如果

14、节点数相同，那么判断节点中数值大小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:addtwo()/ 节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的/ 默认 head0 存

15、的整数绝对值比 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; / 存结果的节点数和符号 w

16、hile(q!=head1->pre)/head0 存的整数绝对值比 head1 大，即 head0 的节点数大于或等于 head1/ 两整数相加如果符号相同相加后超过 10000，那么进位，不进位currptr=new LinkNode;currptr->data=(p->data)*m1+(q->data)*m2+s;if(m1*m2)>0) /if(abs(currptr->data)-10000>=0) /s=currptr->data/10000;currptr->data=abs(currptr->data)%10000;

17、else /abs(currptr->data)-10000<0s=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)/ 符号不同，在此相当于实现负整数加上正整数s=0;if(currptr->data>0) /大于 0 ，

18、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)curr

19、ptr=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->dat

20、a<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

21、->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(resu

22、lt->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;/ 结果记录

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

24、t;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;/ 主函数和其他函数的实现void main() /主函数cout<<"*cout<<"*

25、欢送使用任意长整数加法系统 *n"cout<<"*cout<<"n"cout<<" 在此系统中，可以输入任意长的整数 。 |n" string ch;char Yes_No;docout<<"n"cout<<"|输入形式为：/ * * *(-)*,*,*/ * * * *(-)*,*,*,*|n"cout<<" 即符号 +数，每 4 位加一个 ',' ，两个数之间用 '' 隔开 |n

26、" cout<<" 请输入你要计算的两个数 : |n"cin>>ch;/输入任意长字符串LinkList List;/定义链表对象List.Creat(ch);/把字符串转化为整数，并存到链表中List.Add();/实现两个整数相加List.Display();/输出结果cout<<" 是否继续计算 (Y/N):"/询问是否继续计算cin>>Yes_No;不等于'Y'或'y'时，程序退出while(Yes_No='y'|Yes_No='Y&

27、#39;); Yes_Nocout<<"*ncout<<*感谢使用本系统!*n"cout<<*n"四调试分析在设计初期采用 C语言设计，在编译上出现了好多问题，导致了代码利用率不高并且结 构松散，进而采用 C+勺思想，利用类之后，不仅代码量减少，效率也提高了不少。在编译 的时候，程序不能很好地检测出输入形式，如果输入格式不正确，就不能很好地计算出正确结果，对于这一问题，没找到很好地解决方法。总体来说，这个程序相对简单，但在指针的利用方面，编程的时候出现了一些问题。经过仔细检查与屡次修改，成功的解决了指针问题。五、用户手册1、本程序的运行环境为 DOS操作系统，执行文件为长整数四那么运算.exe。2、进入演示程序后即显示文本方式的用户界面:石'E:6Oe四那么运算.exh*欢送使用任意股整数加法系纟充*；在此系统中，可以输入任意长的整数.!输 A.形式询* *#*：<'>» *» *» «-*弊号摇 疑唯加一个，宀 两