1-4(

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

DuLNode *Mult_func_help( DuLNode *hm, DuLNode *pn, int weight, DuLNode *h_mult )
{
	// 实现乘法中每个四位数与另一个长整数的乘法运算，返回其乘积

	DuLNode *pm,*p;
	int temp,mult,round;

	while ( weight ) {		// 根据乘数在原长整数中的权值在乘积后添位
		AddNode( h_mult, p );
		p->data=0;

		--weight;
	}

	temp=pn->data;
	pm=hm->prior;
	round=0;
	while ( pm!=hm ) {
		mult=temp*pm->data+round;

		AddNode( h_mult, p );

		p->data=mult%10000;
		round=mult/10000;

		pm=pm->prior;
	}

	if ( round!=0 ) {		//两数相乘后最高位出现进位
		AddNode( h_mult, p );
		p->data=round;
	}

	return h_mult;
}

int *Divide_func( DuLNode *ha, DuLNode *hb, DuLink &hc, DuLink &hr )
{
	// 模拟竖式除法的过程，计算两个长整数的商与余数
	// 操作过程中需调用长整数的加法、减法和乘法运算

	int Divide_func_help( DuLink &ha_copy, DuLNode *hb, DuLNode *h_weight, DuLink &h_quotient );

	DuLNode *p,*h_weight,*h_mult,*ha_copy,*h_quotient,*h_temp;
	int weight;

	/* 赋商的初值为0 */
	AddNode( hc, p );
	p->data=0;

	/* 计算被除数与除数的权值差，并以此产生一个形如1,0000,...,0000的操作数 */
	InitList( h_weight );
	weight=CountWeight( ha )-CountWeight( hb )+1;
	Generate_byweight( h_weight, weight );

	/* 调整操作数1000...到合适权值 */
	InitList( h_mult );
	h_mult=Mult_func( hb, h_weight, h_mult );
	while ( Compare( h_mult, ha )>0 ) {
		Dvid_byten( h_weight );
		ClearList( h_mult );
		h_mult=Mult_func( hb, h_weight, h_mult );
	} // while

	InitList( ha_copy );
	CopyList( ha, ha_copy );

	InitList( h_quotient );
	while ( h_weight->next!=h_weight->prior || h_weight->prior->data!=0 ) {

		/* 若运算时遇到被除数的某一位为0,则减小操作数1000...的权值*/
		ClearList( h_mult );
		h_mult=Mult_func( hb, h_weight, h_mult );
		while ( Compare( h_mult, ha_copy )>0 ) {
			Dvid_byten( h_weight );
			ClearList( h_mult );
			h_mult=Mult_func( hb, h_weight, h_mult );
		}

		if ( h_weight->next==h_weight->prior && h_weight->prior->data==0 )
			break;

		/* 求出商的指定位的数值（从高位到低位） */
		ClearList( h_quotient );
		Divide_func_help( ha_copy, hb, h_weight, h_quotient );

		h_temp=hc;
		InitList( hc );
		hc=Add_SameSymb( h_temp, h_quotient, hc );		// 商的值为其每一位的数值的加权和
		DestroyList( h_temp );

		Dvid_byten( h_weight );
	} // while

	hr=ha_copy;

	DestroyList( h_weight );
	DestroyList( h_mult );
	DestroyList( h_quotient );
	
	return 0;
}

int Divide_func_help( DuLink &ha_copy, DuLNode *hb, DuLNode *h_weight, DuLink &h_quotient )
{
	// 在指定的权下通过尝试法求出合适的商值

	DuLNode *h_temp1,*h_temp2,*h_mult;

	InitList( h_temp1 );
	CopyList( h_weight, h_temp1 );
	InitList( h_mult );

	h_mult=Mult_func( hb, h_temp1, h_mult );
	while ( Compare( h_mult, ha_copy )<=0 ) {
		h_temp2=h_temp1;

		InitList( h_temp1 );
		h_temp1=Add_SameSymb( h_temp2, h_weight, h_temp1 );
		DestroyList( h_temp2 );

		ClearList( h_mult );
		h_mult=Mult_func( hb, h_temp1, h_mult );
	}

	h_quotient=Add_DiftSymb( h_temp1, h_weight, h_quotient );		// 商为在指定权下的与除数相乘后小于被除数的最大值

	ClearList( h_mult );
	h_mult=Mult_func( hb, h_quotient, h_mult );		// 计算此时商与余数的乘积
	h_temp2=ha_copy;
	InitList( ha_copy );
	ha_copy=Add_DiftSymb( h_temp2, h_mult, ha_copy );		// 被除数的剩余值为原值减去商与余数的乘积

	DestroyList( h_temp1 );
	DestroyList( h_temp2 );
	DestroyList( h_mult );

	return 0;
}



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

void MainInterface()
{
	// 主菜单界面

	printf("\n");
	printf("*******************************************************************************\n");
	printf("**                                                                           **\n");
	printf("**                                                                           **\n");
	printf("**                           欢迎运行此演示程序                              **\n");
	printf("**                                                                           **\n");
	printf("**                                                                           **\n");
	printf("**        此程序用于实现任意长的整数进行四则运算。按中国对于长整数的表示     **\n");
	printf("**    习惯(如12,3456,7890)输入两个长整数，可输出两数运算的结果。             **\n");
	printf("**                                                                           **\n");
	printf("**                                                                           **\n");
	printf("**        选择菜单：    1. 加法运算                                          **\n");
	printf("**                      2. 减法运算                                          **\n");
	printf("**                      3. 乘法运算                                          **\n");
	printf("**                      4. 除法运算                                          **\n");
	printf("**                                                                           **\n");
	printf("**                      0. 退出演示程序                                      **\n");
	printf("**                                                                           **\n");
	printf("**                                                                           **\n");
	printf("**                                                                           **\n");
	printf("*******************************************************************************\n");
	printf("\n");
	printf("请输入要执行的命令(0-4):");
}

void SubInterface()
{
	// 一次运算任务完成时的提示界面

	printf("\n");
	printf("*******************************************************************************\n");
	printf("**                                                                           **\n");
	printf("**    已完成运算，请选择下一步操作：                                         **\n");
	printf("**               1. 返回主菜单               2. 重新执行该运算               **\n");
	printf("**               0. 退出演示程序                                             **\n");
	printf("**                                                                           **\n");
	printf("*******************************************************************************\n");
	printf("请选择(0-2):");
}

int main()
{
	int option,next=1;

	void Add();
	void Less();
	void Mult();
	void Divide();
	
	while ( next ) {
		if ( next==1 ) {
			MainInterface();

			/* 选择要执行的命令 */
			fflush(stdin);
			option=getchar()-'0';
			while ( option<0 || option>4 ) {
				printf("输入错误，请根据提示重新输入(0-2):");
				fflush(stdin);
				option=getchar()-'0';
			}
		}

		/* 根据命令执行不同的操作 */
		switch ( option ) {
			case 0: {
				printf("\n退出该程序，谢谢您的使用！\n");
				return 0;
			}
			case 1:Add();break;
			case 2:Less();break;
			case 3:Mult();break;
			case 4:Divide();break;
			default :break;
		} // switch

		printf("\n");
		system("pause");

		SubInterface();

		/* 选择下一步指令 */
		fflush(stdin);
		next=getchar()-'0';
		while ( next<0 || next>2 ) {
				printf("输入错误，请根据提示重新输入(0-2):");
				fflush(stdin);
				next=getchar()-'0';
		}

		switch ( next ) {
			case 0: {
				printf("\n退出该程序，谢谢您的使用！\n");
				return 0;
			}
			case 1:printf("\n\n\n");break;
			default :break;
		} // switch

	} // while

	return 0;
}

void Add()
{
	// 加法运算

	DuLNode *ha,*hb,*hc,*hm,*hn;

	/* 读入两个长整数 */		
	printf("\n\t两个长整数的相加 ( a + b )\n\n");

	printf("输入长整数 a:\n");
	InitList( ha );
	while ( ha->next==ha ) {
		fflush(stdin);
		Input( ha );
	}
	
	printf("输入长整数 b:\n");
	InitList( hb );
	while ( hb->next==hb ) {
		fflush(stdin);
		Input( hb );
	}
	
	InitList( hc );

	if ( ha->data*hb->data>0 ) {
		hc->data=ha->data;		// 读入符号位信息
		hc=Add_SameSymb( ha, hb, hc );
	} // if

	else {
		/* 确定两数的大小，用指针hm指向大数，指针hn指向小数 */
		if ( Compare( ha, hb )>=0 ) {
			hm=ha;
			hn=hb;
		}
		else {
			hm=hb;
			hn=ha;
		}
		hc->data=hm->data;
		hc=Add_DiftSymb( hm, hn, hc );
	} // else
	
	printf("\na + b = ");
	DispList( hc );
	printf("\n");

	DestroyList( ha );
	DestroyList( hb );
	DestroyList( hc );
}

void Less()
{
	// 减法运算

	DuLNode *ha,*hb,*hc,*hm,*hn;

	/* 读入两个长整数 */		
	printf("\n\t两个长整数的相减 ( a - b )\n\n");

	printf("输入长整数 a:\n");
	InitList( ha );
	while ( ha->next==ha ) {
		fflush(stdin);
		Input( ha );
	}
	
	printf("输入长整数 b:\n");
	InitList( hb );
	while ( hb->next==hb ) {
		fflush(stdin);
		Input( hb );
	}
	
	InitList( hc );

	if ( ha->data*hb->data<0 ) {
		hc->data=ha->data;		// 读入符号位信息
		hc=Add_SameSymb( ha, hb, hc );
	} // if

	else {
		/* 确定两数的大小，用指针hm指向大数，指针hn指向小数 */
		if ( Compare( ha, hb )>=0 ) {
			hm=ha;
			hn=hb;
			hc->data=hm->data;		
		}
		else {
			hm=hb;
			hn=ha;
			hc->data=-hm->data;
		}
		hc=Add_DiftSymb( hm, hn, hc );
	} // else
	
	printf("\na - b = ");
	DispList( hc );
	printf("\n");
	
	DestroyList( ha );
	DestroyList( hb );
	DestroyList( hc );
}

void Mult()
{
	// 乘法运算

	DuLNode *ha,*hb,*hc,*hm,*hn;

	/* 读入两个长整数 */		
	printf("\n\t两个长整数的相乘 ( a * b )\n\n");

	printf("输入长整数 a:\n");
	InitList( ha );
	while ( ha->next==ha ) {
		fflush(stdin);
		Input( ha );
	}
	
	printf("输入长整数 b:\n");
	InitList( hb );
	while ( hb->next==hb ) {
		fflush(stdin);
		Input( hb );
	}
	
	InitList( hc );

	hc->data=ha->data*hb->data;		// 确定符号信息

	/* 确定两数的大小，用指针hm指向大数，指针hn指向小数 */
	if ( Compare( ha, hb )>=0 ) {
		hm=ha;
		hn=hb;
	}
	else {
		hm=hb;
		hn=ha;
	}
	hc=Mult_func( hm, hn, hc );
	
	printf("\na * b = ");
	DispList( hc );
	printf("\n");

	DestroyList( ha );
	DestroyList( hb );
	DestroyList( hc );
}

void Divide()
{
	// 除法运算

	DuLNode *ha,*hb,*hc,*hr;

	/* 读入两个长整数 */		
	printf("\n\t两个长整数的相除 ( a / b )\n\n");

	printf("输入长整数 a:\n");
	InitList( ha );
	while ( ha->next==ha ) {
		fflush(stdin);
		Input( ha );
	}
	
	printf("输入长整数 b (b!=0):\n");
	InitList( hb );
	while ( hb->next==hb ) {
		fflush(stdin);
		Input( hb );
	}
	
	if ( CountWeight(hb)==1 && hb->next->data==0 ) {		// 除法中除数为0时，运算无意义
		printf("除数为0,为非法值，运算无意义\n");
	}
	else if ( Compare( ha, hb )<0 ) {		// 若被除数小于除数，则商为0,余数与除数相等
		printf("\n a / b = 0, r = ");
		DispList( hb );
	}
	else {
		InitList( hc );
		InitList( hr );

		Divide_func( ha, hb, hc, hr );
		hc->data=ha->data*hb->data;		// 确定符号信息
		printf("\na / b = ");
		DispList( hc );
		printf("\n    r = ");
		DispList( hr );
		printf("\n");

		DestroyList( hc );
		DestroyList( hr );
	}

	DestroyList( ha );
	DestroyList( hb );
}