これは、幅優先のグラフ トラバーサル アルゴリズムになります。「queue」、「dequeue」、「enqueue」、「qempty」関数を作成する方法がわかりません。助けが必要です。
キュー: キューを作成します ($s5)
enqueue: ソースから q に値を取得します
dequeue: 項目を q から v にポップします ($s5 --> $s3)
qempty: q が空かどうかをチェックします
これは私のコードです:
.data
# id, mark, pointers
graph: .word 1 , 0 , 24, 48, 72, -1, # 0
2 , 0 , 00, 96, 120, -1, # 24
3 , 0 , 00, 120, -1, -1, # 48
4 , 0 , 00, -1, -1, -1, # 72
5 , 0 , 24, -1, -1, -1, # 96
6 , 0 , 24, 48, -1, -1 # 120
.text
# graph = $s0, source = $s1, size = $s2, v = $s3, w = $s4, queue = $s5, edge = $s6, i = $s7
# $a0 -> graph, $a1 -> source, $a2 -> size
main:
la $s0, graph
addi $s2, $zero, 6
add $s1, $zero, $zero
move $a0, $s0
move $a1, $s1
move $a2, $s2
jal BFS
j finish
BFS:
addi $sp, $sp, -32
sw $s0, 0($sp)
sw $s1, 4($sp)
sw $s2, 8($sp)
sw $s3, 12($sp)
sw $s4, 16($sp)
sw $s5, 20($sp)
sw $s6, 24($sp)
sw $s7, 28($sp)
jal queue
move $s0, $a0
move $s1, $a1
move $s2, $a2
sll $t0, $s1, 2
add $t0, $t0, $s0
lw $t0, ($t0)
move $a0, $t0
jal enqueue
addi $t1, $s1, 1
sll $t1, $t1, 2
add $t1, $t1, $s0
addi $t2, $zero, 1
sw $t2, ($t1)
while:
jal qempty
beq $v0, $zero, endwhile
jal dequeue
add $s3, $v0, $zero
for:
add $s7, $zero, $zero
slti $t3, $s7, 4
beq $t3, $zero, endfor
addi $t4, $s3, -1
mul $t4, $t4, 6
add $t4, $t4, $s7
sll $s6, $t4, 2
add $s6, $s6, $s0
lw $s6, 0($s6)
if1:
beq $s6, -1, endif1
move $s4, $s6
if2:
addi $t5, $s4, 1
sll $t5, $t5, 2
add $t5, $t5, $s0
lw $t5, 0($t5)
bne $t5, 0, endif2
addi $t6, $s4, 1
sll $t6, $t6, 2
add $t6, $t6, $s0
sw $t6, 1
add $t7, $s4, $zero
sll $t7, $t7, 2
lw $t7, 0($t7)
move $a0, $t7
jal enqueue
endif2:
endif1:
j for
endfor:
j while
endwhile:
finish:
lw $s0, 0($sp)
lw $s1, 4($sp)
lw $s2, 8($sp)
lw $s3, 12($sp)
lw $s4, 16($sp)
lw $s5, 20($sp)
lw $s6, 24($sp)
lw $s7, 28($sp)
addi $sp, $sp, 32