1-4(

清华大学严蔚敏老师《数据结构习题集(C语言版)》的实验题1.4

#include<stdio.h>
#include<malloc.h>
#include<ctype.h>
#include<stdlib.h>

/* 定义双向循环链表的结点 */
typedef struct Node
{
	int data;
	struct Node *prior;
	struct Node *next;
} DuLNode,*DuLink;

/* 定义双向循环链表的初始化、清空、添加与删除结点等操作 */
int InitList( DuLink &L )
{
	// 初始化双向循环链表

	L=(DuLNode *)malloc(sizeof(DuLNode));
	if ( !L ) {
		printf("malloc failure\n");
		exit(0);
	}

	L->data=0;
	L->prior=L;
	L->next=L;

	return 0;
}

int ClearList( DuLink &L )
{
	// 清空双向循环链表的数据信息，返回头结点

	DuLNode *p;

	p=L->next;
	while ( p!=L ) {
		p->prior->next=p->next;
		p->next->prior=p->prior;
		free(p);
		p=L->next;
	}
	L->data=0;

	return 0;
}

int DestroyList( DuLink &L )
{
	// 销毁双向循环链表

	ClearList( L );
	free(L);
	return 0;
}

int AddNode_Input( DuLink &L, DuLink &p )
{
	// 在原尾元结点之后添加结点，并用指针p指向新结点
	// 用于按从高位到低位的顺序将长整数存放至链表

	p=(DuLNode *)malloc(sizeof(DuLNode));
	if ( !p ) {
		printf("malloc failure\n");
		exit(0);
	}

	p->next=L;
	p->prior=L->prior;

	p->next->prior=p;
	p->prior->next=p;

	return 0;
}

int AddNode( DuLink &L, DuLink &p )
{
	// 在原首元结点之前添加结点，并用指针p指向新结点
	// 用于按从低位到高位的顺序进行两长整数的运算

	p=(DuLNode *)malloc(sizeof(DuLNode));
	if ( !p ) {
		printf("malloc failure\n");
		exit(0);
	}

	p->prior=L;
	p->next=L->next;

	p->next->prior=p;
	p->prior->next=p;

	return 0;
}

int DelNode( DuLink &p )
{
	// 删除链表中的元素结点p

	if ( p->next==p || p->prior==p ) exit(0);

	p->prior->next=p->next;
	p->next->prior=p->prior;
	free(p);

	return 0;
}

void DispList( DuLink &L )
{
	// 显示长整数，即链表的数据信息

	DuLNode *p;
	
	if ( L->data==-1 && L->next->data!=0 )
		printf("-");
	p=L->next;
	printf("%d",p->data);
	
	while ( p->next!=L ) {
		printf(",");
		
		p=p->next;
		if ( p->data<10 ) printf("000");
		else if ( p->data<100 ) printf("00");
		else if ( p->data<1000 ) printf("0");
		
		printf("%d",p->data);	
	}
}

int CopyList( DuLink &L, DuLink &L_copy )
{
	// 复制链表L的信息，即将L_copy赋值为L

	DuLNode *p,*q;

	L_copy->data=L->data;
	p=L->prior;

	while ( p!=L ) {
		AddNode( L_copy, q );
		q->data=p->data;
		p=p->prior;
	}

	return 0;
}



// ////////////////////////////////////////////////////////////////////////////////////////////////


int DelZero( DuLink &L )
{
	// 删除从最高位开始的“0”结点，直到出现非零数或最低位

	DuLNode *p=L->next;

	while ( p->data==0 && p->next!=L ) {
		DelNode( p );
		p=L->next;
	}

	return 0;
}

int CountWeight( DuLNode *L )
{
	// 计算长整数中四位组的最高权值，即双向循环链表中非符号结点的个数

	DuLNode *p;
	int weight;

	DelZero( L );

	p=L->prior;
	weight=1;
	while ( p!=L ) {
		p=p->prior;
		++weight;
	}

	return weight;
}

int Compare( DuLNode *ha, DuLNode *hb )
{
	// 比较两个长整数的数字部分（即绝对值）的大小

	DuLNode *pa,*pb;
	int result;
	
	result=CountWeight( ha )-CountWeight( hb );
	
	if ( result>0 ) return 1;
	if ( result<0 ) return -1;

	pa=ha->next;
	pb=hb->next;

	while ( pa!=ha && pb!=hb ) {
		if ( pa->data>pb->data ) return 1;
		if ( pa->data<pb->data ) return -1;

		pa=pa->next;
		pb=pb->next;
	}
	
	if ( pa==ha && pb==hb ) return 0;

	return 0;
}


int Generate_byweight( DuLink &L, int weight )
{
	// 通过权值产生一个1,0000,...,0000的数

	DuLNode *p;

	while ( weight>0 ) {
		AddNode( L, p );
		p->data=0;
		--weight;
	}

	AddNode ( L, p );
	p->data=1;

	return 0;
}

int Dvid_byten( DuLink &L )
{
	// 将一个存放在链表中的长整数除以10
	// 在此程序中主要是对形如1,0000,...,0000的数进行操作

	DuLNode *p;

	p=L->prior;
	while ( p->prior!=L ) {
		p->data=p->data/10+(p->prior->data)%10*1000;
		p=p->prior;
	}

	p->data=p->data/10;

	DelZero( L );

	return 0;
}



// ////////////////////////////////////////////////////////////////////////////////////////////////

int Input( DuLink &L )
{
	// 读入长整数，将其存放在双向循环链表中

	char ch;
	int num,negt=1,i;
	DuLNode *p;

	fflush(stdin);
	ch=getchar();

	if ( ch=='-' ) {
		negt=-1;
		ch=getchar();
	}

	L->data=negt;		// 用头结点数据域表示长整数的符号信息

	/* 将每四位数储存入链表的每一个结点 */
	i=4;
	while ( ch!='\n' ) {
		num=0;
		i=0;
		while ( ch!=',' && ch!='\n' ) {
			if ( isdigit(ch) ) {
				num=num*10+(ch-'0');
				++i;
				if ( i>4 ) break;
			}
			else {
				printf("含非数字的数据，输入错误。请重新输入该长整数:\n");
				ClearList( L );
				return 0;
			}

			ch=getchar();
		}

		AddNode_Input( L, p );

		if ( p==L->next && i<4 ) i=4;
		if ( i!=4 ) {
			printf("格式错误，应该每四位数一组，组间用逗号隔开。请重新输入该长整数:\n");
			ClearList( L );
			return 0;
		}

		p->data=num;

		if ( ch==',') ch=getchar();
	}

	return 0;
}

DuLNode *Add_SameSymb( DuLNode *ha, DuLNode *hb, DuLNode *hc )
{
	// 两数同号时的加法运算

	DuLNode *pa,*pb,*pc;
	int sum,round;
	
	pa=ha->prior;
	pb=hb->prior;
	
	round=0;		// 进位信息
	while ( pa!=ha && pb!=hb ) {
		sum=pa->data+pb->data+round;
		
		AddNode( hc, pc );
		
		pc->data=sum%10000;
		round=sum/10000;

		pa=pa->prior;
		pb=pb->prior;
	} // while
	
	while ( pa!=ha ) {
		sum=pa->data+round;
		
		AddNode( hc, pc );
		
		pc->data=sum%10000;
		round=sum/10000;

		pa=pa->prior;
	} // while
	
	while ( pb!=hb ) {
		sum=pb->data+round;
		
		AddNode( hc, pc );
		
		pc->data=sum%10000;
		round=sum/10000;

		pb=pb->prior;
	} // while
	
	if ( round!=0 ) {		//两数相加后最高位出现进位
		AddNode( hc, pc );
		pc->data=round;
	}

	DelZero( hc );
	
	return hc;
}


DuLNode *Add_DiftSymb( DuLNode *hm, DuLNode *hn, DuLNode *hc )
{
	// 两数异号时的加法运算，用两数绝对值的大数减去小数

	DuLNode *pm,*pn,*pc;
	int temp,round;

	pm=hm->prior;
	pn=hn->prior;
	pc=hc;
	
	round=0;		// 退位信息
	while ( pm!=hm && pn!=hn ) {

		temp=pm->data+round;
		round=0;

		if ( temp<0 || temp<pn->data ) {		// 退位后小于0 或 被减数小于减数
			temp+=10000;
			round=-1;
		}

		AddNode( hc, pc );
		pc->data=temp-pn->data;

		pm=pm->prior;
		pn=pn->prior;
	} // while
	
	if ( pm!=hm ) {
		while ( pm!=hm ) {

			temp=pm->data+round;
			round=0;

			if ( temp<0 ) {
				temp+=10000;
				round=-1;
			}

			AddNode( hc, pc );
			pc->data=temp;

			pm=pm->prior;
		} // while
	} // if

	DelZero( hc );
	
	return hc;
}

DuLNode *Mult_func( DuLNode *hm, DuLNode *hn, DuLNode *hc )
{
	// 应用竖乘法的方法计算两数的乘积，其间调用同号二数加法的函数

	DuLNode *Mult_func_help( DuLNode *hm, DuLNode *pn, int weight, DuLNode *h_mult );

	DuLNode *pn,*h_mult,*hc_temp;
	int weight;

	InitList( h_mult );

	pn=hn->prior;
	weight=0;
	while ( pn!=hn ) {
		h_mult=Mult_func_help( hm, pn, weight, h_mult );

		hc_temp=hc;

		InitList( hc );
		hc->data=hc_temp->data;
		hc=Add_SameSymb( hc_temp, h_mult, hc );

		ClearList( h_mult );
		DestroyList( hc_temp );
	
		pn=pn->prior;
		++weight;
	}

	DestroyList( h_mult );

	return hc;
}