Árvore binária de busca em Assembly - com comentários

Publicado por Perfil removido (última atualização em 15/05/2010)

[ Hits: 7.893 ]

Download 4585.abba.asm




Olá pessoal, postei há pouco tempo aqui uma versão da árvore binária de busca em assembler 8086. Estou enviando agora uma versão com o código mais organizado e também comentado. Se alguém verificar alguma falha, por favor me informe.

Foram desenvolvidos os algoritmos de inserção, caminhamento e busca. Estou quase terminando o de exclusão. Assim que o fizer, posto aqui.

Grande abraço :D

  



Esconder código-fonte

.model small
.stack
.data
primeiro db 0,0
mensagem db 10,13,"Insira um valor (de 0 a 65535): $"
mensagemInsercao db "INSERINDO ELEMENTOS$",10,13
mensagemCaminhamento db 10,13,"CAMINHAMENTO EM ORDEM$",10,13
mensagemBusca db 10,13,"BUSCANDO ELEMENTO$",10,13
mensagemCustoBusca db 10,13,"Custo de busca: $"
naoEncontrou db 10,13,"ITEM NÃO ENCONTRADO$",10,13
encontrou db 10,13,"ITEM ENCONTRADO$",10,13
numero db 6, 1, 0,0,0,0,0
resultado db 10,13,"00000$"

.code

entrada proc                        

    ;Mensagem para inserção de valor
    mov ax, seg mensagem
    mov ds, ax
    lea dx, mensagem
    mov ah, 09h
    int 21h

    ;Leitura de string
    mov ax, seg numero
    mov ds, ax
    lea dx, numero
    mov ah, 0Ah
    int 21h

    ;Coloca o tamanho da string inserida em cx
    mov ch, 0
    mov cl, [numero+1]
   
    ;Coloca a posição do último dígito em bx
    lea bx, numero
    inc bx
    add bx, cx
   
    ;Inicializa contadores: dx é multiplicador e cx é acumulador
    mov dx, 1
    mov cx, 0
   
    ;Loop de cálculo para conversão da string para inteiro
    calculo:
   
    ;Subtrai 48 do conteúdo de bx, e coloca-o em ax
    sub [bx], 48
    mov al, [bx]
    mov ah, 0
   
    ;dx é inicialmente 1 e a cada iteração é multiplicado por 10.
    ;Cada dígito é multiplicado por dx e somado a cx
    ;Exemplo:
    ; 2345 = 5x1 + 4x10 + 3x100 + 2x1000
    push dx
    mul dx
    pop dx
    push ax
    mov ax, dx
    mov dx, 10
    mul dx
    mov dx, ax
    pop ax
    add cx, ax
    dec bl
    lea ax, numero
    inc ax
    cmp bx, ax
    jne calculo

    ret

entrada endp
 
 
saida proc
  
   ;Carrega o seguimento e o deslocamento de "resultado"
   mov bx, seg resultado
   mov ds, bx
   lea si,resultado+6
  
   ;Número de iterações
   mov cx, 5

   ;Faz divisões sucessivas de ax coloca o resto no conteúdo de si
   ;Decrementa si a cada iteração para inserção dos restos nas
   ;posições corretas
   volta:
   mov dx,0
   mov bx,10
   div bx
   add dl,48
   mov [si],dl
   dec si
   loop volta
  
   ;Impressão do resultado
   mov ah, 09h
   lea dx, resultado
   int 21h
  
   ret
  
saida endp


caminhamento proc

    ;ds recebe ponteiro para a raiz da árvore
    mov bx, seg primeiro
    mov ds, bx
    mov dh, [primeiro]
    mov dl, [primeiro+1]
    mov ds, dx
   
    ;(Número de elementos da pilha) + 1
    mov cx, 1
   
    ;Faz todo caminhamento à esquerda empilhando os ponteiros
    ;Quando o caminhamento à esquerda encerra, salta para "fimCaminhamento"
    camEsq:
    mov dx, ds
    cmp dx, 0
    je fimCaminhamento
    push dx
    inc cx
    mov bx, 0
    mov dh, [bx]
    inc bx
    mov dl, [bx]
    mov ds, dx
    jmp camEsq
   
    camDir:
    ;Faz impressão do nó e todo caminhamento à direita
    mov dx ,ds
    cmp dx, 0
    je fimCaminhamento
    mov bx, 4
    mov ah, [bx]
    inc bx
    mov al, [bx]
   
    ;Impressão do nó
    mov bx, ds
    push bx
    push cx
    call saida
    pop cx
    pop bx
    mov ds, bx
   
    ;Caminhamento para o nó da direita
    mov bx, 2
    mov dh, [bx]
    inc bx
    mov dl, [bx]
    mov ds, dx
   
    ;Para cada nó da direita, faz-se o caminhamento da esquerda
    jmp camEsq

   fimCaminhamento:
   ;Verifica se a pilha está vazia
   dec cx
   cmp cx, 0
   je fimfimCaminhamento ;Se estiver vazia, completou o caminhamento
  
   ;Se não estiver vazia, desempilha e faz o caminhamento à direita
   pop dx
   mov ds, dx
   jmp camDir
  
   fimfimCaminhamento:
   ret
        
caminhamento endp


inserir proc   
   
    ;Chama rotina de entrada que recebe um valor em cx
    call entrada
   
    ;Faz alocação dinâmica de um parágrafo de memória
    mov ah, 48h
    mov bx, 1
    int 21h
   
    ;Aponta para seguimento onde foi feita a alocação
    mov ds, ax
   
    ;O descolamento nessa alocação sempre será 0
    mov bx, 0
   
    ;Cria o nó da árvore, usando o espaço alocado com
    ;a seguinte estrutura:
    ;Bytes 0 e 1: ponteiro para esquerda, inicialmente em 0
    ;Bytes 2 e 3: ponteiro para direira, inicialmente em 0
    ;Bytes 4 e 5: inteiro lido pela rotina "entrada"
    mov [bx], 0
    inc bx
    mov [bx], 0
    inc bx
    mov [bx], 0
    inc bx
    mov [bx], 0
    inc bx
    mov [bx], ch
    inc bx
    mov [bx], cl 
   
    ;Verifica se já há item na árvore,
    ;checando se "primeiro" é igual a 0
    mov bx, seg primeiro
    mov ds, bx
    mov dh, [primeiro]
    mov dl, [primeiro+1]
    cmp dx, 0
    jne naoSerPrimeiro
   
    ;Se for a primeira inserção, coloca-se o segmento atual em "primeiro"
    mov [primeiro], ah
    mov [primeiro+1], al
    jmp serPrimeiro ;Salto para o fim
 
   
    ;Se não for a primeira inserção, será feita a busca
    ;de onde deverá ser inserido o novo nó
    naoSerPrimeiro:
    ;dx inicialmente contém o deslocamento de "primeiro"
    busca:
    ;recebe em ds o ponteiro inserido em dx e copia o valor
    ;do nó (bytes 4 e 5) para dx
    mov ds, dx
    mov bx, 4
    mov dh, [bx]
    inc bx
    mov dl, [bx]
   
    ;Faz a comparação do valor do nó atual e do nó a ser inserido
    cmp cx, dx
    jl  casoMenor
   
    ;Se for maior:
    ;coloca em dx o ponteiro do filho da direita (bytes 2 e 3)
    casoMaior:
    mov bx, 2
    mov dh, [bx]
    inc bx
    mov dl, [bx]
    jp comparador ;Salto para comparador
 
    ;Se for menor:
    ;coloca em dx o ponteiro do filho da esquerda (bytes 0 e 1)
    casoMenor:
    mov bx, 0
    mov dh, [bx]
    inc bx
    mov dl, [bx]
   
    ;Verifica se o ponteiro é 0. Se for, esse é o lugar da inserção do novo nó
    comparador:
    cmp dx, 0
    jne busca ; Se não for 0 continua a busca do lugar de inserção

    ;Define o ponteiro para o novo nó
    mov [bx], al
    dec bx
    mov [bx], ah
 
    serPrimeiro:
    ret

inserir endp


buscar proc
   
    ;Chama rotina de entrada que recebe um valor em cx
    call entrada
   
    ;Contador do "custo de busca"
    mov ax, 0
   
    ;ds recebe ponteiro para a raiz da árvore
    ;e copia seu conteúdo para dx
    mov bx, seg primeiro
    mov ds, bx
    mov dh, [primeiro]
    mov dl, [primeiro+1]
   
    ;Algoritmo análogo à busca para inserção
    busca2:
    inc ax ;incremento do "custo de busca"
    mov ds, dx
    mov bx, 4
    mov dh, [bx]
    inc bx
    mov dl, [bx]
    cmp cx, dx
    je encontrar ;se for igual é porque o valor foi encontrado
    jl  casoMenor2
    casoMaior2:
    mov bx, 2
    mov dh, [bx]
    inc bx
    mov dl, [bx]
    jp comparador2
 
    casoMenor2:
    mov bx, 0
    mov dh, [bx]
    inc bx
    mov dl, [bx]
    
    comparador2:
    cmp dx, 0
    jne busca2
   
    ;Caso em que não encontrou: exibe mensagem
    mov ax, seg naoEncontrou
    mov ds, ax
    lea dx, naoEncontrou
    mov ah, 09h
    int 21h
    jp fim ; salto para o fim
   
    ;Caso em que encontrou: exibe mensagem e o custo da busca
    encontrar:
    push ax
    mov ax, seg encontrou
    mov ds, ax
    lea dx, encontrou
    mov ah, 09h
    int 21h
    mov ax, seg mensagemCustoBusca
    mov ds, ax
    lea dx, mensagemCustoBusca
    mov ah, 09h
    int 21h
    pop ax
    call saida
     
    fim:
    ret
       
buscar endp


principal proc

    ;Número de loops para inserção
    mov cx, 5

    ;INSERÇÃO
    mov ax, seg mensagemInsercao
    mov ds, ax
    lea dx, mensagemInsercao
    mov ah, 09h
    int 21h
    loopInsercao:
    push cx
    call inserir
    pop cx
    loop loopInsercao
  
    ;BUSCA
    mov ax, seg mensagemBusca
    mov ds, ax
    lea dx, mensagemBusca
    mov ah, 09h
    int 21h
    call buscar
   
    ;CAMINHAMENTO
    mov ax, seg mensagemCaminhamento
    mov ds, ax
    lea dx, mensagemCaminhamento
    mov ah, 09h
    int 21h
    call caminhamento  
  
    ;ENCERRAMENTO
    mov ax, 4C00h
    int 21h
      
principal endp

end principal

Scripts recomendados

Escrita de um número em decimal na tela em Assembly Puro para Linux x86 (GNU Assembler)

sdfgsd

"Clear Screen" para Linux x86 em Assembly Puro (GNU Assembly)

GAS Informações da CPU

Escrita de um número em decimal na tela em Assembly Puro para Linux x86 (Nasm - Netwide Assembly)


  

Comentários

Nenhum comentário foi encontrado.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts