main.c

利用循环链表表示大整数

#include<stdio.h>
#include<stdlib.h>
#define HUNTHOU 10000

typedef struct node
{
	int data;
	struct node *next;
}NODE; /*定义链表结构*/


/*输入超长整数,存入链表*/
NODE *inputint(void)
{
	NODE *s,*ps,*qs;
	struct number
	{
		int num;
		struct number *np;
	}*p,*q;
	int i,k;
	long sum;
	char c;
	p=NULL; /*指向输入的整数，链首为长整数的最低位，链尾为长整数的最高位*/
	while((c=getchar())!='\n') /*输入整数，按字符接收数字*/
	if(c>='0'&&c<='9') /*若为数字则存入*/
	{
		q=(struct number *)malloc(sizeof(struct number)); /*申请空间*/
		q->num=c-'0'; /*存入一位整数*/
		q->np=p; /*建立指针*/
		p=q;
	}
	s=(NODE *)malloc(sizeof(NODE));
	s->data=-1; /*建立表求超长正整数的链头*/
	ps=s;
	while(p!=NULL) /*将接收的临时数据链中的数据转换为所要求的标准形式*/
	{
		sum=0;i=0;k=1;
		while(i<4&&p!=NULL) /*取出低四位*/
		{
			sum=sum+k*(p->num); 
			i++; 
			p=p->np; 
			k=k*10;
		}
		qs=(NODE *)malloc(sizeof(NODE)); /*申请空间*/
		qs->data=sum; /*赋值，建立链表*/
		ps->next=qs;
		ps=qs;
	}
	ps->next=s; /*指向头结点*/
	return s;
}

/*在u结点后插入一个新的NODE，其值为num*/
NODE *insert_after(NODE *u,int num)
{
	NODE *v;
	v=(NODE *)malloc(sizeof(NODE)); /*申请一个NODE*/
	v->data=num; /*赋值*/
	u->next=v;/*在u结点后插入一个NODE*/
	return v;
}
NODE *addint(NODE *p,NODE *q) /*完成加法操作返回指向*p+*q结果的指针*/
{
	NODE *pp,*qq,*r,*s,*t;
	int total,number,carry;
	pp=p->next;
	qq=q->next;
	s=(NODE *)malloc(sizeof(NODE)); /*建立存放和的链表表头*/
	s->data=-1;
	t=s; carry=0; /*carry:进位*/
	while(pp->data!=-1&&qq->data!=-1) /*均不是表头*/
	{
		total=pp->data+qq->data+carry; /*对应位与前次的进位求和*/
		number=total%HUNTHOU; /*求出存入链中部分的数值 */
		carry=total/HUNTHOU; /*求进位*/
		t=insert_after(t,number); /*将部分和存入s指向的链中*/
		pp=pp->next; /*分别取后面的加数*/
		qq=qq->next;
	}
	r=(pp->data!=-1)?pp:qq; /*取尚未自理完毕的链指针*/
	while(r->data!=-1) /*处理加数中较大的数*/
	{
		total=r->data+carry; /*与进位相加*/
		number=total%HUNTHOU; /*求出存入链中部分的数值*/
		carry=total/HUNTHOU; /*算出进位*/
		t=insert_after(t,number); /*将部分和存入s指向的链中*/
		r=r->next; /*移动指针*/
	}
	if(carry) t=insert_after(t,1); /*处理最后一次进位*/
	t->next=s; /*指向头结点*/
	return s; /*返回指向和的结构指针*/
}

/*比较两个数的大小*/
int compare(NODE *p,NODE *q)
{
	NODE *pt,*qt;
	int i=1,j=1;
    int k;
	pt=p->next;
	qt=q->next;
	while(pt->next->data!=-1) {pt=pt->next;i++;}  /*计算多少个结点*/
	while(qt->next->data!=-1) {qt=qt->next;j++;}
if(i==j)
{
	while(pt->data!=-1)
	{
	if(pt->data-qt->data>0) return 1; 
	if(pt->data-qt->data<0) return 0;   /*p指针指向数链大于等于q，函数返回1否则返回0*/
		for(k=0;k<i;k++)
		{
			pt=pt->next;
			qt=qt->next;
		}
	}
	return 1;
}
if(i>j) return 1;
else return 0;
}

/*完成两个链表减法操作返回指向|*p-*q|结果的指针*/
NODE *subint(NODE *p,NODE *q)
{
	NODE *pr,*qr,*s,*t;
	int total,borrow;  /*borrow:借位*/
	if(compare(p,q))
	{pr=p->next;qr=q->next;} /*pr指向较大的数链,qr指向较小的数链*/
	else {pr=q->next;qr=p->next;}
	s=(NODE *)malloc(sizeof(NODE));
	s->data=-1;
	t=s;borrow=0;
	while(qr->data!=-1)
	{
		total=pr->data-qr->data-borrow;
		if(total<0)     /*有借位*/
		{
			total=HUNTHOU+pr->data-qr->data-borrow;
			borrow=1;
		}
		else borrow=0;
		if(pr->next->data!=-1)
		t=insert_after(t,total);
		else{ 
			if(total!=0) t=insert_after(t,total);  /*最高位为0时不存入求差链中*/
		}
		pr=pr->next;qr=qr->next;	
	}
	while(pr->data!=-1)  /*处理余下结点*/
	{
		total=pr->data-borrow;
		if(total<0)
		{
			total=HUNTHOU+pr->data-borrow;
			borrow=1;
		}
		else borrow=0;
		if(pr->next->data!=-1)
		t=insert_after(t,total);
		else{ 
			if(total!=0) t=insert_after(t,total);
		}
		pr=pr->next;
	}
	t->next=s;
	if(s->next->data==-1) /*处理位数小于等于4位且相减结果为0情况*/
	{
		t=insert_after(t,total);
		t->next=s;
	}		
	return s;
}

/*打印链表*/
void printint(NODE *s)
{
	if(s->next->data!=-1) /*若不是表头，则输出*/
	{
		printint(s->next); /*递归输出*/
		if(s->next->next->data==-1)
		printf("%d",s->next->data); /*打印最高位*/
		else{
			int i,k=HUNTHOU;
			for(i=1;i<=4;i++,k/=10) /*按字符输出不足4位补0*/
			putchar('0'+s->next->data%(k)/(k/10));
		}
	}
}


void main()
{
NODE *s1,*s2,*s,*g;
int f;
char c;
NODE *inputint(), *addint(), *insert_after(),*subint();

do{
	printf("Enter S1= ");
	s1=inputint();
	printf("Enter S2= ");
	s2=inputint();
	printf(" S1="); printint(s1); putchar('\n'); 
	printf(" S2="); printint(s2); putchar('\n'); 
	s=addint(s1,s2); /*求和*/
	printf("S1+S2="); printint(s); putchar('\n'); /*打印结果*/
	f=compare(s1,s2);
	g=subint(s1,s2); /*求差*/
	printf("S1-S2="); 
	if(!f) printf("-"); /*判断符号*/
	printint(g); putchar('\n');
	printf("Enter key to continue other key to Exit:");
}while(c=getchar()=='\n');

}