Practica 5: Soluciones a los ejercicios - myTeachingURJC/2019-20-LAB-AO GitHub Wiki
Práctica 5
Sesión 10
Solución a los ejercicios de la Sesión de laboratorio L12:5-1
Ejercicio 1
#-- Solución al ejericico 1
#-- Programa principal
.include "servicios.asm"
.data
msg: .string "Introduce numeros enteros positivos:\n"
msg2: .string "\nLISTA:\n"
.text
#-- Usamos s0 como puntero de acceso a la lista
#-- Inicialmente es NULL
li s0, 0
#-- Imprimir mensaje
la a0, msg
li a7, PRINT_STRING
ecall
#-- Pedir números hasta que se introduzca uno negativo
next:
#-- Pedir Numero entero
li a7, READ_INT
ecall
#-- Si el a0 < 0, finalizar la introduccion de numeros
blt a0, zero, fin
#-- Guardar el numero en la lista
mv a1, a0
mv a0, s0
jal create
#-- Guardamos en s0 la cabeza de la lista
mv s0, a0
#-- repetir
b next
fin:
#----- Mensaje 2
la a0, msg2
li a7, PRINT_STRING
ecall
#-- Imprimir la lista
mv a0, s0
jal print
#-- Terminar
li a7, EXIT
ecall
Ejercicio 2
El programa principal es el mismo que el del ejercicio 1. La nueva subrutina de print es esta:
#--------------------------------------
#-- Subrutina: Imprimir el contenido de una lista enlazada en sentido inverso
#-- Se imprime usando un algoritmo recursivo
#--
#-- ENTRADA:
#-- a0: Puntero a la lista a imprimir
#--
#-- SALIDA: Ninguna
#------------------------------------------------------------
.include "servicios.asm"
.globl print
#---- Informacion sobre el nodo
.eqv NEXT 0 #-- Offset del campo NEXT
.eqv NUM 4 #-- Offset del campo NUM
.text
print:
#-- Si es una lista vacia, terminar
beq a0, zero, fin
#-- No es una lista vacia
#-- Crear la pila para guardar la direccion de retorno
addi sp,sp,-16
sw ra, 12(sp)
#-- Guardar a0 en la pila, para preservarlo
sw a0, 8(sp)
#-- Obtener el puntero al siguiente nodo
lw a0, NEXT(a0)
#-- Imprimir la sublista en orden inverso
jal print
#-- Recuperar el puntero a la lista original
lw a0, 8(sp)
#-- Imprimir el valor del nodo
lw a0, NUM(a0)
li a7, PRINT_INT
ecall
#-- Imprimir '\n'
li a0, '\n'
li a7, PRINT_CHAR
ecall
#-- Recuperar direccion de retorno
lw ra, 12(sp)
addi sp,sp,16
fin:
#-- Terminar
ret
Ejercicio 3
Esta es la implementación de la función len(), usando un algoritmo iterativo:
#------- Calcular la longitud de una lista
#---- Algoritmo iterativo
#--- SUBRUTINA len
#-- ENTRADAS:
#-- a0: Puntero de acceso a la lista
#--
#-- DEVUELVE:
#-- a0: Número de nodos en la lista
#----------------------------------------------
.globl len
#-- Informacion sobre la lista
.eqv NUM 4
.eqv NEXT 0
len:
#-- Usamos t0 como contador
li t0, 0
next:
#-- Si a0 es NULL, terminar
beq a0, zero, fin
#-- Es un nodo. INcrementar el contador
addi t0, t0, 1
#-- Apuntar al siguiente nodo
lw a0, NEXT(a0)
#-- Repetir
b next
fin:
#-- Devolver en a0 la longitud
mv a0, t0
ret
y este es el programa principal modificado:
#-- Solución al ejericico 3
#-- Programa principal
.include "servicios.asm"
.data
msg: .string "Introduce numeros enteros positivos:\n"
msg2: .string "\nNumero de elementos de la LISTA: "
.text
#-- Usamos s0 como puntero de acceso a la lista
#-- Inicialmente es NULL
li s0, 0
#-- Imprimir mensaje
la a0, msg
li a7, PRINT_STRING
ecall
#-- Pedir números hasta que se introduzca uno negativo
next:
#-- Pedir Numero entero
li a7, READ_INT
ecall
#-- Si el a0 < 0, finalizar la introduccion de numeros
blt a0, zero, fin
#-- Guardar el numero en la lista
mv a1, a0
mv a0, s0
jal create
#-- Guardamos en s0 la cabeza de la lista
mv s0, a0
#-- repetir
b next
fin:
#-- Calcular el numero de elementos de la lista
mv a0, s0
jal len
#-- Guardar la longitud en t0
mv t0, a0
#----- Mensaje 2
la a0, msg2
li a7, PRINT_STRING
ecall
#-- Imprimir su longitud
mv a0, t0
li a7, PRINT_INT
ecall
#-- Terminar
li a7, EXIT
ecall
Ejercicio 4
Implementación de la función len() usando un algoritmo recursivo:
#------- Calcular la longitud de una lista
#---- Algoritmo recursivo
#--- SUBRUTINA len
#-- ENTRADAS:
#-- a0: Puntero de acceso a la lista
#--
#-- DEVUELVE:
#-- a0: Número de nodos en la lista
#----------------------------------------------
.globl len
#-- Informacion sobre la lista
.eqv NUM 4
.eqv NEXT 0
len:
#-- Usamos t0 como acumulador
li t0, 0
#-- Si a0 es NULL, terminar
beq a0, zero, fin
#-- Crear la pila
addi sp, sp, -16
sw ra, 12(sp)
#-- Apuntar al siguiente nodo
lw a0, NEXT(a0)
#-- Calcula la longitud de la sublista
jal len
#-- Sumar un elemento mas
addi t0, a0, 1
#-- Recuperar direccion de retorno
lw ra, 12(sp)
addi sp, sp, 16
fin:
#-- Devolver en a0 la longitud
mv a0, t0
ret
Ejercicio 5
Implementación de la función sum() con algoritmo iterativo
#------- Calcular la suma de todos los elementos de la lista
#---- Algoritmo iterativo
#--- SUBRUTINA sum
#-- ENTRADAS:
#-- a0: Puntero de acceso a la lista
#--
#-- DEVUELVE:
#-- a0: Suma de sus elementos
#----------------------------------------------
.globl sum
#-- Informacion sobre la lista
.eqv NUM 4
.eqv NEXT 0
sum:
#-- Usamos t0 como acumulador de la suma
li t0, 0
next:
#-- Si a0 es NULL, terminar
beq a0, zero, fin
#-- Es un nodo. Leer su valor
lw t1, NUM(a0)
#-- Sumarlo al acumulador
add t0, t0, t1
#-- Apuntar al siguiente nodo
lw a0, NEXT(a0)
#-- Repetir
b next
fin:
#-- Devolver en a0 la suma total
mv a0, t0
ret
Este es el programa principal:
#-- Solución al ejericico 5
#-- Programa principal
.include "servicios.asm"
.data
msg: .string "Introduce numeros enteros positivos:\n"
msg2: .string "\nSuma de los elementos: "
.text
#-- Usamos s0 como puntero de acceso a la lista
#-- Inicialmente es NULL
li s0, 0
#-- Imprimir mensaje
la a0, msg
li a7, PRINT_STRING
ecall
#-- Pedir números hasta que se introduzca uno negativo
next:
#-- Pedir Numero entero
li a7, READ_INT
ecall
#-- Si el a0 < 0, finalizar la introduccion de numeros
blt a0, zero, fin
#-- Guardar el numero en la lista
mv a1, a0
mv a0, s0
jal create
#-- Guardamos en s0 la cabeza de la lista
mv s0, a0
#-- repetir
b next
fin:
#-- Calcular la suma de los elementos
#-- de la lista
mv a0, s0
jal sum
#-- Guardar el resultado en t0
mv t0, a0
#----- Mensaje 2
la a0, msg2
li a7, PRINT_STRING
ecall
#-- Imprimir resultado
mv a0, t0
li a7, PRINT_INT
ecall
#-- Terminar
li a7, EXIT
ecall
Ejercicio 6
Implementación de la función sum() usando algoritmo recursivo:
#------- Calcular la suma de los elmeentos de la lista
#---- Algoritmo recursivo
#--- SUBRUTINA sum
#-- ENTRADAS:
#-- a0: Puntero de acceso a la lista
#--
#-- DEVUELVE:
#-- a0: suma de los elementos de la lista
#----------------------------------------------
.globl sum
#-- Informacion sobre la lista
.eqv NUM 4
.eqv NEXT 0
sum:
#-- Usamos t0 como acumulador
li t0, 0
#-- Si a0 es NULL, terminar
beq a0, zero, fin
#-- Crear la pila
addi sp, sp, -16
sw ra, 12(sp)
#-- Guardar en la pila el puntero a la lista
sw a0, 8(sp)
#-- Apuntar al siguiente nodo
lw a0, NEXT(a0)
#-- Calcula la suma de la sublista
jal sum
#-- Guardar en t0 la suna de la sublista
mv t0, a0
#-- Recuperar puntero al nodo actual
lw a0, 8(sp)
#-- Leer el valor del nodo actual
lw t1, NUM(a0)
#-- Sumar la sublista con el valro actual
add t0, t0, t1
#-- Recuperar direccion de retorno
lw ra, 12(sp)
addi sp, sp, 16
fin:
#-- Devolver en a0 la longitud
mv a0, t0
ret
El programa principal es el mismo que el del ejercicio 5
Ejercicio 7
Implementación de la subrutina append(), con algoritmo iterativo:
#-- Añadir un elemento al final de la lista
#--
#-- ENTRADA:
#-- a0: Puntero a la lista
#-- a1: Numero a guardar en la lista
#--
#-- SALIDAS:
#-- Ninguna
#--------------------------------------------------------
.globl append
#---- Informacion sobre el nodo
.eqv NEXT 0 #-- Offset del campo NEXT
.eqv NUM 4 #-- Offset del campo NUM
append:
#-- Es una subrutina intermdia
#-- Necesitamos crear la pila
addi sp, sp, -16
sw ra, 12(sp)
#--- Primero recorremos la lista
#--- hasta llegar al último nodo
#--- Sabemos si es el ultimo portque NEXT es 0
next:
#-- Leer el campo next
lw t0, NEXT(a0)
#-- Si es el ultimo elemento
#-- salimos del bucle
beq t0, zero, cont
#-- Actualizar a0 para apuntar al siguiente elemento
mv a0, t0
#-- Repetir
b next
cont:
#--- a0 apunta al último elemento de la lista
#-- Guardamos el puntero en la pila
sw a0, 8(sp)
#-- Crear un nodo nuevo, con next = 0 y num = a1
li a0, 0
jal create
#-- Recuperar el puntero del nodo. Lo metemos en t0
lw t0, 8(sp)
#-- Hacemos que su campo next apunter al nuevo nodo creado
sw a0, NEXT(t0)
#-- Recuperar direccion de retorno
lw ra, 12(sp)
addi sp, sp, 16
ret
El programa principal es este:
#-- Solución al ejericico 7
#-- Programa principal
.include "servicios.asm"
.text
#-- Meter el número 1 en la lista
li a0, 0
li a1, 1
jal create
#-- Mover el puntero de acceso a la lista a s0
mv s0, a0
#-- Llamar a add para añadir a la lista el numero 2
li a1,2
jal append
#-- Añadir el numero 3
mv a0, s0
li a1, 3
jal append
#-- Imprimir la lista
mv a0, s0
jal print
#-- Terminar
li a7, EXIT
ecall
Ejercicio 8
Implementación de la función append() recursiva:
#-- Añadir un elemento al final de la lista
#-- Algoritmo recursivo
#--
#-- ENTRADA:
#-- a0: Puntero a la lista
#-- a1: Numero a guardar en la lista
#--
#-- SALIDAS:
#-- Ninguna
#--------------------------------------------------------
.globl append
#---- Informacion sobre el nodo
.eqv NEXT 0 #-- Offset del campo NEXT
.eqv NUM 4 #-- Offset del campo NUM
append:
#-- En todos los casos hay que llamar a otra subrutina
#-- Hay que crear la pila
addi sp, sp, -16
sw ra, 12(sp)
#-- Leer el campo next
lw t0, NEXT(a0)
#-- Si es el ultimo elemento
#-- creamos nodo y lo enlazamos
beq t0, zero, crear
#-- No es el último: Insertar el valor en la sublista
mv a0, t0
jal append
b fin
crear:
#-- Guardar el puntero al ultimo nodo en la pila
sw a0, 8(sp)
#-- Crear un nodo nuevo, con next = 0 y num = a1
li a0, 0
jal create
#-- Recuperar el puntero del nodo. Lo metemos en t0
lw t0, 8(sp)
#-- Hacemos que su campo next apunter al nuevo nodo creado
sw a0, NEXT(t0)
fin:
#-- Recuperar direccion de retorno
lw ra, 12(sp)
addi sp, sp, 16
ret
El programa principal es el mismo que el del ejercicio 8
Ejercicio 9
Implementación de la función create_str():
#-- Crear un nodo inicializado con una cadena
#-- pedida al usuario. Se inicializa el campo NEXT
#-- con el valor pasado
#--
#-- ENTRADAS:
#-- a0: Puntero a almacenar al campo next
#--
#-- SALIDAS:
#-- a0: Puntero al nuevo nodo creado
#--------------------------------------------------------
.include "servicios.asm"
.globl create_str
#-- Informacion del nodo
.eqv NEXT 0
.eqv STR 4
#-- Tamaño del nodo: 20 bytes para la cadena y 4 para el puntero
.eqv TAM 24
.eqv MAX_STR 20 #-- Tamaño de la cadena
.text
create_str:
#-- a0 Contiene se debe guardar en NEXT
#-- Lo movemos a a1 para no perderlo
mv a1, a0
#-- Crear un nodo nuevo
li a0, TAM
li a7, SBRK
ecall
#-- a0 contiene el puntero al nodo
#-- Lo movemos a t0 para no perderlo
mv t0, a0
#-- Inicializar los campos
sw a1, NEXT(t0)
sw zero, STR(t0)
#-- a0 apunta al campo str
addi a0,t0,STR
#-- Pedir cadena al usuario y guardarla en
#-- el campo STR
li a1, MAX_STR
li a7, READ_STRING
ecall
#-- Devolver el puntero al nodo creadd
mv a0, t0
ret
- Implementación de la función print():
#---------------------------------------
#-- Subrutina para imprimir todas las cadenas
#-- contenidas en los nodos de la lista
#--
#-- ENTRADAS:
#-- a0: Puntero a la lista
#--
#-- SALIDAS:
#-- Ninguna
#-----------------------------------------------
.include "servicios.asm"
.globl print
#-- Informacion del nodo
.eqv NEXT 0
.eqv STR 4
.text
print:
#-- Usamos t0 para recorrer la lista
mv t0, a0
next:
#-- Si el puntero es NULL, terminamos
beq t0, zero, fin
#-- a0 apunta al campo
addi a0, t0, STR
#-- Imprimir la cadena del campo STR
li a7, PRINT_STRING
ecall
#-- Apuntar al siguiente nodo
lw t0, NEXT(t0)
#-- Repetir
b next
fin:
ret
- Programa principal:
#-- Solución al ejercicio 9
#-- Programa principal
.include "servicios.asm"
#-- Informacion del nodo
.eqv NEXT 0
.eqv STR 4
#-- Tamaño del nodo: 20 bytes para la cadena y 4 para el puntero
.eqv TAM 24
.eqv MAX_STR 20 #-- Tamaño de la cadena
.data
msg: .string "\nIntroduce dos cadenas:\n"
msg2: .string "\nContenido de la LISTA:\n"
.text
#-- Pedir dos cadenas al usuario
#-- Imprimir mensaje 1
la a0, msg
li a7, PRINT_STRING
ecall
#-- Crear el primer nodo
li a0, 0
jal create_str
#-- a0 contiene el puntero al nodo, inicializado
#-- con NEXT = 0
#-- STR = Cadena introducida por el usuario
#-- Crear el segundo nodo
jal create_str
mv t0, a0
#-- Imprimir mensaje 2
la a0, msg2
li a7, PRINT_STRING
ecall
mv a0, t0
#-- Imprimir la lista
jal print
li a7, EXIT
ecall
Ejercicio 10
El programa principal es:
#-- Solución al ejercicio 10
#-- Programa principal
.include "servicios.asm"
#-- Informacion del nodo
.eqv NEXT 0
.eqv STR 4
.data
msg: .string "\nIntroduce nombres de usuarios:\n"
msg2: .string "\nLa Lista contiene los siguientes nombres:\n"
.text
#-- Pedir dos cadenas al usuario
#-- Imprimir mensaje 1
la a0, msg
li a7, PRINT_STRING
ecall
#--- Usamos s0 como puntero a la lista
#-- Inicialmente s0 es NULL
li s0, 0
bucle:
#-- Crear nodo enlazado como primer elemento de la lista
mv a0, s0
jal create_str
#-- a0 contiene el puntero al nodo
#-- Lo guardamos en s0
mv s0, a0
#-- Leemos el primer byte del campo STR
lw t0, STR(a0)
#-- Si es '\n', es la cadena nula --> Terminar
li t1, '\n'
beq t0, t1, imprimir
#-- Crear siguiente nodo de la lista
b bucle
#-- Henmos terminado de introducir las cadenas
#--- Ahora imprimimos la lista
imprimir:
#-- Imprimir mensaje 2
la a0, msg2
li a7, PRINT_STRING
ecall
#-- El puntero a la lista lo tenemos en s0
mv a0, s0
#-- Imprimir la lista
jal print
li a7, EXIT
ecall
Autores
- Katia Leal Algara
- Juan González-Gómez (Obijuan)
Licencia
