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

Working through some programming interview challenges I found online, I had to write an algorithm to reverse a const char * and return a pointer to a new char *. I think I have it, but to make it work properly I had to do some wonky stuff - basically having to account for the null-terminating character myself. Somehow I feel this is wrong, but I'm stumped, and I was wondering if someone could help me out:

通过在网上找到的一些编程访谈挑战,我不得不编写一个算法来反转一个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;
}

20 个解决方案

#1

std::reverse from <algorithm> works for strings and char arrays:

std :: reverse from 适用于字符串和char数组:

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

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

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

/EDIT: This, of course, modifies the original string. But STL to the rescue. The following creates a new reversed string. Unfortunately (?), this doesn't work directly on C char arrays without creating an additional (implicit) copy:

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

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

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

#2

I had this question once. That's the first answer that comes to mind, but the follow-up is, "now do it without allocating any memory."

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

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

EDIT: Some folks have expressed disdain for not using pointers. This is a tiny bit more readable, though not completely optimal. Others have entered the pointer solution, so I won't repeat it here.

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

One commenter challenged that it should be doable without a (stack based) holding cell for the swap. The mechanism for doing that is bitwise XOR. Replace the inside of the loop with

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

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

But in general, modern compilers can optimize out the local variable of a naive swap. For details, See Wikipedia

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

#3

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

#4

Your code is straight forward and unsurprising. A few things:

您的代码是直截了当的,并不令人惊讶。一些东西:

Use size_t instead of int for your loop index

对循环索引使用size_t而不是int

While your compiler is most likely smart enough to figure out that (length -1) is invariant, it's probably not smart enough to figure out that (length-1)-i is best replaced by a different loop variable that is decremented in each pass

虽然你的编译器很可能足够聪明地发现(长度-1)是不变的,但它可能不够聪明,无法确定(length-1)-i最好被每个传递中递减的不同循环变量所取代。

I'd use pointers instead of array syntax - it will look cleaner to me to have *dst-- = *src++; in the loop.

我使用指针而不是数组语法 - 对我来说看起来更干净* dst-- = * src ++;在循环。

In other words:

换一种说法:

char *dst = reversed_string + length;
*dst-- = '\0';
while (*src) {
   *dst-- = *src++;
}

#5

Uh? No one did it with pointers?

呃?没有人用指针做到了吗?

char *reverse(const char *s) {
    size_t n = strlen(s);
    char *dest = new char[n + 1];
    char *d = (dest + n - 1);

    dest[n] = 0;
    while (*s) {
        *d-- = *s++
    }

    return dest;
}

Hopefully years of Java haven't ruined my C ;-)

希望多年的Java没有破坏我的C ;-)

Edit: replaced all those strlen calls with an extra var. What does strlen return these days? (Thanks plinth).

编辑:用额外的var替换所有那些strlen调用。斯特伦这些天回来了什么? (谢谢基座)。

#6

I know this is highly unportable but x86 assembler instruction bswap lets you swap four bytes by means of just one instruction which can be a good path to boost the code.

我知道这是非常不可移植的,但x86汇编程序指令bswap允许您通过一条指令交换四个字节,这可以是一个提升代码的好途径。

This is an example of how to get it working with GCC.

这是如何让它与GCC一起工作的一个例子。

/* 
 * reverse.c
 *
 * $20081020 23:33 fernando DOT miguelez AT gmail DOT com$
 */

#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_CHARS 10 * 1024 * 1024

/*
 * Borrowed from http://coding.derkeiler.com/Archive/Assembler/comp.lang.asm.x86/2007-03/msg00004.html
 * GNU Compiler syntax
 */
inline uint32_t bswap(uint32_t val)
{
    __asm__("bswap %0" : "=r" (val) : "0" (val));
    return val;
}

char * reverseAsm(const char * str)
{
    int i;
    int length = strlen(str);
    int dwordLength = length/4;

    if(length % 4 != 0)
    {
        printf("Error: Input string length must be multiple of 4: %d\n", length);       
        return NULL;
    }

    char * reversed_string = (char *) malloc(length+1);
    for(i = 0; i < dwordLength; i++)
    {
        *(((uint32_t *) reversed_string) + dwordLength - i - 1) = bswap(*(((uint32_t *) str) + i));
    }

    reversed_string[length] = '\0';

    return reversed_string;
}

char * reverse(const char * str)
{
    int i;
    int length = strlen(str);
    char * reversed_string = (char *) malloc(length+1);

    for(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(void)
{
    int i;
    char *reversed_str, *reversed_str2;
    clock_t start, total;
    char *str = (char *) malloc(MAX_CHARS+1);

    str[MAX_CHARS] = '\0';

    srand(time(0));

    for(i = 0; i < MAX_CHARS; i++)
    {
        str[i] = 'A' + rand() % 26;     
    }

    start = clock();
    reversed_str = reverse(str);
    total = clock() - start;
    if(reversed_str != NULL)
    {
        printf("Total clock ticks to reverse %d chars with pure C method: %d\n", MAX_CHARS, total); 
        free(reversed_str);
    }
    start = clock();
    reversed_str2 = reverseAsm(str);
    total = clock() - start;
    if(reversed_str2 != NULL)
    {
        printf("Total clock ticks to reverse %d chars with ASM+C method: %d\n", MAX_CHARS, total); 
        free(reversed_str2);
    }

    free(str);

    return 0;
}

The results on my old computer under Cygwin:

我在Cygwin下的旧电脑上的结果:

fer@fernando /cygdrive/c/tmp$ ./reverse.exe
Total clock ticks to reverse 10485760 chars with pure C method: 221
Total clock ticks to reverse 10485760 chars with ASM+C method: 140

#7

@Konrad Rudolph: (sorry I don't have the "experience" to post a comment)

@Konrad Rudolph :(抱歉,我没有发表评论的“经验”)

I want to point out that the STL supplies a reverse_copy() algorithm, similar to reverse(). You need not introduce a temporary the way you did, just allocate a new char * of the right size.

我想指出STL提供了reverse_copy()算法,类似于reverse()。你不需要像你那样引入一个临时的,只需分配一个合适大小的新char *。

#8

You cannot (should not) do this:

你不能(不应该)这样做:

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

From: http://en.wikipedia.org/wiki/XOR_swap_algorithm#Code_example

*"This code has undefined behavior, since it modifies the lvalue x twice without an intervening sequence point.

*“此代码具有未定义的行为,因为它在没有插入序列点的情况下两次修改左值x。

#9

Actually, given the constraint that the original string be left unmodified, I think the original approach given in the question is the best. All these fancy approaches to reversing in place people are posting are great, but once copying the given string is factored in, they are all less efficient than simply copying the string backwards.

实际上,考虑到原始字符串未经修改的约束,我认为问题中给出的原始方法是最好的。所有这些花哨的方法都可以在人们发布的情况下进行逆转,但是一旦复制了给定的字符串,它们就会比简单地向后复制字符串效率低。

#10

We've used this question before -- with the surprisingly results of finding a lot of people that can't do it (even with significant C/C++ experience!). I prefer the in-place variant since it saves some overhead, and has the added twist of only needing to iterate over strlen(s)/2 characters.

我们之前使用过这个问题 - 结果令人惊讶地发现很多人无法做到这一点(即使有很高的C / C ++经验!)。我更喜欢就地变体,因为它节省了一些开销,并且还需要迭代strlen(s)/ 2个字符。

Your solution in an interview would be fine. A (correct!) solution using pointer instead of array syntax would rate a bit higher since it shows a greater comfort level with pointers which are so critical in C/C++ programming.

你在采访中的解决方案没问题。使用指针而不是数组语法的(正确!)解决方案会更高一些,因为它显示了更高的舒适度,指针在C / C ++编程中非常关键。

The minor critiques would be to point out that strlen returns a size_t not an int, and you should use delete [] on rev_str.

次要的批评是要指出strlen返回的size_t不是int,你应该在rev_str上使用delete []。

#11

WRT: "Now do it without temporary holding variable"... Something like this perhaps (and keeping array indexing for now):

WRT:“现在没有临时保持变量就行了”......也许这样的事情(现在保持数组索引):

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

#12

this works nicely:

这很好用:

#include <algorithm>
#include <iostream>
#include <cstring>

void reverse_string(char *str) {    
    char *end = str + strlen(str) - 1;
    while (str < end) {
        std::iter_swap(str++, end--);
    }
}

int main() {
    char s[] = "this is a test";
    reverse_string(s);
    std::cout << "[" << s << "]" << std::endl;
}

#13

I would have solved it sort of like this (my c is a bit rusty though, forgive me)

我会解决它有点像这样(我的c有点生疏,但原谅我)

char *reverse( const char *source ) {
  int len = strlen( source );
  char *dest = new char[ len + 1 ];
  int i = 0;
  int j = len;
  while( j > 0 ) {
    dest[j--] = src[i++];
  }
  dest[i] = \0;
  return dest;
}

#14

It wouldn't be more efficient, but you could demonstrate knowledge of data structures by doing something like pushing each letter onto a stack, and then popping them off into your newly allocated buffer.

它不会更高效,但您可以通过执行诸如将每个字母推入堆栈,然后将它们弹出到新分配的缓冲区中来演示数据结构的知识。

It would take two passes and a scratch stack, but I would probably trust myself more to get this right the first time then to not make an off-by one error like the above.

它需要两次传递和一个临时堆栈,但我可能会更信任自己,以便第一次正确地做到这一点,然后不像上面那样做出一个错误的错误。

char* stringReverse(const char* sInput)
{
    std::size_t nLen = strlen(sInput);
    std::stack<char> charStack;
    for(std::size_t i = 0; i < nLen; ++i)
    {
        charStack.push(sInput[i]);
    }
    char * result = new char[nLen + 1];
    std::size_t counter = 0;
    while (!charStack.empty())
    {
        result[counter++] = charStack.top();
        charStack.pop();
    }
    result[counter] = '\0';
    return result;
}

#15

When asking this question as an interviewer, I am looking to a clean, understandable solution and may ask how the initial solution could be made more efficient. I'm not interested in 'smart' solutions.

当我以面试官的身份提出这个问题时,我希望找到一个简洁易懂的解决方案,并可能会问如何提高初始解决方案的效率。我对'智能'解决方案不感兴趣。

I am thinking about thing like; has the candidate made the old with off by one error in their loop, do they pre-allocate enough memory, do they check to bad input, do they use sufficiently efficient types.

我在考虑的事情;让候选人在他们的循环中使用一个错误来解决它,他们预先分配了足够的内存,他们检查错误的输入,他们使用足够有效的类型。

Unfortunately, as already pointed out, too many people can't even do this.

不幸的是,正如已经指出的那样,太多人甚至无法做到这一点。

#16

String reversed in place, no temp variable.

字符串反转到位,没有临时变量。

static inline void
byteswap (char *a, char *b)
{
  *a = *a^*b;
  *b = *a^*b;
  *a = *a^*b;
}

void
reverse (char *string)
{
  char *end = string + strlen(string) - 1;

  while (string < end) {
    byteswap(string++, end--);
  }
}

#17

A method that doesn't need temporary variables

一种不需要临时变量的方法

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

#18

If I was doing the interviewing I would be a bit more fussy with the quality of the solution in terms of its robustness, not just it's performance.

如果我正在进行面试,那么就其稳健性而言,我会对解决方案的质量更加挑剔,而不仅仅是它的性能。

All of the answers submitted thus far will fail if passed a null pointer - most of them leap to immediately calling strlen() on a possible null pointer - which will probably segfault your process.

如果传递了一个空指针,那么到目前为止提交的所有答案都将失败 - 它们中的大多数都会立即在可能的空指针上调用strlen() - 这可能会使您的进程发生段错误。

Many of the answers are obsessive about performance to the point that they miss one of the key issues of the question: reverse a const char *, i.e. you need to make a reversed copy, not reverse in-place. You'll find it difficult to halve the number of iterations if a copy is required!

许多答案都是对性能的痴迷,以至于他们错过了问题的一个关键问题:反转一个常量字符*,即你需要制作一个反向副本,而不是就地反转。如果需要副本,你会发现很难将迭代次数减半!

This is an interview question, so we want to look at the details of the algorithm, but in the real world this just highlights the value of using standard libraries whenever possible.

这是一个面试问题,所以我们想看看算法的细节,但在现实世界中,这只是强调了尽可能使用标准库的价值。

#19

char * reverse(const char * str)
{
  if (!str)
    return NULL;

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

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

  return reversed_string;

}

Half the time but same complexity (note may be off by one error)

一半的时间但相同的复杂性(注意可能会被一个错误关闭)

#20

Above for loop has typo. Check of loop variable i should be <= instead of <, othrewise will fail for odd no of elements. for(int i = 0; i <= length/2; ++i)

以上for循环有拼写错误。检查循环变量i应该<=而不是<,othrewise将因奇数no元素而失败。 for(int i = 0; i <= length / 2; ++ i)

#1