代码之家 › 专栏 › 技术社区 › Tool

ITOA递归

itoa recursion c

Tool · 技术社区 · 16 年前

我一直在写 递归的 函数的版本 itoa ,代码如下所示。

void itoa(int n, char s[])
{
     static int i = 0;

     if(n / 10 != 0)
         itoa(n/10, s);
     else if(n < 0)
         i = 1; /* s[0] is allready taken by - sign */
     else 
         i = 0; /* reset i to 0 */

     if(n < 0) {
          s[0] = '-';
     }

     s[i++] = abs(n % 10) + '0';
     s[i] = '\0';
}

但代码并不理想。它使用 static 变量的执行速度可能不如它应该的快。我正在努力实现 o(n) 算法。有人能给我看个更好的方法吗?我也认为静态变量是不必要的,但我不太确定如何避免它。为了避免静态变量,我应该将函数分成两部分吗?

4 回复 | 直到 13 年前

Yannick Motton 16 年前

如果您想递归地解决它,一个更简单的方法可能是返回最后一个索引:

int itoa(int n, char s[])
{
    int i =  0;         

    if(n / 10 != 0)
        i = itoa(n/10, s);
    else if(n < 0)
        s[i++] = '-';

    s[i++] = abs(n % 10) + '0';
    s[i] = '\0';

    return i;
}

您也可以使用指针来解决它:

char * itoa(int n, char * s)
{
    char * dest = s;

    if(n / 10 != 0)
        dest = itoa(n/10, dest);
    else if(n < 0)
        *dest++ = '-';

    *dest++ = abs(n % 10) + '0';
    *dest = '\0';

    return dest;
}

但是需要注意的是,这个实现容易出现缓冲区溢出。您需要确定已经分配了足够大的缓冲区,以适合整数的整个ASCII表示。一个好主意是包括一些边界检查。

David Jafferian 15 年前

ITOA应该回归无效。
我还没有测试过这个,但我相信它会起作用。
没有静态变量,没有助手函数,没有额外的参数。
while循环中的冗余整数除法可能是一个弱点。

void itoa(int n, char *s)  
{  
    char c;  
    if (n < 0)  
    {  
        *s++ = '-';  
        itoa(-n, s);  
        return;  
    }  
    c = '0' + n % 10;  
    itoa(n / 10, s);  
    while ( n /= 10 ) s++;  
    *s++ = c;  
    *s = '\0';  
}

Oren 16 年前

char* itoa(int n, char s[]) {
  if (n < 0) {
    s[0] = '-';
    return itoa(-n, s+1);
  }
  if (n/10 > 0) {
     s = itoa(n/10, s);
  }
  s[0] = '0' + (n%10);
  s[1] = '\0';
  return &s[1];
}

您还具有ITOA返回字符串结尾地址的功能。

axel22 15 年前

一个小问题的惊人解决方案。此代码接收分段错误,因为递归的基本情况是: n==0 处理不当。我对你的程序做了一个小小的改动,现在它运行得很好。

void itoa(int n,char *s)
{
    char c;
    if (n < 0)
    {
        *s++ = '-';
        itoa(-n, s);
        return;
    }
    if (n==0)
        return;
    c = '0' + n % 10;
    itoa(n/10,s);
    while ( n /= 10 ) s++;
    *s++ = c;
    *s = '\0';
}

现在,对于我自己的两个便士,我解决了这个问题,不使用除法,而是使用双指针来保持函数调用之间的值。

我的解决方案唯一的缺点是我们需要保留字符数组的起始地址。

void itoa(char**a,int i)
{
    int dig;
    if(i<10) //base case;
    {
        **a=i+48;
        *(++(*a))='\0';
        return;
    }
    dig=i%10;
    itoa(a,i/10);
    **a=dig+48;  //char value + 48 will give me the corresponding value
    *(++(*a))='\0';
    return;
}

int main()
{
    char* t=(char*)malloc(sizeof(char)*5);
    char* save=t;
    int ti=1234;
    itoa(&t,ti);
    printf("%s",save);
}