How to reverse a string (如何反转字符串)

How to reverse a string (如何反转字符串)

Question: How to Reverse a string in C? for example.input: “Hello world”, output:”dlrow olleH”

• Most common way  :

 char* strReverse1(char* str)

{

    char *temp=NULL, *ptr=NULL;

    int len, i;

    temp=str;

       for(len=0; *temp !='\0';temp++, len++);

 
    ptr=(char*)malloc(sizeof(char)*(len+1));

 
    for(i=len-1; i>=0; i--)

        *(ptr+len-i-1)=*(str+i);

 
    *(ptr+len)='\0';

    return ptr;

}

Set the characters into a new buffer from last one to first.

Remark, In this method, new memory was malloced, so remember to free it after call this function.

 

• Change the first one and last one, the second and (last -1)…

 char* strReverse2(char* str)

{

    int i=0, j=0, len=0;

    char temp='\0';

    char *ptr=NULL;

     
    len=strlen(str);

    ptr=(char*)malloc(sizeof(char)*(len+1));

    ptr=strcpy(ptr,str);

    for (i=0, j=len-1; i<=j; i++, j--) {

        temp=ptr[i];

        ptr[i]=ptr[j];

        ptr[j]=temp;

    }

    return ptr;

}

 
Remark, In this method, new memory was malloced, so remember to free it after call this function.

Here it a version with no new memory.

char* strReverse3(char* str)

{

    int i=0, j=0, len=0;

    char temp='\0';

 
    len=strlen(str);

    for (i=0, j=len-1; i<=j; i++, j--) {

        temp=str[i];

        str[i]=str[j];

        str[j]=temp;

    }

    return str;

}

 
Operate poiter:

char* strReverse4(char* str)

{

    int i=0, j=0, len=0;

    char temp='\0';

 
    len=strlen(str);

    for (i=0, j=len-1; i<=j; i++, j--) {

        temp=*(str+i);

        *(str+i)=*(str+j);

        *(str+j)=temp;

    }

    return str;

}

 

• Memory optimize: exchange two char without tmp variable.

 
char* strReverse5(char* str)

{

    int i=0, j=0, len=0;

    len=strlen(str);

    for (i=0, j=len-1; i

        *(str+i)^= *(str+j);

        *(str+j)^= *(str+i);

        *(str+i)^= *(str+j);

    }

    return str;

}

 
Key point: By XOR exchange a and b without using a third variable :

a=a^b;
b=b^a; //b^a<=> b^a^b<=>a^(b^b)<=>a^0=a
a=a^b; // a^b^a<=>(a^a)^b<=>0^b<=>b

Pretty C test code:       

a^= b^= a^= b;

    printf("a = %d b = %d\n", a, b);

这里利用了布尔代数地交换率和结合律，Chinese page:

%E5%B8%83%E5%B0%94%E4%BB%A3%E6%95%B0&printable=yes&printable=yes

 

• By recursion

void strReverse6(char* str)

{

    if(*str){

        strReverse6(str+1);

        *strOut++ = *str;

}

}

 
Test main program:

Char *strOut=NULL;

main()

{

       char input[31]="";

       int len=0;

 

       sprintf(input, "Hello world");

       len = strlen(input);

       strOut = (char*)malloc(sizeof(char)*(len+1));

       memset(strOut, 0, len+1);

 

    strReverse6(input);

       printf("strReverse6:%s\n", strOut);

       free(strOut);

}

Use a global variable strOut to store the reversed result string.

 

Reference:

http://discuss.fogcreek.com/techinterview/default.asp?cmd=show&ixPost=2077