병합 정렬을 C에서 MIPS까지 연결된 목록으로 변환

Question

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를 가리 킵니다 (이 경우 & 머리가 main에 전달되었으므로 이제 함수의 "head"는 머리에 머리의 주소를가집니다). 그런 다음 두 포인터를 선언합니다. a와 b (MIPS에서 이것은 = 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 

Answer 1

음 ... 나는 그것을했다. 이것은 숙제 였고 채점되지 않았습니다. 나는 그들이 그것을 웃어 넘겼다 고 생각하지 않기를 바랍니다.

######### 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 

매우 지저분하지만 작동합니다.