• Author / Uploaded
• anon-68902

• Categories
• Algoritmos
• Estructura de datos de matriz
• Archivo de computadora
• Tipo de datos
• C (lenguaje de programación)

Citation preview

TUPLAS Introducción a las Estructuras de Datos Definición de nuevos tipos de datos Manipulación de tuplas Vectores de tuplas Lectura/escritura de Tuplas desde teclado y fichero Funciones y acciones que devuelven tuplas Ejercicio completo Ejercicios propuestos Introducción a las Estructuras de Datos Hasta ahora hemos centrado básicamente nuestro estudio en una forma adecuada de algoritmizar problemas, o lo que es lo mismo, de encontrar algoritmos de solución para ciertos problemas del mundo real. Para conseguirlo nos hemos basado en: • • •

Utilización eficiente de las estructuras de control básicas: asignación, secuencia, alternativa e iteración Dividir el problema en subproblemas más fáciles de solucionar, construyendo programas según un diseño descendente o top-down (diseño modular) Reutilización de algoritmos mediante la utilización de librerías de componentes ya desarrollados y probados

Sin embargo, existe otro gran area de conocimiento que hemos tratado con poca profundidad hasta ahora y es la de utilizar tipos de datos “avanzados”. En nuestro estudio hemos introducido los tipos básicos (predefinidos) como el entero, el real, el carácter, o el lógico, y con posterioridad hemos visto como agrupar datos del mismo tipo (homogeneos) en “almacenes” como son las tablas1. A la vez hemos estudiado que los datos pueden proceder del dispositivo de entrada estandar (el teclado) o bien pueden proceder de un almacenamiento permanente en disco (un fichero2). Asimismo la escritura de resultados puede realizarse en pantalla o bien en ficheros. En programación existe una igualdad que debe intentar cumplirse: PROGRAMA = ALGORITMO + ESTRUCTURAS DE DATOS De tal forma que los programas desarrollados con estructuras de datos adecuadas, resultan de mayor nivel y legibilidad, redundando esto en su costo de mantenimiento, de actualización y de desarrollo. Como estructuras de datos (EDs) se conoce a todo aquello que sirva para almacenar de forma organizada distintas informaciones que se deban manipular en los algoritmos. Existen distintos tipos de EDs como son las listas, colas, árboles, grafos, etc., que se salen fuera de nuestros objetivos. Sin embargo vamos a estudiar como crear nuevos 1

Comúnmente en programación se llama vectores o arrays a las tablas unidimensionales, y matrices a las bidimensionales. Además, los arrays de caracteres se denominan cadenas o strings. 2 Los ficheros que hemos estado utilizando han sido de texto (que contienen caracteres ASCII o de otro código), pero también pueden utilizarse ficheros binarios, cuya manipulación es más eficiente y compacta, pero que no pueden ser abiertos con un editor de texto.

tipos de datos a partir de los ya existentes, de forma que las nuevas variables de estos nuevos tipos puedan contener información diversa (hetereogenea). A estos tipos de datos los llamaremos estructuras, registros o tuplas. Ejemplo: si queremos almacenar algunas de las distintas informaciones que caracterizan a una persona, podremos crear una tupla que contenga un espacio para almacenar su nombre, otro para su edad y otro para su teléfono (cada una de estas informaciones se denomina campo, y cada uno será del tipo adecuado a los datos que tenga que albergar): Nombre: cadena

Edad: entero

Teléfono: cadena

Definición de nuevos tipos de datos Definiremos en lenguaje algorítmico los nuevos tipos de datos dentro del párrafo Utilizando, de forma que podremos utilizarlos en el fichero en el que se incluya3. Veamos un ejemplo concreto: Ejemplo: definición de un tipo de datos tupla para contener información relativa a una persona. Al nuevo tipo lo llamamos persona. Utilizando Tipo Persona=tupla Nombre: cadena Edad: entero Telefono: cadena ftupla Ftipo

A partir de esta definición podemos crear variables de ese nuevo tipo, y por supuesto podemos dar valores a sus campos, para lo que utilizaremos el operador de selección de campo ( . ): p, q: persona; p.nombre:= ”pepe” p.edad:= 23 p.telefono:= ”956662112”

Podemos asignar variables de tipo estructura directamente (por ejemplo, para dos hermanos gemelos): q:=p q.nombre:= ”manolo”

Se pueden crear tipos aún más avanzados, a partir de los ya existentes: 3

Podemos hacerlo también de otra forma: crear un fichero independiente con los nuevos tipos de datos que queramos utilizar en nuestra aplicación en incluir éste posteriormente en todos aquellos archivos en los que se pretenda hacer uso de esos tipos.

Ejemplo: creación de un tipo tupla alumno, a partir del tipo persona (damos por hecho que cualquier alumno es una persona, y además tiene otras características) Tipo Alumno=tupla Datos: persona Notas: tabla[50] de real Curso: entero ftupla Ftipo

De esta forma, podemos definir variables de este nuevo tipo y darle valores: x,y: alumno x.curso:= 1 x.notas[0]:= 5.0 x.notas[1]:= 7.5 x.datos.nombre:= “carlos”

Manipulación de tuplas Aparte de dar valores individuales a los campos de una variable de tipo estructura, debemos estudiar por su importancia y amplia utilización la forma de crear tablas o vectores de tuplas y como rellenar éstas con informaciones procedentes ya sea de teclado o de fichero. Creación de vectores de tuplas De la misma manera que creabamos tablas de números reales o de enteros, es posible crear variables que sean tablas de registros. Por ejemplo: lista_amigos: tabla[100] de persona lista_clase: tabla[400] de alumno

Con estas definiciones podemos hacer, por ejemplo, que “pepe” sea nuestro primer amigo: lista_amigos[0]:=p // ya que “pepe” era la variable persona p

O podemos rellenar individualmente algún campo de alguno de nuestros amigos: lista_amigos[1].nombre:= “alfonso”

Evidentemente sobre los vectores de tuplas se pueden utilizar los mismos mecanismos que sobre las tablas de enteros o reales que estabamos acostumbrados a manejar. Es decir, se pueden atacar de la misma forma (con los mismos esquemas) problemas de recorrido y de búsqueda. Veremos algunos ejemplos después del apartado siguiente.

Lectura/escritura de Tuplas desde teclado y fichero Directamente vamos a escribir una acción para leer una serie de informaciones desde el teclado y almacenar sus valores en un vector de registros. Como las tablas tienen una longitud finita, debemos controlar no pasarnos del límite de valores definidos (supongamos máximo4 100). Además el algoritmo devolverá el número de personas introducidas en el vector, es decir que el vector no tiene porqué rellenarse de forma completa. Como marca o persona final utilizaremos la persona cuyo nombre sea “fin”. acción LeerTuplas (sal v:tabla[100] de persona, sal numero_personas: entero) var p: persona i: entero fvar i:=0 leer(p) mientras p.nombre < > “fin” y i < 100 // para no pasarnos del tamaño definido v[i]:=p i:=i+1 leer(p) // se puede leer( ) una estructura fmientras numero_personas:=i // devolvemos el número de personas que hay en el vector facción

En realidad, no hay demasiadas cosas nuevas, ya que la manipulación de vectores incompletos era un asunto que ya habíamos tratado con anterioridad. Ahora vamos a escribir una acción que rellene el vector de tuplas con los datos contenidos en un fichero de texto que tiene el formato siguiente: Pepe Carlos …

23 24

956662112 956661221

accion LeerFicheroTuplas (ent nomfich: cadena, sal v:tabla[100] de persona, sal numero_personas: entero) var p: persona; i: entero f: fichero; e: lógico fvar AbrirFich(nomfich,”lectura”,f,e) si (no e) i:=0 mientras (no FinFich(f)) y i telefono_sin_nombre y i < numero_amigos i: = i+1 // se hace un recorrido hasta encontrarlo o terminar fmientras si i < > numero_amigos retorna lista_amigos[i] // una persona sino retorna persona_nula // para su control desde el exterior de esta función fsi ffunción

Ejercicio completo Supongamos que tenemos un fichero de texto en el que se encuentran almacenadas las informaciones relativas a una lista de personas, de tal forma que en cada fila del fichero hay un registro completo. Queremos almacenar todos los registros en un vector, buscar las personas que tengan una cierta edad (que se pedirá por teclado), y escribir esos registros en otro fichero. Definiendo // definición de constantes N=100 Utilizando // definición de tipos Tipo Persona=tupla Nombre: cadena Edad: entero Telefono: cadena ftupla Ftipo

5

Hasta ahora sólo habiamos estudiado funciones que devuelven un valor.

// prototipos de acciones y/o funciones función LeerFicheroTuplas (ent nomfich: cadena, sal v:tabla[N] de persona): entero función BuscaEdad (ent v:tabla[N] de persona, ent num:entero, ent edad:entero, sal v_misma_edad:tabla[N] de persona): entero acción EscribirFicheroTuplas (ent nomfich: cadena, ent v:tabla[N] de persona, ent numero_personas: entero) Acción Principal var nomfich1,nomfich2: cadena lista, lista_misma_edad:tabla[N] de persona edad,num_personas, num_edad: entero fvar leer(nomfich1) num_personas:=LeerFicheroTuplas(nomfich1,lista) si num_personas < > -1 leer(edad) num_edad:=BuscaEdad(lista,num_personas,edad,lista_misma_edad) leer(nomfich2) EscribirFicheroTuplas(nomfich2,lista_misma_edad,num_edad) sino escribir(‘Error en la apertura del fichero de datos’) fsi escribir(‘Fin del programa’) facción

función LeerFicheroTuplas (ent nomfich: cadena, sal v:tabla[100] de persona): entero var p: persona i,num_personas: entero f: fichero e: lógico fvar AbrirFich(nomfich,”lectura”,f,e) si (no e) i:=0 mientras (no FinFich(f)) y i