数据结构长整数四则运算

6581次浏览 |355点赞 | 35评论 | 2021-01-11 09:53 更新

来源：互联网

最佳文档

本文由作者推荐

五香卤猪蹄-大学生自我总结范文

2021年1月11日发(作者：计擅)

实习1 1.4长整数四则运算
实习报告
题目：
设计一个实现任意长的整数进行加法运算的演示程序。

一、需求分析
1.本演示程序中，利用双向循环链表实现长整数的存储，每个结点含一个整型变量任何整型
变量的范围是-（215-1）—（215-1）。在每个结点中仅存十进制数的4位，即不超过999 9
的非负整数，整个链表表示为万进制数。输入和输出形式按中国对于长整数的习惯，每四位
一组，组间用逗号隔开。
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,0000,9999,9999；1；应输出1,0001,0000,0000。
二、概要设计
struct LinkNode 定义结构体LinkNode
{
int data; 记录每个节点的整数（小于10000）
LinkNode *next; 记录下一个节点的地址
LinkNode *pre; 记录前一个节点的地址
};
class LinkList 定义类LinkList
1 16

{
private:
LinkNode *head0,*head1; head0，head1分别记录两个整数链表的头指针
LinkNode *currptr;
LinkNode *result; result记录结果链表的头指针
public:
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
#include
using namespace std;
struct LinkNode
{
int data; 记录每个节点的整数（小于10000）
LinkNode *next; 记录下一个节点的地址
LinkNode *pre; 记录前一个节点的地址
2 16

};
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(); 节点多的作为被加数，少的作为加数，实现整数绝对值
大的加小的
};

链表的实现部分

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;
3 16

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;
4 16

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
{

}
for(i=m-1;i>=w;i--)
{
if(a[i]!=',') 把字符转化为整数
5 16
head0->data=1;

{
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--)
6 16

{
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(head 0->pre->data)>abs(head1->pre->data))
两个整数中，绝对值大的为被加数
addtwo();
else if(abs(head0->pre->data)pre->data))
7 16

{
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();
}
}
}
8 16

void LinkList::addtwo()
节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的
默认head0存的整数绝对值比head1大
{
int s=0,m1=head0->data,m2=head1->data;
m1=(head0->pre->dataabs(head0->pre->data)); head0的符号
m2=(head1->pre->dataabs(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->data10000;
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)
符号不同，在此相当于实现两个正整数相减
{
9 16

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长时，继续建链
10 16

while(p!=head0->pre)
{
currptr=new LinkNode;
currptr->data=p->data*m1+s;
s=currptr->data10000;
if((m1*m2)>0)
{
if(abs(currptr->data)-10000>=0)
{
s=currptr->data10000;
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;
11 16

}
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=r esult->pre->dataabs(result->pre->data);结果的符号
while(p->data==0&&p!=result->pre->pre)
12 16

当运算后前几个节点的数据为0时，不输出
{
p=p->next;
result->pre->data=(abs( result->pre->data)-1)*FuHao;
结果记录非0节点数
}
cout<data; 首先显示符号和第一个节点中的数
if(abs(result->pre->data)!=1) p=p->next; 判断非0节点数是否为1
while(p!=result->pre->pre) 继续输出
{
cout<<每4位一组，并用‘，’隔开
(4);
('0');
cout<data;
p=p->next;
}
if(p==result->pre->pre&&abs(result->pre->data)!=1)
显示最后一个节点数据
{
cout<<
(4);
('0');
cout<data;
}
cout<}
int sum(int n) 计算10的乘方
{
int i,s=1;
for(i=1;i<=n;i++)
13 16

{
s=s*10;
}
return s;
}

主函数和其他函数的实现

void main() 主函数
{
cout<<
cout<<欢迎使用任意长整数加法系统***********n
cout <<

cout<<
cout<<在此系统中，可以输入任意长的整数。 |n
string ch;
char Yes_No;

do{
cout<<
cout<<输入形式为：(-)**,****,****;(-)*,*** *,****,****|n
cout<<即符号+数，每4位加一个','，两个数之间用';'隔开 |n
cout<<请输入你要计算的两个数: |n
cin>>ch; 输入任意长字符串
LinkList List; 定义链表对象
(ch); 把字符串转化为整数，并存到链表中
(); 实现两个整数相加
y(); 输出结果
cout<<是否继续计算(YN):询问是否继续计算
cin>>Yes_No;
14 16

}while(Yes_No=='y'||Yes_No=='Y'); Yes_No不等于'Y'或'y'时，程序退出
cout<<
cout<< ****** ***********感谢使用本系统!***************n
cout<< **** *******************************************n
;
}
四调试分析
在设计初期采用C语言设计，在编译上出现了好多问题，导致了代码利用率不高并且结
构松散，进而采用C++的思想，利用类之后，不仅代码量减少，效率也提高了不少。在编译
的时候，程序不能很好地检测出输入形式，如果输入格式不正确，就不能很好地计算出正确< br>结果，对于这一问题，没找到很好地解决办法。
总体来说，这个程序相对简单，但在指针的利用方面，编程的时候出现了一些问题。经
过仔细检查与多次修改，成功的解决了指针问题。

五、用户手册

1、本程序的运行环境为DOS操作系统，执行文件为长整数四则运算.exe。
2、进入演示程序后即显示文本方式的用户界面：

3、按照上面要求输入要计算的两个数即可。输入完成后按回车键，将输出计算结果。继续
计算请按Y或y，否则请按N或n。
15 16