拓扑排序 asm x86
Topological sorting asm x86
我在 emu8086 中编写 asm x86 代码时遇到了很大的问题，该代码在给定邻接矩阵和节点数的情况下找到图（没有圆环）的拓扑排序。我已经尝试了几个想法，但没有任何效果......所以如果你们中的任何人可以给我任何帮助（以文字或代码的形式）来解决这个问题，或者如何解决这个问题，那就太好了因为我不知道该怎么办...
数据是这样给出的：
JMP main
size db 4
graph db 0 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0
ordering db 0 ,0 ,0 ,0
main :
我认为 DFS 算法可能是解决这个问题的最佳方法。但同样，我真诚地尝试了一切，但到目前为止没有任何效果......所以我会感谢任何帮助。
提前致谢！！！ （抱歉英语不好）
编辑：我写了这个但是根本不起作用：
JMP main
size db 4
graph db 0 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0
ordering db 0 ,0 ,0 ,0
permanente db 0, 0, 0, 0
main :
MOV CL,1
PUSH CX
LEA BX,graph
PUSH BX
CALL visitar
RET
visitar:
PUSH BP
MOV BP,SP
MOV BX,[BP+4]
MOV CX,[BP+6]
LEA DI,size
MOV DX,[DI]
MOV SI,0
for:
CMP SI,DX
JE end_for
CMP [BX+SI],1
JE nodo
JMP next
nodo:
MOV CX,SI
ADD CX,1
PUSH CX
MOV AX,SI
MUL size
LEA BX,graph
ADD BX,AX
PUSH BX
CALL visitar
next:
ADD SI,1
JMP for
end_for:
LEA DI,permanente
ADD DI,CX
SUB DI,1
MOV [DI],1
MOV SI,DX
LEA DX,ordering
bajar:
SUB SI,1
CMP [DX+SI],0
JE cambiar
CMP SI,0
JG bajar
cambiar:
MOV [DX+SI],CX
CMP SI,0
JE return
JMP revisar
revisar:
LEA AX,permanente
MOV SI,0
sumar:
CMP [AX+SI],0
JE seguir
ADD SI,1
LEA DI,size
MOV DX,[DI]
CMP SI,DX
JE return
JMP sumar
seguir:
JMP nodo
return:
POP BP
RET 4
我通过阅读源代码发现的一些错误（我不要求列表的完整性，可能还有更多）：
LEA DI,size
MOV DX,[DI]
大小被声明为字节，但你获取的是单词，所以你实际上是从图形中获取大小+第一条边。如果第一个边为 1，则 dx 将为 300 而不是预期的 4。
通过 dw 声明将 size 扩展为单词，或者仅使用字节。
您也可以直接从地址 mov dx,[size] 获取大小，不需要 lea 它的地址。
CMP [BX+SI],1
我不喜欢这种语法，不清楚比较的是什么大小。我不确定 emu8086 语法有什么，尝试在任何一侧添加 byte，如 BYTE 1，或 BYTE PTR [bx+si]，如 TASM/MASM 语法。我希望其中之一能奏效。
虽然这可能看起来像 "style" 偏好，但如果您的边缘定义比 0/1 更复杂并使用单词，那将是错误（因为我怀疑默认结果是字节比较）。
MUL size
详情请查看使用说明。您破坏了另一个寄存器的内容，这将使您的 for 失败。
另外我不喜欢这种语法，你想要内存中的值在 size 地址，而不是地址本身，所以在 size 周围添加 [] 更容易理解，你对内存内容感兴趣。
最后没有指定数据大小，我完全错过了那个。因此，如果汇编程序将其视为字节，那么关于销毁寄存器内容的第一条评论是无效的，但看起来你想要执行 ax*size，这将需要字说明符。顺便说一句，你已经在 dx 中加载了大小，所以 mul dx 或 mul dl 会节省你的内存访问。
CALL visitar
您确实缺少高级文档。
创建汇编函数时，始终在注释中记录什么是参数（如何调用）、结果是什么（如果有）以及修改了哪些寄存器。
您的 visitar 确实修改了许多寄存器，但在 for 循环期间您不知何故期望 si 被保留。不是。然后稍后您使用 cx 作为原始节点号，但同样，在准备调用参数期间已经被销毁。等等...因为它是递归调用，你可以肯定它会破坏所有对你很重要的寄存器。
你将单词存储到ordering，而它被定义为字节数组，偏移量以字节为单位。
MOV CL,1
PUSH CX
ch在这里未初始化（emu8086可能为零，但最好初始化所有内容，因为不同的目标平台可能会在不同的状态下调用您的"start"。
如何改进你所拥有的：
我会做一些设计工作，什么是全局变量，什么是局部变量。然后你可以尝试保持全局变量，比如大小在整个 运行 期间不会改变，或者排序 [next_to_write] 指针是全局的，等等
push/pop 调用 visitar 之前的重要寄存器以保留其值。或者，由于使用堆栈作为函数参数而无论如何都使用堆栈帧，请考虑将局部变量放入堆栈（sub sp,reserved_space 并通过 [bp-x] 访问它）。这样你就不需要担心修改寄存器，虽然它会由于内存访问而工作得更慢。
确保所有值的大小都正确。确定节点数 (size) 是字节还是字，这几乎决定了其余变量。虽然您的 graph 定义是 size*size long，但实际上您不能拥有超过 ~200 个节点，所以只使用 byte 大小是可以的。但这意味着坚持下去，即。 mov [dx+si],cl 将节点号存入ordering。并且在处理图形时，确保 mul 也适用于 16+ 尺寸。
一些样式注释：
add/sub r16,1 -> 还有 inc/dec 说明。
LEA AX,permanente - 原始的 Intel 语法要求表达式类似于访问内存，因此 LEA AX,[permanente] 看起来更像是 Intel 的意图。尽管在 lea 的情况下，它实际上不适用于内存内容，所以我最初并不是英特尔决定的忠实粉丝。然后 lea ax,bx+si*2+permanente 看起来也很奇怪。
MOV SI,0 - xor si,si - 是我学到的第一个 "tricks"，让我明白指令有确切的定义，它们对寄存器和内存做了什么，如果那个效果可以用于实现我想要的，我可以自由使用它们中的任何一个，即使它们的名称并不直接暗示该用法。
多尝试一些不同的寻址方式，你不需要总是lea每个变量地址。我永远不确定 16b 模式允许哪些寄存器（32b 保护模式允许更多组合，所以我习惯了 [eax+ecx*8] 之类的东西，这在 16b 中不起作用），但是例如 [permanente+si] 应该可以正常工作，等等
哦，当然还有一些调试器并学习如何使用它。我很确定您的原始代码必须在调试器中的几个步骤中进入意外状态。
同时尝试在源代码周围保留一些 "high level" 评论，例如每组 3-10 条指令。还有一些关于寄存器分配的注意事项，你期望什么值在哪里。
我在 emu8086 中编写 asm x86 代码时遇到了很大的问题，该代码在给定邻接矩阵和节点数的情况下找到图（没有圆环）的拓扑排序。我已经尝试了几个想法，但没有任何效果......所以如果你们中的任何人可以给我任何帮助（以文字或代码的形式）来解决这个问题，或者如何解决这个问题，那就太好了因为我不知道该怎么办... 数据是这样给出的：
JMP main
size db 4
graph db 0 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0
ordering db 0 ,0 ,0 ,0
main :
我认为 DFS 算法可能是解决这个问题的最佳方法。但同样，我真诚地尝试了一切，但到目前为止没有任何效果......所以我会感谢任何帮助。 提前致谢！！！ （抱歉英语不好）
编辑：我写了这个但是根本不起作用：
JMP main
size db 4
graph db 0 ,1 ,1 ,0 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,1 ,0 ,0 ,0 ,0
ordering db 0 ,0 ,0 ,0
permanente db 0, 0, 0, 0
main :
MOV CL,1
PUSH CX
LEA BX,graph
PUSH BX
CALL visitar
RET
visitar:
PUSH BP
MOV BP,SP
MOV BX,[BP+4]
MOV CX,[BP+6]
LEA DI,size
MOV DX,[DI]
MOV SI,0
for:
CMP SI,DX
JE end_for
CMP [BX+SI],1
JE nodo
JMP next
nodo:
MOV CX,SI
ADD CX,1
PUSH CX
MOV AX,SI
MUL size
LEA BX,graph
ADD BX,AX
PUSH BX
CALL visitar
next:
ADD SI,1
JMP for
end_for:
LEA DI,permanente
ADD DI,CX
SUB DI,1
MOV [DI],1
MOV SI,DX
LEA DX,ordering
bajar:
SUB SI,1
CMP [DX+SI],0
JE cambiar
CMP SI,0
JG bajar
cambiar:
MOV [DX+SI],CX
CMP SI,0
JE return
JMP revisar
revisar:
LEA AX,permanente
MOV SI,0
sumar:
CMP [AX+SI],0
JE seguir
ADD SI,1
LEA DI,size
MOV DX,[DI]
CMP SI,DX
JE return
JMP sumar
seguir:
JMP nodo
return:
POP BP
RET 4
我通过阅读源代码发现的一些错误（我不要求列表的完整性，可能还有更多）：
LEA DI,size
MOV DX,[DI]
大小被声明为字节，但你获取的是单词，所以你实际上是从图形中获取大小+第一条边。如果第一个边为 1，则 dx 将为 300 而不是预期的 4。
通过 dw 声明将 size 扩展为单词，或者仅使用字节。
您也可以直接从地址 mov dx,[size] 获取大小，不需要 lea 它的地址。
CMP [BX+SI],1
我不喜欢这种语法，不清楚比较的是什么大小。我不确定 emu8086 语法有什么，尝试在任何一侧添加 byte，如 BYTE 1，或 BYTE PTR [bx+si]，如 TASM/MASM 语法。我希望其中之一能奏效。
虽然这可能看起来像 "style" 偏好，但如果您的边缘定义比 0/1 更复杂并使用单词，那将是错误（因为我怀疑默认结果是字节比较）。
MUL size
详情请查看使用说明。您破坏了另一个寄存器的内容，这将使您的 for 失败。
另外我不喜欢这种语法，你想要内存中的值在 size 地址，而不是地址本身，所以在 size 周围添加 [] 更容易理解，你对内存内容感兴趣。
最后没有指定数据大小，我完全错过了那个。因此，如果汇编程序将其视为字节，那么关于销毁寄存器内容的第一条评论是无效的，但看起来你想要执行 ax*size，这将需要字说明符。顺便说一句，你已经在 dx 中加载了大小，所以 mul dx 或 mul dl 会节省你的内存访问。
CALL visitar
您确实缺少高级文档。
创建汇编函数时，始终在注释中记录什么是参数（如何调用）、结果是什么（如果有）以及修改了哪些寄存器。
您的 visitar 确实修改了许多寄存器，但在 for 循环期间您不知何故期望 si 被保留。不是。然后稍后您使用 cx 作为原始节点号，但同样，在准备调用参数期间已经被销毁。等等...因为它是递归调用，你可以肯定它会破坏所有对你很重要的寄存器。
你将单词存储到ordering，而它被定义为字节数组，偏移量以字节为单位。
MOV CL,1
PUSH CX
ch在这里未初始化（emu8086可能为零，但最好初始化所有内容，因为不同的目标平台可能会在不同的状态下调用您的"start"。
如何改进你所拥有的：
我会做一些设计工作，什么是全局变量，什么是局部变量。然后你可以尝试保持全局变量，比如大小在整个 运行 期间不会改变，或者排序 [next_to_write] 指针是全局的，等等
push/pop 调用 visitar 之前的重要寄存器以保留其值。或者，由于使用堆栈作为函数参数而无论如何都使用堆栈帧，请考虑将局部变量放入堆栈（sub sp,reserved_space 并通过 [bp-x] 访问它）。这样你就不需要担心修改寄存器，虽然它会由于内存访问而工作得更慢。
确保所有值的大小都正确。确定节点数 (size) 是字节还是字，这几乎决定了其余变量。虽然您的 graph 定义是 size*size long，但实际上您不能拥有超过 ~200 个节点，所以只使用 byte 大小是可以的。但这意味着坚持下去，即。 mov [dx+si],cl 将节点号存入ordering。并且在处理图形时，确保 mul 也适用于 16+ 尺寸。
一些样式注释：
add/sub r16,1 -> 还有 inc/dec 说明。
LEA AX,permanente - 原始的 Intel 语法要求表达式类似于访问内存，因此 LEA AX,[permanente] 看起来更像是 Intel 的意图。尽管在 lea 的情况下，它实际上不适用于内存内容，所以我最初并不是英特尔决定的忠实粉丝。然后 lea ax,bx+si*2+permanente 看起来也很奇怪。
MOV SI,0 - xor si,si - 是我学到的第一个 "tricks"，让我明白指令有确切的定义，它们对寄存器和内存做了什么，如果那个效果可以用于实现我想要的，我可以自由使用它们中的任何一个，即使它们的名称并不直接暗示该用法。
多尝试一些不同的寻址方式，你不需要总是lea每个变量地址。我永远不确定 16b 模式允许哪些寄存器（32b 保护模式允许更多组合，所以我习惯了 [eax+ecx*8] 之类的东西，这在 16b 中不起作用），但是例如 [permanente+si] 应该可以正常工作，等等
哦，当然还有一些调试器并学习如何使用它。我很确定您的原始代码必须在调试器中的几个步骤中进入意外状态。
同时尝试在源代码周围保留一些 "high level" 评论，例如每组 3-10 条指令。还有一些关于寄存器分配的注意事项，你期望什么值在哪里。