任意长的整数加法
任意长的整数加法问题描述：设计一个程序实现两个任意长的整数的求和运算。
要求：
利用双向循环链表，设计一个实现任意长的整数进行加法运算的演示程序。要求输入和输出每四位一组，组间用逗号隔开。如：1，0000，0000，0000，0000。
要求用devc++5.0
回复 2楼 azzbcc
#include<stdio.h>#include<stdlib.h>
//结点的数据结构:
typedef struct jiedian
{
int s;
struct jiedian *next,*prior;
}dian;
//头结点的数据结构:
typedef struct
{
char f;
int l;
dian *zhi;
}head;
//输出函数：
void shuchu(head *ah)
{
dian *a=(dian *)malloc(sizeof(dian));
if(a==NULL)
{
printf("There is no space!");
return;
}
a=ah->zhi->prior; //从尾结点开始，向前输出
printf("%c",ah->f);
do
{
printf("%d,",a->s);
a=a->prior;
}
while(a->next!=NULL);
printf("\n wan");
}
//此函数完成（从后往前的插入式的）双向链表的创建：
int jianbiao(dian *a,int l,head *ah)
{
dian *t,*p,*q;
t=q=p=a; //用t来记录初始化时的第一个结点，即建完表后的最后一个结点
scanf("%d",&q->s);
while(q->s!=0)
{
ah->zhi=q;
q->next=p;
p->prior=q;
p=q;
l++;
q=(dian *)malloc(sizeof(dian));
if(q==NULL)
{
printf("There is no space!");
return 0;
}
scanf("%d,",&q->s);
}
p->prior=t; //使第一个结点的prior指向当前的最后一个结点
t->next=NULL;
return l;
}
//次函数完成头结点初始化:
void chushi(head *ah)
{
dian *a=(dian *)malloc(sizeof(dian));
if(a==NULL)
{
printf("There is no space!");
return;
}
a->s=0;
ah->zhi=a;
ah->l=0;
printf("Please input int :\n");
scanf("%c",&ah->f); //输入第一个结点的数据,即最高位的一个结点的数据
ah->l=jianbiao(a,ah->l,ah);
return;
}
//此函数完成两个链表的相减：
void jian(head *ah,head *bh,head *ch,dian *a,dian *b,dian *c)
{
dian *t;
while(a!=NULL&&b!=NULL)
{
c->next=(dian *)malloc(sizeof(dian));
c->next->s=0;
if(c->s+a->s>=b->s)
c->s=c->s+a->s-b->s;
else
{
c->s=c->s+a->s+10000-b->s; //实现借位运算
c->next->s--;
}
ch->l++;
t=c;
c=c->next;
c->prior=t;
a=a->next;
b=b->next;
}
while(a!=NULL)
{
c->next=(dian *)malloc(sizeof(dian));
c->next->s=0;
if(c->s+a->s>=0)
c->s=c->s+a->s;
else
{
c->s=c->s+a->s+10000; //实现借位运算
c->next->s--;
}
ch->l++;
t=c;
c=c->next;
c->prior=t;
a=a->next;
}
c=c->prior;
c->next=NULL;
ch->zhi->prior=c;
}
//表长相同的两个链表相减：
void jian1(head *ah,head *bh,head *ch,dian *a,dian *b,dian *c,dian *p,dian *q)
{
dian *t;
while(a!=p->next&&b!=q->next)
{
c->next=(dian *)malloc(sizeof(dian));
c->next->s=0;
if(c->s+a->s>=b->s)
c->s=c->s+a->s-b->s;
else
{
c->s=c->s+a->s+10000-b->s; //实现借位运算
c->next->s--;
}
ch->l++;
t=c;
c=c->next;
c->prior=t;
a=a->next;
b=b->next;
}
c=c->prior;
c->next=NULL;
ch->zhi->prior=c;
}
//此函数完成链表加法后期的链接：
void lianjie(dian *a,dian *c,head *ch)
{
dian *p;
while(a!=NULL)
{
c->s+=a->s;
ch->l++;
c->next=(dian *)malloc(sizeof(dian));
if(c->next==NULL) { printf("There is no space!"); return; }
c->next->s=0;
if(c->s>9999)
{
c->next->s=1; //向前进位的实现
c->s-=10000;
}
p=c;
c=c->next;
c->prior=p;
a=a->next;
}
if(c->s=1)c->next=NULL;
else
{
c=c->prior;
c->next=NULL;
}
ch->zhi->prior=c;
}
//此函数实现两个链表的求和
void jisuan(head *ah,head *bh,head *ch)
{
int n,i;
dian *p,*q,*a=(dian *)malloc(sizeof(dian)),*b=(dian *)malloc(sizeof(dian)),*c=(dian *)malloc(sizeof(dian));
if(a==NULL||b==NULL||c==NULL) { printf("There is no space!"); return; }
a=ah->zhi;
b=bh->zhi;
ch->zhi=c;
ch->l=0;
c->s=0;
if(ah->f==bh->f) //两数符号相等时
{
ch->f=ah->f;
do
{
c->s+=a->s+b->s;
ch->l++;
c->next=(dian *)malloc(sizeof(dian));
if(c->next==NULL) { printf("There is no space!"); return; }
c->next->s=0;
if(c->s>9999)
{
c->next->s=1; //向前进位的实现
c->s-=10000;
}
p=c; c=c->next; c->prior=p;
a=a->next; b=b->next;
}
while(a->next!=NULL&&b->next!=NULL);
if(a->next!=NULL)
lianjie(a,c,ch);
if(b->next!=NULL)
lianjie(b,c,ch);
else
{
if(c->s=1)c->next=NULL;
else
{
c=c->prior;
c->next=NULL;
}
ch->zhi->prior=c;
}
}
else //两数符号相异时
{
if(ah->l>bh->l)
{
ch->f=ah->f;
jian(ah,bh,ch,a,b,c);
}
if(ah->l<bh->l)
{
ch->f=bh->f;
jian(bh,ah,ch,b,a,c);
}
else //当两数结点数相等时
{
a=ah->zhi->prior;
b=bh->zhi->prior;
do
{
a=a->prior;
b=b->prior;
}
while(a->s==b->s); //寻找两数不同的最高结点
p=a; q=b;
if(a->s>b->s)
{
a=ah->zhi;
b=bh->zhi;
ch->f=ah->f;
jian1(ah,bh,ch,a,b,c,p,q);
}
else
{
a=ah->zhi;
b=bh->zhi;
ch->f=bh->f;
jian1(bh,ah,ch,b,a,c,p,q);
}
}
}
}
void main()
{
head *ah=(head *)malloc(sizeof(head));
if(ah==NULL) { printf("There is no space!"); return; }
chushi(ah);
head *bh=(head *)malloc(sizeof(head));
if(bh==NULL) { printf("There is no space!"); return; }
chushi(bh);
shuchu(ah);
shuchu(bh);
head *ch=(head *)malloc(sizeof(head)); //创建结果链表ch
if(ch==NULL) { printf("There is no space!"); return; }
jisuan(ah,bh,ch);
shuchu(ch);
}