1

そのため、長さが不明なグラフで深さ優先検索を行うことに取り組んでいます。グラフ自体は、「2D」配列の隣接テーブルとしてコーディングされます。

元：

 Graph: .word 0, 1, 1, 1, 0
        .word 1, 0, 1, 1, 1
        .word 1, 1, 0, 1, 1
        .word 1, 1, 1, 0, 1
        .word 1, 1, 0, 0, 0

ただし、このグラフは任意のサイズにすることができます。グレーディングされると、TA は任意のサイズのグラフをコードに挿入してテストすることができます。そのため、グラフのサイズがわかりません。

これは、隣接テーブルを確認したい場合に問題になります。行の終わりに達したことをどのように知ることができますか? 特定の行に進むにはどうすればよいですか? 単語単位で進める方法は知っていますが、進む必要がある要素 (つまりバイト) の数を知らずに次の行に進む方法がわかりません。

4

1 に答える 1

1

ユーザーの介入なしに行サイズを計算したい場合は、グラフ定義の後にマーカーが必要です (私の例では、マーカーとして EndGraph ラベルを使用しました)。行列の最初の要素のアドレスと行列の終了位置がわかれば、行サイズを計算できます。行列の要素の総数の平方根を計算するだけです。

.data
 Graph: .word 0, 1, 1, 1, 0
        .word 1, 0, 1, 1, 1
        .word 1, 1, 0, 1, 1
        .word 1, 1, 1, 0, 1
        .word 1, 1, 0, 0, 0
EndGraph:
.text        
  la $t1, Graph
  la $t2, EndGraph
  sub $t2, $t2, $t1  # Get size of matrix
  srl $t2, $t2, 2    # Get the total number of items of the matrix
  move $t3, $zero
computeRowSize:
  mult $t3, $t3
  mflo $t4
  beq $t2, $t4, done
  addiu $t3, $t3, 1
  j computeRowSize
done:  
  sll $t3, $t3, 2    # compute the size of each row (number of row elements * size(element)
  # Here you have the RowSize in $t3
于 2013-03-15T13:28:10.480 に答える