nettree.asm

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

;网络的最小生成树算法（利用邻接矩阵）。
;
;              A
;            / | \
;        4 /   |   \ 7
;        /     |     \
;      B      6|       C
;      | \ 9   |   8 / |
;      |   \   |   /   |
;      |     \ | /     |
;     8|       D       |5
;      |     / | \ 3   | 
;      |  5/   |   \   | 
;      | /     |     \ | 
;      E      4|       F 
;       \      |      /
;         \    |    /  
;        2  \  |  / 3
;              G
;
;
NET	EQU	20H	;网络存放的片外RAM页面（顶点总数不超过13）。
LEN	EQU	0E0H	;边长数组起始地址。
POINT	EQU	0F0H	;父指针数组起始地址。
N	DATA	3EH	;顶点总数加一存放单元。
K	DATA	3FH	;生成树的根节点编号存放单元。

	ORG	0000H
	LJMP	TEST
	
	ORG	100H
TEST:	MOV	SP,#5FH	;设置足够大的系统堆栈空间。
	MOV	DPTR,#NETDAT;将网络邻接矩阵拷贝到片外ＲＡＭ中。
	MOV	P2,#NET
	MOV	R0,#0
	MOV	R2,#80H
COPY:	CLR	A
	MOVC	A,@A+DPTR
	MOVX	@R0,A
	INC	DPTR
	INC	R0
	DJNZ	R2,COPY
	MOV	DPH,#NET	;指向网络存放的片外RAM页面。
	MOV	DPL,#0
	MOVX	A,@DPTR		;读取网络顶点总数。
	INC	A
	MOV	N,A		;保存网络顶点总数。
	MOV	K,#1		;以编号为１的顶点作为生成树的根节点。
TEST1:	LCALL	MINTREE		;求解最小生成树。
	INC	K		;换一个顶点作为根节点。
	MOV	A,K
	CJNE	A,N,TEST1
STOP:	LJMP	STOP

;求解结果（本网络的最小生成树是唯一的，与根节点的选择无关）：
;              A
;            / |  
;        4 /   |      
;        /     |      
;      B      6|       C
;              |       |
;              |       |
;              |       |
;              D       |5
;              | \ 3   | 
;              |   \   | 
;              |     \ | 
;      E      4|       F 
;       \      |       
;         \    |       
;        2  \  |     
;              G
;
;

MINTREE:MOV	DPH,#NET;指向网络存放的片外RAM页面。
	MOV	DPL,#0
	MOVX	A,@DPTR	;读取网络顶点总数。
	MOV	R7,A	;保存网络顶点总数。
	MOV	R6,A
CLEAR:	MOV	A,DPL	;指向访问标志数组（竖向分布）。
	ADD	A,#10H
	MOV	DPL,A
	CLR	A
	MOVX	@DPTR,A	;初始化访问标志。
	DJNZ	R6,CLEAR
	MOV	P2,#NET	;指向网络的存放页面。
	MOV	A,K	;读取生成树根节点编号。
	MOV	R2,A
	SWAP	A
	MOV	R1,A	;根节点标志单元。
	MOV	A,#1
	MOVX	@R1,A	;将根节点设置为已访问。
	MOV	R0,#LEN	;准备初始化边长数组。
	MOV	A,R7
	MOV	R6,A	;控制范围。
MINTR:	INC	R1	;调整指针。
	INC	R0	;
	MOVX	A,@R1	;读取到根节点的距离。
	MOVX	@R0,A	;作为该顶点到生成树的初始距离。
	DJNZ	R6,MINTR
	MOV	R0,#POINT;准备初始化父指针数组。
	MOV	A,R7	;控制范围。
	MOV	R6,A
	MOV	A,R2	;读取根节点的编号。
MINTR1:	INC	R0
	MOVX	@R0,A	;作为其它顶点的父节点。
	DJNZ	R6,MINTR1
	MOV	A,R2
	ADD	A,#POINT
	MOV	R0,A	;指向根节点自己的父节点单元。
	MOV	A,#0
	MOVX	@R0,A	;填入０，表示自己是根节点。
	MOV	A,R7
	DEC	A
	MOV	R3,A	;准备将其它n－1个顶点扩充到生成树中来。
MINTR2:	MOV	R4,#0FFH;初始化距离最小值，准备寻找离生成树最近的顶点。
	MOV	R5,#0	;初始化距离最近顶点的编号。
	MOV	R0,#LEN+1;指向边长数组。
	MOV	R1,#10H	;指向标志数组。
	MOV	A,R7	
	MOV	R6,A	;控制寻找范围。
MINTR3:	MOVX	A,@R1	;读取一个标志。
	JNZ	MINTR4	;该顶点已访问，跳过。
	MOVX	A,@R0	;尚未访问，读取该顶点到生成树的距离。
	CLR	C
	SUBB	A,R4	;与当前最小值比较。
	JNC	MINTR4	;不是新的最小值。
	MOVX	A,@R0
	MOV	R4,A	;保存新的最小值。
	MOV	A,R0
	ANL	A,#0FH	;取新的最小值对应的顶点编号。
	MOV	R5,A	;保存新的最小值对应的顶点编号。
MINTR4:	INC	R0	;调整数组指针。
	MOV	A,R1	;调整标志指针。
	ADD	A,#10H
	MOV	R1,A
	DJNZ	R6,MINTR3;查完全部顶点。
	MOV	A,R5	;读取找到的顶点编号。
	SWAP	A
	MOV	R0,A	;指向新顶点的标志单元。
	MOV	A,#1
	MOVX	@R0,A	;设置访问标志，该顶点进入生成树中。
	INC	R0	;指向新顶点的邻接矩阵对应行。
	MOV	DPL,#LEN+1;指向边长数组。
	MOV	R1,#10H	;指向标志数组。
	MOV	A,R7
	MOV	R6,A	;控制调整范围，准备对边长数组进行调整。
MINTR6:	MOVX	A,@R1	;读取访问标志。
	JNZ	MINTR7	;已访问，不需调整。
	MOVX	A,@R0	;读取到新顶点的距离（边长）。
	MOV	R2,A	;并保存之。
	MOVX	A,@DPTR	;读取到生成树的距离。
	SETB	C
	SUBB	A,R2	;进行比较。
	JC	MINTR7	;到新顶点更远，不用调整。
	MOV	A,R2	;取到新顶点的距离。
	MOVX	@DPTR,A	;作为新的到生成树的距离。
	MOV	A,R0	;保存指针。
	MOV	R2,A
	ANL	A,#0FH
	ADD	A,#POINT
	MOV	R0,A	;指向该顶点的父节点编号存放单元。
	MOV	A,R5	;以新顶点作为该顶点的父节点。
	MOVX	@R0,A	;
	MOV	A,R2	;恢复指针。
	MOV	R0,A
MINTR7:	INC	R0	;调整指针。
	INC	DPTR	;
	MOV	A,R1	;
	ADD	A,#10H
	MOV	R1,A
	DJNZ	R6,MINTR6;处理完边长数组的全部单元。
	DJNZ	R3,MINTR2;继续查找下一个准备扩充的顶点。
	RET		;全部顶点均已进入生成树，算法结束。

;2000H: 07 41 42 43 44 45 46 47----顶点信息
;邻接矩阵 :
;2010H: 00 00 04 07 06 FF FF FF
;2020H: 00 04 00 FF 09 08 FF FF
;2030H: 00 07 FF 00 08 FF 05 FF
;2040H: 00 06 09 08 00 05 03 04
;2050H: 00 FF 08 FF 05 00 FF 02
;2060H: 00 FF FF 05 03 FF 00 09
;2070H: 00 FF FF FF 04 02 09 00
;
;20E0H: 00 00 00 00 00 00 00 00----距离数组
;20F0H: 00 00 00 00 00 00 00 00----父指针数组
NETDAT:	DB	07H,41H,42H,43H
	DB	44H,45H,46H,47H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,04H,07H
	DB	06H,0FFH,0FFH,0FFH
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,04H,00H,0FFH
	DB	09H,08H,0FFH,0FFH
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,07H,0FFH,00H
	DB	08H,0FFH,05H,0FFH
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,06H,09H,08H
	DB	00H,05H,03H,04H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,0FFH,08H,0FFH
	DB	05H,00H,0FFH,02H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,0FFH,0FFH,05H
	DB	03H,0FFH,00H,09H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	DB	00H,0FFH,0FFH,0FFH
	DB	04H,02H,09H,00H
	DB	00H,00H,00H,00H
	DB	00H,00H,00H,00H
	END