首页
论坛
课程
招聘
[原创]一道字符串转换面试题的汇编实现及简要注释
2007-12-6 13:01 5871

[原创]一道字符串转换面试题的汇编实现及简要注释

HSQ 活跃值
8
2007-12-6 13:01
5871
这是我在其它论坛上看到的一道面试,由于没有放出答案.虽然没有什么难度,但自认为有点意思,就花了半个小时做了一下. 可能不是很符合要求,最小内存的情况我几乎没有考虑. 其实是自己认为没有必要对于字符串转换想办法减少内存,把过程搞得太复杂,即使是处理串有N大(比喻有100M以上),进行分批处理也能解决内存紧张的问题. 有更好实现的欢迎赐教
;需要申请的最小内存: 
;
;
;-----------------------------题    目-----------------------------------------
;请编写一个算法实现从源字符串到目标字符串的转换(“□”代表空格):
;源字符串:HE□IS□A□GOOD□BOY
;目标字符串:BOY□GOOD□A□IS□HE
;要求在最小内存情况下实现并给出源程序,并分析算法的优缺点。
;------------------------------------------------------------------------------
;  This was writed by Huang Shiquan 12:20   2007-12-6
;------------------------------------------------------------------------------
.386
.model  flat, stdcall
option  casemap:none

include windows.inc
include kernel32.inc
include user32.inc
includelib kernel32.lib
includelib user32.lib

	.data
szTestText		db	'HE IS A GOOD BOY',0
MsgBoxCaption		db	"题目解答"

	.code

Start:
	mov	ecx, 2
@@:
	push	ecx
	push	MB_OK
	push	offset MsgBoxCaption
	push	offset szTestText
	push	NULL
	call	MessageBox		;分两次现实处理前后的效果
	pop	ecx
	jcxz	@f

	push	offset szTestText
	call	SwapString
	loop	@b
@@:
	ret
;---------------------------------------------------------------------------	
SwapString	proc lpString:dword
	pushad
	mov	edi, lpString
	push	edi
	xor	eax, eax
	mov	ebx, eax
	mov	ecx, eax
	dec	ecx
	push	ecx
	cld
	repne	scasb
	pop	eax
	xchg	eax, ecx
	sub	ecx, eax			;计算字符数
	pop	edi
	mov	esi, ecx
	mov	al, 20h
@@:
	inc	ebx
	push	edi
	mov	edx, ecx
	repne	scasb
	sub	edx, ecx
	push	edx
	test	ecx, ecx			;将各块信息入栈保存
	jne	@b
	mov	byte ptr [edi-1], 20h	;修正尾块

	push	esi
	push	0
	call	LocalAlloc			;申请临时空间并写入倒序后的字符块
	mov	edi, eax
	mov	edx, esi
@@:
	dec	ebx
	pop	ecx
	pop	esi
	rep	movsb
	test	ebx, ebx
	jne	@b

	mov	esi, eax
	mov	edi, lpString
	mov	ecx, edx
	rep	movsb			;回写原地址空间
	mov	byte ptr [edi-1], 0		;修正尾块
	
	push	eax
	call	LocalFree			;释放临时空间
	popad
	ret
SwapString	endp

end	Start


效果演示及本文源码和编译文件

[2022夏季班]《安卓高级研修班(网课)》月薪三万班招生中~

上传的附件:
收藏
点赞0
打赏
分享
最新回复 (5)
雪    币: 109
活跃值: 活跃值 (203)
能力值: ( LV13,RANK:1050 )
在线值:
发帖
回帖
粉丝
combojiang 活跃值 26 2007-12-6 14:05
2
0
先下载,再慢慢看
雪    币: 1613
活跃值: 活跃值 (33)
能力值: (RANK:1010 )
在线值:
发帖
回帖
粉丝
北极星2003 活跃值 25 2007-12-6 18:30
3
0
没仔细看你的代码,总之算法复杂度是O(n)就对了
雪    币: 294
活跃值: 活跃值 (74)
能力值: ( LV9,RANK:140 )
在线值:
发帖
回帖
粉丝
liuzewei 活跃值 3 2007-12-19 12:55
4
0
看了你两篇帖子,很不错!
雪    币: 1068
活跃值: 活跃值 (20)
能力值: ( LV9,RANK:210 )
在线值:
发帖
回帖
粉丝
DiKeN 活跃值 5 2008-2-20 14:00
5
0
没事看精华的时候看到这个。最小空间是不需要新分配空间
具体算法步骤:
1。将字符串反转;
2。将每个单词反转;

//这个函数好像C语言库里面就有,没有自己写一个也很简单啦
void strrev(char *p)
{
char *p1, *p2, c;
p1 = p; p2 = p + strlen(p)-1;
while (p1 < p2)
{
  c = *p1;
  *p1 = *p2;
  *p2 = c;
  p1++;
  p2--;
}
}

void main()
{
char p[] = "HE□IS□A□GOOD□BOY";
strrev(p);

char *p1= p;
while (*p1 != 0)
{
  char *p2 =   strstr(' ', p1);
  if (p2 != NULL)
  {
    *p2 = 0;
  }
  strrev(p1);
  if (p2 == NULL)
  {
     break;
  }  
  p1 = p2 + 1;
}
}

/*
0:HE□IS□A□GOOD□BOY
1:YOB□DOOG□A□SI□EH
2:BOY□GOOD□A□IS□HE
*/
雪    币: 5536
活跃值: 活跃值 (56)
能力值: (RANK:1060 )
在线值:
发帖
回帖
粉丝
forgot 活跃值 26 2008-2-21 01:52
6
0
写不出什么好代码,老了唉
; input: esi = source, edi = buffer, ecx = length
  add     edi, ecx
  xor     ecx, ecx
L002:
  mov     al, [ecx+esi]
  cmp     al, 20
  je      L009
  cmp     al, 0
  je      L009
  inc     ecx
  jmp     L002
L009:
  sub     edi, ecx
  push    edi
  rep     movsb
  pop     edi
  lodsb
  test    al, al
  je      L020
  dec     edi
  stosb
  dec     edi
  jmp     L002
L020:
  retn
游客
登录 | 注册 方可回帖
返回