《数据结构长整数四则运算[共13页]》由会员分享，可在线阅读，更多相关《数据结构长整数四则运算[共13页]（13页珍藏版）》请在金锄头文库上搜索。
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,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,
3、0000,9999,9999 ；1；应输出 1,0001,0000,0000 。二、 概要设计struct LinkNode /定义结构体 LinkNodeint data;/记录每个节点的整数（小于10000）LinkNode *next;LinkNode *pre;/记录下一个节点的地址记录前一个节点的地址class LinkList /定义类 LinkList private:LinkNode *head0,*head1;LinkNode *currptr;/head0,head1 分别记录两个整数链表的头指针LinkNode *result;public:/result记录结果链表的头
4、指针LinkList();/构造函数,初始化链表析构函数,释放空间LinkList();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 Li
5、nkNodeint data;/记录每个节点的整数（小于记录下一个节点的地址记录前一个节点的地址10000）LinkNode *next;LinkNode *pre;/ ;class LinkListprivate:LinkNode *head0,*head1;LinkNode *currptr;/head0,head1 分别记录两个整数链表的头指针LinkNode *result;public:/result记录结果链表的头指针LinkList();/构造函数,初始化链表析构函数,释放空间LinkList();void Creat(string a); /引入字符串,创立两个链表,分别表示两
6、个整数实现两个整数相加void Add();/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;/初始化链表,建立双向循环链表
7、 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;c
8、urrptr=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 标记字符串中的 - 号
9、/k 记录字符串中的字符转化为整数的值,l 使每个节点记录 4 位while(am!=;) m+;n=m;/m记录字符串中被加数的字符数while(an!=0) n+;/n记录字符串的总字符数if(a0=-)head0-data=(-1);/记录整数符号w=1;elsehead0-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;currptr-pre=head
10、0-pre;head0-pre-next=currptr;head0-pre=currptr;head0=currptr;s+;k=0;l=0;/节点数加 1重新初始化 k 和 lhead0-pre-data*=s;/存储整数符号和节点数/ 与建第一个整数链表一样,建立第二个整数链表head1k=0;l=0;if(am+1=-)head1-data=(-1);m+;elsehead1-data=1;for(i=n-1;im;i-) if(ai!=,)k+=(ai-0)*sum(l);l+;if(ai=,|i=m+1)currptr=new LinkNode;currptr-data=k;cur
11、rptr-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-data) temp=head0;head0=head1;head1=te
12、mp;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();elsetemp=head0;head0=head1;head1=temp;addtwo(); void LinkList:addtwo()/ 节点多
13、的作为被加数,少的作为加数,实现整数绝对值大的加小的/ 默认 head0 存的整数绝对值比 head1 大int s=0,m1=head0-data,m2=head1-data;m1=(head0-pre-data/abs(head0-pre-data);m2=(head1-pre-data/abs(head1-pre-data);LinkNode *p=head0-pre-pre,*q=head1-pre-pre;/head0/head1的符号的符号result-data=head0-pre-data;while(q!=head1-pre)/存结果的节点数和符号/head0 存的整数绝对值比 head1 大,即 head0 的节点数大于或等于 head1
