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

这是双向链表的数据结构实现的汇编版本,它实现了我们自己管理内存节点的方法,这种技术在上几章中就讲过,它可以大大的加快分配以及释放内存的时间,只有程序最后才真正用API函数进进将所有节点的内存释放.从下面的代码中可以看出,它与单向链表的汇编版本没有多大的差别,只不过我们要考虑任何节点都有一个前驱指针而已:

DList.inc文件:
;////////////////////////////////////////////////////////////
;用于创建一个双向链表节点,它与单向链表节点的不同点是增加了一
;前驱节点的指针.下面定义节点数据结构,并且声明一个指向该节点指
;针的类型.
;////////////////////////////////////////////////////////////
DList  struct
prev  dword NULL   ;前驱节点.
value  dword NULL   ;值
next  dword NULL   ;后继节点.
DList  ends
PDList  typedef ptr DList  ;指针类型.

DList.asm文件:
;////////////////////////////////////////////////////////////
;用于实现双向链表,它包含Link.inc文件中声明的结构体作为节点来
;创建.
;////////////////////////////////////////////////////////////
  .386
  .model flat,stdcall
  option casemap :none
include  windows.inc
include  irvine32.inc
include  DList.inc
include  user32.inc
includelib user32.lib
include  kernel32.inc
includelib kernel32.lib
  .data
head  PDList NULL   ;头指针.
tail  PDList NULL   ;尾指针.
current  PDList NULL   ;当前指针.
freeList PDList NULL   ;自己管理的内存缓冲区指针.
leftNumber dword 0   ;左节点指针.
rightNumber dword 0   ;右节点指针.
  .code
;////////////////////////////////////////////////////////////
;下面的连续三个函数:GlobCreateMem,GlobFreeMem和FreeMemory都是
;操作于freeList栈,实际上它简单的创建了一个栈型的数据结构,而三
;个函数是对它的最简单的操作,例如创建一个节点,插入一个节点,以及
;清空整个栈表.
;////////////////////////////////////////////////////////////
;////////////////////////////////////////////////////////////
;自定义一个节点内存创建函数,如果缓冲区中没有内存,那么用API创建.
;////////////////////////////////////////////////////////////
GlobCreateMem proc uses esi
  mov esi,freeList  ;获取缓冲区节点指针.
  or esi,esi
  jnz @F   ;如果freeList不等于0
  invoke GlobalAlloc,GPTR,sizeof DList
  jmp quit
@@:
  mov eax,esi
  mov esi,(DList ptr[esi]).next
  mov freeList,esi  ;如果freeList不等于0,那么返回一个节点的内存.
quit:
  ret
GlobCreateMem endp
;////////////////////////////////////////////////////////////
;自定义删除一个节点内存的函数,它实际上是将节点内存保存在缓冲
;区中.
;////////////////////////////////////////////////////////////
GlobFreeMem proc uses esi ebx pstLink:PDList
  mov esi,pstLink
  mov ebx,freeList
  or ebx,ebx
  jz @F
  mov (DList ptr[esi]).next,ebx
  mov freeList,esi
  jmp quit
@@:
  mov (DList ptr[esi]).next,NULL
  mov freeList,esi
quit:
  ret
GlobFreeMem endp
;////////////////////////////////////////////////////////////
;真正把内存释放.它使用了GlobalFree函数.
;////////////////////////////////////////////////////////////
FreeMemory proc uses esi ebx
  mov esi,freeList
  .while esi    ;如果freeList不空,
   mov ebx,esi
   mov esi,(DList ptr[esi]).next ;那么使esi指向下一节点.
   invoke GlobalFree,ebx   ;然后释放前一节点的内存.直到esi等于0.
  .endw
  ret
FreeMemory endp

;////////////////////////////////////////////////////////////
;创建并初始化一个头节点.
;////////////////////////////////////////////////////////////
Init  proc
  push eax
  invoke GlobCreateMem   ;创建一个内存块,用于保存一个头节点.
  or eax,eax
  je quit    ;如果申请内存失败,那么退出.
  mov (DList ptr[eax]).value,-999
  mov (DList ptr[eax]).prev,NULL
  mov (DList ptr[eax]).next,NULL ;设置头节点
  mov head,eax
  mov current,eax
  mov tail,eax   ;将三个指针都指向它.
  mov leftNumber,0
  mov rightNumber,0   ;左右节点指针都为0
quit:
  pop eax
  ret
Init  endp
;////////////////////////////////////////////////////////////
;清空链表.
;////////////////////////////////////////////////////////////
RemoveAll proc
  push esi
  mov esi,head
  .while esi
   mov current,esi
   mov esi,(DList ptr[esi]).next
   invoke GlobFreeMem,current ;将链表的内存全部回收到缓冲区中.
  .endw
  mov leftNumber,0 
  mov rightNumber,0   ;使左右节点值为0.
  pop esi
  ret
RemoveAll endp
;////////////////////////////////////////////////////////////
;将原来的链表全部清除,然后重新初始化一个链表,并建立头节点.
;////////////////////////////////////////////////////////////
Clear  proc
  call RemoveAll   ;清空整个链表.
  call Init    ;初始化一个头节点.
  ret
Clear  endp
;////////////////////////////////////////////////////////////
;用于对双向链表进行插入的操作.这个函数比较复杂,因为它不仅要
;创建一个节点,并且给它赋值,而且同时还要考虑插入的这个节点的前
;驱节点以及后继节点,而且要修改该节点之前的节点的后继节点,以及
;后面的那个节点(如果有的话)的前驱节点.
;////////////////////////////////////////////////////////////
Insert  proc uses esi ebx dwVal:dword
  mov esi,current   ;esi指向当前节点.
  mov ebx,(DList ptr[esi]).next ;ebx指向之后的节点,那么要插入的节点就要放在这两个节点之间.
  call GlobCreateMem
  or eax,eax
  je quit
  push dwVal
  pop (DList ptr[eax]).value  ;赋值.
  mov (DList ptr[eax]).prev,esi ;前驱节点.
  mov (DList ptr[eax]).next,ebx ;后继节点.
  mov (DList ptr[esi]).next,eax ;当前节点的后继节点.
  .if ebx
   mov (DList ptr[ebx]).prev,eax ;后面那个节点的前驱节点.
  .else
   mov tail,eax  ;如果节点是插入到最后,那么修改tail指针.
  .endif
  inc rightNumber   ;右边节点数加1.
  or eax,1    ;返回1.
quit:
  ret
Insert  endp
;////////////////////////////////////////////////////////////
;在表尾添加一个节点,即追加一个节点.
;////////////////////////////////////////////////////////////
Append  proc uses esi dwVal:dword
  mov esi,tail
  call GlobCreateMem   ;创建一个节点.
  or eax,eax
  je quit
  push dwVal
  pop (DList ptr[eax]).value
  mov (DList ptr[eax]).prev,esi
  mov (DList ptr[eax]).next,NULL ;赋值.
  mov (DList ptr[esi]).next,eax
  mov tail,eax   ;调整尾指针的位置.
  inc rightNumber   ;右节点数加一.
  or eax,1    ;返回1.
quit:       ;返回0.
  ret
Append  endp
;////////////////////////////////////////////////////////////
;删除一个节点.它将当前节点之后的节点删除.
;////////////////////////////////////////////////////////////
Removed  proc uses esi ebx edx pdwVal:ptr dword
  mov esi,current
  mov esi,(DList ptr[esi]).next ;esi指向要删除的节点.
  .if esi
   mov ebx,pdwVal
   push (DList ptr[esi]).value
   pop dword ptr[ebx]  ;返回要删除节点的值.
   mov ebx,current  ;ebx指向当前节点.
   mov edx,(DList ptr[esi]).next ;edx指向删除节点之后的节点.
   mov (DList ptr[ebx]).next,edx ;定位当前节点的后继节点.
   .if edx
    mov (DList ptr[edx]).prev,ebx ;定位后面的前驱节点.
   .else
    mov tail,ebx ;如果删除的是尾节点,那么定位尾节点指针.
   .endif
   invoke GlobFreeMem,esi  ;删除节点内存.
   dec rightNumber
   or eax,1
  .else
   xor eax,eax
  .endif
  ret
Removed  endp
;////////////////////////////////////////////////////////////
;将当前节点设成起始节点.
;////////////////////////////////////////////////////////////
SetStart proc uses esi eax
  mov esi,head
  mov current,esi   ;设置当前位置为头节点.
  mov eax,leftNumber
  add rightNumber,eax   ;右边节点数为总节点数.
  mov leftNumber,0   ;左边节点数为0.
  ret
SetStart endp
;////////////////////////////////////////////////////////////
;将当前节点设成尾节点.
;////////////////////////////////////////////////////////////
SetEnd  proc uses esi eax
  mov esi,tail
  mov current,esi   ;设置当前位置为尾节点.
  mov eax,rightNumber
  add leftNumber,eax   ;左边节点数为总节点数.
  mov rightNumber,0   ;右边节点数为-
  ret
SetEnd  endp
;////////////////////////////////////////////////////////////
;向后退一个节点.
;////////////////////////////////////////////////////////////
Prev  proc uses esi
  mov esi,current
  cmp esi,head
  je quit    ;如果当前节点为头节点,那么退出.
  mov esi,(DList ptr[esi]).prev
  mov current,esi   ;向后移一个节点.
  dec leftNumber
  inc rightNumber   ;左节点减一,右节点加一.
quit:
  ret
Prev  endp
;////////////////////////////////////////////////////////////
;向前进一个节点.
;////////////////////////////////////////////////////////////
Next  proc uses esi
  mov esi,current
  cmp esi,tail
  je quit    ;如果当前节点为尾节点,那么退出.
  mov esi,(DList ptr[esi]).next
  mov current,esi   ;向前进一个节点.
  inc leftNumber
  dec rightNumber   ;左节点加一,右节点减一.
quit:
  ret
Next  endp
;////////////////////////////////////////////////////////////
;设置当前节点.
;////////////////////////////////////////////////////////////
SetPos  proc uses esi ecx dwPos:dword
  mov eax,leftNumber
  add eax,rightNumber   ;eax=节点总和.
  .if dwPos < 0 || dwPos > eax
   xor eax,eax
   ret
  .endif     ;如果形参不适合,那么返回false.
  mov esi,head
  xor ecx,ecx
  .while ecx < dwPos
   mov esi,(DList ptr[esi]).next
   inc ecx
  .endw
  mov current,esi   ;得到当前节点指针.
  push dwPos
  pop leftNumber
  sub eax,dwPos
  mov rightNumber,eax   ;调整左右节点数目.左节点数=dwPos,右节点数=总节点数-dwPos
  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 ebx pdwVal:ptr dword
  mov esi,current
  mov esi,(DList ptr[esi]).next
  or esi,esi
  je quit    ;当前节点为尾节点.
  mov ebx,pdwVal
  push (DList ptr[esi]).value
  pop dword ptr[ebx]   ;返回要得到的值.
quit:
  ret
GetValue endp
;////////////////////////////////////////////////////////////
;输出链表所有节点的值.
;////////////////////////////////////////////////////////////
Print  proc uses esi eax
  mov esi,head
  mov esi,(DList ptr[esi]).next
  .while esi
   mov eax,(DList ptr[esi]).value
   call WriteDec
   mov al,' '
   call WriteChar
   mov esi,(DList ptr[esi]).next ;输出节点值.
  .endw
  call Crlf
  ret
Print  endp
;////////////////////////////////////////////////////////////
;对链表进行排序.
;////////////////////////////////////////////////////////////
Paixu  proc uses esi ebx eax
  mov esi,head
  mov esi,(DList ptr[esi]).next  ;指向第一个有用的节点.
  .while esi
   mov ebx,(DList ptr[esi]).next
   .while ebx
    mov eax,(DList ptr[esi]).value
    cmp eax,(DList ptr[ebx]).value
    jbe next
     xchg eax,(DList ptr[ebx]).value
     mov (DList ptr[esi]).value,eax ;如果前一个节点的值大于后一个节点的值,那么交换两个节点值.
next:
    mov ebx,(DList ptr[ebx]).next
   .endw
   mov esi,(DList ptr[esi]).next
  .endw
  ret
Paixu  endp

下面是一个测试程序:
;////////////////////////////////////////////////////////////
;对双向链表的测试.
;////////////////////////////////////////////////////////////
main  proc
  local dwTemp:dword
  call Clear    ;清空链表.
  invoke Insert,3
  invoke Insert,2
  invoke Insert,1
  invoke Append,4
  invoke Print    ;用于测试插入,追加,以及输出操作.
  invoke SetPos,3
  invoke Removed,addr dwTemp
  invoke Print
  mov eax,dwTemp
  call WriteDec
  call Crlf    ;用于测试定位节点,以及删除节点操作.
  call SetStart
  invoke Insert,5
  call SetEnd
  invoke Insert,6
  call Print    ;用于测试当前节点设成头以及尾节点.
  invoke SetPos,2
  call Prev
  invoke GetValue,addr dwTemp
  mov eax,dwTemp
  call WriteDec
  mov al,' '
  call WriteChar
  invoke SetPos,2
  call Next
  invoke GetValue,addr dwTemp
  mov eax,dwTemp
  call WriteDec
  call Crlf    ;用于测试向前以及向后节点操作.
  call LeftLength
  call WriteDec
  mov al,' '
  call WriteChar
  call RightLength
  call WriteDec   ;当前节点为2,输出左右节点个数.
  mov al,' '
  call WriteChar
  call ItemNumber
  call WriteDec
  call Crlf
  call Clear    ;初始化链表.
  mov ecx,5
temp1:
  push ecx
  invoke Append,ecx
  pop ecx
  loop temp1    ;创建一个五个节点的链表.
  call Print
  call Paixu
  call Print    ;输出以及排序输出.
  call ItemNumber
  mov ecx,eax
temp2:
  push ecx
  push eax
  sub eax,ecx
  invoke SetPos,eax
  invoke GetValue,addr dwTemp
  mov eax,dwTemp
  call WriteDec
  mov al,' '
  call WriteChar   ;输出当前节点的值.
  pop eax
  pop ecx
  loop temp2
  call Crlf
  call RemoveAll   ;将所有节点放入缓冲区中.
  call FreeMemory   ;真正释放内存.
  invoke ExitProcess,NULL
main  endp
  end main
输出结果与单向链表一样.

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