我在一次采访中被问到这个问题
我应该在自己的位置反转字符数组，而不是反转整个字符数组。
如果
char *ch="krishna is the best";
然后我应该以这样的方式反转，输出应该像
anhsirk si eht tseb
我无法在面试中编写代码。任何人都可以建议我如何编写来做到这一点。？
可以在指针的帮助下完成吗？
如果面试官没有告诉我将其反转到自己的位置，那么使用数组的另一个字符数组是否容易处理，反转后会有新的字符串？
问问题
2887 次
9 回答
7
于 2012-08-29T13:18:03.357 回答
4
This doesn't sound too hard, if I understand it properly. Pseudocode:
let p = ch
while *p != '\0'
while *p is whitespace
++p
let q = last word character starting from p
reverse the bytes between p and q
let p = q + 1
The reversal of a range of bytes is trivial once you have pointers to the start and end. Just loop over half the distance, and swap the bytes.
Of course, as pointed out elsewhere, I assume that the buffer in ch is actually modifiable, which requires a change in the code you showed.
于 2012-08-29T13:23:12.490 回答
2
char *ch="krishna is the best";
No can do, this is a pointer to a read-only string literal. Let us imagine that your interviewer knew C and wrote this instead:
char str[]="krishna is the best";
Then you could do something like this:
#include <stdio.h>
#include <string.h>
#include <ctype.h>
char* str_reverse_word (char* str)
{
char* begin;
char* end;
char* the_end;
char tmp;
while(isspace(*str)) /* remove leading spaces from the string*/
{
str++;
}
begin = str;
end = str;
while(!isspace(*end) && *end != '\0') /* find the end of the sub string */
{
end++;
}
the_end = end; /* save this location and return it later */
end--; /* move back 1 step to point at the last valid character */
while(begin < end)
{
tmp = *begin;
*begin = *end;
*end = tmp;
begin++;
end--;
}
return the_end;
}
void str_reverse_sentence (char* str)
{
do
{
str = str_reverse_word(str);
} while (*str != '\0');
}
int main (void)
{
char str[]="krishna is the best";
str_reverse_sentence (str);
puts(str);
}
于 2012-08-29T13:44:16.090 回答
1
You can reverse it word-by-word.
Just read the string till ' '(space) ie. you will get krishna and reverse this string and continue reading original string till another ' '(space) and keep reversing the string.
于 2012-08-29T13:24:53.800 回答
1
Does the string really have to be reversed in place, or is it just the output that has to be reversed?
If the former, then you have a problem. If the declaration really is
char *ch = "krishna is the best";
then you're attempting to modify a string literal, and the behavior upon attempting to modify a string literal is undefined. If you're working on a platform where string literals are stored in read-only memory, you'll get a runtime error. You would either need to change the declaration to
char ch[] = "krishna is the best";
or allocate a dynamic buffer and copy the contents of the string to it
char *ch = "krishna is the best";
char *buf = malloc(strlen(ch) + 1);
if (buf)
{
strcpy(buf, ch);
// reverse the contents of buf
}
in order to accomplish a reversal in place.
If it's just the output that needs to be reversed, then storage doesn't really matter, you'd just need a couple of pointers to keep track of the beginning and end of each substring. For example:
#include <stdio.h>
#include <string.h>
int main(void)
{
char *ch = "krishna is the best";
char *start, *end;
// point to the beginning of the string
start = ch;
// find the next space in the string
end = strchr(start, ' ');
// while there are more spaces in the string
while (end != NULL)
{
// set up a temporary pointer, starting at the space following the
// current word
char *p = end;
// while aren't at the beginning of the current word, decrement the
// pointer and print the character it points to
while (p-- != start)
putchar(*p);
putchar(' ');
// find the next space character, starting at the character
// following the previous space character.
start = end + 1;
end = strchr(start, ' ');
}
// We didn't find another space character, meaning we're at the start of
// the last word in the string. We find the end by adding the length of the
// last word to the start pointer.
end = start + strlen(start);
// Work our way back to the start of the word, printing
// each character.
while (end-- != start)
putchar(*end);
putchar('\n');
fflush(stdout);
return 0;
}
There's probably a better way to do that, this is just off the top of my head.
于 2012-08-29T14:06:34.437 回答
0
Not sure of specific code right now, but here is the way I would do it (assuming you were able to write over original variable).
1) Split the string into an array of words using blank space as the delimiter
2) Loop through array and sort the words in reverse order
3) Rebuild the string and assign back to variable.
于 2012-08-29T13:19:37.563 回答
0
Here is an in-place swap using XOR:
void reverseStr(char *string)
{
char *start = string;
char *end = string + strlen(string) - 1;
while (end > start) {
if (*start != *end)
{
*start = *start ^ *end;
*end = *start ^ *end;
*start = *start ^ *end;
}
start++;
end--;
}
}
This of course assumes that string is in writeable memory, so don't come complaining that it isn't.
If you need to split the words first, then give me a few minutes and I'll write something up.
EDIT:
For words separated by space (0x20), the following code should work:
void reverseStr(char *string)
{
// pointer to start of word
char *wordStart = string;
// pointer to end of word
char *wordEnd = NULL;
// whether we should stop or not
char stop = 0;
while (!stop)
{
// find the end of the first word
wordEnd = strchr(wordStart, ' ');
if (wordEnd == NULL)
{
// if we didn't a word, then search for the end of the string, then stop after this iteration
wordEnd = strchr(wordStart, '\0');
stop = 1; // last word in string
}
// in place XOR swap
char *start = wordStart;
char *end = wordEnd - 1; // -1 for the space
while (end > start) {
if (*start != *end)
{
*start = *start ^ *end;
*end = *start ^ *end;
*start = *start ^ *end;
}
start++;
end--;
}
wordStart = wordEnd + 1; // +1 for the space
}
}
于 2012-08-29T13:24:58.093 回答
0
Here is my working solution ->
#include<stdio.h>
#include<ctype.h>
#include<string.h>
char * reverse(char *begin, char *end)
{
char temp;
while (begin < end)
{
temp = *begin;
*begin++ = *end;
*end-- = temp;
}
}
/*Function to reverse words*/
char * reverseWords(char *s)
{
char *word_begin = s;
char *temp = s; /* temp is for word boundry */
while( *temp )
{
temp++;
if (*temp == '\0')
{
reverse(word_begin, temp-1);
}
else if(*temp == ' ')
{
reverse(word_begin, temp-1);
word_begin = temp+1;
}
} /* End of while */
return s;
}
int main(void)
{
char str[]="This is the test";
printf("\nOriginal String is -> %s",str);
printf("\nReverse Words \t -> %s",reverseWords(str));
return 0;
}
于 2012-09-14T05:07:42.700 回答
0
Here is my working solution ->
#include<stdio.h>
#include<ctype.h>
#include<string.h>
char * reverse(char *begin, char *end)
{
char temp;
while (begin < end)
{
temp = *begin;
*begin++ = *end;
*end-- = temp;
}
}
/*Function to reverse words*/
char * reverseWords(char *s)
{
char *word_begin = s;
char *temp = s; /* temp is for word boundry */
while( *temp )
{
temp++;
if (*temp == '\0')
{
reverse(word_begin, temp-1);
}
else if(*temp == ' ')
{
reverse(word_begin, temp-1);
word_begin = temp+1;
}
} /* End of while */
return s;
}
int main(void)
{
char str[]="This is the test";
printf("\nOriginal String is -> %s",str);
printf("\nReverse Words \t -> %s",reverseWords(str));
return 0;
}
于 2012-09-14T05:08:02.747 回答