| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1592 人关注过本帖
标题:一个面试题: reverse words in place with O(n) time
只看楼主 加入收藏
medicihophy
Rank: 1
等 级:新手上路
威 望:1
帖 子:102
专家分:0
注 册:2007-7-28
收藏
得分:0 

纯粹是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;
}


2007-08-02 13:27
jianweichief
Rank: 1
等 级:新手上路
帖 子:80
专家分:0
注 册:2007-7-18
收藏
得分:0 
能回答一下我的问题吗

2007-08-02 16:54
medicihophy
Rank: 1
等 级:新手上路
威 望:1
帖 子:102
专家分:0
注 册:2007-7-28
收藏
得分:0 
以下是引用jianweichief在2007-8-1 22:18:10的发言:

红字部分看的不是很懂啊,当第一次循环结束后,b和e应该都指向.belong中的l的位置吧。然后执行while(*b && *b == ' ') ++b;语句,b能指向i吗?
还有e刚执行完第一次循环后,不是也指向l吗,如何在第二次调用strsrev(b, e-1);时,指向i呢?
注意,第一个while循环基本没什么所用,当你规范输入的时候。只是跳过前面的空格或者中间的很多空格。
所以你规范输入的时候,当第一次循环结束后,b没有变,还是在开头,而第二个while后,e就开始指向空格了,当有很多空格在一起的时候指向第一个。然后调用strsrev(b,e-1)即将第一个单词转向回来了啊,
接着b不是和e指在一起了吗?这是第一个while就有作用了,跳过空格,自然就指向第二个单词的开头了,然后
一直这样做当然可以解决问题了!


2007-08-02 17:05
快速回复:一个面试题: reverse words in place with O(n) time
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.075913 second(s), 7 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved