你会如何改进这个算法？(c字符串反转)

Question

通过我在网上找到的一些编程访谈挑战,我不得不编写一个算法来反转一个const char*并返回一个指向新char*的指针.我想我已经拥有它,但是为了让它正常工作,我不得不做一些不稳定的事情 - 基本上我必须自己考虑一个空终止的角色.不知怎的,我觉得这是错的,但我很难过,我想知道是否有人可以帮助我:

char * reverse(const char * str)
{
  int length = strlen(str);
  char * reversed_string = new char[length+1];

  for(int i = 0; i < length; ++i)
  {
    reversed_string[i] = str[(length-1) - i];
  }
  //need to null terminate the string
  reversed_string[length] = '\0';

  return reversed_string;

}

int main(int argc, char * argv[])
{

  char * rev_str = reverse("Testing");

  cout << "Your string reversed is this: " << rev_str << endl;

  delete rev_str;
  rev_str = 0;

  return 0;
}

Answer 1

std::reverse来自<algorithm>字符串和char数组的工作:

string str = "Hello";
char chx[] = "Hello";

reverse(str.begin(), str.end());
reverse(chx, chx + strlen(chx));

cout << str << endl;
cout << chx << endl;

/编辑:当然,这会修改原始字符串.但STL要救援.以下内容创建一个新的反转字符串.不幸的是(？),如果char没有创建额外的(隐式)副本,这不能直接在C 数组上工作:

string reverse_string(string const& old) {
    return string(old.rbegin(), old.rend());
}

cout << reverse_string("Hello") << endl;

Answer 2

我曾经有过这个问题.这是我想到的第一个答案,但后续工作是"现在不用分配任何记忆就行了".

int length = strlen(string);
for(int i = 0; i < length/2; i++) {
  char c = string[i];
  string[i] = string[length - i];
  string[length - i] = c;
}

编辑:有些人表示不使用指针.虽然不是完全最优的,但它更具可读性.其他人已进入指针解决方案,所以我在此不再重复.

一位评论者质疑,如果没有(基于堆栈的)持有单元用于交换,它应该是可行的.这样做的机制是按位异或.用.替换环的内部

string[i] = string[i] ^ string[length - i];
string[length - i] = string[i] ^ string[length - i];
string[i] = string[i] ^ string[length - i];

但总的来说,现代编译器可以优化天真交换的局部变量.有关详细信息,请参阅Wikipedia

Answer 3

if( string[0] )
{
    char *end = string + strlen(string)-1;
    while( start < end )
    {
        char temp = *string;
        *string++ = *end;
        *end-- = temp;
    }
}