一、【实验内容】
【问题描述】
设计一个实现任意长的整数进行加法运算的演示程序
【基本要求】：利用双向循环链表实现长整数的存储，每个结点含一个整形变量。任何整形变量的范围是 -(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、本程序实现计算任意长的整数的加法运算. 以用户和计算机对话的方式，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，然后程序就计算并显示出这两个数的运算。
2、本演示程序中，集合的元素限定为数字字符[‘0’~’9’]和字符‘，’与‘；’，输入字符可以任意长，输入形式以“回车符”为结束标志，串中字符顺序不限，且允许出现重复字符。
3、利用双向循环链表现实长整数的存储，每个结点含一个整形变量。输入的形式以回车结束，可以直接输入正数或负数。按中国对于长整数的表示习惯，每四位一组，除数字和位于首位置的负号外，其它一切字符都将作为分隔符，连续多个分隔符当一个处理。但不使用分隔符也不影响结果。
4、测试数据
(1)0; 0; 输出“0”;
(2)-2345,6789; -7654,3211; 输出 “-1,000,000”;
(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. 抽象数据类型定义为：
ADT OrderedList{
数据对象：D={ai|ai∈int,i=1,2,...n, n≥0}
数据关系：R1={|ai-1,ai∈D|=2,……n }
基本操作：
Creat(string a)
操作结果：通过字符串a构造两个位数不限的长整数。
addtwo(head0,head1，result)
初始条件：head0,head1都已存在,且head0的绝对值比head1大
操作结果：result等于head0和head1的和。
Add(head0,head1)
初始条件：head0,head1都已存在。
操作结果：判断head0与head1绝对值的大小，
并使head0的绝对值比head1大
Display(result)
初始条件：result已存在。
操作结果：按四位一组，分隔符为","的格式，在屏幕上输出result。
}ADT OrderedList
2.本程序包含三个模块：
1)主程序模块：
void main(){
初始化；
do{
接受命令；
处理命令；
}while(“命令”=”退出”)
}
2)、集合单元模块——实现集合的抽象数据类型
3)、结点结构单元模块——定义集合的结点结构
各模块之间的调用关系如下：
主程序模块
集合单元模块
结点模块
二、详细设计
1、ZhengshuAdd.h文件，链表的定义部分
#include<iostream>
#include<string>
#include<math.h>
using namespace std;
struct LinkNode
{
int data; //记录每个节点的整数（小于10000）
LinkNode *next; //记录下一个节点的地址
LinkNode *pre; //记录前一个节点的地址
};
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();
//节点多的作为被加数，少的作为加数，实现整数绝对值大的加小的
};
2、ZhengshuAdd.cpp文件，链表的实现部分
#include"ZhengshuAdd.h"
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->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;
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 {head0->data=1;}
for(i=m-1;i>=w;i--)
{
if(a[i]!=',') //把字符转化为整数
{
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--)
{
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(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;
//如果节点数相同，则判断节点中数值大小
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();
}
}
}
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->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->data/10000;
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)
//符号不同，在此相当于实现两个正整数相减
{
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长时，继续建链
while(p!=head0->pre)
{
currptr=new LinkNode;
currptr->data=p->data+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->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;
}
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=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;
//结果记录非0节点数
}
cout<<FuHao*p->data; //首先显示符号和第一个节点中的数
if(abs(result->pre->data)!=1) p=p->next; //判断非0节点数是否为1
while(p!=result->pre->pre) //继续输出
{
cout<<","; //每4位一组，并用‘，’隔开
cout.width(4);
cout.fill('0');
cout<<p->data;
p=p->next;
}
if(p==result->pre->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;
}
3、main.cpp文件，主函数和其他函数的实现
#include"ZhengshuAdd.h" //访问文件ZhengshuAdd.h
void main() //主函数
{
cout<<"|===============================================|/n";
cout<<"|***********************************************|/n";
cout<<"|**********欢迎使用任意长整数加法系统***********|/n";
cout<<"|**********************刘伟高*******************|/n";
cout<<"|***********************************************|/n";
cout<<"|在此系统中，可以输入任意长的整数 。 |/n";
string ch;
char Yes_No;
do{
cout<<"|输入形式为：(-)**,****,****;(-)*,****,****,****|/n";
cout<<"|即符号+数，每4位加一个','，两个数之间用';'隔开 |/n";
cout<<"|请输入你要计算的两个数: |/n";
cin>>ch; //输入任意长字符串
LinkList List; //定义链表对象
List.Creat(ch); //把字符串转化为整数，并存到链表中
List.Add(); //实现两个整数相加
List.Display(); //输出结果
cout<<"是否继续计算(Y/N):"; //询问是否继续计算
cin>>Yes_No;
}while(Yes_No=='y'||Yes_No=='Y'); //Yes_No不等于'Y'或'y'时，程序退出
cout<<"|===============================================|/n";
cout<<"|***********************************************|/n";
cout<<"|*****************感谢使用本系统!***************|/n";
cout<<"|***********************************************|/n";
}
4、函数的调用关系图反映了演示程序的层次结构：
Main
List.Creat(ch) List.Add() List.Display()
四、调试分析
1、由于对任意长整数运算的算法推敲不足，是程序调试时费时不少
2、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性
3、本程序模块划分比较合理，且把指针全部封装在链表模块中，操作方便。
4、算法的时空分析
由于链表采用双向循环链表结构，可以从链表两头操作，各种操作的算法时间复杂度比较合理，各函数以及确定链表中的结点位置都是O（n）,n为链表长度。
5、本实验采用数据抽象的程序设计方法，将程序分为3个模块，使得设计时思路清晰，实现时调试顺利，各模块具有较好的可重用性，确实得到了一次良好的程序设计训练。
五、用户手册
1、本程序的运行环境为DOS操作系统
2、进入演示程序后即显示文本方式的用户界面
3、进入界面后，就会提示输入字符串的输入形式，结束符为“回车符”。
4、接受其他命令后继执行相应运算和现实相应结果
六、测试结果
键入0；0 输出0
键入y -2345；6789；-7654，3211 输出-1，0000，0000
键入y -9999，9999；1，0000，0000，0000 输出9999，0000，0001
键入y 1，0001，0001；-1，0001，0000 输出1
键入y -9999，9999，9999；-9999，9999，9999 输出-1，9999，9999，9998
键入y 1，0000，9999，9999；1 输出1，0001，0000，0000
键入n (退出)
七、附录
源程序文件名清单：
ZhengshuAdd.h //元素结点定义单元
ZhengshuAdd.cpp //链表实现单元
Main.cpp //主程序
四、实验总结（心得体会）
１、进一步熟悉掌握了双向循环链表的基本操作；
２、熟悉任意长字符串的输入，并实现把字符串转化为整数；
３、熟悉任意长整数的加法运算；
４、更进一步掌握有关类的操作
5、由于对任意长整数运算的算法推敲不足，是程序调试时费时不少
6、本程序有些代码重复出现，从而减少了空间的利用率和增加了程序代码的杂乱性
五、参考文献：
1、《数据结构与算法》 黄定 黄煜廉 刘贤兴 编著
广东科技出版社 2000年1月第1版
2、《〈数据结构与算法〉学习与实验指导》 黄煜廉 编著 2005. 8