itoa ricorsivamente

Question

Ho cercato di scrivere un ricorsiva la versione della funzione itoa, il codice è mostrato sotto.

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';
}

Ma il codice non è l'ideale. Esso utilizza una variabile static e probabilmente non è in esecuzione veloce come dovrebbe essere. Sto cercando di ottenere un O (n) algoritmo. Qualcuno mi potrebbe mostrare un modo migliore? Penso anche che variabile statica non è necesary, ma io non sono abbastanza sicuro come evitarlo. Dovrei rompere la funzione in due inorder per evitare la variabile statica?

Answer 1

Se si vuole risolvere in modo ricorsivo, un approccio più semplice potrebbe essere quello di restituire l'ultimo indice:

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;
}

Si potrebbe anche risolvere usando puntatori:

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;
}

Tuttavia su cosa da notare è che questa implementazione è soggetta a buffer overflow. È necessario essere certi di aver assegnato un numero sufficientemente ampio di buffer per adattare l'intera rappresentazione ASCII del numero intero. Una buona idea sarebbe quella di includere alcuni controlli di confine.

Answer 2

itoa dovrebbe restituire void.
Non ho ancora testato questo, ma credo che funzionerà.
Non ci sono variabili statiche, senza funzioni di aiuto, senza argomenti extra.
La divisione intera ridondante nel ciclo while può essere una debolezza.

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';  
}  

Answer 3

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];
}

Si ha anche la caratteristica che itoa restituisce l'indirizzo della fine della stringa.

Answer 4

soluzione Incredibile anche se un piccolo problema. Questo codice di errore di segmentazione riceve perché il caso base della ricorsione: quando n==0 non è gestito correttamente. Ho fatto una piccola modifica al vostro programma e ora funziona benissimo.

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';
}

Ora per il mio due pence, ho risolto questo senza usare la divisione, ma usando invece doppi puntatori per i valori a persistere tra le chiamate di funzione.

Solo demerito della mia soluzione è che abbiamo bisogno di preservare l'indirizzo iniziale della matrice di caratteri.

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);
}