dfs.asm

在定时器中断中做LED的PWM输出 AT89C2051实现A/D转换的C51程序 单片机开发系统 指令系统 程序设计 定时与中断 系统扩展 接口技术 串行口

;图的深度优先遍历算法（利用邻接矩阵）。

STACK	EQU	1FH	;用户堆栈所在页面。
BOTTOM	EQU	00H	;用户堆栈栈底单元。
TOP	DATA	3DH	;用户堆栈栈顶指针。
GRAPH	EQU	20H	;图存放的片外RAM页面（顶点总数不超过15）。
OUT	EQU	21H	;被访问顶点信息输出存放页面。
N	DATA	3EH	;顶点总数加一存放单元。
K	DATA	3FH	;访问出发点编号存放单元。

	ORG	0000H
	LJMP	TEST
	
	ORG	100H
TEST:	MOV	SP,#5FH	;设置足够大的系统堆栈空间。
	MOV	DPTR,#GRA;将邻接矩阵拷贝到片外ＲＡＭ中。
	MOV	P2,#GRAPH
	MOV	R0,#0
	MOV	R2,#0A0H
COPY:	CLR	A
	MOVC	A,@A+DPTR
	MOVX	@R0,A
	INC	DPTR
	INC	R0
	DJNZ	R2,COPY
	MOV	P2,#GRAPH;指向图的存放页面。
	MOV	R0,#0
	MOVX	A,@R0	;读取图的有效顶点总数。
	JZ	STOP	;如果是空图，则结束访问。
	INC	A
	MOV	N,A	;保存顶点总数加一。
	MOV	K,#1	;从编号为１的顶点开始访问。
TEST1:	MOV	DPH,#OUT;指向输出存放顶点信息的片外RAM页面。
	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;指向输出存放顶点信息的片外RAM页面。
	MOV	DPL,#0
	MOVX	A,@R0	;读取图的有效顶点总数。
	MOVX	@DPTR,A	;存放到输出区的00H单元。
	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	;设置已访问标志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
	DB	00H,00H,00H,00H
	DB	00H,00H,01H,00H
	DB	00H,00H,00H,00H
	DB	01H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,01H,00H,01H
	DB	00H,00H,00H,00H
	DB	00H,01H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,01H,00H
	DB	01H,00H,01H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,01H
	DB	00H,01H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	01H,00H,01H,01H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,01H
	DB	00H,01H,00H,01H
	DB	00H,01H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,01H,01H,00H
	DB	01H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,01H,00H,00H
	DB	00H,00H,00H,01H
	DB	00H,01H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,01H,00H
	DB	00H,00H,01H,00H
	DB	01H,00H,00H,00H
	DB	00H,00H,00H,00H
	END