Assembly - MIPS - 鄰接表的未知大小，如何遍歷

因此，我正在對未知長度的圖進行深度優先搜索。圖本身將被編碼爲「2D」陣列鄰接表。Assembly - MIPS - 鄰接表的未知大小，如何遍歷

例：

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

但是，該圖可以是任意大小，當它被分級助教可以把任何大小的圖形在我的代碼進行測試。所以我不知道圖的大小。

當我想檢查鄰接表時，這成爲一個問題。我如何知道什麼時候我已經排到最後？我如何前進到特定的行？我知道如何通過單詞前進，但我不知道如何在不知道需要前進多少個單元（因此字節）的情況下前進到下一行。

來源

2013-03-15 Doronz

提示：鄰接矩陣必須是一個正方形。 – 2013-03-15 02:49:34

是的，我意識到這一點。但問題是，我無法知道數組的結尾。所以即使知道它必須是一個正方形，我也無法知道它有多少個元素，因爲沒有數組或末尾的指示符。我很感興趣，如果這可以找出，但我最終只是要求用戶輸入圖形大小。這仍然允許我遵循規範，並且不要求我開發算法來計算長度。 – Doronz 2013-03-15 03:20:29

鄰接矩陣後面必須有一些符號，對吧？ – 2013-03-15 03:21:32

如果您想在沒有用戶干預的情況下計算行大小，您需要在圖形定義之後使用標記（在我的示例中，我使用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-15 13:28:10 gusbro

Assembly - MIPS - 鄰接表的未知大小，如何遍歷

回答

相關問題