十进制整数num转换为m进制，链栈实现（C语言）

十进制整数num转换为m进制，链栈实现（C语言）

内容:

   将十进制整数num转换为r进制数，其转换方法为辗转相除法。要求用链栈实现。

步骤：

1.算法分析：

进行算法分析前，首先需要了解辗转相除法。

欧几里得算法又称辗转相除法，是指用于计算两个非负数啊，b的最大公约数。计算公式gcd(a,b) = gcd(b,a mod b)。

假如需要求 1997 和 615 两个正整数的最大公约数,利用辗转相除法，是这样进行的：

1997 / 615 = 3  (余 152)

615 / 152 = 4   (余 7)

152 / 7 = 21    (余 5)

7 / 5 = 1        (余 2)

5 / 2 = 2        (余 1)

2 / 1 = 2        (余 0)

至此，最大公约数为1

以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 1997 和 615 的最大公约数 1。

那么怎么利用辗转相除法进行进制转化呢？这里以789为例进行二进制转换：

789 / 2 = 394  (余 1)

394 / 2 = 197  (余 0)

197 /2 = 98    (余 1)

98 / 2 = 49    (余 0)

49 / 2 = 24    (余 1)

24 / 2 = 12    (余 0)

12 / 2 = 6     (余 0)

6 / 2 = 3      (余 0)

3 / 2 =1       (余 1)

1 / 2 =0       (余 1)

则789的十进制转二进制结果为：1100010101

由此可见，10进制转2进制就是，除2取余；再用商除2取余，一直到被除数（商）为0，余数的逆序就是该2进制数。所以，10进制转m进制就是，除m取余；再用商除m取余，一直到被除数（商）为0，余数的逆序就是该m进制数。

数值转换问题需要用到栈的基本 *** 作，程序中用三个函数分别实现链栈的入栈、判断栈空和出栈 *** 作。主函数有两个输入，即输入待转化的进制，函数Convert算法思想为：对待转换的数先判断正负，用if···else语句分别实现正数和负数的转化，转换的方法思想是利用算数运算中的取余和取整 *** 作，借助于栈的 *** 作，进行辗转相除来实现。

链栈的数据类型定义如下：

typedef int datatype;

 typedef struct node

 {

     datatype data;

     struct node *next;

  } *linkstack;

本程序实现的是整数的转换。

2.概要设计（使用C语言，设置了以下函数）

函数作用InitStack()初始化一个顺序栈Empty()实现栈的判空 *** 作Pop()实现元素的出栈 *** 作Convert()实现数制转换算法

3.程序的设计流程图

 

 4.源代码（编译环境：vc++6.0）：

#include
 #include
 #include
 typedef int datatype;
 typedef struct node
 {
 	datatype data;
 	struct node *next;
  } *linkstack;
  //入栈
  int Push(linkstack*top,datatype x)
  {
  	linkstack s=(linkstack)malloc(sizeof(struct node));
    if(s==NULL)
     return 0;
     s->data=x;
     s->next=(*top);
     (*top)=s;
     return 1;
   } 
   //判空
   int Empty(linkstack top)
   {
   	if(top==NULL)
   	  return 1;
   	  return 0;
	} 
	//出栈
	int Pop(linkstack*top,datatype*x)
	{
		if(top!=NULL)
		{
			linkstack p=(*top);
			(*x)=(*top)->data;
			(*top)=(*top)->next;
			free(p);
			return 1;
		}
		return 0;
	 } 
	 //十进制整数转化为任意进制数
	 void Convert(int num,int mode)
	 {
	 	int h;
	 	linkstack top=NULL;
	 	printf("转化结果为：");
	 	if(num>0)
	 	{
	 		while(num!=0)
	 		{
	 			h=num%mode;
	 			Push(&top,h);
	 			num=num/mode;
			 }
			 while(!Empty(top))
			 {
			 	Pop(&top,&h);
			 	printf("%d",h);
			 }
			 printf("n");
		 }
		 else if(num<0)
		 {
		 	printf("-");
		 	  num=num*(-1);
		 	while(num!=0)
		 	{
		 		h=num%mode;
		 		Push(&top,h);
		 		num=num/mode;
			 }
			 while(!Empty(top))
			 {
			 	Pop(&top,&h);
			 	printf("%d",h);
			 }
			 printf("n");
		 }
		 else
		 printf("%dn",0);
	  } 
	  void main()
	  {
	  	int num,mode;
	  	printf("n 输入要转化的数：");
	  	    scanf("%d",&num);
	  	printf("n 输入要转化的进制：");
	  	    scanf("%d",&mode);
	  	    Convert(num,mode);
	  }

5.测试结果：

正整数实例（789）：

 负整数实例（-789）：

 非法数字输入（789.5）：