线性表(单向链表)的汇编实现

这是单向链表数据结构实现的汇编版本.在写这个程序时,我悟出了一个道理,在写程序时尽量不要用类似高级语言的汇编伪指令,这是非常重要的,因为它们的底层代码是由编译器实现的,那么我们不清楚在转换代码时会改变哪些寄存器的值,那么这些伪代码之后我们自己的指令中使用改变了的寄存器,就有可能会出现无法预测的错误.在写这个代码时我就遇到这样的问题.

所以当且仅当表达式很复杂,而且跳转指令很多,还有就是保证我们要使用的寄存器不会被编译器在进行伪指令转换时使用并且改变时才用高级伪指令,在其它情况下一般不用.下面是两个文件的代码,这两个文件共同完成了单向链表的数据结构.
在写这个程序时,可以比较熟练的使用寻址方式对节点进行操作,这是一个进步.
LList.inc文件:
;///////////////////////////////////////////////////////////
;LList.inc文件,它用于定义一个节点的数据结构.
;///////////////////////////////////////////////////////////
LList struct
value dword ? ;数据.
next dword ? ;下一个节点的位置.
LList ends
PLList typedef ptr LList ;定义一个指向LList结构体的指针类型.

LList.asm文件:
;///////////////////////////////////////////////////////////
;实现对单向链表的定义.
;///////////////////////////////////////////////////////////

.386
.model flat,stdcall
option casemap :none
include windows.inc
include irvine32.inc
include LList.inc
include user32.inc
include kernel32.inc
includelib irvine32.lib
includelib user32.lib
includelib kernel32.lib
.data
head PLList ?
current PLList ?
tail PLList ?
leftNumber dword ?
rightNumber dword ?
.code
;///////////////////////////////////////////////////////////
;用于对链表进行初始化过程.
;///////////////////////////////////////////////////////////
Init proc
push eax
mov eax,sizeof LList
invoke GlobalAlloc,GPTR,eax
or eax,eax
je quit
assume eax:ptr LList
mov [eax].value,-999
mov [eax].next,NULL ;给头节点赋值,对于value赋什么值无所谓,但next成员要初始化成NULL最好.
mov head,eax
mov current,eax
mov tail,eax ;给三个指针赋初值,用于创建一个头节点.
mov leftNumber,0
mov rightNumber,0 ;左右节点数初始化为0.
assume eax:nothing
quit:
pop eax
ret
Init endp
;///////////////////////////////////////////////////////////
;用于销毁链表过程.
;///////////////////////////////////////////////////////////
RemoveAll proc
mov esi,head
assume esi:ptr LList
.while esi
mov current,esi ;current=head;
mov esi,[esi].next ;head=head->next;
invoke GlobalFree,current ;delete current;
.endw
mov head,esi
assume esi:nothing
mov leftNumber,0
mov rightNumber,0 ;将两个数值为0
ret
RemoveAll endp
;///////////////////////////////////////////////////////////
;清除并初始化链表,它用于新建一个链表.
;///////////////////////////////////////////////////////////
Clear proc
call RemoveAll ;先销毁链表
call Init ;再新建一个链表,并初始化表头.
ret
Clear endp
;///////////////////////////////////////////////////////////
;插入一个节点过程.
;///////////////////////////////////////////////////////////
Insert proc uses esi dwVal:dword ;参数为要插入的节点的有效数值.
invoke GlobalAlloc,GPTR,sizeof LList ;新建一个节点.
.if eax
mov esi,current
push dwVal
pop (LList ptr[eax]).value
push (LList ptr[esi]).next
pop (LList ptr[eax]).next ;给新建的节点赋值,并向后连接.
.if esi == tail
mov tail,eax ;如果插入的是结尾,那么调整结尾指针.
.endif
mov (LList ptr[esi]).next,eax ;前连接.
inc rightNumber ;右节点数加一.
.else
xor eax,eax ;失败返回false.
ret
.endif
or eax,1 ;成功返回true.
ret
Insert endp
;///////////////////////////////////////////////////////////
;从尾部追加节点过程.
;///////////////////////////////////////////////////////////
Append proc uses esi dwVal:dword
invoke GlobalAlloc,GPTR,sizeof LList
.if eax
mov esi,tail
push dwVal
pop (LList ptr[eax]).value
push NULL
pop (LList ptr[eax]).next ;给这个节点赋值,由于这个节点作为尾节点,所以next成员的值为NULL
mov (LList ptr[esi]).next,eax ;进行链接.
mov tail,eax ;重新调整尾指针.
inc rightNumber ;右节点数加一.
.else
xor eax,eax ;内存分配失败,那么返回false
ret
.endif
or eax,1 ;追加成功,返回true.
ret
Append endp
;///////////////////////////////////////////////////////////
;删除当前指针后面的那个节点.
;///////////////////////////////////////////////////////////
Removed proc uses esi pdwVal:Ptr dword
mov esi,current
.if esi == tail ;当前指针是指向尾节点的,返回flase.
xor eax,eax
ret
.endif
mov esi,(LList ptr[esi]).next ;得到要删除节点的起始地址.
.if esi == tail ;如果要删除的节点是尾节点,那么将当前位置节点设成尾节点.
mov eax,current
mov tail,eax
.endif
mov eax,pdwVal
push (LList ptr[esi]).value
pop (dword ptr[eax]) ;将要删除的节点的数据返回.
mov eax,current
push (LList ptr[esi]).next
pop (LList ptr[eax]).next ;要删除的节点首先让它脱离链表.
invoke GlobalFree,esi ;释放要删除节点的内存空间.
dec rightNumber ;右节点减一.
or eax,1 ;返回true
ret
Removed endp
;///////////////////////////////////////////////////////////
;设当前节点为首节点.
;///////////////////////////////////////////////////////////
SetStart proc
push eax
push head
pop current ;使当前节点设为首节点.
mov eax,leftNumber
add rightNumber,eax ;rightNumber+=leftNumber
mov leftNumber,0 ;leftNumber=0
pop eax
ret
SetStart endp
;///////////////////////////////////////////////////////////
;设当前节点为尾节点.
;///////////////////////////////////////////////////////////
SetEnd proc
push eax
push tail
pop current ;使当前节点设为尾节点.
mov eax,rightNumber
add leftNumber,eax ;leftNumber+=rightNumber
mov rightNumber,0 ;rightNumber=0
pop eax
ret
SetEnd endp
;///////////////////////////////////////////////////////////
;向后移一个节点.
;///////////////////////////////////////////////////////////
Prev proc uses esi ebx
mov esi,head
assume esi:ptr LList
.if esi == current
ret ;移到了表头,不能再移动了.
.endif
mov ebx,current
.while [esi].next!=ebx ;下一个节点不是当前节点.
mov esi,[esi].next
.endw
mov current,esi ;指向上一节点.
dec leftNumber
inc rightNumber
assume esi:nothing
ret
Prev endp
;///////////////////////////////////////////////////////////
;向前移动一个节点.
;///////////////////////////////////////////////////////////
Next proc uses esi
mov esi,current
assume esi:ptr LList
.if esi == tail
ret
.endif ;如果移动到结尾节点.
mov esi,[esi].next ;指向下一节点.
mov current,esi
inc leftNumber
dec rightNumber
assume esi:nothing
ret
Next endp
;///////////////////////////////////////////////////////////
;设置当前节点的位置.
;///////////////////////////////////////////////////////////
SetPos proc uses esi ecx dwPos:dword
mov eax,leftNumber
add eax,rightNumber ;eax=leftNumber+rightNumber
.if dwPos<0 || dwPos>eax ;超出范围就返回
xor eax,eax
ret
.endif ;返回false
mov esi,head
xor ecx,ecx
.while ecx<dwPos
mov esi,(LList ptr[esi]).next ;esi指向下一个节点.
inc ecx
.endw
mov current,esi ;新的当节点.
sub eax,dwPos
mov rightNumber,eax ;新的右节点数.
push dwPos
pop leftNumber ;新的左节点数.
or eax,1
ret
SetPos endp
;///////////////////////////////////////////////////////////
;返回左节点数.
;///////////////////////////////////////////////////////////
LeftLength proc
mov eax,leftNumber
ret
LeftLength endp
;///////////////////////////////////////////////////////////
;返回右节点数.
;///////////////////////////////////////////////////////////
RightLength proc
mov eax,rightNumber
ret
RightLength endp
;///////////////////////////////////////////////////////////
;返回总节点数.
;///////////////////////////////////////////////////////////
ItemNumber proc
mov eax,leftNumber
add eax,rightNumber
ret
ItemNumber endp
;///////////////////////////////////////////////////////////
;得到当前位置这后的节点的值.
;///////////////////////////////////////////////////////////
GetValue proc uses esi eax pdwVal:ptr dword
mov esi,current
mov esi,(LList ptr[esi]).next
mov eax,pdwVal
.if esi
push (LList ptr[esi]).value ;赋值.
pop dword ptr[eax]
.endif
ret
GetValue endp
;///////////////////////////////////////////////////////////
;打印链表中节点的数值.
;///////////////////////////////////////////////////////////
Print proc uses esi eax
mov esi,head
assume esi:ptr LList
mov esi,[esi].next
.while esi
mov eax,[esi].value
call WriteDec
mov al,' '
call WriteChar ;如果节点不为空,输出值.
mov esi,[esi].next
.endw
call Crlf
assume esi:nothing
ret
Print endp
;///////////////////////////////////////////////////////////
;对链表节点中的值按从小到大的顺序排序.
;///////////////////////////////////////////////////////////
Paixu proc uses esi edi eax
mov esi,head;
assume esi:ptr LList
assume edi:ptr LList
mov esi,[esi].next ;第n个节点
.while esi
mov edi,[esi].next ;第n+1个节点.
.while edi
mov eax,[esi].value
.if eax > [edi].value ;如果第n个节点的值大于第n+1个节点的值,那么交换.
xchg eax,[edi].value
mov [esi].value,eax
.endif
mov edi,[edi].next ;下一个节点.
.endw
mov esi,[esi].next ;下一个节点.
.endw
assume edi:nothing
assume esi:nothing
ret
Paixu endp
;///////////////////////////////////////////////////////////
;测试上面的链表的数据结构函数.
;///////////////////////////////////////////////////////////
main proc
local dwval:dword
call Clear ;清除并初始化链表.
invoke Insert,3
invoke Insert,2
invoke Insert,1
invoke Append,4
invoke Print ;插入三个数值,再追加一个值,然后输出.
invoke SetPos,3
invoke Removed,addr dwval
invoke Print
mov eax,dwval
call WriteDec
call Crlf ;当前节点设为3(从0开始),然后删除并输出.

call SetStart
invoke Insert,5
call SetEnd
invoke Insert,6
invoke Print ;首尾各插入一个值,然后输出.
invoke SetPos,2
invoke Prev
invoke GetValue,addr dwval
mov eax,dwval
call WriteDec
mov al,' '
call WriteChar
invoke SetPos,2
invoke Next
invoke GetValue,addr dwval
mov eax,dwval
call WriteDec
call Crlf ;输出当前位置为2的前和后节点的值.
invoke LeftLength
call WriteDec
mov al,' '
call WriteChar
invoke RightLength
call WriteDec
mov al,' '
call WriteChar
invoke ItemNumber
call WriteDec
call Crlf ;输出左右节点以及总节点数.
invoke Clear ;清除链表.
mov ecx,5
temp1:
push ecx
invoke Append,ecx
pop ecx
loop temp1 ;追加五个数值.
invoke Print ;然后输出.
invoke Paixu ;再排序
invoke Print ;再输出.
invoke ItemNumber
mov ecx,eax
temp2:
push ecx
push eax
sub eax,ecx
invoke SetPos,eax ;设置当前节点.
invoke GetValue,addr dwval
mov eax,dwval
call WriteDec
mov al,' '
call WriteChar ;输出当前节点值.
pop eax
pop ecx
loop temp2
call Crlf

invoke RemoveAll ;释放链表所占内存空间.
invoke ExitProcess,NULL
main endp
end main
从这个例子可以看出,三个指针使用了全局变量而非局部变量,这是为了简化函数的实现,否则每个函数都要添加PLList类型的三个指针,这样看起来更加复杂.
上面包含了详细的注释,所以不再多说.程序的执行结果也与相应的C++程序的结果完全相同.

本文来源 我爱IT技术网 http://www.52ij.com/jishu/1764.html 转载请保留链接。