C/C++面试之算法系列－－从“整数转换成字符串”看算法的联想

【序】“将给定的一个整数转换成字符串”是面试中常见的考题，本文参考了两位CSDN博友的帖子，在此感谢！

从低位开始转换，然后再翻转字符串是最容易想到的方式；先确定该整数的位数，取模运算从低位开始，将保存的位置递减，此方法无需翻转字符串，因此整体效率较高，值得借鉴。

受先确定该整数的位数的思想启发，我想取商运算从高位开始也可以，并且是顺序存储，无需翻转字符串

从获得最高位的方法，我又获得了一点想法，那就是用递归的方式来获得最高位，递归的条件很简单，只要参数不为10以内，即表示当前未找到最高位，当然递归退出的条件是当前数为个位数了

发现很多算法都有一定的共性，总能找到其中的某些联系，我相信只要大家善于思考，举一反三，从不同的角度包括时间效率空间效率去考察时，定会受益良多

最后一个递归算法稍有瑕疵，欢迎朋友们讨论！

************************************************

将给定的一个整数转换成字符串

Sailor_forever [e-mail]转载请注明

×××××××××××××××××××××××××××××××

算法一 计数互换

下面的这个算法显示了一个C语言新手所应有的水平。而且处理不完全，算法考虑不周到，代码过于啰嗦，不够简洁。

char * IntToStr(int Number)

{

char ch,*str,*t;

int i ,Len=0;

str = (char *)malloc(11*sizeof(char));

t = str;

while(Number!= 0)

{

*t = (Number %10)+0x30;

Number = Number /10;

Len++;

t++;

}

*t = '\0';

t = str;

for(i=0;i<Len/2;i++)

{

ch = *t;

*t = *(t+Len-2*i-1);

*(t+Len-2*i-1) = ch;

t++;

}

return str;

}

×××××××××××××××××××××××××××××××

算法二 指针，首尾互换

char * IntToStr(int Number)

{

char ch,*str,*right,*left;

unsigned int Value;

str = (char *)malloc(12*sizeof(char));

left = right = str;

//如果是负数，则应加上负号，left、right向后走。

if(Number < 0)

{

Value = -Number;

*str = '-';

left++,right++;

}

else

Value = (unsigned)Number;

//把数字转换成字符串（倒置的）

while(Value)

{

*right = (Value%10)+0x30;

Value = Value/10;

right++;

}

*right-- = '\0';

//把倒置的字符串正放过来

while(right > left)

{

ch = *left;

*left++ = *right;

*right-- = ch;

}

return str;

}

上面的函数在内部申请动态空间，返回给调用者后需要调用者释放空间，不满足模块间的耦合特性，因此函数原型最好为

char * IntToStr(int Number, char * output)

output指针由调用者自己申请的堆区或自动分配的栈区，IntToStr将转换后的字符串保存即可

×××××××××××××××××××××××××××××××

算法三 取模，从低到高

先求出当前整型数按照十进制有几位数，算出最低位转换后存放的地址求模，取出最低位，从高地址往低地址存，好处是不用翻转字符串

char* up_str_from_i(int i_in,char* str_out)

{

int t_i_in;

int t_num_count=0;

char * back = str_out;

if (i_in<0)

{

i_in*=(-1);

*str_out++='-';

}

t_i_in=i_in;

while (t_i_in /= 10)

t_num_count++;

//先求出当前整型数按照十进制有几位数，算出最低位转换后存放的地址

//求模，取出最低位，从高地址往低地址存，好处是不用翻转字符串

str_out+=t_num_count;

str_out++;

*str_out='\0';

str_out--;

do

{

*str_out = i_in % 10+'0';

if (i_in/=10)

str_out--;////if there r some num forword ,so str_out go back

}while (i_in%10);///if there r some num ,so loop

return back;

}

×××××××××××××××××××××××××××××××

算法四 求余，从高到低

先求出当前整型数按照十进制有几位数，算出求余时取出最高位应该除的数devide_num，以后devide_num每次除以10，求余从高到低依次取出各位，从低地址往高地址存，好处是不用翻转字符串

char* down_str_from_i(int i_in,char* str_out)

{

int t_i_in;

unsigned int devide_num=1;

char * back = str_out;

if (i_in<0)

{

i_in*=(-1);

*str_out++='-';

}

t_i_in=i_in;

while (t_i_in /= 10)

devide_num*=10; // updating devide_num by multiplying 10

printf("the absolute integer is %d, and devide_num is %d\n",i_in,devide_num);

while (i_in/10)

{

*str_out ++= i_in/devide_num +'0';

i_in %= devide_num;

devide_num/=10;

//更新除数和被除数

}

*str_out++ = i_in+'0'; //个位数

*str_out++ = '\0';

return back;

}

×××××××××××××××××××××××××××××××

算法五 递归寻找高位

char* rcsv_str_from_i(int i_in,char* str_out)

{

//static unsigned count=0;

// in case it is a minor integer for the first time

if (i_in<0)

{

i_in*=(-1);

*str_out++='-';

}

if(i_in/10) // not the most important bit in decimal, then recursively calling itself

{

str_out = rcsv_str_from_i(i_in/10,str_out);

*str_out++=i_in%10+'0';

*str_out = '\0'; // in case this is the last step

}

else// the most important bit

{

*str_out++=i_in+'0';

*str_out = '\0'; // in case this is the last step

}

// return the address for the next valid char

return str_out;

}

int main(void)

{

int i;

char str_out[100];

while(1)

{

scanf("%d",&i);

printf("up method gets %s\n",up_str_from_i(i,str_out));

printf("down method gets %s\n",down_str_from_i(i,str_out));

rcsv_str_from_i(i,str_out);

printf("recursive method gets %s\n",str_out);

}

return 0;

}

此递归算法源于上面的down方法，down方法的本质是找到最高位，然后从高位依次取出各位，按照数组顺序依次存储，不需翻转字符串。

因此继续递归的条件是当前数大于10，即仍未到达最高位

递归退出的条件是当前是个位数，即表示找到了最高位，退出时要将改动后的指针值传给上层调用者

每层递归退出后要保存个位数，依次向上退出，即可转换初始数的最后一位

目前该递归方法的缺点是不能实现链式操作，即最后一次返回的指针值不是函数调用者传进来的值，我想通过static变量保存转换的次数，最后递归退出时将返回的指针减掉该值即为最初的指针值，毕竟这个问题在面试中并不严重，没有深思，感兴趣的朋友可以试试

各位朋友有其他更好的方法欢迎讨论！

×××××××××××××××××××××××××××××××

参考资料：

http://blog.csdn.net/ammana_babi/archive/2006/07/18/936918.aspx

http://blog.csdn.net/kimn/archive/2005/01/14/253434.aspx