longint.cpp

任意长整数相加问题 任意输入两个任意长的整数进行相加 可以得出正确结果

#include"malloc.h"
#include"stdio.h"

#define OK		1
#define ERROR	0
#define len		10

typedef struct DLNode
{
	char data;
	struct DLNode *prior;
	struct DLNode *next;
}DLNode,*DLinkList;						//结点类型


void CreateList(DLinkList &T)//构造空的双向循环链表
{
	T=(DLinkList)malloc(sizeof(DLNode));
	if(!T)return;
	T->data='+';
	T->next=T;
	T->prior=T;
}

void DataIn(DLinkList &T)	//根据输入来构造链表
{
	char temp;			
	DLinkList p,s;			//s为新的结点，p为T中的移动指针
	p=T;
	scanf("%c",&temp);
	if(temp=='-')
	{
		T->data=temp;
		scanf("%c",&temp);	//如输入为负号，将负号存到T的头指针里面，并接受下一个字符
	}
	while(temp!=10)			//接收屏幕上的所有字符
	{
		s=(DLinkList)malloc(sizeof(DLNode));
		if(!s)return;		//分配空间不成功则退出程序
		s->data=temp;
		s->prior=p;
		p->next=s;
		T->prior=s;
		s->next=T;
		p=s;
		scanf("%c",&temp);
	}
}

int Judge(DLinkList T)		//判断输入的数据是否合法
{
	int num=0;				//记录当前逗号的位置
	int flag=0;				//记录上次逗号的位置，num-flag用来判断逗号输入是否正确（逗号之间要有4个数字）
	DLinkList p;
	p=T;
	if(p->next==p)			//链表为空
	{
		return ERROR;
	}
	else 
	{
		p=p->next;			//第一个数
		while(p!=T)									//除了正负号外，只能输入逗号和数字
		{
			num++;
			if(p->data==',')						//判断逗号输入是否正确					  
			{
				if(num==1)return ERROR;
				else if(flag==0)					//第一个逗号之前的数可以不是4个，但逗号之间的数必须为4个
				{
					if((num-flag-1)>4)return ERROR;	//输入有错误
				}
				else 
				{
					if((num-flag-1)!=4)return ERROR;//输入有错误
				}
				flag=num;
			}
			else if(p->data <'0'||p->data>'9')		//判断数字输入是否正确
			{
				return ERROR;
			}
			p=p->next;
		}
		if(flag==0)
		{if(num>4)return ERROR;}
		else if(num-flag!=4)return ERROR;
		return OK;
	}
}

void FreeList(DLinkList T)							//释放错误输入的链表空间	
{
	DLinkList p,q;
	p=T->next;
	while(p!=T)
	{
		q=p->next;
		p->prior->next=p->next;
		p->next->prior=p->prior;
		free(p);
		p=q;
	}
	free(T);
}

int Compare(DLinkList first,DLinkList second)		//比较两个整数的大小，first>=second则返回OK，
{
	int i=0,j=0,flag=0;
	DLNode *p,*q;
	p=first->next;
	while(p!=first){i++;p=p->next;}
	q=second->next;
	while(q!=second){j++;q=q->next;}
	if(i>j)return OK;						//判断两个整数的长度first长则返回OK
	else if(i==j)							//若长度相等，则从高位开始判断两个数值的大小
	{
		p=first->next;
		q=second->next;
		while(p!=first&&q!=second&&flag==0)
		{
			if(p->data==','){p=p->next;q=q->next;}
			else 
			{
				if(p->data<q->data){flag=1;return ERROR;}
				p=p->next;q=q->next;
			}
		}
		return OK;
	}
	else return ERROR;
}


void AddTwoList(DLinkList &first,DLinkList &second,DLinkList &third)				//两个整数相加
{
	int carry=0,flag=0;
	DLinkList s,p,q;
	DLinkList pfirst,psecond,pthird;
	pfirst=first->prior;
	psecond=second->prior;
	pthird=third;
	//-----------------------------------------------------------------------------------------------------------
	//-----------------------------------------------------------------------------------------------------------
	if((first->data=='+'&&second->data=='+')||(first->data=='-'&&second->data=='-'))//两个数都为正或者都为负 
	{
		third->data=first->data;

		while(pfirst!=first&&psecond!=second)
		{
			flag++;
			s=(DLinkList)malloc(sizeof(DLNode));
			if(pfirst->data==',')									//如果为逗号，取下一个数
			{flag=0;s->data=pfirst->data;}
			else 
				{	
					s->data=carry+pfirst->data+psecond->data-2*'0';	//二者之和存入到s->data中
					carry=0;
					if(s->data>=len)					//若和大于10，则减去10，并设进位carry为1
					{
						s->data=s->data-len;
						carry=1;
					}
				}
				third->next=s;							//把相加的结果放入third链表
				s->prior=third;
				pthird->prior=s;
				s->next=pthird;
				pthird=s;
				pfirst=pfirst->prior;
				psecond=psecond->prior;
		}
		while(pfirst!=first)//若first链表比较长，把剩下的数值也存入third链表----------------------------------------------
		{
			flag++;
			s=(DLinkList)malloc(sizeof(DLNode));
			if(pfirst->data==',')						//如果为逗号，取下一个数
			{
				flag=0;s->data=pfirst->data;
			}
			else 
				{	
					s->data=carry+pfirst->data-'0';		//二者之和存入到s->data中
					carry=0;
					if(s->data>=len)					//若和大于10，则减去10，并设进位carry为1
					{
						s->data=s->data-len;
						carry=1;
					}
				}
				third->next=s;							//把相加的结果放入third链表
				s->prior=third;
				pthird->prior=s;
				s->next=pthird;
				pthird=s;
				pfirst=pfirst->prior;
		}
		if(carry==1)
		{
			if(flag==4)
			{	
				s=(DLinkList)malloc(sizeof(DLNode));	//有进位，若超过4位需要新添加一个逗号
				s->data=',';
				third->next=s;
				s->prior=third;
				pthird->prior=s;
				s->next=pthird;
				pthird=s;
			}
			s=(DLinkList)malloc(sizeof(DLNode));		//有进位，开辟新空间存放
			s->data=carry;
			third->next=s;
			s->prior=third;
			pthird->prior=s;
			s->next=pthird;
			pthird=s;
		}
	}
	//---------------------------------------------------------------------------------------------------------------
	//---------------------------------------------------------------------------------------------------------------
	else												//first和second的数值一个为正一个为负 
	{
		third->data=first->data ;
		while(pfirst!=first&&psecond!=second)
		{
			s=(DLinkList)malloc(sizeof(DLNode));
			if(pfirst->data==',')						//如果为逗号，取下一个数
			{s->data=pfirst->data;}
			else 
				{	
					s->data=carry+pfirst->data-psecond->data;//二者之和存入到s->data中
					carry=0;
					if(s->data<0)						//若和小于0，则加上10，并设进位carry为-1
					{
						s->data=s->data+len;
						carry=-1;
					}
				}
				third->next=s;
				s->prior=third;
				pthird->prior=s;
				s->next=pthird;
				pthird=s;
				pfirst=pfirst->prior;
				psecond=psecond->prior;
		}
		while(pfirst!=first)//first链表比较长-------------------------------------------------------------------
		{
			s=(DLinkList)malloc(sizeof(DLNode));
			if(pfirst->data==',')						 //如果为逗号，取下一个数
			{s->data=pfirst->data;}
			else 
				{	
					s->data=carry+pfirst->data-'0';		//二者之和存入到s->data中
					carry=0;
					if(s->data<0)						//若和小于0，则加上10，并设进位carry为-1
					{
						s->data=s->data+len;
						carry=-1;
					}
				}
				third->next=s;
				s->prior=third;
				pthird->prior=s;
				s->next=pthird;
				pthird=s;
				pfirst=pfirst->prior;
		}
		p=third->next;
		q=third;
		while(p->next!=third&&p->data==0)				//相减之后消去前面的零
		{
			q->next=p->next;p->next->prior=q;free(p);p=q->next;
			if(p->data==',')
			{q->next=p->next;p->next->prior=q;free(p);p=q->next;}
		}
		if((p->next==third)&&p->data==0){third->data=' ';}
	}
}
//----------------------------------------------------------------------------------------------------------------------
//----------------------------------------------------------------------------------------------------------------------
void DataOut(DLinkList T)								//输出相加的数值
{
	DLinkList p;
	printf("\n相加结果为：");
	if(T->data=='+')T->data=' ';
	printf("%c",T->data);
	p=T->next;
	while(p!=T)
	{
		if(p->data!=',')p->data=p->data+'0';			//将数字转为ASC11值，用字符形式输出
		printf("%c",p->data);
		p=p->next;
	}
	printf("\n");
}

main()
{
	int i=1;
	char goon;
	DLinkList first,second,third,temp;
	while(i<80){printf("*");i++;}//输出最上面一行星号*
	printf("任意长整数加法运算\n");
	printf("输入形式：	-1234,5678,9000\n");
	i=1;
	while(i<80){printf("*");i++;}	
	printf("\n");
	do{CreateList(first);						//构造新表
	CreateList(second);
	CreateList(third);
	printf("请输入第一个整数：");
	DataIn(first);								//接收第一个整数
	while(Judge(first)==ERROR)					//如果输入非法则请重新输入
	{
		FreeList(first);
		printf("数据错误！\n请输入正确的数值：");
		CreateList(first);
		DataIn(first);
		Judge(first);
	}
	printf("\n输入第二个整数：");
	DataIn(second);								//接收第二个整数
	while(Judge(second)==ERROR)					//输入非法则重新输入
	{
		FreeList(second);
		printf("数据错误！\n请输入正确的数值：");
		CreateList(second);
		DataIn(second);
		Judge(second);
	}
	if(Compare(first,second)==ERROR){temp=first;first=second;second=temp;}	//如第一个整数较小则交换两个整数
	AddTwoList(first,second,third);				//两个整数相加
	DataOut(third);								//输出相加结果
	FreeList(first);							//释放链表空间
	FreeList(second);
	FreeList(third);
	printf("\n要继续吗？(y/n)：");			//判断是否要继续
	scanf("%c",&goon);
	getchar();
	printf("\n\n");
	}while(goon=='y'||goon=='Y');				//输入为n则退出，否则继续
	return;
}