汇编网

帐号密码


多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页首页上一页下一页尾页

算法讲堂
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。现本栏目的内容处于不断添加中，请随时关注。

算法讲堂－》循环链表【源代码】

    assume cs:code
data segment
MTa     db      256 dup (0)             ;存储空间映射表
Mem     db      256 dup ( 16 dup (0))    ;存储空间

buf     db      256 dup (?)              ;
List    dw      0
list1   dw      0
Point   dw      0
idx     dw      1
elem    dw      61h

data ends
code segment

start:
        mov ax,data
        mov ds,ax

        call simp

exit:   mov ax,4c00h
        int 21h

;++++++++++++++++++++++++++++++++
;基本操作  circular linked list
;++++++++++++++++++++++++++++++++
;建立表：
;               申请空间
;               初始化数据
;参数：         无
;返回值         bx  表的地址
;               ax 0 成功  1 失败
;____________________________________
InitList:
        lea  si,mem
        call Alloc
        cmp  ax,0
        jne  initret
        ;初始化
        mov  word ptr ds:[bx+si][0],0  ;长度
        mov  word ptr ds:[bx+si][2],0  ;头指针
        mov  word ptr ds:[bx+si][4],0  ;尾指针
initret:
        ret
;+++++++++++++++++++++++++++++
;销毁表
;参数:(栈传递)          表地址
;返回值                 无
;-----------------------------------
DestroyList:
        push bp
        mov  bp,sp
        mov  bx,[bp+4]
        push bx
        call clearlist
        mov  bx,[bp+4]
        call free
        mov  sp,bp
        pop  bp
        ret  2
;+++++++++++++++++++++++++++++
;建立结点
;                       申请空间
;                       初始化数据
;参数:                  无
;返回值:                        地址  bx
;------------------------------
MakeNode:
        push si
        call Alloc
        cmp ax,0
        jne makeret
        lea si,mem
        mov word ptr ds:[bx+si][0],0  ;数据域
        mov word ptr ds:[bx+si][2],0  ;后继
        pop si
makeret:ret
;+++++++++++++++++++++++++++++
;销毁结点
;参数:(栈传递)          地址
;返回                   无
;-----------------------------------
RuinNode:
        push bp
        mov bp,sp
        mov bx,[bp+4]
        call free
        mov sp,bp
        pop bp
        ret
;+++++++++++++++++++++++++++++
;插入结点
;参数:(栈传递)          表地址,位置,数据
;返回值:                        ah=0成功 , (al) = idx
;                       ah=1失败
;-------------------------------------
InsertList:
        push bp
        mov  bp,sp
        sub  sp,2
        push si
        push di
        push bx
        push dx
        mov  si,[bp+4]

        mov bx,offset mem
        mov ax,[bx+si]           ;length
        mov [bp-2],ax
        cmp word ptr [bp+6],1
        jb   insfail
        inc ax
        cmp [bp+6],ax
        ja  insfail

        call makenode
        cmp  ax,0
        je   lnslistgoon
        jmp insfail
lnslistgoon:
        mov  point,bx
        mov bx,offset mem

        mov di,[bx+si+4]         ;tail
        xor dx,dx
        mov dx,1
        jmp inscmp
insloop:
        inc dx
        mov di,[bx+di+2]
inscmp:
        cmp  dx,[bp+6]
        jb  insloop
        mov ax,[bx+di+2]        ;di->next
        mov si,point
        mov [bx+si+2],ax        ;new->next =
        mov ax,[bp+8]           ;元素值
        mov [bx+si],ax          ;new->data
        mov [bx+di+2],si        ;p->next = new
        cmp word ptr [bp+6],1   ;idx==1?
        jne insnothead
        cmp word ptr [bp-2],0   ;idx==1&&length==0?
        jne insnotemp
        mov [bx+si+2],si        ;nen->next=new
insnotemp:
        mov di,[bp+4]
        mov [bx+di+2],si        ;head = new
insnothead:mov ax,[bp-2]        ;length+1
        inc ax
        cmp ax,[bp+6]
        jne insnottail
        mov di,[bp+4]
        mov [bx+di+4],si        ;tail = new
insnottail:
        mov si,[bp+4]
        inc word ptr [bx+si]    ;length++
        mov ax,[bp+6]
        jmp inssucc
insfail:mov ax,0100h
inssucc:pop dx
        pop bx
        pop di
        pop si
        mov sp,bp
        pop bp
        ret 6
;+++++++++++++++++++++++++++++
;追加
;参数:(栈传递)          表地址，数据
;返回值：                ah = 0  成功
;                       ah = 1  失败
;-----------------------------------
appendlist:
        push bp
        mov bp,sp
        push si
        push di
        push bx
        ;push ax
        call makenode
        cmp  ax,0
        je  appenlistgoon
        mov ah,1
        jmp appendlistret
appenlistgoon:
        mov  point,bx
        mov bx,offset mem
        mov si,[bp+4]
        mov di,point
        mov ax,[bp+6]
        mov [bx+di],ax          ;new新结点的数据

        ;cmp word ptr [bx+si+2],0
        cmp word ptr [bx+si],0
        je  appempty
        mov ax,[bx+si+2]        ;head 所指
        mov [bx+di+2],ax        ;作为new后继结点
        push si
        mov si,[bx+si+4]        ;tail指向结点
        mov [bx+si+2],di        ;后继设为new
        pop si
        jmp applen
appempty:mov [bx+di+2],di       ;new后继是new自身
        mov [bx+si+2],di        ;head指向new
applen: mov [bx+si+4],di        ;tail 指向 new
        inc word ptr [bx+si]    ;length+1
        mov ax,[bp+6]
appendlistret:
        ;pop ax
        pop bx
        pop di
        pop si
        mov sp,bp
        pop bp
        ret 4
;+++++++++++++++++++++++++++++
;删除结点
;参数:(栈传递)          表地址,位置
;返回值:                        ah = 1 失败
;                       ah = 0 成功
;-----------------------------------
deletelist:
        push bp
        mov bp,sp
        push di
        push si
        push bx
        push cx
        push dx
        mov bx,offset mem
        mov si,[bp+4]
        ;  (idx<1||idx>length)
        mov dx,[bx+si]
        cmp dx,1
        jl  delfail
        cmp dx,[bp+6]
        jl  delfail
        ;  while(idx<length)
        xor cx,cx
        mov cx,1
        mov di,[bx+si+4]        ;di=tail
        jmp delcmp
delloop:inc cx
        mov di,[bx+di+2]        ;di= di->next

delcmp: cmp cx,[bp+6]
        jb  delloop

        mov  point,di           ;保存di0
        push [bx+di+2]          ;di0的后继,等待释放
                                ;也是ruinnode的参数
        mov di,[bx+di+2]
        mov ax,[bx+di+2]        ;di0后继的后继
        mov di,point
        mov [bx+di+2],ax

        call ruinnode
        mov bx,offset mem
        cmp word ptr [bp+6],1    ;idx==1?
        jne delnothead
        ;idx==1;
        mov si,[bp+4]
        mov [bx+si+2],ax        ;head = di0后继的后继
delnothead:
        cmp [bp+6],dx           ;idx==length?;
        jne delnottail
        ;idx==length;
        mov ax,point
        mov [bx+si+4],ax        ;tail = di0
delnottail:dec word ptr [bx+si]
        cmp word ptr [bx+si],0
        jne delnotempty
        mov word ptr [bx+si+2],0
        mov word ptr [bx+si+4],0
delnotempty:
        mov ah,0
        mov al,[bp+6]
        jmp delok

delfail: mov ax,0100h
delok:  pop dx
        pop cx
        pop bx
        pop di
        pop si
        mov sp,bp
        pop bp
        ret 4
;+++++++++++++++++++++++++++++
;清空表
;参数:(栈传递)          表地址
;--------------------------------
clearlist:
        push bp
        mov  bp,sp
        push bx
        push si
        mov  bx,[bp+4]
clecon:
        xor  si,si
        mov  si,1
        push si
        push bx
        call deletelist
        cmp  ah,1
        jne  clecon
        pop  si
        pop  bx
        mov  bp,sp
        pop  bp
        ret  2
;++++++++++++++++++++++++++++++++++++
;取得结点数据
;参数：(栈传递)          表地址，位置
;返回值                 dx = 数据，ah =0 成功
;                       ah=1 失败
;------------------------------------
getelement:
        push bp
        mov bp,sp
        sub sp,4
        push bx
        push si
        push di
        mov bx,offset mem
        mov si,[bp+4]
        mov ax,[bx+si]          ;bx+si 表地址 0 长度 2 头指针 4 尾指针
        mov [bp-2],ax           ;length 入栈
        mov ax,[bx+si+4]
        mov [bp-4],ax           ;tail 入栈
        xor si,si
        mov si,1
        mov ax,[bp+6]
        cmp ax,si               ;[bp+4] = idx
        jl  getFail
        cmp ax,[bp-2]
        jg  getFail

        mov di,[bp-4]           ;di = tail
        jmp getcmpare
getadd: inc si
        mov di,[bx+di+2]
getcmpare:cmp si,[bp+6]         ;si<idx
        jle getadd

        mov dx,[bx+di]
        mov ax,0
        jmp getok

getFail:
        mov ah,1
getok:  pop di
        pop si
        pop bx
        mov sp,bp
        pop bp
        ret 4

;+++++++++++++++++++++++++++++**
;更新
;参数:(栈传递)           表地址，位置，新数据
;返回值                  ah=1 失败   ah =0 成功
;-------------------------------
updatelist:
        push bp
        mov bp,sp
        sub sp,4
        push bx
        push si
        push di
        mov bx,offset mem
        mov si,[bp+4]
        cmp word ptr [bx+si],0
        je setFail
        mov ax,[bx+si]  ;
        mov [bp-2],ax           ;length 入栈
        mov ax,[bx+si+4]
        mov [bp-4],ax           ;tail 入栈
        xor si,si
        mov si,1
        mov ax,[bp+6]
        cmp ax,si               ;[bp+4] = idx
        jl  setFail
        cmp ax,[bp-2]
        jg  setFail

        mov di,[bp-4]           ;di = tail
        jmp setcmpare
setadd: inc si
        mov di,[bx+di+2]
setcmpare:cmp si,[bp+6]         ;si<idx
        jle setadd

        mov ax,[bp+8]
        mov [bx+di],ax
        mov ax,1
        jmp setok

setFail:mov ah,1
        jmp setret
setok:  mov ax,[bp+6]
setret: pop di
        pop si
        pop bx
        mov sp,bp
        pop bp
        ret 6
;+++++++++++++++++++++++++++++++++
;检索特定结点的first索引
;参数: (栈传递)         表地址，数据
;返回值：                ah=0成功 , al  索引
;                       ah=0 失败
;---------------------------------
findElemOf:
        push bp
        mov bp,sp
        sub sp,4
        push bx
        push si
        push di
        mov bx,offset mem
        mov si,[bp+4]
        mov ax,[bx+si]          ;bx+si 表地址
        mov [bp-2],ax           ;length 入栈
        mov ax,[bx+si+4]
        mov [bp-4],ax           ;*tail 入栈
        xor si,si
        ;mov si,1

        mov di,[bp-4]           ;di = tail
        jmp findcmpare
findadd:        inc si
        mov di,[bx+di+2]
        ;\\\\\\\\\\\\\\\\选择条件\\\\\\\\\\\
        mov ax,[bx+di]
        cmp ax,[bp+6]
        je  findfirst
        ;////////////相等///////
findcmpare:
        cmp si,[bp-2]  ;si<
        jnb  findfail
        jmp findadd
findfirst:
        mov ax,si
        mov ah,0
        jmp findok

findFail:mov ax,0100h

findok:  pop di
        pop si
        pop bx
        mov sp,bp
        pop bp
        ret 4

;+++++++++++++++++++++++++++++
;遍历
;参数：(栈传递)          表地址
;-----------------------------
traverse:
        push bp
        mov bp,sp
        sub sp,2
        push si
        push di
        push cx
        mov bx,offset mem
        mov si,[bp+4]
        mov ax,[bx+si]                  ;length
        mov [bp-2],ax
        xor cx,cx
        lea di,buf                      ;store elem value
        jmp tracmp
traloop:inc cx
        mov si,[bx+si+2]                ;p=p->next
        ;////对结点数据进行操作,保存到buf////
        mov ax,[bx+si]
        mov [di],ax
        inc di
        tracmp:cmp cx,[bp-2]
        jb traloop
        pop cx
        pop di
        pop si
        mov sp,bp
        pop bp
        ret  2

;++++++++++++++++++++++++++++++++++++++++
;功能：合并
;参数：(栈传递)          表地址1 ，表地址2
;返回值：                bx
;----------------------------------------
union:
        push bp
        mov  bp,sp
        push si
        push di
        push ax
        push dx
        mov  bx,offset mem
        mov  si,[bp+4]                  ;list1
        mov  di,[bp+6]                  ;list2
        mov  ax,[bx+di]         ;list2->length
        add  [bx+si],ax         ;length = list1->length+list2->length
        mov ax,[bx+di+2]        ;list2->head
        mov dx,[bx+di+4]        ;list2->tail
        push si
        mov si,[bx+si+4]        ;si=list->tail
        mov [bx+si+2],ax        ;list1->tail->next = list2->head
        pop si
        mov [bx+si+4],dx        ;list1->tail=list2->tail
        mov ax,[bx+si+2]        ;list1->head
        push di
        mov di,dx
        mov [bx+di+2],ax        ;list2->tail->next=list1->head
;       free (list2)
        mov bx,[bp+6]
        call free
        mov bx,[bp+4]
        pop dx
        pop ax
        pop di
        pop si
        mov sp,bp
        pop bp
        ret 4
;+++++++++++++++++++++++++++++++++
;取得表中结点个数
;参数:                  si
;返回值:                        cx
;---------------------------------
lengthof:
        push bx
        lea bx,mem
        mov cx,[bx+si]
        pop bx
        ret
;+++++++++++++++++++++++++++++++++
;申请一块内存空间
;参  数:                        无
;返回值:                        bx 空间地址
;-----------------------------------
Alloc:
        xor bx,bx
        lea bx,mta
allocing:
        cmp word ptr ds:[bx],0
        jne alloccon
        mov byte ptr ds:[bx],1
        shl bx,1
        shl bx,1
        shl bx,1
        shl bx,1
        mov ax,0
        jmp allocret
alloccon:
        inc bx
        cmp bx,256           ;最多可分配256个空间单位
        jne allocing
        xor ax,ax
        mov ax,1
allocret:
        ret
;+++++++++++++++++++++++++++++
;释放内存空间
;参  数;                bx 空间地址
;返回值:                无
;-----------------------------------;
free:
        shr  bx,1
        shr  bx,1
        shr  bx,1
        shr  bx,1
        and  bx,00fffh
        cmp  bx,256             ;max=256
        jnb  freefail
        lea  si,mta
        cmp  byte ptr ds:[bx+si+0],1
        jne  freefail
        mov  byte ptr ds:[bx+si],0
freefail:
        ret
;++++++++++++++++++++++++++++++

;-----------------------------
simp:
        ;函数调用例程

        ;建立表
        call initlist                   ;建立一个表
        mov  ds:[list],bx               ;返回 bx

        ;插入元素
        mov ax,'n'                      ;插入结点
        push ax
        mov ax,1
        push ax
        push list
        call InsertList

        mov ax,'s'                      ;插入结点
        push ax
        mov ax,2
        push ax
        push list
        call InsertList

        mov ax,'i'                      ;插入结点
        push ax
        mov ax,1
        push ax
        push list
        call InsertList

        ;遍历表 ,验证插入操作
        push list
        call traverse

        ;追加元素
        push elem
        push list
        call appendlist

        push list                       ;遍历,验证追加操作
        call traverse

        ;删除元素
        push idx
        push list
        call deletelist

        push list                       ;遍历,验证删除操作
        call traverse

        ;读取结点数据
        push idx
        push list                       ;返回 dx
        call getelement

        ;更新元素
        push elem
        push idx
        push list
        call updatelist

        push list                       ;遍历,验证删除操作
        call traverse

        ;寻找特定元素
        push elem
        push list
        call findElemOf                 ;返回 ax

        ;建立表
        call initlist                   ;建立第二个表,准备合并
        mov  ds:[list1],bx
                                        ;unni
        mov ax,'u'
        push ax
        mov ax,1
        push ax
        push list
        call InsertList
        mov ax,'n'
        push ax
        mov ax,2
        push ax
        push list
        call InsertList
        mov ax,'n'
        push ax
        mov ax,2
        push ax
        push list
        call InsertList
        mov ax,'i'
        push ax
        mov ax,3
        push ax
        push list
        call InsertList
        ;合并
        push list1
        push list
        call union

        ;遍历表,验证删除操作
        push list
        call traverse

        ;取结点数量
        call lengthof                   ;返回 cx

        ;清空表
        push list
        call clearlist

        ;销毁表
        push list
        call destroylist
        ret

;------------结束------------------

code ends
     end  start

[07/09/29]

Email: asmedu@163.com