将带链表的归并排序从 C 翻译成 MIPS
Translate merge sort with linked lists from C to MIPS
我正在尝试使用链表在 MIPS 中实现合并排序算法。我基本上是在尝试翻译这段代码：http://www.geeksforgeeks.org/merge-sort-for-linked-list/
但是，我遇到了一些问题。排序的列表是不完整的，好像它丢失了整个递归分支，例如，这是要排序的链表：
4 -> 3 -> 1 -> 2
输出为：1 -> 2 -> 4。然后当我尝试将列表写入文件时出现错误（0x004003fc 处的运行时异常：地址超出范围 0x00000000）。我猜那是因为我希望打印 4 个数字，但列表中只有 3 个数字。
我认为我需要帮助的地方是 MergeSort 函数，因为我不完全理解它实际上在指针方面做了什么。这就是我认为的作用：
它接收一个指向列表头部的指针作为参数。在函数内部，它创建了 "head" 指针，它指向 headRef 的 VALUE（在这种情况下，&head 是在 main 上传递的，所以现在函数内部的 "head" 具有 head 在主要的）。然后它声明两个指针，a 和 b（在 MIPS 中这就像做 a = 0 和 b = 0？我不能 "declare" 寄存器）。然后它检查列表是否有 1 个或 0 个元素，如果有，则检查 returns。否则，它会使用 FrontBackSplit(head, &a, &b) 将列表分成两半，但这是棘手的部分……这个函数没有 return 任何东西。相反，它修改指针 "a" 和 "b"，使它们分别指向列表的前半部分和后半部分。在 MIPS 中，我认为这是两个 return 值 $v0 和 $v1。然后它递归地对列表进行排序，从左边开始，但是再一次，它没有 return 任何东西……它修改了指针 "a" 和 "b"。最后，它改变指向列表头部的指针的值，使其指向新的排序列表。
因为太多的 **ptr 和 &ptr 值，我对要在堆栈上保存什么感到困惑。这是我到目前为止关于该功能的内容：
# void mergesort(node** headRef)
# input $a0: head of the list
mergesort:
move $t0, $s3 # node* head = headRef
li $t1, 0 # node* a
li $t2, 0 # node* b
# if(head == NULL || head->next == NULL)
beqz $t0, mergesort_return
lw $t3, node_next($t0) # $t3 = head->next
beqz $t3, mergesort_return
move $a0, $t0
move $a1, $t1
move $a2, $t2
# save head and $ra
addi $sp, $sp, -8
sw $t0, 0($sp)
sw $ra, 4($sp)
jal frontbacksplit
# restore head and $ra
lw $t0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
# save output results
move $t1, $v0 # a now points to the first half + 1 (if odd) of the list (frontRef)
move $t2, $v1 # b now points to the second half of the list (backRef)
# save head, a, b and $ra
addi $sp, $sp, -16
sw $t0, 0($sp)
sw $t1, 4($sp)
sw $t2, 8($sp)
sw $ra, 12($sp)
# mergesort(a)
move $a0, $t1
jal mergesort
# restore registers and $ra
lw $t0, 0($sp)
lw $t1, 4($sp)
lw $t2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
# save head, a, b and $ra
addi $sp, $sp, -16
sw $t0, 0($sp)
sw $t1, 4($sp)
sw $t2, 8($sp)
sw $ra, 12($sp)
# mergesort(b)
move $a0, $t2
jal mergesort
# restore registers and $ra
lw $t0, 0($sp)
lw $t1, 4($sp)
lw $t2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
move $a0, $t1
move $a1, $t2
# save head, a, b and $ra
addi $sp, $sp, -16
sw $t0, 0($sp)
sw $t1, 4($sp)
sw $t2, 8($sp)
sw $ra, 12($sp)
jal sortedmerge
# restore registers and $ra
lw $t0, 0($sp)
lw $t1, 4($sp)
lw $t2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
move $s3, $v0 # s3 is the saved head of the original list declared in main
mergesort_return:
jr $ra
嗯...我做到了。这是作业，还没有评分。我希望他们不会认为我抄袭了哈哈。
######### uses function frontbacksplit
######### WORKING
# mergesort
# input $a0: head of the list to merge
mergesort:
li $t0, 0 # head_one = NULL
li $t1, 0 # head_two = NULL
# base case
beqz $a0, mergesort_return
lw $t2, node_next($a0)
beqz $t2, mergesort_return
addi $sp, $sp, -8
sw $ra, 0($sp)
sw $a0, 4($sp)
# move $a0, $a0
move $a1, $t0
move $a2, $t1
jal frontbacksplit
move $t0, $v0
move $t1, $v1
lw $ra, 0($sp)
lw $a0, 4($sp)
addi $sp, $sp, 8
# mergesort(a)
addi $sp, $sp, -16
sw $ra, 0($sp)
sw $t0, 4($sp)
sw $t1, 8($sp)
sw $a0, 12($sp)
move $a0, $t0
jal mergesort # mergesort(a)
move $t9, $v0
lw $ra, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
lw $a0, 12($sp)
addi $sp, $sp, 16
# mergesort(b)
addi $sp, $sp, -20
sw $ra, 0($sp)
sw $t0, 4($sp)
sw $t1, 8($sp)
sw $a0, 12($sp)
sw $t9, 16($sp)
move $a0, $t1
jal mergesort # mergesort(b)
move $t8, $v0
lw $ra, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
lw $a0, 12($sp)
lw $t9, 16($sp)
addi $sp, $sp, 20
# t8 = a, t9 = b
addi $sp, $sp, -24
sw $ra, 0($sp)
sw $t0, 4($sp)
sw $t1, 8($sp)
sw $a0, 12($sp)
sw $t9, 16($sp)
sw $t8, 20($sp)
move $a0, $t8
move $a1, $t9
jal merge
lw $ra, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
lw $a0, 12($sp)
lw $t9, 16($sp)
lw $t8, 20($sp)
addi $sp, $sp, 24
#move $v0, $v0
jr $ra
mergesort_return:
move $v0, $a0
jr $ra
######### WORKING
# input $a0: source node (list to split)
# input $a1: front ref (a) $s4
# input $a2: back ref (b) $s5
# output $v0: frontRef
# output $v1: backRef
frontbacksplit:
# $a0 = node* source, $a1 = node* frontRef, $a2 = node* backRef
move $t0, $a0 # $t0 = source
move $t1, $a1 # $t1 = frontRef
move $t2, $a2 # $t2 = backRef
li $t3, 0 # node* fast;
li $t4, 0 # node* slow;
# if(source == NULL)
beqz $t0, frontbacksplit_sorted
lw $t5, node_next($t0) # $t5 = source->next
# if(source->next == NULL)
beqz $t5, frontbacksplit_sorted
# else
move $t4, $t0 # slow = source
lw $t3, node_next($t0) # fast = source->next
frontbacksplit_while:
# while(fast != NULL)
beqz $t3, frontbacksplit_endwhile
lw $t3, node_next($t3) # fast = fast->next
# if(fast != NULL)
beqz $t3, frontbacksplit_while
lw $t4, node_next($t4) # slow = slow->next
lw $t3, node_next($t3) # fast = fast->next
j frontbacksplit_while
frontbacksplit_endwhile:
move $t1, $t0 # frontRef = source
lw $t2, node_next($t4) # backRef = slow->next
sw $zero, node_next($t4) # slow->next = NULL
move $v0, $t1
move $v1, $t2
j frontbacksplit_end
frontbacksplit_sorted:
move $v0, $t0 # frontRef = source
li $v1, 0 # backRef = NULL
frontbacksplit_end:
jr $ra
############ WORKING
# input $a0: head of the first list
# input $a1: head of the second list
# output $v0: pointer to the head of the merged-sorted list
merge:
beqz $a0, merge_return2
beqz $a1, merge_return1
li $t3, 0 # head_three = NULL
lw $t0, node_int($a0)
lw $t1, node_int($a1)
addi $sp, $sp, -16
sw $ra, 0($sp)
sw $a0, 4($sp)
sw $a1, 8($sp)
sw $t3, 12($sp)
bge $t0, $t1, merge_else
# if head_one->num < head_two->num
lw $a0, node_next($a0)
# $a1 already has head_two
jal merge
move $t0, $v0 # ptr = merge(head_one->next, head_two)
# restore values
lw $ra, 0($sp)
lw $a0, 4($sp)
lw $a1, 8($sp)
lw $t3, 12($sp)
move $t3, $a0
sw $t0, node_next($t3)
move $v0, $t3
addi $sp, $sp, 16
jr $ra
merge_else:
# $a0 already has head_one
lw $a1, node_next($a1)
jal merge
move $t0, $v0 # ptr = merge(head_one->next, head_two)
# restore values
lw $ra, 0($sp)
lw $a0, 4($sp)
lw $a1, 8($sp)
lw $t3, 12($sp)
move $t3, $a1
sw $t0, node_next($t3)
move $v0, $t3
addi $sp, $sp, 16
jr $ra
merge_return1:
move $v0, $a0
jr $ra
merge_return2:
move $v0, $a1
jr $ra
我知道这很乱，但它确实有效:P.
我正在尝试使用链表在 MIPS 中实现合并排序算法。我基本上是在尝试翻译这段代码：http://www.geeksforgeeks.org/merge-sort-for-linked-list/ 但是，我遇到了一些问题。排序的列表是不完整的，好像它丢失了整个递归分支，例如，这是要排序的链表： 4 -> 3 -> 1 -> 2 输出为：1 -> 2 -> 4。然后当我尝试将列表写入文件时出现错误（0x004003fc 处的运行时异常：地址超出范围 0x00000000）。我猜那是因为我希望打印 4 个数字，但列表中只有 3 个数字。
我认为我需要帮助的地方是 MergeSort 函数，因为我不完全理解它实际上在指针方面做了什么。这就是我认为的作用：
它接收一个指向列表头部的指针作为参数。在函数内部，它创建了 "head" 指针，它指向 headRef 的 VALUE（在这种情况下，&head 是在 main 上传递的，所以现在函数内部的 "head" 具有 head 在主要的）。然后它声明两个指针，a 和 b（在 MIPS 中这就像做 a = 0 和 b = 0？我不能 "declare" 寄存器）。然后它检查列表是否有 1 个或 0 个元素，如果有，则检查 returns。否则，它会使用 FrontBackSplit(head, &a, &b) 将列表分成两半，但这是棘手的部分……这个函数没有 return 任何东西。相反，它修改指针 "a" 和 "b"，使它们分别指向列表的前半部分和后半部分。在 MIPS 中，我认为这是两个 return 值 $v0 和 $v1。然后它递归地对列表进行排序，从左边开始，但是再一次，它没有 return 任何东西……它修改了指针 "a" 和 "b"。最后，它改变指向列表头部的指针的值，使其指向新的排序列表。
因为太多的 **ptr 和 &ptr 值，我对要在堆栈上保存什么感到困惑。这是我到目前为止关于该功能的内容：
# void mergesort(node** headRef)
# input $a0: head of the list
mergesort:
move $t0, $s3 # node* head = headRef
li $t1, 0 # node* a
li $t2, 0 # node* b
# if(head == NULL || head->next == NULL)
beqz $t0, mergesort_return
lw $t3, node_next($t0) # $t3 = head->next
beqz $t3, mergesort_return
move $a0, $t0
move $a1, $t1
move $a2, $t2
# save head and $ra
addi $sp, $sp, -8
sw $t0, 0($sp)
sw $ra, 4($sp)
jal frontbacksplit
# restore head and $ra
lw $t0, 0($sp)
lw $ra, 4($sp)
addi $sp, $sp, 8
# save output results
move $t1, $v0 # a now points to the first half + 1 (if odd) of the list (frontRef)
move $t2, $v1 # b now points to the second half of the list (backRef)
# save head, a, b and $ra
addi $sp, $sp, -16
sw $t0, 0($sp)
sw $t1, 4($sp)
sw $t2, 8($sp)
sw $ra, 12($sp)
# mergesort(a)
move $a0, $t1
jal mergesort
# restore registers and $ra
lw $t0, 0($sp)
lw $t1, 4($sp)
lw $t2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
# save head, a, b and $ra
addi $sp, $sp, -16
sw $t0, 0($sp)
sw $t1, 4($sp)
sw $t2, 8($sp)
sw $ra, 12($sp)
# mergesort(b)
move $a0, $t2
jal mergesort
# restore registers and $ra
lw $t0, 0($sp)
lw $t1, 4($sp)
lw $t2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
move $a0, $t1
move $a1, $t2
# save head, a, b and $ra
addi $sp, $sp, -16
sw $t0, 0($sp)
sw $t1, 4($sp)
sw $t2, 8($sp)
sw $ra, 12($sp)
jal sortedmerge
# restore registers and $ra
lw $t0, 0($sp)
lw $t1, 4($sp)
lw $t2, 8($sp)
lw $ra, 12($sp)
addi $sp, $sp, 16
move $s3, $v0 # s3 is the saved head of the original list declared in main
mergesort_return:
jr $ra
嗯...我做到了。这是作业，还没有评分。我希望他们不会认为我抄袭了哈哈。
######### uses function frontbacksplit
######### WORKING
# mergesort
# input $a0: head of the list to merge
mergesort:
li $t0, 0 # head_one = NULL
li $t1, 0 # head_two = NULL
# base case
beqz $a0, mergesort_return
lw $t2, node_next($a0)
beqz $t2, mergesort_return
addi $sp, $sp, -8
sw $ra, 0($sp)
sw $a0, 4($sp)
# move $a0, $a0
move $a1, $t0
move $a2, $t1
jal frontbacksplit
move $t0, $v0
move $t1, $v1
lw $ra, 0($sp)
lw $a0, 4($sp)
addi $sp, $sp, 8
# mergesort(a)
addi $sp, $sp, -16
sw $ra, 0($sp)
sw $t0, 4($sp)
sw $t1, 8($sp)
sw $a0, 12($sp)
move $a0, $t0
jal mergesort # mergesort(a)
move $t9, $v0
lw $ra, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
lw $a0, 12($sp)
addi $sp, $sp, 16
# mergesort(b)
addi $sp, $sp, -20
sw $ra, 0($sp)
sw $t0, 4($sp)
sw $t1, 8($sp)
sw $a0, 12($sp)
sw $t9, 16($sp)
move $a0, $t1
jal mergesort # mergesort(b)
move $t8, $v0
lw $ra, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
lw $a0, 12($sp)
lw $t9, 16($sp)
addi $sp, $sp, 20
# t8 = a, t9 = b
addi $sp, $sp, -24
sw $ra, 0($sp)
sw $t0, 4($sp)
sw $t1, 8($sp)
sw $a0, 12($sp)
sw $t9, 16($sp)
sw $t8, 20($sp)
move $a0, $t8
move $a1, $t9
jal merge
lw $ra, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
lw $a0, 12($sp)
lw $t9, 16($sp)
lw $t8, 20($sp)
addi $sp, $sp, 24
#move $v0, $v0
jr $ra
mergesort_return:
move $v0, $a0
jr $ra
######### WORKING
# input $a0: source node (list to split)
# input $a1: front ref (a) $s4
# input $a2: back ref (b) $s5
# output $v0: frontRef
# output $v1: backRef
frontbacksplit:
# $a0 = node* source, $a1 = node* frontRef, $a2 = node* backRef
move $t0, $a0 # $t0 = source
move $t1, $a1 # $t1 = frontRef
move $t2, $a2 # $t2 = backRef
li $t3, 0 # node* fast;
li $t4, 0 # node* slow;
# if(source == NULL)
beqz $t0, frontbacksplit_sorted
lw $t5, node_next($t0) # $t5 = source->next
# if(source->next == NULL)
beqz $t5, frontbacksplit_sorted
# else
move $t4, $t0 # slow = source
lw $t3, node_next($t0) # fast = source->next
frontbacksplit_while:
# while(fast != NULL)
beqz $t3, frontbacksplit_endwhile
lw $t3, node_next($t3) # fast = fast->next
# if(fast != NULL)
beqz $t3, frontbacksplit_while
lw $t4, node_next($t4) # slow = slow->next
lw $t3, node_next($t3) # fast = fast->next
j frontbacksplit_while
frontbacksplit_endwhile:
move $t1, $t0 # frontRef = source
lw $t2, node_next($t4) # backRef = slow->next
sw $zero, node_next($t4) # slow->next = NULL
move $v0, $t1
move $v1, $t2
j frontbacksplit_end
frontbacksplit_sorted:
move $v0, $t0 # frontRef = source
li $v1, 0 # backRef = NULL
frontbacksplit_end:
jr $ra
############ WORKING
# input $a0: head of the first list
# input $a1: head of the second list
# output $v0: pointer to the head of the merged-sorted list
merge:
beqz $a0, merge_return2
beqz $a1, merge_return1
li $t3, 0 # head_three = NULL
lw $t0, node_int($a0)
lw $t1, node_int($a1)
addi $sp, $sp, -16
sw $ra, 0($sp)
sw $a0, 4($sp)
sw $a1, 8($sp)
sw $t3, 12($sp)
bge $t0, $t1, merge_else
# if head_one->num < head_two->num
lw $a0, node_next($a0)
# $a1 already has head_two
jal merge
move $t0, $v0 # ptr = merge(head_one->next, head_two)
# restore values
lw $ra, 0($sp)
lw $a0, 4($sp)
lw $a1, 8($sp)
lw $t3, 12($sp)
move $t3, $a0
sw $t0, node_next($t3)
move $v0, $t3
addi $sp, $sp, 16
jr $ra
merge_else:
# $a0 already has head_one
lw $a1, node_next($a1)
jal merge
move $t0, $v0 # ptr = merge(head_one->next, head_two)
# restore values
lw $ra, 0($sp)
lw $a0, 4($sp)
lw $a1, 8($sp)
lw $t3, 12($sp)
move $t3, $a1
sw $t0, node_next($t3)
move $v0, $t3
addi $sp, $sp, 16
jr $ra
merge_return1:
move $v0, $a0
jr $ra
merge_return2:
move $v0, $a1
jr $ra
我知道这很乱，但它确实有效:P.