Я пытаюсь реализовать алгоритм сортировки слиянием в MIPS, используя связанные списки. Я в основном пытаюсь перевести этот код: http://www.geeksforgeeks.org/merge-sort-for-linked-list/ Однако у меня возникают некоторые проблемы. Сортированный список неполный, как если бы он потерял всю рекурсивную ветвь, например, это связанный список для сортировки: 4 -> 3 -> 1 -> 2 И результат: 1 -> 2 -> 4 . И затем появляется ошибка, когда я пытаюсь записать список в файл (исключение времени выполнения в 0x004003fc: адрес вне диапазона 0x00000000). Я предполагаю, что это потому, что я ожидаю напечатать 4 числа, но у меня только 3 числа в списке.Перевести сортировку слияния со связанными списками с C на MIPS
Я думаю, где мне нужна помощь в функции MergeSort, так как я НЕ ПОЛНОСТЬЮ понимаю, что на самом деле делает указатель. Это то, что я думаю:
Он получает в качестве параметра указатель на указатель на голову списка. Внутри функции он создает указатель «head», и он указывает на значение VALUE в headRef (в этом случае головка была передана по основному, так что теперь «голова» внутри функции имеет адрес головы в главном). Затем он объявляет два указателя: a и b (в MIPS это будет похоже на a = 0, а b = 0? Я не могу «объявить» регистры). Затем он проверяет, имеет ли список 1 или 0 элементов и возвращается, если это произойдет. В противном случае он разбивает список на две половины с FrontBackSplit (head, & a, & b), но это сложный элемент ... эта функция ничего не возвращает. Вместо этого он изменяет указатели «a» и «b», чтобы они указывали на первую половину списка и вторую половину соответственно. В MIPS я бы подумал, что это два возвращаемых значения $ v0 и $ v1. Затем он сортирует список рекурсивно, начиная слева, но еще раз, он ничего не возвращает ... он изменяет указатель «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
Поздравляем вас с поиском решения самостоятельно. Для учебных целей для других пользователей, у которых может быть аналогичная проблема, вам может быть приятно отредактировать ваш ответ здесь, чтобы подробно рассказать о том, что вы исправили из вашего первоначального вопроса. Кроме того, другие проблемы, с которыми вы столкнулись [и исправлены] и т. Д. Кроме того, что вы узнали и/или улучшили. –
Я сделаю это, как только у меня будет больше времени: D. Может быть, на следующей неделе. – Sebasuraa