8.3.3利用邻接矩阵的图深度优先遍历算法.txt

是关于嵌入式编程的图和树部分程序

STACK	EQU		1FH				
BOTTOM	EQU		00H					
TOP		DATA	3DH				
GRAPH	EQU		20H				
OUT		EQU		21H					
N		DATA	3EH				
K		DATA	3FH					
TST:	
MOV	SP,#5FH					
MOV	DPTR,#GRA					
MOV	P2,#GRAPH
MOV	R0,#0
MOV	R2,#0A0H
CPY:	
CLR	A
MOVC	A,@A+DPTR
MOVX	@R0,A
INC		DPTR
INC		R0
DJNZ	R2,CPY
MOV	P2,#GRAPH					
MOV	R0,#0
MOVX	A,@R0						
JZ		STOP					
INC		A
MOV	N,A						
MOV	K,#1						
TST1:	
MOV	DPH,#OUT				
MOV	DPL,#0
MOV	R2,#0
CLR		A
CLEAR:	
MOVX	@DPTR,A						
INC	DPTR
DJNZ	R2,CLEAR
MOV	P2,#GRAPH					
MOV	R0,#0
MOV	DPH,#OUT				
MOV	DPL,#0
MOVX	A,@R0						
MOVX	@DPTR,A						
MOV	R7,A						
INC		R7							
INC		DPTR						
LCALL	SETNULL					
MOV	R0,#10H					
CLRF:	CLR	A
MOVX	@R0,A
MOV	A,#10H					
ADD		A,R0
MOV	R0,A
JNZ		CLRF
MOV	A,K						
LCALL	DFS							
INC		K							
MOV	A,K
CJNE	A,N,TEST1				
STOP:	LJMP	STOP
;出发点为1时的遍历顺序：ABCDEFGHI
;出发点为2时的遍历顺序：BAHGEDCFI
;出发点为3时的遍历顺序：CBAHGEDFI
;出发点为4时的遍历顺序：DCBAHGEFI
;出发点为5时的遍历顺序：EDCBAHGFI
;出发点为6时的遍历顺序：FCBAHGEDI
;出发点为7时的遍历顺序：GEDBCAHIF
;出发点为8时的遍历顺序：HABCDEFGI
;出发点为9时的遍历顺序：IBAHGEDCF

DFS:	
MOV	R2,A							
MOV	R0,A
MOVX	A,@R0					
MOVX	@DPTR,A						
INC		DPTR					
MOV	A,R0	
SWAP	A
MOV	R1,A						
MOV	A,#0FFH						
MOVX	@R1,A
SEARCH:	
INC		R1							
MOV	A,R1							
XRL		A,R7
ANL		A,#0FH						
JZ		DFSEND						
MOVX	A,@R1						
JZ		SEARCH						
MOV	A,R1
ANL		A,#0FH						
SWAP	A
MOV	R0,A
MOVX	A,@R0						
JNZ		SEARCH						
MOV	A,R1							
LCALL	DPUSH						
ANL		A,#0FH						
LCALL	DFS						
LCALL	DPOP						
MOV	R1,A
LJMP	SEARCH						
DFSEND:	RET							
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: 09 41 42 43 44 45 46 47 48 49
;2010H: 00 00 01 00 00 00 00 00 01 00
;2020H: 00 01 00 01 00 00 00 00 00 01
;2030H: 00 00 01 00 01 00 01 00 00 00
;2040H: 00 00 00 01 00 01 00 00 00 00
;2050H: 00 00 00 00 01 00 01 01 00 00
;2060H: 00 00 00 01 00 01 00 01 00 01
;2070H: 00 00 00 00 00 01 01 00 01 00
;2080H: 00 01 00 00 00 00 00 01 00 01
;2090H: 00 00 01 00 00 00 01 00 01 00
GRA:	
DB		09H,41H,42H,43H				
DB		44H,45H,46H,47H
DB		48H,49H,00H,00H
END