您将如何改进这个算法? (c 字符串反转)

发布于 2024-07-08 15:16:36 字数 695 浏览 7 评论 0原文

为了解决我在网上发现的一些编程面试挑战,我必须编写一个算法来反转 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;
}

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:

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

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(20

〆凄凉。 2024-07-15 15:16:36

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

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

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

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

/EDIT:这当然会修改原始字符串。 但 STL 可以拯救你。 以下创建一个新的反转字符串。 不幸的是(?),如果不创建额外的(隐式)副本,这不能直接在 C char 数组上工作:

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

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

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

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:

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

cout << reverse_string("Hello") << endl;
花开浅夏 2024-07-15 15:16:36

我曾经有过这样的疑问。 这是我想到的第一个答案,但接下来的答案是,“现在就在不分配任何内存的情况下执行此操作。”

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

但一般来说,现代编译器可以优化朴素交换的局部变量。 有关详细信息,参见维基百科

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

烧了回忆取暖 2024-07-15 15:16:36
if( string[0] )
{
    char *end = string + strlen(string)-1;
    while( start < end )
    {
        char temp = *string;
        *string++ = *end;
        *end-- = temp;
    }
}
if( string[0] )
{
    char *end = string + strlen(string)-1;
    while( start < end )
    {
        char temp = *string;
        *string++ = *end;
        *end-- = temp;
    }
}
海拔太高太耀眼 2024-07-15 15:16:36

您的代码很简单并且不足为奇。 一些事情:

  1. 使用 size_t 而不是 int 作为循环索引
  2. 虽然您的编译器很可能足够聪明,可以弄清楚 (length -1) 是不变的,但它可能不够聪明,无法弄清楚 (length-1)-i 是不变的最好用不同的循环变量替换,该变量在每次传递中都会递减
  3. 我会使用指针而不是数组语法 - 对我来说,拥有 *dst-- = *src++; 看起来会更干净 在循环。

换句话说:

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

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

  1. Use size_t instead of int for your loop index
  2. 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
  3. I'd use pointers instead of array syntax - it will look cleaner to me to have *dst-- = *src++; in the loop.

In other words:

char *dst = reversed_string + length;
*dst-- = '\0';
while (*src) {
   *dst-- = *src++;
}
迷爱 2024-07-15 15:16:36

呃? 没有人用高手指点一下吗?

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

希望多年的 Java 没有毁掉我的 C ;-)

编辑:用额外的 var 替换所有这些 strlen 调用。 strlen 最近返回什么? (感谢底座)。

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

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

耶耶耶 2024-07-15 15:16:36

我知道这是非常不可移植的,但 x86 汇编器指令 bswap 允许您仅通过一条指令交换四个字节,这可能是增强代码的一个很好的途径。

这是如何让它与 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;
}

我的旧电脑上 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

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.

This is an example of how to get it working with 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:

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
最初的梦 2024-07-15 15:16:36

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

我想指出STL提供了一个reverse_copy() 算法,类似于 reverse() 。 您无需像以前那样引入临时变量,只需分配一个正确大小的新 char * 即可。

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

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.

夏了南城 2024-07-15 15:16:36

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

字符串[i] ^= 字符串[长度 - i] ^= 字符串[i] ^= 字符串[长度 - i]; 
  

来自:http://en.wikipedia.org/wiki/XOR_swap_algorithm#Code_example

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

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.
南巷近海 2024-07-15 15:16:36

实际上,考虑到原始字符串不被修改的约束,我认为问题中给出的原始方法是最好的。 所有这些在人们发布的地方进行反转的奇特方法都很棒,但是一旦考虑到复制给定的字符串,它们都比简单地向后复制字符串效率低。

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.

痴梦一场 2024-07-15 15:16:36

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

你在面试中的解决方案就很好。 使用指针而不是数组语法的(正确!)解决方案的评分会更高一些,因为它显示出对 C/C++ 编程中至关重要的指针的更高舒适度。

较小的批评是指出 strlen 返回 size_t 而不是 int,并且您应该在 rev_str 上使用 delete []。

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.

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.

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.

柒七 2024-07-15 15:16:36

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

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

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];
}
活泼老夫 2024-07-15 15:16:36

这很好用:

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

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;
}
想你的星星会说话 2024-07-15 15:16:36

我会像这样解决它(虽然我的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;
}

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

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;
}
戒ㄋ 2024-07-15 15:16:36

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

这需要两次传递和一个临时堆栈,但我可能会更相信自己第一次就能正确完成此操作,然后不会犯像上面这样的错误。

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

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;
}
不寐倦长更 2024-07-15 15:16:36

当作为面试官提出这个问题时,我正在寻找一个干净、易于理解的解决方案,并可能会问如何使最初的解决方案更加高效。 我对“智能”解决方案不感兴趣。

我在想这样的事情; 候选人是否在循环中因一个错误而导致旧的问题,他们是否预先分配了足够的内存,他们是否检查了错误的输入,他们是否使用了足够高效的类型。

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

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.

酸甜透明夹心 2024-07-15 15:16:36

字符串就地反转,没有临时变量。

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

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--);
  }
}
叹梦 2024-07-15 15:16:36

不需要临时变量的方法

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

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];
}
终遇你 2024-07-15 15:16:36

如果我进行面试,我会对解决方案的质量更加挑剔,包括其稳健性,而不仅仅是性能。

如果传递空指针,到目前为止提交的所有答案都将失败 - 大多数答案都会立即在可能的空指针上调用 strlen() - 这可能会导致你的段错误过程。

许多答案都过于关注性能,以至于忽略了问题的关键问题之一:反转 const char *,即您需要进行反转复制,不是原地反转。 如果需要副本,您会发现很难将迭代次数减半!

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

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.

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.

清晨说晚安 2024-07-15 15:16:36

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;

}

时间减半,但复杂性相同(注意可能会因一个错误而偏离)

.

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)

我做我的改变 2024-07-15 15:16:36

上面的 for 循环有拼写错误。
循环变量 i 的检查应该是 <= 而不是 <,否则对于奇数个元素将会失败。
for(int i = 0; i <= 长度/2; ++i)

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)

~没有更多了~
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文