苛刻的字符串逆转

2011-03-06 wcdj

 

问题描述：

编写如下形式的字符串处理函数，要求将s1指向的字符串倒向复制给s2，如s1 = "hello"，则使 s2 = "olleh"。且不能使用除s1和s2以外的其余任何变量。 void ReverseStr( const char* s1 ,char* s2);

问题来自 ：讨论

 

总结几种实现方法如下：

 

方法一：递归

#include <cstdio> void ReverseStr( const char *s1 ,char *s2) { if (*s1) { ReverseStr(s1+1, s2);// recursion while(*s2) s2++; *s2 = *s1; *(s2+1) = 0; } else *s2 = 0; } int main() { char dst[128]={0}; ReverseStr("wcdj",dst);// dst == "jdcw" return 0; }

方法二：设置标记位，即添加一个哨兵

#include <cstdio> void ReverseStr( const char* s1 ,char* s2) { // 给s2头部加一个哨兵 *s2 = '/0'; // 令s1,s2均到达字符串最后一个字符位置 while(*s1) { ++s1,++s2; *s2 = '#';// 填充字符 } // 给s2尾部加终结符 ++s2; *s2 = '/0'; --s2; // 利用s2的头部哨兵将s2定位到头部 while(*s2) --s2; // 开始复制数据 --s1; do { *s2 = *s1; ++s2; --s1; } while(*s2); } int main() { char dst[128]={0}; ReverseStr("wcdj",dst);// dst == "jdcw" return 0; }

方法三：不使用变量使用内存，把长度存储在s2中

#include <cstdio> void ReverseStr( const char* s1 ,char* s2) { *((int*)s2) = 0; while (*s1) { s1++; *((int*)s2) += 1; } s1 -= *((int*)s2); s2 += *((int*)s2); *s2-- = '/0'; while (*s1) { *s2-- = *s1++; } return; } int main() { char dst[128]={0}; ReverseStr("wcdj",dst);// dst == "jdcw" return 0; }

方法四：使用异或运算交换变量

#include <iostream> #include <cstring> using namespace std; void ReverseStr(const char *s1 ,char *s2) { strcpy(s2,s1); while( s2 < s2+2*strlen(s2)-strlen(s1)-1 ) { (*s2)=(*s2)^(*(s2+2*strlen(s2)-strlen(s1)-1)); (*(s2+2*strlen(s2)-strlen(s1)-1))=(*s2)^(*(s2+2*strlen(s2)-strlen(s1)-1)); (*s2)=(*s2)^(*(s2+2*strlen(s2)-strlen(s1)-1)); ++s2; } } int main() { const char *s1="12345"; char s2[100]; ReverseStr(s1,s2); cout<<s2<<endl; return 0; }

方法五：使用字符串常量

#include<iostream> using namespace std; void reserveStr(const char* c1,char* c2) { while(*c1!='/0') ++c1; --c1; while(*c1!='/0'){ *c2=*c1; ++c2; --c1; } *c2='/0'; } int main() { //char c1[]="hello";// 这样循环不会停止 char* c1="hello";// 使用字符串常量 char c2[6]; reserveStr(c1,c2); cout<<c2<<endl; return 0; }

方法六：巧用strlen和置'/0'

#include <iostream> using namespace std; void ReverseStr(char* s1, char* s2) { while(strlen(s1)) { s2[strlen(s2)] = s1[strlen(s1)-1]; s1[strlen(s1)-1] = '/0'; } cout<<s2<<endl; } int _tmain(int argc, _TCHAR* argv[]) { char s1[] = "abcdefgh"; char s2[1024]; memset(s2,0,1024); ReverseStr(s1, s2); system("pause"); return 0; }

 

 

补充：CRT中strrev.c的实现

/* c:/Microsoft SDK/src/crt/strrev.c *strrev.c - reverse a string in place * * Copyright (c) 1985-2001, Microsoft Corporation. All rights reserved. * *Purpose: * defines _strrev() - reverse a string in place (not including * '/0' character) * *******************************************************************************/ /*** *char *_strrev(string) - reverse a string in place * *Purpose: * Reverses the order of characters in the string. The terminating * null character remains in place. * *Entry: * char *string - string to reverse * *Exit: * returns string - now with reversed characters * *Exceptions: * *******************************************************************************/ */ #include <cstdio> char * __cdecl _strrev ( char * string ) { char *start = string; char *left = string; char ch; while (*string++) /* find end of string */ ; string -= 2; while (left < string) { ch = *left; *left++ = *string; *string-- = ch; } return(start); } int main() { char src[]="wcdj"; printf("%s/n",_strrev(src)); return 0; }