一个面试题: reverse words in place with O(n) time

规则就是这样,所以才提的问啊.

/*---------------------------------------------------------------------------
File name: ReverseWords.c
Author: HJin (email: fish_sea_bird [at] yahoo [dot] com )
Created on: 7/25/2007 09:05:10
Environment: Windows XP Professional SP2 English +
Visual Studio 2005 v8.0.50727.762

Modification history:
===========================================================================

1. I wrote this function a few years ago. Fully test it before delivering it
to your client.
2. I removed comments to force you study the code instead of copy it.
3. Good luck!
*/

#include <stdio.h>
#include <string.h>

void strsrev(char* p, char* r)
{
char t;
while(p<r)
{
t = *p;
*p++ = *r;
*r-- = t;
}
}

/**
Reverse words in place.

O(n) algorithm.
*/
void wordrev(char* s)
{
char*b =s, *e = s+strlen(s)-1;

if(!s)
return;

strsrev(b, e);
b=e=s;

while(*b)
{
while(*b && *b == ' ')
++b;

e = b;
while(*e && *e != ' ')
++e;

strsrev(b, e-1);

b=e;
}
}

int main()
{
char s[100] = "Somewhere i belong.";

wordrev(s);
*s &= 0xDF;

printf("%s\n", s);

return 0;
}

[此贴子已经被作者于2007-7-26 0:07:08编辑过]

比较精炼的程序，没有用到栈，对了，这个首字符大写是我猜的，哪里有写？经验不足啊！

[此贴子已经被作者于2007-8-2 12:29:06编辑过]

纯粹是HJin他的算法翻译过来的，可见，好的算法用汇编实现也会很简单啊。欢迎大家努力搞算法啊！
#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std;

void strsrev(char* p, char* r)
{
char t;
_asm
{
$L1:
mov eax, DWORD PTR p
cmp eax, DWORD PTR r
jae SHORT $L2 //while(p<r)
mov ecx, DWORD PTR p
mov dl, BYTE PTR [ecx]
mov BYTE PTR t, dl //t=*p
mov eax, DWORD PTR p
mov ecx, DWORD PTR r
mov dl, BYTE PTR [ecx]
mov BYTE PTR [eax], dl
mov eax, DWORD PTR p
add eax, 1 //p++
mov DWORD PTR p, eax//*p=*r
mov ecx, DWORD PTR r
mov dl, BYTE PTR t
mov BYTE PTR [ecx], dl
mov eax, DWORD PTR r
sub eax, 1//r--
mov DWORD PTR r, eax//*r=t
jmp SHORT $L1
$L2:
}
}

void wordrev(char* s)
{
char* b,*e;
_asm
{
mov eax, DWORD PTR s
mov DWORD PTR b, eax//b=s
mov ecx, DWORD PTR s
push ecx//压入参数s指针
call strlen//调用strlen
add esp, 4//清除堆栈
mov edx, DWORD PTR s
lea eax, DWORD PTR [edx+eax-1]//eax是strlen返回的参数即strlen(s),
mov DWORD PTR e, eax//edx是字符串s首地址，所以实现e=s+strlen(s)-1
cmp DWORD PTR s, 0//if(!s)return
jne SHORT $L1
jmp $L7
$L1:
mov ecx, DWORD PTR e
push ecx//压入参数e
mov edx, DWORD PTR b
push edx//压入参数b
call strsrev //调用strsrev实现strsrev(b,e)
add esp, 8//清除堆栈
mov eax, DWORD PTR s
mov DWORD PTR e, eax//e=s
mov ecx, DWORD PTR e
mov DWORD PTR b, ecx//b=e
$L2:
mov edx, DWORD PTR b
movsx eax, BYTE PTR [edx]
test eax, eax//判断*b
je SHORT $L7//为0则返回
$L3:
mov ecx, DWORD PTR b
movsx edx, BYTE PTR [ecx]
test edx, edx//*b为0则停止循环
je SHORT $L4
mov eax, DWORD PTR b
movsx ecx, BYTE PTR [eax]
cmp ecx, 32 //*b与' '比较
jne SHORT $L4//不相等就跳出循环
mov edx, DWORD PTR b
add edx, 1
mov DWORD PTR b, edx//++b
jmp SHORT $L3
$L4:
mov eax, DWORD PTR b
mov DWORD PTR e, eax//e=b
$L5:
mov ecx, DWORD PTR e
movsx edx, BYTE PTR [ecx]
test edx, edx//e为0就跳出循环
je SHORT $L6
mov eax, DWORD PTR e
movsx ecx, BYTE PTR [eax]
cmp ecx, 32
je SHORT $L6//*e不是空格就跳出循环
mov edx, DWORD PTR e
add edx, 1
mov DWORD PTR e, edx//++e
jmp SHORT $L5
$L6:
mov eax, DWORD PTR e
sub eax, 1//e-1
push eax//压入e-1
mov ecx, DWORD PTR b
push ecx//压入b
call strsrev//调用strsrev实现strsrev(b,e-1)
add esp, 8//清除堆栈
mov edx, DWORD PTR e
mov DWORD PTR b, edx//b=e
jmp SHORT $L2
$L7:
}
}

int main()
{
char s[255];
cin.getline(s,255);

wordrev(s);
*s &= 0xDF;

printf("%s\n", s);

return 0;
}