我有代码将在16位汇编程序中正确地将节点添加到树中。我可以显示任意数量的左树而不会出现问题。每当我试图让合适的孩子打印时,它都会使系统崩溃。我试图看看turbo调试器中发生了什么,并假设我没有得到保存或正确弹出堆栈的东西。
我通过turbo调试器运行此代码的次数比我记忆中的多,并且无法查看问题的位置。
.MODEL small
.STACK 100h
.DATA
menuchoice DB 10, 10, 13, 'Please enter your choice from the menu. $'
message DB 10, 10, 13, 'Please enter the character you would like to add (enter # to exit): $'
menu DB 10, 10, 13, 'Binary Search Tree Menu'
DB 10, 10, 13, '1 - Add a character to the tree'
DB 10, 10, 13, '2 - Search the tree for a character'
DB 10, 10, 13, '3 - Display the contents of the tree'
DB 10, 10, 13, '4 - Exit the program $'
empty DB 10, 10, 13, ' The tree is empty. $'
crlf DB 10, 13, ' $'
bintree DB 60 DUP(0) ; create a list with a size of 20 characters
node DB 0 ; node starts at zero become 1 once value is added
root DB 1 ; next available slot
next DB 1 ; next is the pointer to the next slot for the character
.CODE
tree PROC
; first two lines in main in all assembler
mov ax, @data
mov ds, ax
DISPLAYMENU: ; set up my label
; display menu
mov dx, OFFSET menu
mov ah, 09h
int 21h
; display menu choice prompt
mov dx, OFFSET menuchoice
mov ah, 09h
int 21h
; get the character from the keyboard with echo
mov ah, 01h
int 21h
MAINLOOP: ; set up my label
; compare data entry to 4 to exit program
cmp al, 34h
je exitprog
; compare data entry to 1 to add node
cmp al, 31h
je starttree
; set root to 1
mov root, 1
; determine if tree is empty, if empty display message
cmp node, 0
je emptymessage
; compare data entry to 2 to search tree
cmp al, 32h
jne check3
call searchtree
CHECK3: ; set up my label
; compare date entry to 3 to display data
cmp al, 33h
jne mainloop
call disptree
jmp mainloop
; set si to zero to represent empty
; mov si, 0
; set di to zero to represent empty
; mov di, 0
EXITPROG: ; set up my label
; exit to DOS
mov al, 0
mov ah, 04ch
int 21h
EMPTYMESSAGE: ; set up my label
; display empty message
mov dx, OFFSET empty
mov ah, 09h
int 21h
; move back to main
jmp displaymenu
STARTTREE: ; set up my label
; display message
mov dx, OFFSET message
mov ah, 09h
int 21h
; get character from keyboard with echo
mov ah, 01h
int 21h
mov ah, 0
; check to see if the character entered is #
cmp al, 23h
; if equal jump to exit program
je exitprog
mov root, 1
; compare next to 60 to determine if there is still space in the tree if not exit
cmp next, 60
jnl exitprog
CHECKTREE: ; set up my label
; check to see if tree is empty and jump to addnode if equal
cmp node, 0
je addnode
; compare root to zero and jump to addnode if equal
cmp root, 0
je addnode
; if not equal then jump to evaltree
jne evaltree
ADDNODE: ; set up my label
; change node value to 1
mov node, 1
; move the array position value in next to si
mov bl, next
mov bh, 0
mov si, bx
; move the value into tree
mov [bintree + si], al
; increment next by 3 to move position to next character slot
add next, 3
; jump back to menu
jmp displaymenu
EVALTREE: ; set up my label
; move root to di to compare position
mov bl, root
mov bh, 0
mov di, bx
; compare bintree to value
cmp al, [bintree + di]
; if less than jump to left child
jl leftchild
; if greater than jump to right child
jg rightchild
LEFTCHILD: ; set up my label
; subtract 1 from di
sub di, 1
; move the position in bintree + di to root
mov bl, [bintree + di]
mov root, bl
; compare root to zero and if equal jump to change pointer and not equal to checktree
cmp root, 0
je changeptr
jne checktree
RIGHTCHILD: ; set up my label
; add 1 from di
add di, 1
; move the position in bintree + di to root
mov bl, [bintree + di]
mov root, bl
; compare root to zero and if equal jump to change pointer and not equal to checktree
cmp root, 0
je changeptr
jne checktree
CHANGEPTR: ; set up my label
; move next to bintree + di
mov bl, next
mov [bintree + di], bl
; jump to checktree
jmp checktree
tree ENDP
searchtree PROC
searchtree ENDP
disptree PROC
; save the value in root to the stack
mov bl, root
mov bh, 0
push bx
; mov value in root to si
mov si, bx
; decrement si to check the left child of character
sub si, 1
; compare the value in bintree to 0
cmp [bintree + si], 0
je ldispret
; move the value in bintree + si to root
mov bl, [bintree + si]
mov root, bl
; return to disptree
call disptree
; get root value from the stack
mov root, bl
; move root to si
mov bl, root
mov bh, 0
DISPRIGHT: ; set up my label
mov si, bx
; display the character
mov dl, [bintree + si]
mov ah, 02h
int 21h
; increment si to check the right child of the character
add si, 1
; compare the value in bintree + si to 0
cmp [bintree + si], 0
jne goright
jmp rdispret
GORIGHT: ; set up my label
; move the value in bintree + si to root
mov bl, [bintree + si]
mov root, bl
; go back to disptree
call disptree
ldispret: ; set up my label
pop bx
pop ax
push bx
push ax
ret
rdispret: ; set up my label
; mov cl, root
; add cl, 3
; cmp next, cl
;je tomain
pop bx
pop bx
jmp dispright
pop bx
pop bx
ret
disptree ENDP
TOMAIN: ; set up my label
;jmp mainloop
end tree
当它显示二叉树的内容时,它应按字母顺序打印字符。如果我的输入是m,b,a,c它应该显示abcm然后返回菜单。程序在评估右树并尝试显示它时崩溃。
按照你的程序流程并不容易,但我认为我设法找到了代码崩溃的一些(重要的)原因。
; return to disptree call disptree ; get root value from the stack mov root, bl
disptree过程使用ldispret:中的stackmanipulation在堆栈上留下一个字,但与上面的注释相反,你没有从堆栈中获得任何东西!使用pop bx
mov root, bl
。
请注意,第一次调用disptree(来自菜单的那个)也必须从堆栈中丢弃这个单词。
rdispret: ; set up my label pop bx pop bx jmp dispright
和
DISPRIGHT: ; set up my label mov si, bx ; display the character mov dl, [bintree + si]
rdispret:代码首先弹出一个根值,然后弹出一个返回地址。它是您在bintree数组中错误地用作索引的返回地址。使用pop bx
pop ax
jmp dispright
。
对于任何使用递归的程序,最好分配一个大堆栈。 256字节有点便宜。
CHECK3: ; set up my label ; compare date entry to 3 to display data cmp al, 33h jne mainloop
如果用户未能输入“1”到“4”范围内的数字,您的程序将进入无限循环。
如果发生这种情况,您需要向用户索要另一个角色。将主循环标签向上移动2行。