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 !=”;temp++, len++);

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

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

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

 
    *(ptr+len)=”;

   
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=”;

   
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=”;

 
   
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=”;

 
   
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<j; i++, j–) {

       
*(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:

http://wiki.ccw.com.cn/index.php?title=%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://everything2.com/index.pl?node_id=612464

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

发表评论

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / 更改 )

Twitter picture

You are commenting using your Twitter account. Log Out / 更改 )

Facebook photo

You are commenting using your Facebook account. Log Out / 更改 )

Google+ photo

You are commenting using your Google+ account. Log Out / 更改 )

Connecting to %s