Сортировка и массив MIPS

У меня проблема с домашним заданием. Я предполагаю написать программу, которая сделает следующее:

  1. Отсортируйте буквы в предложении в порядке сортировки ASCII (т. Е. По алфавиту). Выведите результаты и общее количество символов в предложении.
  2. Затем распечатайте список, сколько раз каждая буква встречается в предложении.
  3. Наконец, распечатайте общее количество различных символов в предложении.

Когда я пытаюсь проверить первое требование, я не получаю выходную строку. Мне также нужна помощь в выполнении двух вторых. Я новичок в MIPS, и я кое-что понимаю, но испытываю некоторые трудности. Я изменил некоторый код для сортировки из примера кода, который я нашел.

        .data
length: .word   0
buffer: .space 255
prompt1:.asciiz  "Type in a sentence: "

after:  .asciiz  "\nString  after: "


    .text


# Start of code section

main:
      li       $v0, 4         # Prompt user for a text string
      la       $a0, prompt1      # address of string to print
      syscall
      li       $v0, 8         # Read in text string
      la       $a0, buffer
      li       $a1, 255
      syscall

      la       $t0, buffer    #  Read character from text string
      lw       $t1, length
      addu     $t0, $t0, $t1

# Call on QuickSort

        la      $a0, buffer       # Constant pointer to string

        add     $a1, $a0, 0      # Pointer to left end

        add     $a2, $a0, 25     # Pointer to right end

        jal     QS               # The one call from main

# Print out results

        la      $a0, after

        li      $v0, 4

        syscall

        la      $a0, buffer

        syscall

# End main

        li      $v0, 10

        syscall


QS:     sub     $sp, $sp, 16     # \
        sw      $a1, 0($sp)      #  \

        sw      $a2, 4($sp)      #   > Save registers

        sw      $t2, 8($sp)      #  /  

        sw      $ra, 12($sp)     # / and return address

        bge     $a1, $a2, QSret  # Nothing to sort   

        sub     $t3, $a1, $a0     # index i

        sub     $t4, $a2, $a0     # index j

        add     $t0, $t3, $t4     # t0 = i+j choose middle

        sra     $t0, $t0, 1       # t0 = (i+j) div 2

        add     $t0, $t0, $a0     # t0 -> A[(i+j) div 2]

        lb      $t5, 0($t0)       # t5 = pivot value 

        lb      $t6, 0($a1)       # t6 = A[i] = left element

        sb      $t5, 0($a1)       # Swap them so pivot

        sb      $t6, 0($t0)       # is first element
# 

        move    $t1, $a1         # Initdially i -> first (pivot) item a1

        add     $t2, $a2, 1      # Initially j -> just past last item a2

        lb      $t0, 0($a1)      # Pivot value in t0 (in $t5)

# 
loop:
# 

i_loop: add     $t1, $t1, 1      # i=i+1;

        lb      $t5, 0($t1)      # t5 = A[i]

        bgt     $t0, $t5, i_loop # until pivot <= A[i]

j_loop: sub     $t2, $t2, 1      # j=j-1;

        lb      $t6, 0($t2)      # t6 = A[j]

        blt     $t0, $t6, j_loop # until pivot >= A[j]
#

        bge     $t1, $t2, test   # if i<j swap
#

        sb      $t6, 0($t1)      # A[i] and

        sb      $t5, 0($t2)      # A[j]
#

test:   blt     $t1, $t2, loop   # until i >= j
#

        lb      $t5, 0($a1)      # swap a[a1] = pivot

        lb      $t6, 0($t2)      # and a[j]

        sb      $t5, 0($t2)      # now a[j] is

        sb      $t6, 0($a1)      # in its final position

# Done with partition

        lw      $a1, 0($sp)

        sub     $a2, $t2, 1

        jal     QS               # Recursive call on left

        add     $a1, $t2, 1

        lw      $a2, 4($sp)

        jal     QS               # Recursive call on right
#

QSret:  lw      $ra, 12($sp)     # \Replace return address

        lw      $t2, 8($sp)      #  \

        lw      $a2, 4($sp)      #   > and registers

        lw      $a1, 0($sp)      #  /
        add     $sp, $sp, 16     # /

        jr      $ra

person 6502forlife    schedule 11.11.2010    source источник
comment
Не могли бы вы предоставить c-код, который вы использовали?   -  person João Víctor Melo    schedule 05.07.2021


Ответы (1)


buffer: .space 255

Это заполняет buffer нулями.

li       $v0, 8         # Read in text string
la       $a0, buffer
li       $a1, 255
syscall

Я не знаю, какую среду вы используете, но обычно это работает так же, как fgets() в C, поэтому, если вы введете hello, ваш буфер будет иметь следующий вид:

+-----+-----+-----+-----+-----+-----+-----+-----+   more    +-----+
| 'h' | 'e' | 'l' | 'l' | 'o' |'\n' |  0  |  0  |..zeroes...|  0  |
+-----+-----+-----+-----+-----+-----+-----+-----+           +-----+

Код сразу после этого не делает ничего полезного:

la       $t0, buffer    #  Read character from text string
lw       $t1, length
addu     $t0, $t0, $t1

но length никогда не записывался, и $t0 больше не используется (до тех пор, пока он не будет перезаписан внутри QS).

Вызов QS передает фиксированное значение в $a2 (25 - почему?). Предполагая, что процедура QS действительно работает так, как было заявлено: если ваша исходная строка короткая, некоторые из нулевых байтов в буфере будут включены в диапазон, который будет отсортирован, и, таким образом, окажутся в начале буфера - диапазоне, который будет выглядеть примерно так:

+-----+   more    +-----+-----+-----+-----+-----+-----+-----+-----+
|  0  |..zeroes...|  0  |  0  |'\n' | 'e' | 'h' | 'l' | 'l' | 'o' |
+-----+           +-----+-----+-----+-----+-----+-----+-----+-----+

т.е. если сортируемый диапазон включает любые нулевые байты, первый байт результата будет равен нулю, и вы напечатаете пустую строку.

Часть 2: если у вас есть правильно отсортированная строка, это должно быть просто, поскольку все вхождения каждого символа являются смежными. Просто пройдите по строке и подумайте, является ли каждый символ таким же, как предыдущий, или другим.

Часть 3: просто нужен дополнительный счетчик при выполнении работы по части 2.

person Matthew Slattery    schedule 13.11.2010
comment
Мэтью, зачем нам дополнительный счетчик для части 2? - person João Víctor Melo; 09.07.2021