add.h

本程序中

typedef struct LNode{
	struct LNode *prior;
	struct LNode *next;
	int data;
	int length;                   //用length来标记存放数据的链表的节点总数
}LNode,*LinkList;

using namespace std;

class Add_operation{
public:
	LinkList CreatLink(string add);              //创建双向循环的链表，用来存放加数
	LinkList Insert(LinkList &L,LinkList &p);    //插入操作，用来创建加法结果的链表
	LinkList Add(LinkList L1,LinkList L2);       //实现两个加数的相加运算
	void Print(LinkList L);                      //输出加法操作的结果
	void Destroy(LinkList L);                    //释放链表空间函数
};

LinkList Add_operation::CreatLink(string add)
{
	string s(10,'\0');            //设置一个字符串来存放每四位的数字
	LinkList L=new LNode,p2=NULL;
	L->length=0;            
	int Signal=0,length=strlen(add.c_str());     //Singal作为一个信号，用来标记每段数字的开始
	for(int it=0;it<length;++it)    //通过一个循环函数来将输入的加数分配到每个节点中
	{
		if(it==0)               //先判断加数的符号位
		{
			if(add[it]=='-')
			{
				Signal=it+1;
				L->data=1;       //若为负数，则将头节点的数据域设为1
			}
			else
			{
				Signal=it;
				L->data=0;       //若为正数，则将头节点的数据域设为0
			}
			L->next=L->prior=NULL;
			L->length=1;
		}
		if(add[it]==','||it==length-1)   //遇到，或到字符串结尾时将字符串转化为数字后存入相应的数据域中
		{
			if(add[it]==',')
				for(int i=0;Signal+i<it;++i)
					s[i]=add[Signal+i];
			if(it==length-1)
				for(int i=0;Signal+i<=it;++i)
					s[i]=add[Signal+i];
			LinkList p1=new LNode;
			p1->data=atoi(s.c_str());
			if(L->length==1)         //以下为设置链表节点之间的指向关系
				p2=L;
			else
				p2=p2->next;
			if(it==length-1)
			{
				p1->next=L;
				L->prior=p1;
			}
			else
				p1->next=NULL;
			p2->next=p1;
			p1->prior=p2;
			L->length++;
			Signal=it+1;
		}
	}
	return L;
}

LinkList Add_operation::Insert(LinkList &L,LinkList &p)
{
	p->next=L->next;
	L->next=p;
	p->prior=L;
	if(L->length==1)
		L->prior=p;
	return L;
}

LinkList Add_operation::Add(LinkList L1,LinkList L2)
{
	LinkList p1=L1->prior,p2=L2->prior,L3=L1,L4=L2,L=new LNode,p3=L1,p4=L2;
	L->length=1;
	L->next=L->prior=L;
	if(L1->length<=L2->length)  //始终使p1指向绝对值较大的数,L3,L4分别指向绝对值大的和小的两个链表
	{
		if(L1->length<L2->length)
		{
			p2=L1->prior;
			p1=L2->prior;
			L3=L2;
			L4=L1;
		}
		else        //当两个链表等长时，通过每个节点的数字的大小来判断整个链表中数字的大小
			while((p3=p3->next)->data==(p4=p4->next)->data&&p3->next!=L1);
			if(p3->data<p4->data)
			{
				p2=L1->prior;
		     	p1=L2->prior;
		     	L3=L2;
	     		L4=L1;
			}
	}
	int sum=0,carry=0,borrow=0;
	if(L1->data==L2->data)      //两个加数同号运算
	{
		L->data=L1->data;  //设置符号位
		int p2_data=0;       //由于要求不改变原链表，所以定义一个整型数来存放p2->data的值
	    while(p1!=L3)
		{
			p2_data=p2!=L4?p2->data:0;      //根据p2所指位置的不同来给p2_data赋值
    		sum=p1->data+p2_data+carry;  
			carry=sum/10000>0?1:0;    //判断是否有进位产生
    		if(sum/10000>0)     
    			sum-=10000;
			LinkList p=new LNode;    //创建存放相加结果的链表，并将各数字存入
			p->data=sum;
			L=Insert(L,p);
			L->length++;
    		p1=p1->prior;
            if(p2!=L4)            //当p2循环结束后，p2停止循环操作	
	        	p2=p2->prior;
		}
		if(p1==L3&&p2==L4)     //若两个加数等长，则要考虑最高位的进位情况
			if(carry==1)
			{
				LinkList p=new LNode;
		    	p->data=carry;
		    	L=Insert(L,p);
		    	L->length++;
			}
	}
	else                            //两个加数异号运算
	{		
		L->data=L3->data==1?1:0;    //判断做减法时结果的符号位的情况
		int p2_data=0;
		while(p1!=L3)
		{
			p2_data=p2!=L4?p2->data:0;     //为不破坏链表，用p2_data来存放p2中的数据
			if(p1->data-borrow>=p2_data)   //进行借位处理后判断两个数的大小再进行相应的操作
			{
				sum=p1->data-p2_data-borrow;
				borrow=0;
			}
			else
			{
				sum=10000+p1->data-borrow-p2_data;
				borrow=1;
			}	
			LinkList p=new LNode;    //同加法一样，将结果存入一个重新创建的链表中
			p->data=sum;
			L=Insert(L,p);
			L->length++;
    		p1=p1->prior;
	    	if(p2!=L4)            //当p2循环结束后，p2停止循环操作	
	        	p2=p2->prior;
		}
	}	
	return L;
}

void Add_operation::Print(LinkList L)
{
	LinkList p=L;
	int n=1;
	cout << "\nThe result of the operation is : ";
	while((p=p->next)!=L&&p->data==0);   //判断结果是否为0，若为0则直接输出0后退出
	if(p==L)
	{
		cout << "0" << endl;
		return;
	}
	if(L->data==0)    //判断符号位，并输出相应的符号
		cout << " ";
	else
		cout << "-";
	p=L;
	while((p=p->next)!=L&&p->data==0);    //对结果的非零的最高位进行直接输出
	cout << p->data;
	if(p->next!=L)
		cout << ",";
	p=p->next;
	while(p!=L)    //对结果的后面尾数进行相应的处理，对不满四位的数字进行加零处理
	{		
		int num=p->data;
		for(int i=3;i>=0;--i)
		{
			int chushu=1;
			for(int b=0;b<i;b++)
				chushu*=10;
			cout << num/chushu;
			num%=chushu;
		}		
		if(p->next!=L)
			cout << ",";
		p=p->next;
	}
	cout << endl;
}

void Add_operation::Destroy(LinkList L)
{
	LinkList p1=L->next,p2;
	if(L->next==NULL)   
	{
		cout << "List Null !" << endl;
		exit(0);
	}
	do
	{
		p2=p1->next;
		delete p1;
		p1=p2;
	}while(p1!=L);
}