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

Comments:

Post a Comment:
Comments are closed for this entry.
About

williamxue

Search

Archives
« April 2014
SunMonTueWedThuFriSat
  
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
   
       
Today