帐号 密码  
 
多路树查找-外部查找(B树)【源代码】

多路树查找-外部查找(B树)【下载及演示说明】

双向链表演示程序【下载及演示说明】

循环链表演示程序【下载及演示说明】

链表【讲解】

动态存储分配之边界标识法演示程序【下载及演示说明】

动态存储分配之边界标识法【讲解】

首次适应算法和最佳适应算法【讲解】

动态存储分配之边界标识法【源代码】

振荡排序算法【讲解】

振荡排序演示程序【下载及演示说明】

树和二叉树相互转化【讲解】

深度优先搜索【下载及演示说明】

深度优先搜索【源代码】

朴素字符串匹配演示程序【下载及演示说明】

当前1/4页
首页 上一页 下一页 尾页

算法讲堂

    本栏目所有文章由本站组织业内技术专家原创而成,用汇编语言向学习者讲解经典问题的编程思想和编程方法。

    本栏目所有文章的版权归本站所有,转载请注明出处为汇编网<www.asmedu.net> 。

    现本栏目的内容处于不断添加中,请随时关注。
算法讲堂-》多路树查找-外部查找(B树)【源代码】
    assume cs:code,ds:data,ss:stack

data segment

    ;存储B树
    ;关键字个数,父指针,关键字数组,儿子指针数组,
    BTRD  db 256 dup(0)

    ;构建树的原始数据
    NODED db 45,24,3,12,37,53,90,50,61,70,99,'#'
    
    ;根指针
    BOOT  db 0
    
    ;节点数量
    NODENUM db 0
    
    SIGN db 8
    
    TEMP dw 0,0
    
    ;变量
    BTRV  db 16 dup(0)
    
    RIGHT db "Copyright (c) 2007 www.asmedu.net#"
    
data ends

stack segment stack

    dw 32 dup(0)
    
stack ends

code segment
start:
        mov ax,data
        mov ds,ax
        mov si,0
        
        mov ax,stack
        mov ss,ax
        mov sp,0
        
        mov byte ptr NODENUM[0],0
        mov byte ptr BOOT[0],-1
        
        call CreateTree
        
        mov byte ptr BTRV[0],68
        call InsertNode
        
        mov byte ptr BTRV[0],12
        call SearchNode
        
        mov byte ptr BTRV[0],3
        call DelBNode
        
        mov ax,4c00h
        int 21h
        
;-----------------------------------CreateTree start
        ;根据ds:[si]的数据位置创建一棵3阶B树
        ;这里把阶定义为非根节点中子树的最大数目。
CreateTree:
        push ax
        push si
        
        mov si,0
CBTS:
        cmp byte ptr NODED[si],'#'
        je CBTRe
        mov al,NODED[si]
        mov BTRV[0],al
        call InsertNode
        inc si
        jmp CBTS
CBTRe:
        pop si
        pop ax
        ret
        
;-----------------------------------CreateTree end

;-----------------------------------SearchNode start
        ;前序遍历在B树中查找关键字
        ;BTRV[0]存储要查找的关键字
        ;BTRV[1]返回值 1不存在树,2不存在关键字
        ;找到返回BTRV[1]节点的位置,BTRV[2]关键字在节点中的位置
SearchNode:
        push ax
        push bx
        push cx
        push dx
        push di
        push si
        
        mov bx,0
        mov bl,BOOT[0]
        ;是否存在树
        cmp byte ptr BOOT[0],-1
        jne SNS
        ;未找到
        mov byte ptr BTRV[1],1
        jmp SNReturn
        ;查找当前节点是否有关键字
SNS:
        mov byte ptr BTRD[bx + 2],0
        mov cx,0
        mov cl,BTRD[bx]
        mov di,0
        mov al,BTRV[0]
SNS1:
        cmp BTRD[bx + di + 3],al
        je SNS2
        inc di
        loop SNS1
        jmp SNS3
SNS2:
        ;找到返回
        mov BTRV[1],bl
        mov ax,di
        mov BTRV[2],al
        jmp SNReturn
        ;当前节点是底层节点?
SNS3:
        cmp byte ptr BTRD[bx + 6],-1
        je SNS4
        inc byte ptr BTRD[bx + 2]
        mov ax,0
        mov al,BTRD[bx + 6]
        mov bx,ax
        jmp SNS
        ;返回到父节点,父节点是否还有未访问的孩子
SNS4:
        cmp byte ptr BTRD[bx + 1],-1
        je SNS6
        mov ax,0
        mov al,BTRD[bx + 1]
        mov bx,ax
        mov al,BTRD[bx + 2]
        cmp al,BTRD[bx]
        ja SNS5
        ;孩子为当前节点
        mov ax,0
        mov di,0
        mov al,BTRD[bx + 2]
        add di,ax
        mov al,BTRD[bx + di + 6]
        inc byte ptr BTRD[bx + 2]
        mov bx,ax
        jmp SNS
        
        ;当前节点没有未访问的孩子
        ;当前节点是根
SNS5:
        cmp byte ptr BTRD[bx + 1],-1
        je SNS6
        jmp SNS4
SNS6:
        ;未找到
        mov byte ptr BTRV[1],2
        
SNReturn:
        pop si
        pop di
        pop dx
        pop cx
        pop bx
        pop ax
        ret
;-----------------------------------SearchNode end

;-----------------------------------InsertNode start
        ;在B树中插入关键字
        ;BTRV[0]存储要插入的关键字
        ;BTRV[1]存储返回值,1关键字已存在,2超过16个结点,3插入成功
InsertNode:
        push ax
        push bx
        push di
        push si
        push cx
        
        mov bx,0
        mov di,0
        mov bl,BOOT[0]
        ;是否存在树
        cmp byte ptr BOOT[0],-1
        jne INS
        ;不存在树
        mov bx,0
        mov byte ptr BTRD[bx],1
        mov byte ptr BTRD[bx + 1],-1
        mov byte ptr BTRD[bx + 2],0
        mov al,BTRV[0]
        mov byte ptr BTRD[bx + 3],al
        mov byte ptr BTRD[bx + 6],-1
        mov byte ptr BTRD[bx + 10],1
        mov byte ptr BOOT[0],0
        mov byte ptr BTRV[1],3
        inc byte ptr NODENUM[0]
        jmp INReturn
        ;存在树
        ;查找在当前节点中是否已存在关键字
INS:
        mov cx,0
        mov cl,BTRD[bx]
        mov al,BTRV[0]
        mov di,0
INS1:
        cmp BTRD[bx + di + 3],al
        je INS2
        inc di
        loop INS1
        jmp INS3
        ;关键字已存在
        ;提示关键字已存在不可插入
INS2:
        mov byte ptr BTRV[1],1
        jmp INReturn
        ;当前节点是底层节点
INS3:
        cmp byte ptr BTRD[bx + 6],-1
        je INS6
        ;在当前节点找到合适位置向下搜索,选中的孩子为当前节点
        mov cx,0
        mov cl,BTRD[bx]
        mov al,BTRV[0]
        mov di,0
INS4:
        cmp BTRD[bx + di + 3],al
        ja INS5
        inc di
        loop INS4
        ;找到合适位置向下搜索
INS5:
        mov ax,0
        mov al,BTRD[bx + di + 6]
        mov bx,ax
        jmp INS
        ;是底层节点
        ;找到合适位置插入关键字
INS6:
        cmp byte ptr BTRD[bx],2
        jb INS18
        cmp byte ptr NODENUM[0],16
        jb INS18
        mov byte ptr BTRV[1],2
        jmp INReturn
INS18:
        mov byte ptr BTRV[1],3
        mov cx,0
        mov cl,BTRD[bx]
        mov al,BTRV[0]
        mov di,0
INS7:
        cmp BTRD[bx + di + 3],al
        ja INS8
        inc di
        loop INS7
INS8:
        ;插入节点
        call Insert
        ;关键字个数 > m - 1
INS10:
        cmp byte ptr BTRD[bx],3
        ;插入成功
        jb INR
        jmp INR1
INR:
        mov byte ptr BTRV[1],3
        jmp INReturn
INR1:
        ;当前节点是根?
        cmp byte ptr BTRD[bx + 1],-1
        jne INS12
        ;当前节点是根
        ;中间关键字生成新根,原节点分裂成两个新节点
        ;对新根的处理
        call Malloc
        mov ax,0
        mov al,BTRV[1]
        mov BOOT[0],al
        mov di,ax
        mov al,BTRD[bx + 4]
        mov BTRD[di + 3],al
        mov byte ptr BTRD[di],1
        mov byte ptr BTRD[di + 1],-1
        mov byte ptr BTRD[di + 2],0
        mov BTRD[di + 6],bl
        mov byte ptr BTRV[2],0
        mov byte ptr BTRV[3],0
        jmp INS11
        
        ;当前节点不是根
        ;插入父节点中
INS12:
        mov ax,0
        mov al,BTRD[bx + 1]
        mov di,ax
        push di
        mov al,0
INS15:
        cmp BTRD[di + 6],bl
        je INS16
        inc al
        inc di
        jmp INS15
INS16:
        mov di,ax
        mov BTRV[3],al
        mov al,BTRD[bx + 4]
        mov BTRV[0],al
        pop ax
        push ax
        push bx
        mov bx,ax
        call Insert
        pop bx
        pop di
        mov byte ptr BTRV[2],1
        ;/////////////////////
INS11:
        mov byte ptr BTRD[bx],1
        mov ax,di
        mov BTRD[bx + 1],al
        ;分裂出的新节点的处理
        call Malloc
        push di
        mov ax,0
        mov al,BTRV[1]
        mov di,ax
        mov al,BTRD[bx + 5]
        mov BTRD[di + 3],al
        cmp byte ptr BTRD[bx + 6],-1
        jne INS13
        mov byte ptr BTRD[di + 6],-1
        jmp INS14
INS13:
        mov al,BTRD[bx + 8]
        mov BTRD[di + 6],al
        mov al,BTRD[bx + 9]
        mov BTRD[di + 7],al
        push bx
        mov bx,0
        mov ax,di
        mov bl,BTRD[di + 6]
        mov BTRD[bx + 1],al
        mov bl,BTRD[di + 7]
        mov BTRD[bx + 1],al
        pop bx
        
INS14:
        mov byte ptr BTRD[di],1
        mov byte ptr BTRD[di + 2],0
        pop ax
        mov si,ax
        mov bx,ax
        mov BTRD[di + 1],al
        mov ax,0
        mov al,BTRV[3]
        inc ax
        add si,ax
        mov ax,di
        mov BTRD[si + 6],al
        
        cmp byte ptr BTRV[2],0
        je INS19
        jmp INS10
INS19:
        mov byte ptr BTRV[1],3
INReturn:
        
        pop cx
        pop si
        pop di
        pop bx
        pop ax
        ret
        
;-----------------------------------InsertNode end

;-----------------------------------Malloc start
        ;在BTRD中寻找空间
        ;存储在BTRV[1]中
Malloc:
        push bx
        mov bx,0
MS:
        cmp byte ptr BTRD[bx + 10],1
        je MS1
        jmp MReturn
MS1:
        add bx,16
        jmp MS
        
MReturn:
        inc byte ptr NODENUM[0]
        mov byte ptr BTRD[bx],0
        mov byte ptr BTRD[bx + 2],0
        mov byte ptr BTRD[bx + 10],1
        mov BTRV[1],bl
        pop bx
        ret
        
;-----------------------------------Malloc end

;-----------------------------------Free start
        ;在BTRD中释放一个节点的空间
Free:
        mov byte ptr BTRD[bx + 10],0
        dec byte ptr NODENUM[0]
FReturn:
        ret
;-----------------------------------Free end

;-----------------------------------Insert start
        ;在节点内部插入
        ;bx指向当前节点,di关键字的位置
        ;BTRV[0]存储插入的关键字
Insert:
        push ax
        push cx
        push si
        
        mov ax,di
        cmp BTRD[bx],al
        jne IS
        mov al,BTRV[0]
        mov BTRD[bx + di + 3],al
        jmp IS1
        ;在内部插入
IS:
        mov cx,0
        mov cl,BTRD[bx]
        sub cx,di
        mov ax,0
        mov al,BTRD[bx]
        mov si,ax
        push di
        mov di,si
        dec di
IS2:
        mov al,BTRD[bx + di + 3]
        mov BTRD[bx + si + 3],al
        mov al,BTRD[bx + di + 7]
        mov BTRD[bx + si + 7],al
        dec di
        dec si
        loop IS2
        pop di
        mov al,BTRV[0]
        mov BTRD[bx + di + 3],al
IS1:
        inc byte ptr BTRD[bx]
IReturn:
        pop si
        pop cx
        pop ax
        ret
        
;-----------------------------------Insert end

;-----------------------------------DelBNode start
        ;在B树中删除节点
        ;BTRV[0]存储要删除的关键字
        ;BTRV[1]返回值1不存在树,2在整个树中未找到要删除的键,3删除成功
DelBNode:
        push ax
        push bx
        push cx
        push di
        push si
        
        mov bx,0
        mov bl,BOOT[0]
        mov byte ptr BTRV[1],0
        cmp byte ptr BOOT[0],-1
        jne DBNS
        mov byte ptr BTRV[1],1
        jmp DBNReturn
        ;在B树中查找关键字
        ;在当前节点查找要删除的关键字
DBNS:
        mov cx,0
        mov cl,BTRD[bx]
        mov al,BTRV[0]
        mov di,0
DBNS1:
        cmp BTRD[bx + di + 3],al
        je DBNS2
        ja DBNS3
        inc di
        loop DBNS1
        
        ;在当前节点找到合适位置向下搜索,选中的孩子为当前节点
DBNS3:
        cmp byte ptr BTRD[bx + 6],-1
        je DBNS4
        mov ax,0
        mov al,BTRD[bx + di + 6]
        mov bx,ax
        jmp DBNS
        ;在整个树中未找到要删除的键
DBNS4:
        mov byte ptr BTRV[1],2
        jmp DBNReturn
        ;找到关键字删除
        ;当前节点是底层节点?
DBNS2:
        cmp byte ptr BTRD[bx + 6],-1
        je DBNS5
        ;节点不是底层节点,替换操作
        ;找到这个节点的中序前驱节点
        push bx
        push di
        mov ax,0
        mov al,BTRD[bx + di + 6]
        mov bx,ax
DBNS15:
        cmp byte ptr BTRD[bx + 6],-1
        je DBNS14
        mov ax,0
        mov al,BTRD[bx]
        mov di,ax
        mov ax,0
        mov al,BTRD[bx + di + 6]
        mov bx,ax
        jmp DBNS15
        ;前驱节点的最大关键字上移到父关键字
DBNS14:
        mov si,bx
        pop di
        pop bx
        push si
        mov ax,0
        mov al,BTRD[si]
        dec al
        add si,ax
        mov al,BTRD[si + 3]
        mov BTRD[bx + di + 3],al
        pop bx
        dec byte ptr BTRD[bx]
        jmp DBNS12
        
        ;删除关键字,移位操作
DBNS5:
        dec byte ptr BTRD[bx]
        ;移位操作
        mov cx,0
        mov cl,BTRD[bx]
        sub cx,di
        cmp cx,0
        je DBNSS1
DBNSS:
        mov al,BTRD[bx + di + 4]
        mov BTRD[bx + di + 3],al
        inc di
        loop DBNSS
DBNSS1:
        cmp byte ptr BTRD[bx + 1],-1
        jne DBNS12
        ;当前节点是根
        cmp byte ptr BTRD[bx],0
        ja DBNS13
        mov byte ptr BOOT[0],-1
DBNS13:
        mov byte ptr BTRV[1],3
        jmp DBNReturn
        
        ;关键字是否 > = m / 2 - 1
DBNS12:
        cmp byte ptr BTRD[bx],1
        jb DBNS6
        ;删除结束
        mov byte ptr BTRV[1],3
        jmp DBNReturn
        ;当前节点关键字个数 < m / 2 - 1
        ;回溯到父节点
DBNS6:
        push bx
        mov ax,0
        mov al,BTRD[bx + 1]
        mov bx,ax
        pop ax
        mov cx,0
        mov cl,BTRD[bx]
        inc cx
        mov di,0
DBNS7:
        cmp BTRD[bx + di + 6],al
        je DBNS8
        inc di
        loop DBNS7
        
        ;这个节点是否存在右兄弟
DBNS8:
        mov ax,0
        mov al,BTRD[bx]
        cmp di,ax
        je DBNS18
        ;这个节点的右兄弟是否 > m / 2 - 1
        mov ax,0
        mov al,BTRD[bx + di + 7]
        mov si,ax
        cmp byte ptr BTRD[si],1
        jna DBNS9
        call MoveRightNode
        jmp DBNReturn
DBNS18:
        dec di
        mov TEMP[0],di
        jmp DBNS19
        ;是否存在左兄弟
DBNS9:
        cmp di,0
        je DBNS10
        mov TEMP[0],di
        dec di
        ;左兄弟节点关键字是否 > m / 2 - 1
DBNS19:
        mov ax,0
        mov al,BTRD[bx + di + 6]
        mov si,ax
        cmp byte ptr BTRD[si],1
        jna DBNS20
        call MoveLeftNode
        jmp DBNReturn
DBNS20:
        mov di,TEMP[0]
        ;合并
DBNS10:
        call JoinNode
        
        cmp byte ptr BTRD[bx + 1],-1
        jne DBNS21
        cmp byte ptr BTRD[bx],1
        jb DBNS16
        jmp DBNReturn
DBNS21:
        jmp DBNS12
DBNS16:
        mov ax,0
        mov al,BTRD[bx + 6]
        call Free
        mov bx,ax
        mov BOOT[0],al
        mov BTRD[bx + 1],-1
        
DBNReturn:
        
        pop si
        pop di
        pop cx
        pop bx
        pop ax
        ret
;-----------------------------------DelBNode end

;-----------------------------------JoinNode start
        ;左右孩子节点都 < = m / 2 - 1
        ;合并父关键字,与其对应的两个子树到左孩子
        ;把这个键右边的键和对应的右子树左移
JoinNode:
        push ax
        push bx
        push cx
        push di
        push si
        
        dec byte ptr BTRD[bx]
        ;把这个键下移到它的左子树
        mov ax,0
        mov al,BTRD[bx + di + 6]
        mov si,ax
        push si
        add al,BTRD[si]
        mov si,ax
        mov al,BTRD[bx + di + 3]
        mov BTRD[si + 3],al
        pop si
        inc byte ptr BTRD[si]
        ;把右子树中的所有键值和子树转移到左子树
        push di
        mov ax,0
        mov al,BTRD[bx + di + 7]
        mov di,ax
        push di
        push si
        mov ax,si
        add al,BTRD[si]
        mov si,ax
        mov cx,0
        mov cl,BTRD[di]
        cmp cx,0
        je JNSS4
JNSS:
        mov al,BTRD[di + 3]
        mov BTRD[si + 3],al
        mov al,BTRD[di + 6]
        mov BTRD[si + 6],al
        inc si
        inc di
        loop JNSS
JNSS4:
        mov al,BTRD[di + 6]
        mov BTRD[si + 6],al
        pop si
        pop di
        mov al,BTRD[di]
        add BTRD[si],al
        
        ;销毁右子树
        push bx
        mov bx,di
        push di
        cmp byte ptr BTRD[bx + 6],-1
        je JNSS3
        ;更新右子树转到左子树的节点的父指针
        mov cx,0
        mov cl,BTRD[di]
        mov bx,si
        inc cx
JNSS2:
        mov ax,0
        mov al,BTRD[di + 6]
        mov si,ax
        mov BTRD[si + 1],bl
        inc di
        loop JNSS2
JNSS3:
        pop bx
        call Free
        pop bx
        pop di
        
        ;这个节点右边的关键字和对应的右子树向左移动
        mov cx,0
        mov cl,BTRD[bx]
        sub cx,di
        cmp cx,0
        je JNReturn
JNSS1:
        mov al,BTRD[bx + di + 4]
        mov BTRD[bx + di + 3],al
        mov al,BTRD[bx + di + 8]
        mov BTRD[bx + di + 7],al
        inc di
        loop JNSS1
        
JNReturn:
        pop si
        pop di
        pop cx
        pop bx
        pop ax
        ret
        
;-----------------------------------JoinNode end

;-----------------------------------MoveRightNode start
        ;从一个键的右子树向左子树转移一个键,使两个子树平衡
        ;右孩子节点 > m / 2 - 1
        ;右孩子中最小的关键字上移到父关键字
MoveRightNode:
        push ax
        push cx
        push si
        ;把这个键下移到它的左子树
        mov ax,0
        mov al,BTRD[bx + di + 6]
        mov si,ax
        push si
        add al,BTRD[si]
        mov si,ax
        mov al,BTRD[bx + di + 3]
        mov BTRD[si + 3],al
        pop si
        inc byte ptr BTRD[si]
        ;把右子树的最左子树转移成左子树的最右子树
        push di
        mov ax,0
        mov al,BTRD[bx + di + 7]
        mov di,ax
        cmp byte ptr BTRD[di + 6],-1
        je MRNS
        ;左右子树不是底层节点
        push si
        mov ax,si
        add al,BTRD[si]
        mov si,ax
        mov ax,0
        mov al,BTRD[di + 6]
        mov BTRD[si + 6],al
        pop si
        push di
        mov di,ax
        mov cx,si
        mov BTRD[di + 1],cl
        pop di
        jmp MRNS1
        ;左右子树是底层节点
MRNS:
        mov byte ptr BTRD[di + 7],-1
        ;把右子树的最左键提升到这个键的位置上
MRNS1:
        mov si,di
        pop di
        mov al,BTRD[si + 3]
        mov BTRD[bx + di + 3],al
        dec byte ptr BTRD[si]
        ;把右子树中的所有键值和对应的子树左移 1 个位置
        mov cx,0
        mov cl,BTRD[si]
        cmp cx,1
        jb MRNReturn
MRNS2:
        mov al,BTRD[si + 4]
        mov BTRD[si + 3],al
        mov al,BTRD[si + 7]
        mov BTRD[si + 6],al
        inc si
        loop MRNS2
        mov al,BTRD[si + 7]
        mov BTRD[si + 6],al
        
MRNReturn:
        
        pop si
        pop cx
        pop ax
        ret
;-----------------------------------MoveRightNode end

;-----------------------------------MoveLeftNode start
        ;从一个键的左子树向右子树转移一个键,使两个子树平衡
        ;左孩子节点 > m / 2 - 1
        ;左孩子中最大的关键字上移到父关键字
MoveLeftNode:
        push ax
        push cx
        push si
        
        ;右子树中所有的键值和对应的子树向右移 1 个位置
        mov ax,0
        mov al,BTRD[bx + di + 7]
        mov si,ax
        push si
        mov cx,0
        mov cl,BTRD[si]
        add ax,cx
        mov si,ax
        cmp cx,1
        jb MLNS3
MLNS:
        mov al,BTRD[si + 2]
        mov BTRD[si + 3],al
        mov al,BTRD[si + 6]
        mov BTRD[si + 7],al
        dec si
        loop MLNS
MLNS3:
        mov al,BTRD[si + 6]
        mov BTRD[si + 7],al
        ;把这个键下移到它的右子树
        pop si
        mov al,BTRD[bx + di + 3]
        mov BTRD[si + 3],al
        inc byte ptr BTRD[si]
        ;把左子树的最右子树转移成右子树的最左子树
        push di
        mov ax,0
        mov al,BTRD[bx + di + 6]
        mov di,ax
        cmp byte ptr BTRD[di + 6],-1
        je MLNS1
        ;左右孩子不是底层节点
        push di
        mov ax,di
        add al,BTRD[di]
        mov di,ax
        mov ax,0
        mov al,BTRD[di + 6]
        mov BTRD[si + 6],al
        mov di,ax
        mov cx,si
        mov BTRD[di + 1],cl
        pop di
        jmp MLNS2
        ;左右孩子是底层节点
        ;右子树
MLNS1:
        mov byte ptr BTRD[si + 6],-1
        ;左孩子中最大的关键字上移到这个键的位置上
MLNS2:
        mov si,di
        pop di
        push si
        mov ax,si
        add al,BTRD[si]
        mov si,ax
        dec si
        mov al,BTRD[si + 3]
        mov BTRD[bx + di + 3],al
        pop si
        dec byte ptr BTRD[si]
        
MLNReturn:
        pop si
        pop cx
        pop ax
        ret
        
;-----------------------------------MoveLeftNode end
code ends
end start

[07/11/22]

Copyright C 2006-2024 ASMEDU.NET All Rights Reserved
Email: asmedu@163.com