 多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页 首页 上一页 下一页 尾页 | |
算法讲堂 |
|
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。 本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。 现本栏目的内容处于不断添加中，请随时关注。 |
|
| 算法讲堂－》完全二叉树度求通路长度【源代码】 |
|
;完全二叉树度求通路长度。
ASSUME cs:CODE,ds:DATA,ss:STACK DATA SEGMENT NODES db 5*257 dup(0) ;存放树的节点，每个节点占5个字节,结构如下：0-字符，1-行位置，2-列位置，3-左孩子位置，4-右孩子位置 STRIN db 256 dup(0) ;存放输入的字符串(以0为结尾符) BYTESTACK db 256 dup(0) ;字符型栈空间 WSTACK dw 256 dup(0) ;字型型栈空间 NUMSPO db 10 dup(0) ;由word型数据转化为十进制字符串(以0为结尾)后存放的位置 ROOT db 1 ;根节点地址 TOPNODE db 0 ;存放树节点的个数 NOTE1 db 'input a string to create a Complete Binary Tree(a-z or A-Z and Maxsize = 31):',0 NOTE2 db 'The Complete Binary Tree path length:',0 NOTE3 db 'The Complete Binary Tree is:',0 DATA ENDS STACK SEGMENT dw 256 dup(0) STACK ENDS CODE SEGMENT START: mov ax,DATA mov ds,ax mov ax,STACK mov ss,ax mov sp,256 ;以下两句设置0页为显示页，解决server 2003下不显示问题 mov ax,0500h int 10h call CLEAR ;清屏 mov dh,10 mov dl,2 mov al,00000010B mov si,offset NOTE1 call SHOWSTR ;输入时的提示信息显示 mov dh,12 mov dl,22 mov si,offset STRIN call GETSTR ;输入字符串 call CLEAR ;清屏 mov si,offset STRIN mov di,offset NODES call TREEINIT ;利用输入的字符串生成一棵完全二叉树 mov si,offset WSTACK mov di,offset NODES call GETTREELEN ;计算完全二叉树的通路长度，结果保存在ax中 mov si,offset NUMSPO call DTOC ;把得到的通路长度(ax)转化为字符串 mov dh,14 mov dl,56 mov al,00000111B mov si,offset NUMSPO call SHOWSTR ;对得到的通路长度进行显示 mov dh,12 mov dl,18 mov al,00000010B mov si,offset NOTE3 call SHOWSTR ;提示信息显示 mov dh,12 mov dl,47 mov al,00000111B mov si,offset STRIN call SHOWSTR ;显示已经输入的字符串 mov dh,14 mov dl,18 mov al,00000010B mov si,offset NOTE2 call SHOWSTR ;提示信息显示 mov ah,07h ;相当于按任意键向下执行 int 21h call CLEAR mov ax,4c00h int 21H ;由给定的字符串建立一棵二叉树 ;参数说明： ; ds:si指向字符串首地址 ; ds:di指向树存储首地址 TREEINIT: jmp initstart heads db 128 dup(0) ;存储临时信息 downs db 128 dup(0) ;存储临时信息 deep db 0 cursor db 0 pointer db 0 ;指针变量 curchar db 0 ;当前字符 charpo db 0 ;当前字符在字符串中的位置 temp db 2 dup(0) ;临时变量 fornum dw 0 ;循环次数 initstart: push ax push bx push cx push dx push di mov charpo,-1 for0: mov al,ds:[si] mov curchar,al inc charpo mov dl,deep inc dl call POW ;求2的dl次方，存入ax中 dec ax cmp al,charpo jne toother1 jmp cmpdeep toother1: jmp other1 cmpdeep: cmp deep,1 jb toadddeep jmp movdeep toadddeep: jmp adddeep movdeep: mov dl,deep call POW mov cx,ax mov fornum,cx ;记录下当前的循环次数 cmp cx,0 je for3star for2: mov bx,cx mov ax,fornum sub ax,bx mov bx,ax mov al,heads[bx] mov pointer,al cmp pointer,0 je tofor2 mov bx,cx mov ax,fornum sub ax,bx mov bx,ax add bx,bx mov al,downs[bx] mov temp[0],al mov al,downs[bx+1] mov temp[1],al mov al,5 mul pointer mov bx,ax mov al,temp[0] mov NODES[bx+3],al mov al,temp[1] mov NODES[bx+4],al tofor2: loop for2 for3star: mov cl,cursor mov ch,0 mov fornum,cx cmp cx,0 je clearcur for3: mov bx,cx mov ax,fornum sub ax,bx mov bx,ax mov al,downs[bx] mov heads[bx],al loop for3 clearcur: mov cursor,0 adddeep: cmp curchar,0 ;判断遍历是否结束 je toendinit jmp incdeep toendinit: jmp endinit incdeep: inc deep jmp overif other1: cmp curchar,0 ;判断当前字符是不是0，如果不是则进行节点处理 jne tooverif jmp decdeep tooverif: jmp overif decdeep: dec deep mov al,128 sub al,cursor mov ah,0 mov cx,ax mov fornum,cx cmp cx,0 je for5start for4: mov bx,cx mov ax,fornum sub ax,bx add al,cursor mov bx,ax mov downs[bx],0 loop for4 for5start: mov dl,deep call POW mov cx,ax mov fornum,cx ;记录下当前的循环次数 cmp cx,0 je for6star for5: mov bx,cx mov ax,fornum sub ax,bx mov bx,ax mov al,heads[bx] mov pointer,al cmp pointer,0 je tofor5 mov bx,cx mov ax,fornum sub ax,bx mov bx,ax add bx,bx mov al,downs[bx] mov temp[0],al mov al,downs[bx+1] mov temp[1],al mov al,5 mul pointer mov bx,ax mov al,temp[0] mov NODES[bx+3],al mov al,temp[1] mov NODES[bx+4],al tofor5 : loop for5 for6star: mov cl,cursor mov ch,0 mov fornum,cx cmp cx,0 je goendinit jmp for6 goendinit: jmp endinit for6: mov bx,cx mov ax,fornum sub ax,bx mov bx,ax mov al,downs[bx] mov heads[bx],al loop for6 jmp endinit ;遇到结尾符0退出，树构造完成 overif: cmp charpo,0 ;如果为根节点 jne overelse inc TOPNODE mov bl,TOPNODE mov al,5 mul bl mov bx,ax mov al,curchar mov ds:[bx+di],al mov al,deep mov ds:[bx+di+1],al mov al,cursor mov ds:[bx+di+2],al mov byte ptr ds:[bx+di+3],0 mov byte ptr ds:[bx+di+4],0 mov al,ROOT mov bl,charpo mov bh,0 mov heads[bx],al jmp for0end overelse: cmp curchar,'#' jne sonif mov pointer,0 jmp addcursor sonif: inc TOPNODE mov al,TOPNODE mov pointer,al mov bl,TOPNODE mov al,5 mul bl mov bx,ax mov al,curchar mov ds:[bx+di],al mov al,deep mov ds:[bx+di+1],al mov al,cursor mov ds:[bx+di+2],al mov byte ptr ds:[bx+di+3],0 mov byte ptr ds:[bx+di+4],0 addcursor: mov bl,cursor mov bh,0 mov al,pointer mov downs[bx],al inc cursor for0end: inc si jmp for0 endinit: pop di pop dx pop cx pop bx pop ax ret ;遍历二叉树，并计算其通路长度 ;参数说明： ; ds:si指向字符栈空间 ; ds:di指向树的存放位置 ; 返回值：(ax)=二叉树的通路长度 GETTREELEN: jmp getstart treelen dw 0 ;存储树的通路长度 treecur dw 0 ;当前节点的路径长度 getstart: push bx push es push cx push dx mov al,0 mov ah,ROOT mov dh,0 call WORDSTACK outwhile: mov bx,offset wordtop mov ax,cs:[bx] cmp ax,0 jnz ow jmp outret ow: mov dh,1 call WORDSTACK cmp al,0 jne case1 inc al mov dh,0 call WORDSTACK mov bl,ah mov al,5 mul bl mov bx,ax mov ah,ds:[di+bx+3] ;得到当前节点的左孩子位置 cmp ah,0 je jmp1 mov al,0 mov dh,0 call WORDSTACK inc treecur mov bx,treecur add treelen,bx jmp1: jmp tooutwhile case1: cmp al,1 jne case2 inc al mov dh,0 call WORDSTACK mov bl,ah mov al,5 mul bl mov bx,ax mov ah,ds:[di+bx+4] ;得到当前节点的右孩子位置 cmp ah,0 je jmp2 mov al,0 mov dh,0 call WORDSTACK inc treecur mov bx,treecur add treelen,bx jmp2: jmp tooutwhile case2: cmp al,2 jne tooutwhile cmp ah,ROOT je tooutwhile dec treecur tooutwhile: jmp outwhile outret: mov ax,treelen ;得到数的通路长度 pop dx pop cx pop es pop bx ret ;将word型数据转变为表示十进制数的字符串，字符串以0为结尾符 ;参数说明： ; (ax)=word型数据 ; ds:si指向字符串的首地址 DTOC: push si push bx push cx push dx push ax mov bx,0 mov dx,0 M: mov cx,10 call divdw push cx inc bx mov cx,ax jcxz N jmp M N: mov cx,dx jcxz F jmp M F: mov cx,bx G: pop ax add al,30h mov ds:[si],al inc si loop G mov byte ptr ds:[si],0 pop ax pop dx pop cx pop bx pop si ret ;解决除法溢出 ;参数说明： ; (ax)=dword型数据的低十六位 ; (bx)=dword型数据的高十六位 ; (cx)=除数 ; 返回：(dx)=结果的高十六位，(ax)=结果的低十六位，(cx)=余数 DIVDW: push bx push bp mov bx,ax mov ax,dx mov dx,0 div cx mov bp,ax mov ax,bx div cx mov cx,dx mov dx,bp pop bp pop bx ret ;地计算2的n次方,结果存放在ax中 ;参数说明： ; (dl)->n POW: push dx push cx mov ax,1 cmp dl,0 je p2 mov cl,dl mov ch,0 p1: mov bx,ax mov al,2 mul bl loop p1 jmp p3 p2: mov ax,1 p3: pop cx pop dx ret ;在指定的位置显示指定的以0结尾的字符串 ;参数说明： ; ds:si指向要显示的字符串(以0结尾) ; (dh)显示的行数,(dl)为显示列数,(al)为字符显示特征 SHOWSTR: push bx push es push cx mov cl,al mov ax,0b800h mov es,ax mov al,160 mul dh add dl,dl mov dh,0 add ax,dx mov bx,ax ss1: mov al,ds:[si] cmp al,0 je ss2 mov es:[bx],al mov es:[bx+1],cl add bx,2 inc si jmp ss1 ss2: pop cx pop es pop bx ret ;word型栈的入栈、出栈 ;参数说明： ; (dh)=功能号，0表示入栈，1表示出栈 ; ds:si指向字栈空间 ; 对于0号功能：(ax)=入栈字 ; 对于1号功能：(ax)=返回字 WORDSTACK: jmp short wordstart wordtable dw wordpush,wordpop wordtop dw 0 wordstart: push bx push dx push di push es cmp dh,1 ja wordret mov bl,dh mov bh,0 add bx,bx jmp word ptr wordtable[bx] wordpush: mov bx,wordtop add bx,bx mov [si][bx],ax inc wordtop jmp wordret wordpop: cmp wordtop,0 je wordret dec wordtop mov bx,wordtop add bx,bx mov ax,[si][bx] jmp wordret wordret: pop es pop di pop dx pop bx ret ;字符栈的入栈、出栈和显示 ;参数说明： ; (ah)=功能号，0表示入栈，1表示出栈，2表示显示 ; ds:si指向字符栈空间 ; 对于0号功能：(al)=入栈字符 ; 对于1号功能：(al)=返回字符 ; 对于2号功能：(dh)、(dl)=字符串显示的行列位置 CHARSTACK: jmp short charstart table dw charpush,charpop,charshow top dw 0 charstart: push bx push dx push di push es cmp ah,2 ja sret mov bl,ah mov bh,0 add bx,bx jmp word ptr table[bx] charpush: mov bx,top mov [si][bx],al inc top jmp sret charpop: cmp top,0 je sret dec top mov bx,top mov al,[si][bx] jmp sret charshow: mov bx,0b800h mov es,bx mov al,160 mov ah,0 mul dh mov di,ax add dl,dl mov dh,0 add di,dx mov bx,0 charshows: cmp bx,top jne noempty mov byte ptr es:[di],' ' jmp sret noempty: mov al,[si][bx] mov es:[di],al mov byte ptr es:[di+2],' ' inc bx add di,2 jmp charshows sret: pop es pop di pop dx pop bx ret ;接受字符串输入，字符存放在ds:si所指地址空间 GETSTR: push ax push si mov top,0 mov si,offset STRIN getstrs: mov ah,0 int 16h cmp al,20h jb nochar cmp al,'A' jb nochar cmp al,'Z' ja atoz jmp instack atoz: cmp al,'a' jb nochar cmp al,'z' ja nochar instack: cmp top,30 ja nochar mov ah,0 call charstack mov ah,2 call charstack jmp getstrs nochar: cmp ah,0eh ;退格键扫描码 je backspace cmp ah,1ch ;回车键扫描码 je enter jmp getstrs backspace: mov ah,1 call charstack mov ah,2 call charstack jmp getstrs enter: mov al,0 ;以0符作为字符串的结尾 mov ah,0 call charstack mov ah,2 call charstack pop si pop ax ret ;清屏函数 CLEAR: push ax push bx push cx push es push di mov ax,0b800h mov es,ax mov bx,0 mov di,0 mov cx,25 clear1: push cx mov cx,80 clear2: mov byte ptr es:[bx+di],0 mov byte ptr es:[bx+di+1],00000111B add di,2 loop clear2 add bx,160 mov di,0 pop cx loop clear1 pop di pop es pop cx pop bx pop ax ret CODE ENDS END START [07/10/08] |