003.cpp

长整数加法器

#include "stdio.h"
#include "malloc.h"
#include "string"
#define ADDSIZE 10
typedef struct{
	char *ch;
	int length,listsize;
}sqlist;
typedef struct Dlist{
	int data;
	int f;
	struct Dlist *prior,*next;
}Dlist,*Dlinklist;
int Initcharlist(sqlist &l)
{
	if(!l.ch)
		return 1;
	l.length=0;
	l.listsize=0;
	return 0;
}
void Createcharlist(sqlist &l)
{
	char ch;
	int i;
	for(i=0;(ch=getchar())!='=';++i)
	{
		l.ch[l.length++]=ch;
		if(l.length>=l.listsize-1)
			l.listsize+=ADDSIZE;
	}
	l.ch[l.length++]='\0';
}
int findchar(char *&ch,int i,char c)
{
	while((ch[i]!=c)&&(ch[i]!='\0'))
		i++;
	if(ch[i]=='\0')
		return -1;
	return i;
}
void CreateDlink(Dlinklist &l,char *p)
{
	Dlinklist h,s;
	int i=0;
	char *q=p;
	l->f=0;
	h=l;
	while((i=findchar(p,i,','))!=-1)
	{
		q[i]='\0';
		p=&p[i+1];
		s=(Dlinklist)malloc(sizeof(Dlist));
		s->data=atoi(q);
		s->prior=h;
		s->f=0;
		h->next=s;
		h=s;
		q=p;
	}
	s=(Dlinklist)malloc(sizeof(Dlist));
	s->data=atoi(p);
	s->prior=h;
	s->f=0;
	h->next=s;
	s->next=l;
	l->prior=s;
}
void Addlist(Dlinklist &l1,Dlinklist &l2)
{
	Dlinklist h1,h2;
	h1=l1->prior;
	h2=l2->prior;
	while((h1!=l1)&&(h2!=l2))
	{
		h1->f=(h1->data+h2->data+h1->next->f)/10000;
        h1->data=(h1->data+h2->data+h1->next->f)%10000;
		h1=h1->prior;
		h2=h2->prior;
	}
	if((h1==l1)&&(h2==l2))
	{
		l1->data=l1->next->f;
	}
	else{
		if(h1==l1)
		{
			h2->next=h1->next;
			h1->next->prior=h2;
			while(h2->next->f)
			{
				h2->f=(h2->data+h2->next->f)/10000;
				h2->data=(h2->data+h2->next->f)%10000;
				h2=h2->prior;
			}
			l1->next=l2->next;
		}
		else{
			while(h1->next->f)
			{
				h1->f=(h1->data+h1->next->f)/10000;
                h1->data=(h1->data+h1->next->f)%10000;
				h1=h1->prior;
			}
		}
	}
}
void Displaydlink(Dlinklist &l)
{
	int n;
    Dlinklist h=l->next;
	if(l->next->f)
		printf("%d,",l->next->f);
	while(h!=l)
	{
		n=1000;
		while(n!=0)
		{
			printf("%d",h->data/n);
			h->data%=n;
			n/=10;
		}
		printf(",");           
		h=h->next;
	}
	printf("\n");
}
int main()
{
	int i;
	sqlist l;
	Dlinklist l1,l2;
	char *p,*q;
	Initcharlist(l);
	Createcharlist(l);
	i=findchar(l.ch,0,'+');
	l.ch[i]='\0';
	p=l.ch;
	q=&l.ch[i+1];
	CreateDlink(l1,p);
	CreateDlink(l2,q);
	Addlist(l1,l2);
	Displaydlink(l1);
	return 0;
}