8.3.5利用邻接表图的深度优先生成树生成算法.txt

《MCS-51单片机应用开发实用子程序》配套源代码

STACK	EQU		1FH				
BOTTOM	EQU		00H					
TOP		DATA	3DH					
GRAPH	EQU		20H				
TREE	EQU		21H				
NODE	EQU		30H				
FG		EQU		40H				
D		EQU		05H				
POINT	EQU		80H					
N		DATA	3EH				
K		DATA	3FH				
TST:	
MOV	SP,#5FH						
MOV	DPTR,#GRA				
MOV	P2,#GRAPH
MOV	R0,#0
MOV	R2,#4AH
CPY:	
CLR		A
MOVC	A,@A+DPTR
MOVX	@R0,A
INC		DPTR
INC		R0
DJNZ	R2,CPY
MOV	P2,#GRAPH					
MOV	R0,#NODE
MOVX	A,@R0						
JZ		STOP					
INC		A
MOV	N,A							
MOV	K,#1							
MOV	SP,#5FH					
TST1:	
MOV	DPH,#TREE					
MOV	DPL,#0
MOV	R2,#0						
CLR		A
CLEAR:	
MOVX	@DPTR,A						
INC		DPTR
DJNZ	R2,CLEAR
MOV	P2,#GRAPH				
MOV	R0,#NODE
MOV	DPH,#TREE				
MOV	DPL,#0
MOVX	A,@R0						
MOVX	@DPTR,A						
INC		DPTR					
MOV	R7,A
MOV	R0,#FG					
INC		R0
CLRF:	
LR		A
MOVX	@R0,A
INC		R0
DJNZ	R7,CLRF
LCALL	SETNULL						
MOV	A,K						
MOV	R4,#0						
LCALL	DTREE						
INC		K							
MOV	A,K
CJNE	A,N,TEST1					
STOP:	LJMP	STOP
DTREE:	
MOV	R2,A						
ADD		A,#NODE
MOV	R0,A
MOVX	A,@R0						
MOVX	@DPTR,A						
MOV	A,DPL
CPL		ACC.7					
MOV	DPL,A
MOV	A,R4							
MOVX	@DPTR,A						
MOV	A,DPL
CPL		ACC.7						
MOV	DPL,A
INC		DPTR					
MOV	A,R2	
ADD		A,#FG
MOV	R0,A							
MOV	A,#0FFH
MOVX	@R0,A						
MOV	A,R2						
DEC		A
MOV	B,#D
MUL		AB
MOV	R1,A
SEARCH:	
MOVX	A,@R1					
JZ		DFSEND					
MOV	R3,A
ADD		A,#FG
MOV	R0,A
MOVX	A,@R0						
JNZ		SEAR1					
MOV	A,R2						
LCALL	DPUSH					
MOV	A,R1
LCALL	DPUSH						
MOV	A,R2						
MOV	R4,A							
MOV	A,R3							
LCALL	DTREE						
LCALL	DPOP						
MOV	R1,A
LCALL	DPOP						
MOV	R2,A
SEAR1:	
INC		R1
LJMP	SEARCH					
DFSEND:	
ET								
SETNULL:
MOV	A,#BOTTOM					
MOV	TOP,A					
RET								
DPUSH:	
INC		TOP						
PUSH	DPH
PUSH	DPL
MOV	DPH,#STACK					
MOV	DPL,TOP						
MOVX	@DPTR,A						
POP		DPL
POP		DPH
RET								
DPOP:	
PUSH	DPH
PUSH	DPL
MOV	DPH,#STACK				
MOV	DPL,TOP						
MOVX	A,@DPTR					
DEC		TOP						
POP		DPL
POP		DPH
RET									
;2000H: 02 08 00 00 00
;2005H: 01 03 09 00 00
;200AH: 02 04 06 00 00
;200FH: 03 05 00 00 00
;2014H: 04 06 07 00 00
;2019H: 03 05 07 09 00
;201EH: 05 06 08 00 00
;2023H: 01 07 09 00 00
;2028H: 02 06 08 00 00
;2030H: 09 41 42 43 44 45 46 47 48 49
;2040H: 00 00 00 00 00 00 00 00 00 00
GRA:	
DB		02H,08H,00H,00H				
DB		00H,01H,03H,09H
DB		00H,00H,02H,04H
DB		06H,00H,00H,03H
DB		05H,00H,00H,00H
DB		04H,06H,07H,00H
DB		00H,03H,05H,07H
DB		09H,00H,05H,06H
DB		08H,00H,00H,01H
DB		07H,09H,00H,00H
DB		02H,06H,08H,00H
DB		00H,00H,00H,00H
DB		09H,41H,42H,43H
DB		44H,45H,46H,47H
DB		48H,49H,00H,00H
END