Ficha 15 [2016] - Arreglos De Registros [python] 1r11z

Cátedra de AED [Ciclo 2016]

Ficha 15: Arreglos de Registros

Ficha 15 Arreglos de Registros 1.] Arreglos correspondientes (o "paralelos").

En muchas ocasiones será necesario almacenar información en varios arreglos unidimensionales a la vez, pero de tal forma que haya correspondencia entre los valores almacenados en la casillas con el mismo índice (llamadas casillas homólogas). Por ejemplo, podría ocurrir que se pida guardar en un arreglo los nombres de ciertas personas, y en otro arreglo el importe del sueldo que perciben: Figura 1: Dos arreglos correspondientes o paralelos. nombres sueldos

Juan 1100 0

Ana

Alejandro

María

Pedro

2100

1300

750

800

2

3

4

1

Como se está pidiendo almacenar los datos en dos arreglos, sólo se debe cuidar que el nombre y el importe del sueldo de una misma persona aparezcan en ambos arreglos en casillas homólogas. Así, en nuestro ejemplo, la persona representada por la casilla 0 del arreglo Nombres (o sea, nombres[0]) se llama "Juan", y el sueldo que percibe aparece en el arreglo sueldos también en la casilla con índice 0 (o sea, sueldos[0] ) y es el valor 1100. Cuando dos o más arreglos se usan de esta forma, se los suele designar como arreglos correspondientes o paralelos [1]. El manejo de ambos arreglos es simple: sólo debe recordar el programador que hay que usar el mismo índice en ambos arreglos para entrar a la información de una misma persona. El siguiente esquema, muestra por pantalla el nombre y el sueldo de la persona en la casilla 2: print('Nombre:', nombres[2]) print('Sueldo:', sueldos[2])

# Alejandro # 1300

El siguiente problema servirá para aclarar la forma general de manejar arreglos paralelos: Problema 37.) Desarrollar un programa que permita cargar tres arreglos con n nombres de personas, sus edades y los sueldos que ganan. Luego de realizar la carga de todos los datos, mostrar los nombres de las personas mayores de 18 años que ganan menos de 10000 pesos, pero de forma que el listado salga ordenado en forma alfabética. Discusión y solución: El programa usará una función read() cuyo objetivo es cargar por teclado los tres arreglos. Cuando se trabaja con arreglos paralelos, en los que la componente en la casilla i de cada arreglo contiene información relacionada al mismo objeto o entidad del problema, es conveniente que la carga por teclado se haga de forma de barrer los tres arreglos al mismo tiempo: se carga primero la componente 0 de todos los arreglos, luego la componente 1 de todos ellos, y así sucesivamente. De esta forma, quien hace la carga de datos ve facilitada su tarea pues carga los datos de una persona de una sola vez, sin tener

Ing. Valerio Frittelli - 317

Cátedra de AED [Ciclo 2016]

Ficha 15: Arreglos de Registros

que volver atrás luego de cargar los nombres o las edades para cargar los sueldos (lo que sería realmente incómodo). La función read() de nuestro programa sería la siguiente: def read(nombres, edades, sueldos): n = len(nombres) for i in range(n): nombres[i] = input('Nombre[' + str(i) + ']: ') edades[i] = int(input('Edad: ')) sueldos[i] = int(input('Sueldo: ')) print()

El proceso de ordenamiento será realizado por la función sort() mediante nuestro ya conocido algoritmo de ordenamiento por Selección Directa. El arreglo de nombres debe ser ordenado en forma alfabética o lexicográfica: como sabemos, la idea intuitiva es que las palabras que en un diccionario aparecerían primero se consideran "menores" (alfabéticamente hablando) que las palabras que en el diccionario aparecerían después. Así, el nombre "Ana" es lexicográficamente menor que el nombre "Luis", pues "Ana" aparecería primero en un diccionario que "Luis". En Python, La comparación de cadenas es simple y directa: como sabemos, dos cadenas pueden ser comparadas directamente mediante los operadores relacionales típicos, y Python hará el trabajo correcto [2] [3]. Note, no obstante, que la función sort() no sólo debe ordenar el arreglo de nombres, sino que debe cuidar que al ordenar ese arreglo se mantenga la correspondencia entre los elementos de ese arreglo y los elementos de los otros dos que contienen las edades y los sueldos. El principio es simple: si se realiza un cambio en el arreglo de nombres, el mismo cambio debe reflejarse en los otros dos, por lo cual se realizan tres operaciones de intercambio (una para el arreglo de nombres, otra para el arreglo de edades y otra para el de sueldos). La función que hace el ordenamiento sería la que sigue: def sort(nombres, edades, sueldos): n = len(nombres) for i in range(n-1): for j in range(i+1, n): if nombres[i] > nombres[j]: nombres[i], nombres[j] = nombres[j], nombres[i] edades[i], edades[j] = edades[j], edades[i] sueldos[i], sueldos[j] = sueldos[j], sueldos[i]

Finalmente, la función display() usa un ciclo for para analizar cada componente del arreglo de edades y del arreglo de sueldos. Si se encuentra que la edad en la posición i es mayor a 18 y al mismo tiempo el sueldo es menor a 10000, se muestran los tres datos que corresponden a esa persona, que se encuentra en cada arreglo en la misma posición i. La función podría ser la siguiente: def display(nombres, edades, sueldos): n = len(nombres) print('ayores de 18 que ganan menos de 10000 pesos:') for i in range(n): if edades[i] > 18 and sueldos[i] < 10000: print('Nombre:', nombres[i], 'Edad:', edades[i], 'Sueldo:', sueldos[i])

El programa completo que se muestra a continuación. está incluido en el modelo tes01.py que forma parte del proyecto [F15] Arreglos de Registros que acompaña a esta Ficha. __author__ = 'Cátedra de AED' def validate(inf): n = inf

Ing. Valerio Frittelli - 318

Cátedra de AED [Ciclo 2016]

Ficha 15: Arreglos de Registros

while n <= inf: n = int(input('Cantidad de elementos (> a ' + str(inf) + ' por favor): ')) if n <= inf: print('Error: se pidio mayor a', inf, '... cargue de nuevo...') return n def read(nombres, edades, sueldos): n = len(nombres) for i in range(n): nombres[i] = input('Nombre[' + str(i) + ']: ') edades[i] = int(input('Edad: ')) sueldos[i] = int(input('Sueldo: ')) print() def sort(nombres, edades, sueldos): n = len(nombres) for i in range(n-1): for j in range(i+1, n): if nombres[i] > nombres[j]: nombres[i], nombres[j] = nombres[j], nombres[i] edades[i], edades[j] = edades[j], edades[i] sueldos[i], sueldos[j] = sueldos[j], sueldos[i] def display(nombres, edades, sueldos): n = len(nombres) print('Personas mayores de 18 que ganan menos de 10000 pesos:') for i in range(n): if edades[i] > 18 and sueldos[i] < 10000: print('Nombre:', nombres[i], 'Edad:', edades[i], 'Sueldo:', sueldos[i]) def test(): # cargar cantidad de personas... n = validate(0) # crear los tres arreglos de n elementos... nombres = n * [' '] edades = n * [0] sueldos = n * [0] # cargar los tres arreglos por teclado... print('\nCargue los datos de las personas:') read(nombres, edades, sueldos) # ordenar alfabéticamente el sistema... sort(nombres, edades, sueldos) # avisar por pantalla el resultado de la búsqueda... display(nombres, edades, sueldos) # script principal... if __name__ == '__main__': test()

2.] Arreglos de registros en Python.

En muchas aplicaciones será más útil almacenar registros completos en cada casillero de un arreglo, en lugar de usar arreglos paralelos como mostramos en la sección anterior. Esto es perfectamente válido en Python: un arreglo en Python puede contener elementos de cualquier tipo incluyendo elementos que sean referencias a registros. Esta técnica es efectivamente más cómoda que la de los arreglos paralelos, ya que en lugar de definir varios arreglos separados para almacenar en cada uno una parte de los valores que se necesitan, se Ing. Valerio Frittelli - 319

Cátedra de AED [Ciclo 2016]

Ficha 15: Arreglos de Registros

define un único arreglo que contiene a todos los datos y con eso no sólo se simplifica el código fuente sino que se ahorra esfuerzo cuando se tiene que enviar ese conjunto de datos como parámetro a una función, ya que en lugar de varios arreglos, se pasa sólo uno [1]. Supongamos que se tiene definido un registro Estudiante y que se desea almacenar varios registros de ese tipo en un arreglo. Suponga que se cuenta con el tipo Estudiante ya definido y con una función constructora __init()__ para crear y asignar los campos a cada registro de ese tipo: class Estudiante: def __init__(self, leg=0, nom='', pro=0): self.legajo = leg self.nombre = nom self.promedio = pro

Si se conoce de antemano la cantidad n de registros a almacenar, una forma de crear el arreglo pedido consiste en declarar primero la referencia a ese arreglo, reservando n casilleros que pueden comenzar valiendo cualquier valor (por ejemplo, None): lo importante no es qué valor comience asignado en cada casillero (puesto que este valor puede cambiarse más tarde incluso por uno de otro tipo), sino que se tengan efectivamente n casilleros [2]: n = 6 v = n * [None]

La instrucción anterior crea un arreglo de n = 6 componentes con valor inicial None. La idea es que en cada uno se almacene luego una referencia a un registro de tipo Estudiante, aunque todavía no se han creado esos registros. El aspecto que tendría este arreglo en este momento en memoria sería como el que se muestra a continuación: Figura 2: Un arreglo con n = 6 casilleros con valor inicial None.

v None

None

0

1

None None

2

3

None None

4

5

A diferencia de un arreglo que contenga valores de tipo simple, un arreglo de referencias todavía no contiene elementos listos para usar (a menos que el programador quiera efectivamente usar los valores None...): deben crearse los registros que serán apuntados desde cada casilla del arreglo, y recién entonces comenzar a usar esos objetos. Por ejemplo, en este caso, podría hacerse algo como: for i in range(n): v[i] = Estudiante()

lo cual haría que cada casilla del arreglo contenga ahora una referencia a un registro de tipo Estudiante, pero con todos sus campos valiendo los valores default que asigna la función constructora (ya que al invocarla en el momento de crear cada registro, no le hemos enviando ningún valor como parámetro formal). Los valores None ya no están en cada casillero, y fueron reemplazados por las direcciones de cada uno de los registros. Una mejor forma de proceder, podría ser que no sólo se creen los registros vacíos, sino que también se proceda a cargar por teclado los datos a almacenar en cada uno, y luego se creen los registros con sus campos inicializados de forma definitiva. La secuencia que sigue muestra la forma de hacerlo: for i in range(n): leg = int(input('Legajo[' + str(i) + ']: '))

Ing. Valerio Frittelli - 320

Cátedra de AED [Ciclo 2016]

Ficha 15: Arreglos de Registros

nom = input('Nombre: ') pro = float(input('Promedio: ')) print() v[i] = Estudiante(leg, nom, pro)

Está claro que puede lograrse el mismo resultado dejando los valores default de la función constructora __init()__, y luego creando y asignando directamente los campos en cada casillero. Lo anterior es equivalente a: for i in range(n): v[i] = Estudiante() v[i].legajo = int(input('Legajo[' + str(i) + ']: ')) v[i].nombre = input('Nombre: ') v[i].promedio = float(input('Promedio: ')) print()

Como cada casillero v[i] del arreglo es un registro de tipo Estudiante, entonces el a cada campo de v[i] se hace con el operador punto combinado con el propio identificador v[i]: v[i].legajo permite acceder al campo legajo del registro ubicado en v[i], y en forma similar ocurre para el resto de los campos. Las dos secuencias anteriores crean diferentes registros y los asignan en distintas casillas del arreglo, que podría verse ahora como sigue (suponga que los datos cargados por teclado fueron efectivamente los que se ven en la figura): Figura 3: Un arreglo con n = 6 referencias a registros ya creados de tipo Estudiante.

v

0

1

2

3

4

5

legajo: 76

legajo: 57

legajo: 10

legajo: 21

legajo: 45

legajo: 33

nombre: Luis promedio: 8

nombre: Juan

nombre: Ana

nombre: Ale

nombre: Maria

nombre: Pedro

promedio: 5

promedio: 7

promedio: 4

promedio: 10

promedio: 8

Sólo cuando cada registro haya sido creado se puede recorrer el arreglo y aplicar a cada uno alguna tarea o proceso. Recuerde que v[i] es la referencia que apunta al registro en la casilla i, y por lo tanto algo como v[i].legajo accede al número de legajo almacenado en el registro v[i]. Pero esto sólo es válido si v[i] es efectivamente un registro de tipo Estudiante: si se intenta acceder a un campo desde una referencia que no apunta a un registro de ese tipo, el programa se interrumpirá lanzando un mensaje de error por campo inexistente. Finamente, el arreglo se usa como se usaría a cualquier arreglo: si se sabe qué clase de registros se almacenaron dentro de él, se podrá cargarlos por teclado, visualizarlos, ordenarlos, efectuar búsquedas, etc. Analice el siguiente ejercicio que completa el ejemplo que hemos venido utilizando: Problema 38.) Se desea almacenar en un arreglo la información de los n estudiantes que se registraron para participar de un curso de programación. Por cada estudiante se tiene su número de legajo, su nombre y su promedio en la carrera que cursa. Participarán del curso

Ing. Valerio Frittelli - 321

Cátedra de AED [Ciclo 2016]

Ficha 15: Arreglos de Registros

los estudiantes cuyo promedio sea mayor o igual a x, siendo x un valor cargado por teclado. Muestre los datos de los estudiantes que participarán del curso, pero ordenados de menor a mayor por número de legajo. Discusión y solución: El programa que resuelve este problema es el modelo test02.py (incluido en el proyecto [F15] Arreglos – Registros – Ordenamiento que viene con esta Ficha), y es el siguiente: __author__ = 'Cátedra de AED' class Estudiante: def __init__(self, leg, nom, pro): self.legajo = leg self.nombre = nom self.promedio = pro def write(est): print('Legajo:', est.legajo, end=' ') print('- Nombre:', est.nombre, end=' ') print('- Promedio:', est.promedio) def validate(inf): n = inf while n <= inf: n = int(input('Cantidad de elementos (mayor a ' + str(inf) + '): ')) if n <= inf: print('Error: se pidio mayor a', inf, '... cargue de nuevo...') return n def read(estudiantes): n = len(estudiantes) for i in range(n): leg = int(input('Legajo[' + str(i) + ']: ')) nom = input('Nombre: ') pro = float(input('Promedio: ')) print() estudiantes[i] = Estudiante(leg, nom, pro) def sort(estudiantes): n = len(estudiantes) for i in range(n-1): for j in range(i+1, n): if estudiantes[i].legajo > estudiantes[j].legajo: estudiantes[i], estudiantes[j] = estudiantes[j], estudiantes[i] def display(estudiantes, x): n = len(estudiantes) print('Estudiantes que harán el curso (tienen promedio >=', x, '):') for i in range(n): if estudiantes[i].promedio >= x: write(estudiantes[i]) def test(): # cargar cantidad de estudiantes... n = validate(0) # crear un arreglo con n casilleros de valor indefinido...

Ing. Valerio Frittelli - 322

Cátedra de AED [Ciclo 2016]

Ficha 15: Arreglos de Registros

# ... se usará para almacenar luego las referencias a los Estudiantes... estudiantes = n * [None] # cargar el arreglo por teclado... print('\nCargue los datos de los estudiantes:') read(estudiantes) print() x = float(input('Promedio mínimos para poder hacer el curso: ')) print() # ordenar alfabéticamente el arreglo... sort(estudiantes) # mostrar por pantalla el listado... display(estudiantes, x) # script principal... if __name__ == '__main__': test()

La función test() define un arreglo referenciado por la variable estudiantes, que contendrá referencias a registros de tipo Estudiante (tipo que fue definido al inicio del módulo). Este arreglo se usará para almacenar los datos de todos los estudiantes que se hayan inscripto para hacer el curso. La misma función test() carga por teclado la cantidad total de alumnos n, y en base a ese valor crea el arreglo con n casilleros valiendo None. Recuerde que no se debería comenzar a usar el arreglo hasta crear o asignar registros de tipo Estudiante en cada componente (cosa que se hace en este caso la función read(). La función sort() ordena el arreglo de acuerdo a los legajos de los estudiantes, de menor a mayor. Lo más relevante de esta función es la condición para determinar si debe hacerse un intercambio o no: if estudiantes[i].legajo > estudiantes[i].legajo: estudiantes[i], estudiantes[j] = estudiantes[j], estudiantes[i]

Puede verse que en la condición se accede al campo legajo de cada registro, y se comparan sus valores: ahora cada casillero contiene un registro y no un valor int, por lo que comparar directamente estudiantes[i] con estudiantes[j] carece de sentido (¡y provocaría un error!). Además, si la condición es verdadera puede verse que se procede a intercambiar directamente las referencias a los registros, sin tener que hacer ese intercambio campo por campo. Finalmente, la función display() recorre el contenido del arreglo mostrando por consola los datos de los alumnos cuyo promedio sea mayor o igual al valor x que se tomó como parámetro. Como el arreglo está ordenado por legajo, los datos de los estudiantes que se muestren saldrán a su vez ordenados por legajo.

Anexo: Temas Avanzados En general, cada Ficha de Estudios podrá incluir a modo de anexo un capítulo de Temas Avanzados, en el cual se tratarán temas nombrados en las secciones de la Ficha, pero que requerirían mucho tiempo para ser desarrollados en el tiempo regular de clase. El capítulo de Temas Avanzados podría incluir profundizaciones de elementos referidos a la programación en particular o a las ciencias de la computación en general, como así también explicaciones y demostraciones de fundamentos

Ing. Valerio Frittelli - 323

Cátedra de AED [Ciclo 2016]

Ficha 15: Arreglos de Registros

matemáticos. En general, se espera que el alumno sea capaz de leer, estudiar, dominar y aplicar estos temas aun cuando los mismos no sean específicamente tratados en clase. a.) Conteo y/o acumulación por directo (vectores de conteo y/o acumulación).

Los arreglos son estructuras de datos especialmente útiles, puesto que brindan la posibilidad del directo a cada componente. Es decir: si se necesita acceder directamente a un elemento, sólo se requiere conocer el índice del mismo y no es necesario pasar en forma secuencial por todos los elementos anteriores. Existen situaciones (el caso de la búsqueda binaria es una de ellas) en las cuales esta propiedad permite resolver problemas en forma notablemente sencilla y rápida. Por ejemplo, considérese el siguiente problema: Problema 39.) Cargar por teclado un conjunto de valores tales que todos ellos estén comprendidos entre 0 y 99 (incluidos ambos). Se indica el fin de datos con el número -1. Determinar cuántas veces apareció cada número. Discusión y solución: A primera vista, el problema parece de solución obvia: se usa un ciclo para cargar de a un valor (num) por vez, de forma que el ciclo sólo se detenga cuando sea num == -1. Como se pide determinar cuántas veces apareció cada valor posible de num, se usa un contador distinto por cada valor diferente que num pueda asumir. Así, para contar cuántas veces apareció el 1, se puede usar el contador c1, para el 2 se podrá usar c2, y así sucesivamente. En cada repetición del ciclo se usa un if encadenado para determinar qué número se cargó en esa vuelta, y en función del número se elige el contador correspondiente. Al finalizar el ciclo, se muestran todos los contadores, y asunto terminado... Sin embargo, esa solución dista mucho de ser buena y sobre todo en casos como éste, en que la variable num puede asumir valores en un rango muy amplio (0 a 99). El programador debería declarar y poner en cero cien contadores, y luego, dentro del ciclo, usar ¡cien condiciones anidadas! para determinar qué contador debería usar de acuerdo al número ingresado. Además del gran esfuerzo de codificación que el programador deberá realizar, se tendrá el problema de la enorme redundancia de instrucciones semejantes, y por si esto fuera poco, el programa resultante será muy poco flexible en la práctica: si luego de plantearlo nos cambian las condiciones supuestas (por ejemplo: si los valores que puede asumir num pasaran a ser entre 0 y 150) entonces el programa original ya no serviría de nada... La solución correcta es usar un arreglo unidimensional c de cien componentes, de forma que cada componente se use como uno de los contadores que se están necesitando [1]. Se pone inicialmente en cero cada componente del vector (dado que esos componentes serán contadores). Luego comienza el ciclo para cargar los valores num. La idea central, es que si num vale 0, entonces debe usarse c[0] para contarlo. Si num vale 1, se usa c[1], y así sucesivamente. En general, para cada valor de la variable num tal que 0 <= num <= 99, debe usarse c[num] para contarlo... En otras palabras: dentro del ciclo no es necesario usar condiciones anidadas para determinar qué casillero del arreglo usar para contar cada número: se accede directamente al casillero cuyo índice es num y se incrementa el mismo en uno... Al cortar el ciclo, se muestra el contenido del arreglo, y ahora sí el problema queda resuelto de manera convincente.

Ing. Valerio Frittelli - 324

Cátedra de AED [Ciclo 2016]

Ficha 15: Arreglos de Registros

Cuando un arreglo unidimensional se usa de esta forma, se lo suele designar como vector de conteos o simplemente como vector de contadores1. Si el arreglo se usara para acumular valores (en vez de contarlos como se supuso en el ejemplo), se hablaría entonces de un vector de acumulación. Se muestra a continuación el programa que aplica lo dicho y resuelve el problema (ver modelo test03.py en el proyecto [F15] Arreglos de Registros): en la función test() se define el vector de conteos c de n = 100 elementos valiendo cada uno de ellos inicialmente 0, que se usará para contar cuántas veces aparecen los números en el rango [0, n-1]. Luego se cargan los números mediante un ciclo de doble lectura, y se aplica la técnica vista para proceder a contarlos. Al finalizar, se recorre el vector de conteos y se visualizan los resultados, pero de forma que sólo se muestran los conteos de los números que hayan entrado al menos una vez (lo cual ahorra algo de espacio en la consola de salida…): __author__ = 'Cátedra de AED' def test(): # crear el vector de conteo... n = 100 c = n * [0] # cargar y contar los números... num = int(input('Ingrese un valor entre 0 y 99 (con –1 corta): ')) while num != -1: if 0 <= num < n: c[num] += 1 else: print('Error... el número debía ser >= 0 y <', n) num = int(input('Ingrese otro valor entre 0 y 99 (con –1 corta): ')) # mostrar los resultados... print('Resultados:') for i in range(n): if c[i] != 0: print('Número', i, '- Frecuencia de aparición', c[i]) if __name__ == '__main__': test()

Créditos El contenido general de esta Ficha de Estudio fue desarrollado por el Ing. Valerio Frittelli para ser utilizada como material de consulta general en el cursado de la asignatura Algoritmos y Estructuras de Datos – Carrera de Ingeniería en Sistemas de Información – UTN Córdoba, en el ciclo lectivo 2016.

1

Una situación de conteo muy conocida se da en las famosas cuentas regresivas que tienen lugar en distintos tipos de eventos (lanzamientos de naves espaciales, llegada del Año Nuevo, etc.) A su vez, es muy común en el cine encontrar escenas basadas en cuentas regresivas: Una de esas escenas se dio en la película Independence Day (o Día de la Independencia), de 1996, dirigida por Roland Emmerich y protagonizada por Will Smith y Jeff Goldblum. Una avanzada (y hostil) civilización extraterrestre llega a la Tierra y posiciona numerosas naves en el espacio aéreo de muchas ciudades importantes de todo el mundo, como si estuviesen vigilándolas. Estas naves emiten una extraña señal mientras se están posicionando, y pronto alguien descubre que la señal es en realidad una cuenta regresiva… que en cuanto llegue a cero provocará el ataque simultáneo de todas esas naves a todas las ciudades vigiladas, iniciando una invasión.

Ing. Valerio Frittelli - 325

Cátedra de AED [Ciclo 2016]

Ficha 15: Arreglos de Registros

Actuaron como revisores (indicando posibles errores, sugerencias de agregados de contenidos y ejercicios, sugerencias de cambios de enfoque en alguna explicación, etc.) en general todos los profesores de la citada asignatura como de la Cátedra, y en especial las ing. Analía Guzmán, Cynthia Corso y Karina Ligorria, que realizaron aportes de contenidos, propuestas de ejercicios y sus soluciones, sugerencias de estilo de programación, y planteo de enunciados de problemas y actividades prácticas, entre otros elementos.

Bibliografía [1] V. Frittelli, Algoritmos y Estructuras de Datos, Córdoba: Universitas, 2001. [2] Python Software Foundation, "Python Documentation," 2016. [Online].

Available: https://docs.python.org/3/. [Accessed 24 February 2016]. [3] M. Pilgrim, "Dive Into Python - Python from novice to pro," 2004. [Online]. Available: http://www.diveintopython.net/toc/index.html. [Accessed 6 March 2016].

Ing. Valerio Frittelli - 326