 多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页 首页 上一页 下一页 尾页 | |
算法讲堂 |
|
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。 本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。 现本栏目的内容处于不断添加中，请随时关注。 |
|
| 算法讲堂－》哈夫曼树求加权通路长度【源代码】 |
|
ASSUME cs:CODE,ds:DATA,ss:STACK
DATA SEGMENT TREENODES dw 3*256 dup(0) ;存放数的节点(节点最多为255,且前三个字空间没有用到)，每个节点占3个字 0:权值 1:左孩子位置 2:右孩子位置，位置为0代表位置空 ROOTNODE dw 0 ;树根地址 NODETOP dw 0 ;存储当前树节点个数 LEAFNUM dw 0 ;存放叶子节点的数目 WSTACK dw 256 dup(0) ;字型型栈空间 LEAFNODES dd 6,7,8,5,9 ;存储生成哈夫曼树叶子节点的权值,叶子节点的数量最大为128 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 mov si,offset LEAFNODES ;指向生成的哈夫曼树的存储位置 mov di,offset TREENODES ;指向叶子节点权值的存放位置(注：每个叶子节点的权值占用两个字节） mov cx,5 ;叶子节点的个数 call HFTREEINIT ;由给定的叶子节点的权值生成哈夫曼树 mov di,offset TREENODES ;指向指向哈夫曼树的存储位置 call GETTREELEN ;计算哈夫曼树的加权通路长度，结果放入ax中 mov ax,4c00h int 21H ;由给定的叶子节点生成一颗哈夫曼树 ;参数说明： ; ds:di指向哈夫曼树的存储位置 ; ds:si执向生成哈夫曼树叶子节点的起始位置 ; (cx)=叶子节点的个数 HFTREEINIT: push ax push bx push cx push dx mov LEAFNUM,cx cmp LEAFNUM,0 je hfret hfA: call GETTWOMIN cmp LEAFNUM,1 je hfret jmp hfA hfret: mov ax,NODETOP mov ROOTNODE,ax ;确定根节点的位置 pop dx pop cx pop bx pop ax ret ;查找权值中的最小值和次小值并生成树的节点 GETTWOMIN: push ax push bx push cx push dx push di push ds push si jmp gestart first dw 0 ; 存储最小值 firstpo dw 0 ; 存储最小值位置 second dw 0 ; 存储次小值 secondpo dw 0 ; 存储次小值位置 lchild dw 0 ;左孩子位置 rchild dw 0 ;右孩子位置 gestart: cmp LEAFNUM,0 je jmpA jmp jmpB jmpA: jmp toretA jmpB: mov ax,LEAFNUM cmp ax,1 je jmpC jmp jmpD jmpC: jmp toretB jmpD: mov ax,ds:[si] mov first,ax mov firstpo,si mov cx,LEAFNUM dec cx ;循环次数 push si push si getA: jcxz getG add si,4 mov ax,ds:[si] cmp ax,first jnb togetA mov first,ax mov firstpo,si togetA: loop getA getG: mov bx,firstpo mov ax,ds:[bx+2] ;得到当前叶子节点在树的存储位置，0代表还没有生成节点 cmp ax,0 je crenodeA mov word ptr lchild,ax ;记录左孩子位置 jmp getE crenodeA: inc NODETOP ;生成一个节点 mov ax,NODETOP mov lchild,ax ;记录左孩子位置（作为父结点的左孩子） mov al,6 mov bx,NODETOP ;最大支持255个节点 mov bh,0 mul bl mov bx,ax mov ax,first mov ds:[bx+di],ax ;记录权值 mov word ptr ds:[bx+di+2],0 ;左孩子位置0 mov word ptr ds:[bx+di+4],0 ;右孩子位置0 getE: pop si mov cx,LEAFNUM dec cx mov ax,ds:[si] mov second,ax mov secondpo,si cmp si,firstpo jne getB add si,4 dec cx mov ax,ds:[si] mov second,ax mov secondpo,si getB: jcxz getF add si,4 mov ax,ds:[si] cmp si,firstpo je togetB cmp ax,second jnb togetB mov secondpo,si mov second,ax togetB: loop getB getF: mov bx,secondpo mov ax,ds:[bx+2] ;得到当前叶子节点在树的存储位置，0代表还没有生成节点 cmp ax,0 je crenodeB mov word ptr rchild,ax ;记录左孩子位置 jmp getC crenodeB: inc NODETOP ;生成一个节点 mov ax,NODETOP mov rchild,ax ;记录右孩子位置（作为父结点的右孩子） mov al,6 mov bx,NODETOP ;最大支持255个节点 mov bh,0 mul bl mov bx,ax mov ax,second mov ds:[bx+di],ax ;记录权值 mov word ptr ds:[bx+di+2],0 ;做孩子位置0 mov word ptr ds:[bx+di+4],0 ;右孩子位置0 getC: mov ax,first add ax,second push ax mov bx,firstpo mov ds:[bx],ax inc NODETOP ;生成父结点 mov ax,NODETOP mov ds:[bx+2],ax ;记录下生成的新节点的位置 mov al,6 mov bx,NODETOP mov bh,0 mul bl mov bx,ax pop ax mov ds:[bx+di],ax mov ax,lchild mov ds:[bx+di+2],ax mov ax,rchild mov ds:[bx+di+4],ax pop si mov di,secondpo sub di,si mov bl,4 mov ax,di div bl mov ah,0 mov cx,LEAFNUM dec cx sub cx,ax mov si,secondpo getD: jcxz toretD mov ax,ds:[si+4] mov ds:[si],ax mov ax,ds:[si+6] mov ds:[si+2],ax add si,4 loop getD jmp toretD toretA: mov cx,0 ;叶子节点个数为0 jmp getover toretB: mov cx,1 ;只有一个叶子节点 mov ax,ds:[si] mov ds:[di+6],ax mov word ptr ds:[di+8],0 mov word ptr ds:[di+10],0 inc NODETOP jmp getover toretD: dec LEAFNUM mov ax,first mov bx,second mov cx,2 getover: pop si pop ds pop di pop dx pop cx pop bx pop ax ret ;遍历二叉树，并计算其通路长度 ;参数说明： ; ds:di指向树的存放位置 ; 返回值：(ax)=二叉树的通路长度 GETTREELEN: jmp getstart treelen dw 0 ;存储树的通路长度 treecur dw 0 ;当前节点的路径长度 temppo dw 0 ;临时变量 leafflag dw 0 ;当前叶子标记 getstart: push bx push es push cx push dx push si mov si,offset WSTACK mov ax,ROOTNODE mov dh,0 call WORDSTACK mov ax,0 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 mov bx,ax ;把标记位存在bx中 mov dh,1 call WORDSTACK ;ax存放位置 mov temppo,ax cmp bx,0 jne case1 mov ax,temppo mov dh,0 call WORDSTACK inc bx mov ax,bx mov dh,0 call WORDSTACK mov ax,6 mov bx,temppo mul bx mov bx,ax mov ax,ds:[di+bx+2] ;得到当前节点的左孩子位置 cmp ax,0 je jmp1 push ax mov dh,0 call WORDSTACK mov ax,0 mov dh,0 call WORDSTACK inc treecur pop ax mov bx,ax mov ax,6 mul bx mov bx,ax mov ax,ds:[bx+di+2] cmp ax,0 jne jmp1 mov ax,ds:[bx+di+4] cmp ax,0 jne jmp1 mov ax,ds:[bx+di] ;得到权值 mov bx,treecur mul bx add treelen,ax inc leafflag jmp1: jmp tooutwhile case1: cmp bx,1 jne case2 mov ax,temppo mov dh,0 call WORDSTACK inc bx mov ax,bx mov dh,0 call WORDSTACK mov ax,6 mov bx,temppo mul bx mov bx,ax mov ax,ds:[di+bx+4] ;得到当前节点的右孩子位置 cmp ax,0 je jmp2 push ax mov dh,0 call WORDSTACK mov ax,0 mov dh,0 call WORDSTACK inc treecur pop ax mov bx,ax mov ax,6 mul bx mov bx,ax mov ax,ds:[bx+di+2] cmp ax,0 jne jmp2 mov ax,ds:[bx+di+4] cmp ax,0 jne jmp2 mov ax,ds:[bx+di] ;得到权值 mov bx,treecur mul bx add treelen,ax inc leafflag jmp2: jmp tooutwhile case2: cmp bx,2 jne tooutwhile mov ax,temppo cmp ax,ROOTNODE je tooutwhile dec treecur tooutwhile: jmp outwhile outret: mov ax,treelen ;得到数的通路长度 pop si pop dx 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 CODE ENDS END START [07/10/08] |