link.cpp

用双向链表实现大整数相加

//        程序名：LINK.cpp
//      程序功能：用双链表实现长整数相加
//          作者：骆宏峰
//          日期：2006.11.6
//          版本：1.0     
//
//


//对应主程序文件: main.cpp
//  对应类头文件：LINK.h
//

#include<stdio.h>
#include<iostream.h>
#include<iomanip.h>
#include"LINK.h"
//////////////////////////////////////////////////////////////////////////////

//构造函数

link::link(void)
{
	head=new LinkNode;
	head->right=head->left=NULL;
	
}

//////////////////////////////////////////////////////////////////////////////
//头插入函数
//函数参数：最多四位的整数
//返回值：无
//功能：将相加的结果储存

link::HCreate(int n)
{
	struct LinkNode *p;
	p=new LinkNode;
	p->data=n;
	if(head->right==NULL)//表头节点的right为空则插入建链
	{
		head->right=p;
		head->left=p;
		p->right=head;
		p->left=head;
	}
	else
	{
		head->right->left=p;
		p->right=head->right;
		head->right=p;
		p->left=head;
	}
}

//////////////////////////////////////////////////////////////////////////////
//尾插入函数
//函数参数：最多四位的整数
//函数返回值：无
//函数功能：将两个相加的数储存

link::TCreate(int n)
{
	struct LinkNode *p;
	p=new LinkNode;
	p->data=n;

	if(head->right==NULL)//表头节点的right为空则插入建链
	{
		head->right=p;
		head->left=p;
		p->right=head;
		p->left=head;
	}
	else
	{
		p->left=head->left;
	    head->left->right=p;
	    head->left=p;
	    p->right=head;
	}
}

//////////////////////////////////////////////////////////////////////////////
//长整数输入
//函数参数：无
//函数返回值：无
//功能：将键盘输入的字符输入

void link::GetNo()
{
	char in;
	int p,No;
	p=0;
	No=0;
	while((in=getchar())!=10)                  //输入不为回车做这个循环（10为回车的ASCii码）
	{
		if(in=='-'||in=='+')
		{
			if(in=='-')
				head->data=-1;                  //输入为正数表头节点指想的值为-1否则为0
			else
				head->data=1;
		}
		else if(in>='0'&&in<='9')                
		{
			if(p==4)
			{
				cout<<"error";
				break;
			}
			else
			{
				//if(!head->data)
					//head->data=1;                  //默认符号为“+”
				No=No*10+in-'0';
				p++;
			}	
			
		}
		else if(in==',')
		{
			/*if(!head->data)
			{
				cout<<"error";
				break;
			}*/
			if(p<3&&p!=0&&head->right!=NULL)
			{	
				cout<<"error";
				break;
			}
			else if(p==0&&head->right==NULL)
				{	
				cout<<"error";
				break;
			}
			else 
			{
				p=0;
				TCreate(No);         //调用尾插入函数
				No=0;
			}
		}
		else if(!head->data)
            head->data=1;
	}
	if(p>0)
	{
		TCreate(No);                          //调用尾插入函数
		No=0;
	}
}

//////////////////////////////////////////////////////////////////////////////
//头指针所指向的地址返回函数
//函数参数：无
//函数返回值：头指针指向的地址
//功能：将头指针指向的地址返回 

Link *link::GetHead(void)
{
	struct LinkNode *p;
	p=head;
	return p;
}

//////////////////////////////////////////////////////////////////////////////
//相加函数
//参数：储存两个大整数的链表的头节点
//返回值：无
//功能：将两个大整数相加

void link::add(Link *a,Link *b)
{
	Link *c,*d;
	int result,jw=0;
	
	if(a->data==b->data)                          //同号运算
	{
		c=a->left;
	    d=b->left;
		head->data=a->data;
		while(c!=a&&d!=b)
		{
			result=c->data+d->data+jw;
			if(result>9999)
			{
				result=result-10000;
				jw=1;
			}
			else
				jw=0;
			HCreate(result);                 // 调用头插入函数储存结果
			c=c->left;
			d=d->left;
		}
		if(d!=b)
		{
			c=d;
			a=b;
		}
		while(c!=a)
		{
			result=c->data+jw;
			if(result>9999)
			{
				result=result-10000;
				jw=1;
			}
			else
				jw=0;
			HCreate(result);                            // 调用头插入函数储存结果
			c=c->left;
		}
		if(jw)
			HCreate(jw);                                    // 储存没入链的进位数
	}
	else                           //异号运算
	{
		Link *p;
		switch(compare(a,b))          //调用比较函数，结果的符号同大的一样，且大的数放前面一个链表
		{
		case 1:
			head->data=a->data;
			break;
		case -1:                     //第二个数大，调换位置
			p=a;
			a=b;
			b=p;
			head->data=a->data;
			break;
		case 0:                               //互为相反数
			head->data=1;
			HCreate(0);
		}
		c=a->left;
	    d=b->left;
		while(c!=a&&d!=b)
		{
			
			result=c->data-d->data+jw;
			if(result<0)
			{
				result=result+10000;
				jw=-1;
			}
			else
				jw=0;
			HCreate(result);
			c=c->left;
			d=d->left;
		}
		while(c!=a)
		{
			result=c->data+jw;
            if(result<0)
			{
				result=result+10000;
				jw=-1;
			}
			else
				jw=0;
			HCreate(result);
			c=c->left;
		}
	}
}

//////////////////////////////////////////////////////////////////////////////
//比较函数
//参数：两个大整数的表头节点
//返回值：第一个绝对值大返回1，第二个绝对值大返回-1，一样大返回0
//功能：比较两个整数的绝对值大小
int link::compare(Link *in1,Link *in2)
{
	Link *a,*b;
	a=in1->right;
	b=in2->right;
	while(a!=in1&&b!=in2)
	{
		a=a->right;
		b=b->right;
	}
	if(a==in1&&b!=in2)return -1;
	if(b==in2&&a!=in1)return 1;
    a=in1->right;
	b=in2->right;
	while(a!=in1&&a->data==b->data)
	{
		a=a->right;
		b=b->right;
	}
	if(a==in1)
		return 0;
	else if(a->data>b->data)
		return 1;
	else
		return -1;
}

//////////////////////////////////////////////////////////////////////////////
//输出函数
//参数：无
//返回值：无
//功能：将运算结果打印出来

void link::Print()
{
	struct LinkNode *p;
	p=new LinkNode;
	p=head->right;
	cout<<"The data are:"<<endl;         
	if(head->data==-1)                    //如果是负数先输出负号
		cout<<"-";
	while(p->data==0&&p->right!=head)           //如果前面节点为0则不输出
		p=p->right;
	cout<<p->data;                    //输出第一个不为0的节点
	p=p->right;
	while(p!=NULL&&p!=head)
	{
		cout<<","<<setw(4)<<setfill('0')<<p->data;          //后面的每个输出的数前面输出一个“，”
		p=p->right;
	}
	cout<<endl;
}