itoa rekursiv

Question

Ich habe versucht, eine schreiben rekursive Version der Funktion itoa, wird der Code angezeigt wird.

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

Aber der Code ist nicht ideal. Es verwendet eine static Variable und wahrscheinlich nicht so schnell, wie es sein sollte, ausgeführt wird. Ich versuche, einen O (n) Algorithmus zu erreichen. Kann mir jemand einen besseren Weg zeigen? Ich denke auch, dass statische Variable nicht necesary ist, aber ich bin mir nicht ganz sicher, wie es zu vermeiden. Soll ich die Funktion in zwei Inorder brechen die statische Variable zu vermeiden?

Answer 1

Wenn Sie es rekursiv lösen wollen, ein einfachen Ansatz könnte sein, den letzten Index zurück:

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

Sie können auch lösen es Zeiger verwendet werden:

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

Allerdings auf, was zu beachten ist, dass diese Implementierung anfällig ist Buffer Overflows. Sie müssen sicher sein, dass Sie einen ausreichend großen Puffer zugeordnet haben die gesamte ascii Darstellung der ganzen Zahl passen. Eine gute Idee wäre, eine gewisse Grenze Prüfung umfassen.

Answer 2

sollte itoa Leere zurück.
Ich habe nicht getestet, aber ich glaube, es wird funktionieren.
Keine statischen Variablen, keine Hilfsfunktionen, keine zusätzlichen Argumente.
Die redundante ganzzahligen Division in der while-Schleife kann eine Schwäche sein.

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

Sie haben auch die Funktion, dass itoa die Adresse des Endes des Strings zurück.

Answer 4

Erstaunlich Lösung obwohl ein kleines Problem. Dieser Code erhält Segmentierungsfehler, da der Basisfall Rekursion: wenn n==0 ist nicht richtig gehandhabt. Ich habe eine kleine Änderung an Ihrem Programm und jetzt funktioniert es gut.

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

Jetzt für meine eigenen zwei Pence, ich löste dies ohne Teilung mit, sondern mit Doppelzeigern für die Werte zwischen Funktionsaufrufen bestehen bleiben.

Nur meine Lösung demerit ist, dass wir die Startadresse des Zeichenfeldes erhalten müssen.

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