;队列之循环队列实现 算法详解及算法演示请参考 《队列【讲解】》及《队列【演示程序说明及下载】》
assume cs:code
null equ 0
true equ 1
false equ 0
data segment
Copyright db 'Copyright (c) 2007 www.asmedu.net','$';版权声明字符串
;队列元素定义
node_Def dw 0 ;01data element
node_Len equ $ - node_Def ;the length of data element
;队列头结点指针
node_OA dw 0 ;23pointer element OA
node_OA_Len equ $ - node_OA ;the length OA
node_SA dw 0 ;45pointer element SA
node_SA_Len equ $ - node_SA ;the length SA
;队列 一个队头下标,一个队尾下标
queue_Size dw 10h ;67当前队列长度最大值
head dw 0;89队头
rear dw 0;AB队尾
queue_Len dw 0;CD当前队列长度
queue_Max_Len equ X;自定义
data ends
code segment
start:
;相关准备工作
;算法调用
call create_Queue;创建队列
call entry_Queue ;入队
call peek_Queue ;取队头元素
call out_Queue ;出队
call clear_Queue ;清空队列
call exit ;退出程序
exit:
call cls
mov ax,4c00h
int 21h
;------------------------------------------------------------------------------------------
;-----------队列操作算法-------------------------------------------------------------------
;--1 equ success or true ------------------------------------------------------------------
;--0 equ failure or false------------------------------------------------------------------
;------------------------------------------------------------------------------------------
create_Queue:;创建队列;;(bx) = 0 失败 ,(bx) = 1 成功
push ax
call exist_Queue
cmp bx,true;已存在队列
je create_Queue_Failure
call malloc
cmp bx,false
je create_Queue_Failure
mov bx,true
jmp create_Queue_Ret
create_Queue_Failure:;失败
sub bx,bx
create_Queue_Ret:
pop ax
ret
exist_Queue:;判断是否存在有效的队列;(bx) = 1 存在 ,(bx) = 0 不存在
push ax
push ds
mov ax,data
mov ds,ax
mov bx,offset node_OA
mov ax,[bx]
cmp ax,null
jne exist_Queue_True
mov bx,offset node_SA
mov ax,[bx]
cmp ax,null
jne exist_Queue_True
sub bx,bx
jmp short exist_Queue_Ret
exist_Queue_True:
mov bx,true
exist_Queue_Ret:
pop ds
pop ax
ret
entry_Queue:;(ax) = new_Node.data 新节点入队 rear += node_Len ; ((node_SA)*10h+(node_OA)+(rear)) = (ax) ;;(bx) = 0 入队失败 ,(bx) = 1 成功
push ax
push dx ;保护现场
push ds
push ax
call exist_Queue
cmp bx,false
je entry_Queue_Failure
mov ax,data
mov ds,ax
mov bx,offset queue_Len
cmp word ptr [bx],queue_Max_Len
jnb entry_Queue_Failure
call full_Queue;判断队列是否已满
cmp bx,false
je not_Full
call malloc;满了,申请空间,追加
cmp bx,false
je entry_Queue_Failure
not_Full:;没满
mov ax,data
mov ds,ax
mov bx,offset rear
mov dx,[bx];找到队尾内存空间首址
mov bx,offset node_OA
mov bx,[bx]
add bx,dx
push bx
mov bx,offset node_SA
mov dx,[bx]
mov ds,dx
pop bx
pop ax
mov word ptr [bx],ax;节点数据存入队尾 mov [bx],ax
mov ax,data
mov ds,ax;
mov bx,offset queue_Len
add word ptr [bx],1;当前队列长度加 1
mov bx,offset rear
add word ptr [bx],node_Len;;对于非空队列,尾指针后移
mov dx,0;调整尾指针 rear=(rear+1)%queue_Max_Len
mov ax,[bx]
mov cx,queue_Max_Len*node_Len
div cx
mov word ptr [bx],dx
mov bx,true;成功
jmp entry_Queue_Ret
entry_Queue_Failure:
pop ax
sub bx,bx
entry_Queue_Ret:
pop ds;恢复现场
pop dx
pop ax
ret
out_Queue:;队头元素出队,head -= node_Len ; (ax) = ((node_SA)*10h+(node_OA)+(head));(bx) = 0 队列为空 ,出队失败 ,(bx) = 1 出队成功
push dx;保护现场
push ds
call exist_Queue
cmp bx,false
je out_Queue_Failure
call empty_Queue
cmp bx,true
je out_Queue_Failure
mov ax,data
mov ds,ax
mov bx,offset head ;定位头结点数据所在位置
mov dx,[bx]
mov bx,offset node_OA;
add dx,[bx]
push dx
mov bx,offset node_SA
mov dx,[bx]
mov ds,dx
pop bx
mov ax,[bx];取出头结点,由ax返回
mov word ptr [bx],null;结点清零,可根据结点长度改变指令重复次数
push ax
mov dx,data
mov ds,dx
mov bx,offset queue_Len
sub word ptr [bx],1 ;队列长度减 1
mov bx,offset head;调整头指针 head=(head+1)%queue_Max_Len
add word ptr [bx],node_Len
mov dx,0
mov ax,[bx]
mov cx,queue_Max_Len*node_Len
div cx
mov [bx],dx
pop ax
mov bx,true
jmp short out_Queue_Ret
out_Queue_Failure:
sub bx,bx
out_Queue_Ret:
pop ds;恢复现场
pop dx
ret
peek_Queue:;读取队首元素,不改变队列状态 head += node_Len ; (ax) = ((node_SA)*10h+(node_OA)+(head)) ; head -= node_Len ;;(bx) = 0 队列为空 ,读取失败 ,(bx) = 1读取成功
push dx
push ds
call exist_Queue
cmp bx,false
je peek_Queue_Failure
call empty_Queue
cmp bx,true
je peek_Queue_Failure
mov dx,data
mov ds,dx
mov bx,offset head
mov dx,[bx]
mov bx,offset node_OA
add dx,[bx]
push dx
mov bx,offset node_SA
mov dx,[bx]
mov ds,dx
pop bx
mov ax,[bx]
mov bx,true
jmp peek_Queue_Ret
peek_Queue_Failure:
sub bx,bx
peek_Queue_Ret:
pop ds ;恢复现场
pop dx
ret
clear_Queue:;清除队列;(bx) = 1 清除成功 ,(bx) = 0清除失败
push dx;保护现场
push ds
call exist_Queue
cmp bx,false
je clear_Queue_Failure
out_Queue_Element:
call out_Queue
cmp bx,false
je clear_Queue_Success
jmp out_Queue_Element
clear_Queue_Success:
mov bx,true
jmp clear_Queue_Ret
clear_Queue_Failure:
sub bx,bx
clear_Queue_Ret: ;恢复现场
pop ds
pop dx
ret
empty_Queue:;判断队列是否为空 (bx) = 1 空;(bx) = 0 非空
push ax;保存现场
push cx
push ds
mov ax,data
mov ds,ax
mov bx,offset queue_Len
cmp word ptr [bx],null
jne empty_Queue_Failure
mov bx,true;队列为空 返回 1
jmp empty_Queue_Ret
empty_Queue_Failure:
sub bx,bx;队列非空返回 0
empty_Queue_Ret:
pop ds;恢复现场
pop cx
pop ax
ret
full_Queue:;判队列是否已满 返回 (bx) = 0 未满 ,(bx) = 1 已满
push ax ;保存现场
push dx
push ds
mov ax,data
mov ds,ax
mov bx,offset queue_Len
cmp word ptr [bx],queue_Max_Len
jb full_Queue_Failure
mov bx,true
jmp full_Queue_Ret
full_Queue_Failure:
sub bx,bx
full_Queue_Ret:
pop ds;恢复现场
pop dx
pop ax
ret
malloc: ;申请内存空间 (bx) = 0申请失败,(bx) = 申请空间大小,成功
push ax;保存现场
push dx
push ds
mov ax,data
mov ds,ax
mov bx,offset queue_Size
mov ax,[bx]
mov dx,0
mov bx,node_Len
mul bx
mov bx,ax;
push bx;计算再追加的空间大小 queue_Size*node_Len
call exist_Queue;检验是否是初始化还是重新分配内存
cmp bx,false
je short malloc_Update;
malloc_For_Exist_Queue:;重新分配内存空间 (ax) = offset queue ;返回内存空间偏移地址, 当前队列偏移地址+head偏移量
mov bx,offset node_OA;获得当前队列存储空间的首地址_OA
mov ax,[bx];(bx) = 比较一下追加空间后,是否超过最大限度
mov bx,offset head
add ax,[bx]
pop bx;
push bx
add ax,bx;(ax)=(node_OA)+(head)+allocSpace (bx)
mov dx,limit_Size
cmp ax,dx
ja malloc_Failure
mov bx,offset node_OA
mov ax,[bx]
mov bx,offset head;队列空间初始分配 当前队列偏移地址+head偏移量
add ax,[bx]
malloc_Update:
mov ax,offset queue;队列空间初始分配 内存空间偏移地址---数据空间首地址偏移地址
mov bx,offset node_OA;将地址传给队指针
mov [bx],ax;OA内存空间的偏移地址
mov ax,queue
mov bx,offset node_SA
mov [bx],ax;SA内存空间的段地址
mov bx,offset rear;
mov ax,[bx]
mov bx,offset head
sub ax,[bx] ;rear-head
mov word ptr [bx],null;调整头指针 head = 0
mov bx,offset rear;调整尾指针
mov [bx],ax
pop bx
jmp malloc_Ret
malloc_Failure:
sub bx,bx
malloc_Ret:
pop ds ;恢复现场
pop dx
pop ax
ret
free: ;(ax) = 释放内存空间段地址;释放内存空间 (bx) = 1 释放成功, (bx) = 0释放失败
push es;保存现场
push dx
push ax
mov ah,49h
int 21h
pop bx
push bx
cmp bx,ax
jne free_Failure;释放内存空间失败
mov bx,true
jmp free_Ret
free_Failure:
sub bx,bx
free_Ret:
pop ax;恢复现场
pop dx
pop es
ret
;------------------------------------------------------------------------------------------
;----算法定义完毕--------------------------------------------------------------------------
;------------------------------------------------------------------------------------------
code ends
queue segment ;队列放置内存空间,可自定义
data_Memory_Space db 1000h dup(0)
limit_Size equ $ - data_Memory_Space
queue ends
end start
[07/09/21] |