Árvore binária de busca em Assembly - com comentários
Publicado por Perfil removido (última atualização em 15/05/2010)
[ Hits: 7.893 ]
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
.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
Escrita de um número em decimal na tela em Assembly Puro para Linux x86 (GNU Assembler)
"Clear Screen" para Linux x86 em Assembly Puro (GNU Assembly)
Escrita de um número em decimal na tela em Assembly Puro para Linux x86 (Nasm - Netwide Assembly)
Nenhum comentário foi encontrado.
Agora temos uma assistente virtual no fórum!!! (246)
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Efeito "livro" em arquivos PDF
Como resolver o erro no CUPS: Unable to get list of printer drivers
Flatpak: remover runtimes não usados e pacotes
Mudar o gerenciador de login (GDM para SDDM e vice-versa) - parte 2
Como eu faço para ativar o sistema de gestos do mousepad? (4)
NGNIX - Aplicar SNAT para evitar roteamento assimetrico (13)
[Python] Automação de scan de vulnerabilidades
[Python] Script para analise de superficie de ataque
[Shell Script] Novo script para redimensionar, rotacionar, converter e espelhar arquivos de imagem
[Shell Script] Iniciador de DOOM (DSDA-DOOM, Doom Retro ou Woof!)
[Shell Script] Script para adicionar bordas às imagens de uma pasta