 多路树查找－外部查找(B树)【源代码】多路树查找－外部查找(B树)【下载及演示说明】双向链表演示程序【下载及演示说明】循环链表演示程序【下载及演示说明】链表【讲解】动态存储分配之边界标识法演示程序【下载及演示说明】动态存储分配之边界标识法【讲解】首次适应算法和最佳适应算法【讲解】动态存储分配之边界标识法【源代码】振荡排序算法【讲解】振荡排序演示程序【下载及演示说明】树和二叉树相互转化【讲解】深度优先搜索【下载及演示说明】深度优先搜索【源代码】朴素字符串匹配演示程序【下载及演示说明】当前1/4页 首页 上一页 下一页 尾页 | |
算法讲堂 |
|
本栏目所有文章由本站组织业内技术专家原创而成，用汇编语言向学习者讲解经典问题的编程思想和编程方法。 本栏目所有文章的版权归本站所有，转载请注明出处为汇编网<www.asmedu.net> 。 现本栏目的内容处于不断添加中，请随时关注。 |
|
| 算法讲堂－》双向链表【源代码】 |
|
assume cs:code
data segment ;------------------------------------------ MTa db 256 dup (0) ;存储空间映射表 Mem db 256 dup ( 16 dup (0)) ;存储空间 buf dw 256 dup (?) List dw 0 List2 dw 0 Point dw 0 data ends ;-------------------------------------------- code segment start: mov ax,data mov ds,ax call initlist ;建立表一 mov list,bx call initlist ;建立表二 mov list2,bx mov si,list mov dx,0034h call appendnode ;appendnode mov si,list mov dx,0044h call appendnode ;appendnode mov si,list mov dx,0054h call appendnode ;appendnode mov si,list2 mov ax,1 mov dx,0074h call insertnode ;insertnode mov si,list2 mov ax,2 mov dx,0064h call insertnode ;insertnode mov si,list2 mov ax,3 mov dx,0068h call insertnode ;insertnode mov si,list ;deletenode mov ax,1 call deletenode mov si,list mov ax,2 call getelement mov si,list mov ax,3 mov dx,0ffffh call updatenode mov si,list mov dx,0ffffh call findElemOf call lengthof mov si,list ;合并 mov di,list2 call union mov list,bx push list ;对合并后所得表遍历 call traverse mov si,list ;清空 call clearlist mov bx,list ;销毁 call destroylist mov ax,4c00h int 21h ;+++++++++++++++++++++++++++++0 ;Basic operation 〈double linked list〉 ;++++++++++++++++++++++++++++ ;创建表： Create dulinklist： ; (1)allocate memory ; (2)初始化数据 ;参数: 无 ;返回值： bx - 表的地址 ; ah = 0 成功 ; ah = 1 失败 ;------------------------------------ ;call initlist ;------------------------------------ InitList: push si call Alloc cmp ah,0 jne initret lea si,mem mov word ptr [bx][si][0],0 ;长度初始化为零 mov word ptr [bx][si][2],0 ;左端指针空 mov word ptr [bx][si][4],0 ;右端指针空 ;bx保存表地址 initret: pop si ret ;+++++++++++++++++++++++++++++ ;销毁表 ;参数： BX - 表的地址 ;----------------------------- DestroyList: push bp mov bp,sp mov si,list call clearlist mov bx,list call free mov sp,bp pop bp ret ;+++++++++++++++++++++++++++++ ;建立结点： ; （1）申请空间 ; （2）初始化数据 ;参数 无 ;返回值 point ; ah = 0 成功 ; ah = 1 失败 ;------------------------------ ;call makenode ;------------------------------ MakeNode: push si push bx call Alloc cmp ah,0 je makenodeok mov ah,1 jmp makeret makenodeok: lea si,mem mov word ptr [bx+si],0 ;数据域初始化为零 mov word ptr [bx+si+2],0 ;前驱指针空 mov word ptr [bx+si+4],0 ;后继指针空 mov Point,bx ;保存地址在全局变量 pop bx pop si makeret:ret ;+++++++++++++++++++++++++++++ ;插入结点: ;参数: si-表地址, ax-位置, dx-结点数据 ;返回值: ah=0 成功 , (al)=位置 ; ah=1,申请结点失败,ah=2 位置不正确 ;------------------------------------- ; mov si,0 ; mov ax,2 ; mov dx,1111h ; call insertnode ;------------------------------------- insertnode: push bp mov bp,sp sub sp,2 mov [bp-2],ax push bx push cx push di push si call cmpnull cmp ah,1 jne insertg jmp insertnoderet insertg: call makenode cmp ah,0 je insertgoon_1 mov ax,[bp-2] mov ah,1 jmp insertnoderet insertgoon_1: ;make node succ mov ax,[bp-2] lea bx,mem cmp ax,1 jnb insertgoon mov ah,2 jmp insertnoderet insertgoon: ; pos>=1 mov cx,[bx+si] inc cx ;length+1 cmp ax,cx jna insertgoon1 mov ah,2 jmp insertnoderet insertgoon1: ;and pos<=length+1 cmp ax,cx jne insertgoon2 jmp insertnodetail insertgoon2: ;1<=pos<length+1 cmp ax,1 jne insertgoon3 jmp insertonlyhead insertgoon3: ;pos is neither 1 nor length+1 xor cx,cx mov cx,2 ;from 2 to position mov di,[bx+si+2] ;di=dulinklist.left jmp insertnodecmp insertnodeloop: inc cx mov di,[bx+di+4] ; insertnodecmp: cmp cx,ax jb insertnodeloop inc word ptr [bx+si] ;length++ push si mov si,point mov [bx+si],dx ;point.data=value push [bx+di+4] ; pop [bx+si+4] ;point.next=[di].next mov [bx+si+2],di ;point.prior = di push di mov di,[bx+di+4] ;di = [di] mov [bx+di+2],si ;[di].prior=si pop di mov [bx+di+4],si ;[di].next=si pop si mov ah,0 jmp insertnoderet insertnodetail: ; pos=length+1 cmp cx,1 jne insertonlytail mov di,point ; length=0 mov [bx+si+2],di ; leftlink = new mov [bx+si+4],di ; riggtlink =new mov word ptr [bx+si],1 ; length = 1 mov [bx+di],dx ; point.data=value mov word ptr [bx+di+2],0 ; point.prior=null mov word ptr [bx+di+4],0 ; point.next= null mov ah,0 jmp insertnoderet insertonlytail: ; length>0 and position=length+1 mov di,point mov [bx+di],dx ;value mov word ptr [bx+di+4],0 ;next=null push [bx+si+4] ;dulinklist.right pop [bx+di+2] ;prior=(old)right push di push di mov di,[bx+si+4] ;(old)right pop [bx+di+4] ;(old)[right].next pop [bx+si+4] ;dulinklist.right=point inc word ptr [bx+si] ;dulinklist.length++ mov ah,0 jmp insertnoderet insertonlyhead: ; length>0 and position=1 mov di,point mov [bx+di],dx ;point.data=value mov word ptr [bx+di+2],0 ;point.prior=null push [bx+si+2] ; dulinklist.left(old) pop [bx+di+4] ; point.next= push di push di mov di,[bx+si+2] ;[dulinklist.left(old)].prior pop [bx+di+2] ; = point pop [bx+si+2] ;dulinklist.left = point inc word ptr [bx+si] ;length++ mov ah,0 ; jmp insertnoderet insertnoderet: pop di pop cx pop bx mov sp,bp pop bp ret ;+++++++++++++++++++++++++++++ ;追加 ;参数： si - 表地址, ; dx - 结点数据 ;返回值： ah = 0 成功 ; ah = 1 失败 ;----------------------------------- ;mov si,0 ;mov dx,1111h ;call appendnode ;------------------------------------- appendnode: push di push dx push bx push si call cmpnull cmp ah,1 jne appendg jmp appendret appendg: call makenode cmp ah,0 je appndgoon jmp appendfail appndgoon: ;mov point,bx mov di,point lea bx,mem mov [bx+di],dx mov ax,[bx+si] cmp ax,0 ;length==0? je appendemp push [bx+si+4] ;push right mov [bx+si+4],di ;right = di mov word ptr[bx+di+4],0 ;di->next=0 pop [bx+di+2] ;di->pre=(old)right push di mov di,[bx+di+2] ;di->pre->next=di pop [bx+di+4] jmp appendok appendemp: lea bx,mem mov di,point mov [bx+di],dx ;data mov word ptr[bx+di+2],0 mov word ptr[bx+di+4],0 mov [bx+si+2],di mov [bx+si+4],di appendok: inc word ptr [bx+si] ;lenght++ mov ah,0 jmp appendret appendfail: mov ah,1 appendret: pop bx pop dx pop di ret ;+++++++++++++++++++++++++++++ ;删除结点 ;参数： si 表地址,ax 位置 ;返回值： ah = 1失败 ; ah = 0成功 ;----------------------------------- ;mov si,0 ;mov ax,2 ;call deletenode ;------------------------------------- deletenode: push bp mov bp,sp sub sp,2 mov [bp-2],ax push bx push di push si call cmpnull cmp ah,1 jne deleteg jmp deleteret deleteg:lea bx,mem mov ax,[bp-2] cmp ax,[bx+si] ;>length? jna delnextcmp jmp deletefail delnextcmp: cmp ax,1 jnb delgoon jmp deletefail delgoon: cmp word ptr[bx+si],1 je delleftandright cmp ax,1 je delleft cmp ax,[bx+si] je delonlyright jmp delmiddle delleft: push [bx+si+2] ;left pop di push di mov di,[bx+di+4] ;left->next mov word ptr[bx+di+2],0 ;()->pre=0 dec word ptr [bx+si] mov [bx+si+2],di pop bx call free jmp deleteok delleftandright: mov word ptr [bx+si],0 push [bx+si+2] mov word ptr [bx+si+2],0 mov word ptr [bx+si+4],0 pop bx call free jmp deleteok delonlyright: push [bx+si+4] ;rightt mov di,[bx+si+4] mov di,[bx+di+2] ;rightt->pre mov word ptr [bx+di+4],0 ;()->next=0 dec word ptr [bx+si] mov [bx+si+4],di ;update right pop bx call free jmp deleteok delmiddle: mov di,[bx+si+2] ;left delnext:mov di,[bx+di+4] ;left->next dec ax cmp ax,1 ja delnext dec word ptr[bx+si] push di push [bx+di+2] ;di->pre push [bx+di+4] ;di->next mov di,[bx+di+2] ;di->di->pre pop [bx+di+4] ;di->pre ->next ==di->next mov di,[bx+di+4] ;di->next pop [bx+di+2] pop bx call free jmp deleteok deleteok: mov ah,0 jmp deleteret deletefail: mov ah,1 deleteret: pop di pop bx mov sp,bp pop bp ret ;++++++++++++++++++++++++++++++++ ;清空表 ;参数: si 表地址 ;-------------------------------- ;call clearlist ;-------------------------------- clearlist: mov ax,1 call deletenode cmp ah,0 je clearlist ret ;++++++++++++++++++++++++++++++ ;取得结点数据 ;参数: si-表地址 ; ax-结点位置 ;返回值: dx-结点数据 ; ah=0成功,ah=1失败 ;------------------------------- ; mov si,0 ; mov ax,2 ; call getelement ;------------------------------- getelement: push bp mov bp,sp sub sp,2 mov [bp-2],ax push bx push di push si call cmpnull cmp ah,1 je getelemfail mov ax,[bp-2] lea bx,mem cmp ax,[bx+si] ja getelemfail cmp ax,1 jb getelemfail mov di,[bx+si+2] ;left jmp getelemcmp getelemloop: mov di,[bx+di+4] ;di->next dec ax getelemcmp: cmp ax,1 ja getelemloop mov dx,[bx+di] mov ah,0 jmp getelemret getelemfail: mov ax,[bp-2] mov ah,01h getelemret: pop di pop bx mov sp,bp pop bp ret ;+++++++++++++++++++++++++++++++++ ;更新元素 ;参数： si-表地址, ax-位置(1，length), dx-元素值 ;返回值： ah=1 失败 ah =0 成功 ;------------------------------ ;mov si,0 ;mov ax,1 ;mov dx,0ffffh ;call updatenode ;------------------------------- updatenode: push bp mov bp,sp sub sp,2 mov [bp-2],ax push di push si call cmpnull cmp ah,1 je updateret lea bx,mem mov ax,[bp-2] cmp ax,[bx+si] ja updatefail cmp ax,1 jb updatefail mov di,[bx+si+2] ;left jmp updatecmp updateloop: mov di,[bx+di+4] dec ax updatecmp: cmp ax,1 ja updateloop mov [bx+di],dx mov ax,0 jmp updateret updatefail: mov ax,0100h updateret: pop di mov sp,bp pop bp ret ;+++++++++++++++++++++++++++++++++ ;考察所给元素在表中是否存在 ;参数: si-表地址,dx-要考察的值 ;返回值: ah = 0成功,al=idx; ah= 1 失败 ;--------------------------------- ;mov si,0 ;mov dx,0ffffh ;call findElemOf ;------------------------------- findElemOf: push di push si call cmpnull cmp ah,1 je findret lea bx,mem mov ax,1 ;length = count mov di,[bx+si+2] ;left findloop: cmp dx,[bx+di] je findout cmp ax,[bx+si] je findfail mov di,[bx+di+4] inc ax findout: mov ah,0 jmp findret findfail: mov ax,0100h findret: pop di ret ;++++++++++++++++++++++++++++ ;功能：合并 ;参数：si ，di ;返回值：list1 --> bx ;---------------------------- union: push bp mov bp,sp sub sp,4 push si call cmpnull cmp ah,1 je uniret push di call cmpnull cmp ah,1 je uniret lea bx,mem mov [bp-2],si mov [bp-4],di mov ax,[bx+si] add ax,[bx+di] mov [bx+si],ax ;length push [bx+si+4] mov di,[bx+di+2] pop [bx+di+2] mov si,[bx+di+2] mov [bx+si+4],di mov si,[bp-2] mov di,[bp-4] push [bx+di+4] pop [bx+si+4] ;si存储合并后的表地址,用作返回值 mov bx,di call free ;释放表指针不用的 uniret: mov sp,bp pop bp ret ;+++++++++++++++++++++++++++++++++ ;取得表中结点个数 ;参数: si-表地址 ;返回值: cx ;--------------------------------- ; call lengthof ;------------------------------- lengthof: push si call cmpnull cmp ah,1 je lengthret push bx lea bx,mem mov cx,[bx+si] pop bx lengthret: ret ;+++++++++++++++++++++++++++++++++ ;遍历 ;参数:栈传递 -表地址 ;---------------------------------- ; push list ; call traverse ;---------------------------------- traverse: push bp mov bp,sp mov ax,[bp+4] push ax call cmpnull cmp ah,1 je trafail mov si,[bp+4] call lengthof cmp cx,0 jna tra0 mov ax,0 lea di,buf traing: inc ax push ax mov si,list call getelement mov [di],dx inc di inc di pop ax loop traing tra0: nop trafail:mov sp,bp pop bp ret 2 ;+++++++++++++++++++++++++++++ ;申请一块内存空间 ;参 数: 无 ;返回值: bx 空间地址 ; ah=0 成功, ah=1 失败 ;----------------------------------- ; call alloc ;----------------------------------- Alloc: xor bx,bx lea bx,mta allocing: cmp word ptr ds:[bx],0 jne alloccon mov byte ptr ds:[bx],1 shl bx,1 shl bx,1 shl bx,1 shl bx,1 xor ax,ax mov ah,0 jmp allocret alloccon: inc bx cmp bx,79;256 ;最多可分配256个空间单位 jne allocing xor ax,ax mov ah,01h allocret: ret ;+++++++++++++++++++++++++++++ ;释放内存空间 ;参 数; bx 空间地址 ;返回值: 无 ;-----------------------------------; ; mov bx, ; call free ;-----------------------------------; free: push si push bx push bx call cmpnull cmp ah,1 je freefail shr bx,1 shr bx,1 shr bx,1 shr bx,1 and bx,00fffh cmp bx,79;256 ;max=256 jnb freefail lea si,mta cmp byte ptr ds:[bx+si+0],1 jne freefail mov byte ptr ds:[bx+si],0 freefail: pop bx pop si ret ;+++++++++++++++++++++++++++++ ;判断存储空间是否为空 ;参数： bx 空间地址 ;返回值： ah =1 null ;----------------------------------- ; cmpNULL:push bp mov bp,sp push si push bx mov bx,[bp+4] shr bx,1 shr bx,1 shr bx,1 shr bx,1 cmp bx,79;256 jnb benull lea si,mta cmp byte ptr [bx+si],1 jne benull mov ax,0 jmp notnull benull: mov ax,0100h notnull: pop bx pop si mov sp,bp pop bp ret 2 ;++++++++++++++++++++++++++++++ code ends end start [07/09/30] |