长整数四则运算实验报告.doc

数据结构
课内实验报告书

一、实验题目：长整数四则运算
二、实验目的：
通过本次实验，熟练掌握链表的存储结构及其各种基本运算，体会链表操作的特点。
三、实验要求：
设计一个实现任意长的整数进行加法运算的演示程序。
要求：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是-(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,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”。
五、设计与实现过程
（1）存储结构的定义

typedefstructint72{

inti[4];

}INT72;

INT72a,b,c;

typedefstructLinkNode
{
intdata;//记录每个节点的整数（小于10000）
LinkNode*next,*pre;//记录下一个节点的地址*pre;//记录前一个节点的地址
}linklist;

（2）主要算法的描述

voidaddtwo()
//节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的
//默认head0存的整数绝对值比head1大
{
ints=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的符号
linklist*p=head0->pre->pre,*q=head1->pre->pre;
result->data=head0->pre->data;//存结果的节点数和符号
while(q!=head1->pre)
//head0存的整数绝对值比head1大，即head0的节点数大于或等于head1
{
currptr=(linklist*)malloc(sizeof(linklist));
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)-10000<0，不进位
{
s=0;
currptr->data=abs(currptr->data);
}
}
elseif(m1>0&&m2<0)
//符号不同，在此相当于实现两个正整数相减
{
s=0;
if(currptr->data<0)//小于0，向前一位借1
{
currptr->data+=10000;
s=-1;
}
}
elseif(m1<0&&m2>0)
//符号不同，在此相当于实现负整数加上正整数
{
s=0;
if(currptr->data>0)//大于0，
{
currptr->data=10000-currptr->data;
s=1;
}
elsecurrptr->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)
{
currptr=(linklist*)malloc(sizeof(linklist));
currptr->data=p->data+s;
s=currptr->data/10000;
if((m1*m2)>0)
{
if(abs(currptr->data)-1000