btree.asm

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

;图的广度优先生成树生成算法（利用邻接表）。
GRAPH	EQU	20H	;图存放的页面（邻接表起点为页面起点）。
TREE	EQU	21H	;生成树节点存放的片外RAM页面。
QUEUE	EQU	1FH	;循环队列存储页面。
NODE	EQU	30H	;顶点信息存放起点。
FG	EQU	40H	;访问标志存放起点。
D	EQU	05H	;邻接子表长度。
POINT	EQU	80H	;父指针数组存放起点。
F	DATA	3CH	;队首指针的存放单元。
R	DATA	3DH	;队尾指针的存放单元。
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,#4AH
COPY:	CLR	A
	MOVC	A,@A+DPTR
	MOVX	@R0,A
	INC	DPTR
	INC	R0
	DJNZ	R2,COPY
	MOV	P2,#GRAPH;指向图的存放页面。
	MOV	R0,#NODE
	MOVX	A,@R0	;读取图的有效顶点总数。
	JZ	STOP	;如果是空图，则结束访问。
	INC	A
	MOV	N,A	;保存顶点总数加一。
	MOV	K,#1	;以编号为１的顶点作为生成树的树根。
TEST1:	MOV	DPH,#TREE;指向生成树存放的片外RAM页面。
	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;指向存放生成树的片外RAM页面。
	MOV	DPL,#0
	MOVX	A,@R0	;读取图的有效顶点总数。
	MOVX	@DPTR,A	;存放到生成树的00H单元。
	INC	DPTR	;指生成树第一个节点的存放位置。
	MOV	R7,A
	MOV	R0,#FG	;初始化访问标志。
	INC	R0
CLRF:	CLR	A
	MOVX	@R0,A
	INC	R0
	DJNZ	R7,CLRF
	LCALL	SETNULL	;初始化队列为空队。
	MOV	A,#0	;根节点的父节点编号为零（没有父节点）。
	LCALL	DATAIN	;排入队列中。
	MOV	A,K	;取生成树根节点的编号。
	LCALL	DATAIN	;排入队列中。
	LCALL	BTREE	;调用广度优先生成树算法。
	INC	K		;换一个顶点作为生成树的树根。
	MOV	A,K
	CJNE	A,N,TEST1	;测试完所有顶点。
STOP:	LJMP	STOP

BTREE:	MOV	A,F	;判断是否为空队。
	XRL	A,R
	JZ	BFSEND	;是空队，访问结束。
	LCALL	DATAOUT	;队首顶点的父节点编号出队。
	MOV	R4,A
	LCALL	DATAOUT	;队首顶点编号出队。
	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	R1,A
	MOV	A,#0FFH
	MOVX	@R1,A	;设立已访问标志。
	MOV	A,R2	;计算邻接子表的起始地址。
	DEC	A
	MOV	B,#D
	MUL	AB
	MOV	R1,A	;开始查邻接矩阵。
LOOP:	MOVX	A,@R1	;读取邻接子表的元素。
	JZ	BTREE	;为零，子表结束，继续处理队列中的其它顶点。
	MOV	R3,A	;保存相邻顶点编号。
	ADD	A,#FG
	MOV	R0,A
	MOVX	A,@R0	;读取相邻顶点的访问标志。
	JNZ	LOOPE	;该顶点已访问（或者已在队列中），跳过。
	MOV	A,R2	;尚未访问过，取当前顶点编号。
	LCALL	DATAIN	;作为父节点，将其排入队列中。
	MOV	A,R3	;取相邻顶点编号。
	LCALL	DATAIN	;将其排入队列中。
	MOV	A,#1
	MOVX	@R0,A	;设置已经入队标志。
LOOPE:	INC	R1	;调整邻接子表元素指针。
	LJMP	LOOP	;继续处理邻接子表中的其它单元。
BFSEND:	RET	;返回。

SETNULL:MOV	A,#0FFH
	MOV	F,A		;使队首指针指向队列页面的最后一个单元。
	MOV	R,A		;使队尾指针也指向队列页面的最后一个单元。
	RET			;设置好空队列。

DATAIN:	PUSH	DPH
	PUSH	DPL
	INC	R		;调整队尾指针。
	MOV	DPL,R
	MOV	DPH,#QUEUE
	MOVX	@DPTR,A		;排入队尾。
	POP	DPL
	POP	DPH
	RET			;结束

DATAOUT:PUSH	DPH
	PUSH	DPL
	INC	F		;调整队首指针。
	MOV	DPL,F
	MOV	DPH,#QUEUE
	MOVX	A,@DPTR		;取待出队数据。
	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
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H
	END