【原创】如何REVERSE一个C STRING?
我有个朋友面试遇到了这个问题来问我,我做了一阵没做出来.关键是还有个附加要求,不得使用任何函数和临时变量, 也就是说reverse_string(char *p)里面唯一能出现的变量就是p,不能有str_len之类的函数和INT INDEX之类的临时变量,也不能出现reverse_string之外的函数.

我知道用递归可以把它反向显示出来(这显示出来其实已不对了,因为要用PUTCHAR),但没办法把它放回p.

AleaJactaEst 选转。

找了一下,网上的答案大多是错的.

各路高手们,帮帮忙啊?俺挨个送花:),发言就有花!

递归解法 2
如果P或者P+1为0，直接返回
否则递归处理P+1;
然后用循环将P依次后移1位，直到遇到0为止
返回P

说到递归，我就想出来了 1
叙述算法太麻烦，举例吧，一看就明白
12345
15432 -- 递归
51432 -- 交换前两个
51234 -- 再递归
54321 -- 再再递归

不用额外变量交换两个变量的值，相信您会的哦？

update: 才看到楼下的，比我的简单，更重要的是复杂度好多了。

code出来了,谢谢帮忙,CODE在内, 3
void reverse(char *p)
{
    if(p[0]=='\0') return;
    if(p[1]=='\0') return;

    if(p[2]!='\0') reverse(p+1);
  
    while(p[1]!='\0') {
          p[0]=p[0]+p[1];
          p[1]=p[0]-p[1];
          p[0]=p[0]-p[1]; //switch.
          
          p++;
    }
}

调试已经通过,
"然后用循环将P依次后移1位，直到遇到0为止" 我费了好一会儿才明白.

最后于2007-02-18 20:04:05改,共2次;

这东西，说的是不用什么临时变量。。。
帝归起来，用的空间多多了。。。

这个方法好。花

哈，我也问个算法。。。
前些天算两个7两个4（+-*/），怎么让它等于24，便想写个code:
任意给4个数，输出是否等于24，如果等于，给出怎么得到的结果。

忙活了半天，没有一个自己满意的算法和code，现请教一下，给个算法就行，谢谢了。 （不喜欢删掉好了）

这个我以前写过 1
思路是生成所有可能的四则运算表达式树，然后依次检查结果。
可以用逆波兰方式来表达，这样不用考虑括号和优先级的问题
需要注意的是，有时候中间结果非整数，可能要用写一个有理数类来存放结果。

想起来SICP里有道练习题就是这个
用LISP的方法来做的话一般都是用尾递归的
不过C好像无法不用临时变量模拟cdr

太谢谢了
考试太忙，匆匆献花。
小弟不是学计算机的，逆波兰这个算法第一次听说，要搞懂得花些时日（哈，俺是出了名的慢）。不过听你介绍，不用考虑不用考虑括号和优先级的问题，确实是我需要的算法！日后还要请教。

Does it really work?
Does your code really work?

Which compiler are you using and on which platform, Windows? Unix?

I tried your code using Visual C++ 6.0 on Windows and got an access violation for the following line as expected:

p[0] = p[0] + p[1];

Bigbug

I test it already.Notice:
you need to pass a char[], you can not pass "hello the world" directly, you need to scan a string to a char buffer.

My environment is gcc/Linux.

Do you kown the difference for "char *p="hello the world" and the "char p[100]"?

My test code is something like
"
main()
{
char str[100],
scan("%s",str);

printf("original:%s\n",str);
reverse(str);

printf("reversed:%s\n",str);
}

"

It works fine. I guess you pass "hello the world" directly into the reverse function.

老成都的code的复杂度不是变成了
n factorial了吗？是不是原地reverse只能让时间复杂度增加到那么大？谢谢

有那么高吗？n平方吧？我的倒是指数增长的

至少要一个临时变量吧！
否则用递归好像也没法做。

再说递归比用临时变量，无论从时间上还是空间上消耗的更多啊！

这比用一个临时变量，记住长度效率差多了 1
void reverse(char *p)
{
    int cnt = 0;
    
    // calculate length
    while (p[cnt] != 0) ++cnt;

    while ((cnt>>1) > 0)
    {
       // switch first and the last
       *p ^= p[cnt-1] ^= *p ^=p[cnt-1];
        
       p++;
       // cuz p moved forward, we have to minus 2
       cnt -= 2;
    }
}

您老看看，算长度，n, 交换位置1/2n，总共O(n)。只用一个临时变量。

递归算法，
1）要是N很大，stack就爆掉了，
2）而且每次调用函数，必须push ebp,调整ebp，压入参数，还要记住retern addr, jump回来，clean stack。浪费无数。
3）时间复杂度上，递归算法是O(n^2)

就为省一个临时变量。

现实生活中，谁要这么写程序，真可以直接fire了。出这种题的也应该fire，纯粹误导。



最后于2007-03-29 17:26:40改,共2次;