UNIVERSIDAD NACIONAL DE CÓRDOBA
ESCUELA SUPERIOR DE COMERCIO MANUEL BELGRANO
NIVEL TERCIARIO
ANALISTA DE SISTEMAS
ESTRUCTURA DE DATOS
Prof. MARIA DEL VALLE ARANDA
AÑO 2013
FU�DAME�TACIÓ�
Desde la perspectiva del aprendizaje esta asignatura implica añadir nuevos niveles de
dificultad y complejidad a las ya complejas relaciones entre la estructura del conocimiento
y las estrategias de aprendizaje a desarrollar por los alumnos.
La resolución de problemas en este espacio es considerada desde una concepción
tecnológica, donde un problema se plantea combinando la lógica del conocimiento y la
aplicación de diferentes técnicas.
Desde un enfoque pedagógico, la incorporación de las estructuras de datos como modelos
matemáticos y lógicos en correspondencia con su aplicación, no sólo pone en juego los
esquemas de pensamiento de los alumnos, sino también representa un estímulo creativo, y
una valoración de la propia producción.
La integración de conocimientos y experiencia a través de la práctica facilitan una
comprensión más reflexiva y crítica de los contenidos curriculares, destacando el dominio
de los procesos que son necesarios para alcanzar nuevos conocimientos.
OBJETIVOS GE�ERALES
• Desarrollar el razonamiento intuitivo y lógico.
• Valorar la información como fundamento en la toma de decisiones.
• Escoger las herramientas informáticas más convenientes para el desempeño de su
actividad.
• Generar estrategias personales de resolución de problemas.
OBJETIVOS ESPECÍFICOS
• Reconocer la organización elemental de los datos como medio para la obtención de
información.
• Reconocer las distintas estructuras de datos como medios de almacenamiento de
información.
• Desarrollar habilidades para seleccionar las estructuras de datos más adecuadas
teniendo en cuenta el contexto de funcionamiento de las mismas.
• Desarrollar una lógica para la resolución de problemas que se le planteen en la
aplicación de las estructuras de datos.
CO�TE�IDO
U�IDAD I: Introducción. Organización elemental de los datos.
� Dato. Campo. Registro. Tabla o Archivo.
� Atributo. Entidad. Conjunto de Entidades.
� Elementos simples. Grupos de Elementos.
� Tipos de datos.
� Tipos de registros.
� Clave primaria.
� Creación de índices.
U�IDAD II: Estructura de Datos.
� Concepto.
� Arrays. Array Lineal. Array Bidimensional. Array multidimensional.
� Listas Enlazadas. Punteros. Enlaces.
� Árbol.
� Pila. Cúspide.
� Cola. Frente y final.
� Grafo.
U�IDAD III: Operaciones con Estructura de Datos
� Recorrido.
� Búsqueda.
� Inserción.
� Eliminación.
� Modificación.
� Ordenamiento.
� Mezcla.
U�IDAD IV: Algoritmos.
� Complejidad y relación espacio-tiempo.
� Algoritmos de búsqueda.
� Algoritmos de ordenamiento.
� Diseño.
� Notación algorítmica.
� Componentes.
U�IDAD V: Cadenas.
� Procesamiento de cadenas.
� Terminología básica.
� Almacenamiento de cadenas.
� Operaciones con cadenas.
METODOLOGÍA DE E�SEÑA�ZA
El docente desarrollará los contenidos teóricos, para luego ser aplicados en las
ejercitaciones planteadas.
Los trabajos prácticos han sido formulados con la intención de que los conceptos teóricos
sean llevados al campo experimental, al de la resolución de los problemas. Se busca
enfatizar la formación práctica de los alumnos privilegiando el “saber - hacer”.
BIBLIOGRAFIA:
• Estructura de Datos, Seymour Lipschutz, Mc Graw Hill, 2001.
• Estructura de Datos y Organización de Archivos, Mary e. S. Loomis, Prentice-Hall,
2001.
• Estructura de Datos y Algoritmos, Roberto Hernández, Raquel Dormido, Juan Carlos
Lázaro y S. Ros, Prentice-Hall, 2001.
• Estructura de Datos, Luis Joyanes Aguilar, Ignacio Zahonero Martínez, Mc Graw-Hill,
2007.
• Notas de Cátedra con ejercitaciones prácticas, versión 2013, elaborada por María del
Valle Aranda.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 5
UNIDAD I:
Introducción. Organización elemental de los datos.
Introducción:
Los datos son los que dan origen a la información. Por lo tanto los datos son la materia
prima de la que deriva la información. La información esta compuesta por datos que se han
recopilado y procesado de una forma significativa.
En nuestras experiencias diarias nos enfrentamos rutinariamente a ambos conceptos,
datos e información. Usamos los datos para producir información que nos ayudará a tomar
decisiones. Por ejemplo, al levantarnos por la mañana recopilamos dos unidades de datos: vemos
la hora y luego recordamos la hora a la que comienza nuestra actividad. Sustraemos después la
hora actual de la hora de inicio de nuestra actividad. Este cálculo mental nos da la información
de cuánto tiempo debemos emplear para prepararnos e irnos. Basándonos en esta información
tomamos una decisión: apresurarnos, o relajarnos y tomar todo con calma.
Producimos información a través de datos para ayudarnos a tomar decisiones en miles
de situaciones cada día.
Organización Elemental de los datos:
Dato. Campo. Registro. Archivo.
En el siguiente nivel de jerarquía se combinan los caracteres para representar un
elemento dato. El elemento dato, a veces mal llamado campo por ser este quien lo contiene, es
la unidad lógica más pequeña en la representación de datos. Algunos ejemplos pueden ser el
Número de Legajo del Empleado, el Nombre y el Estado Civil. Luego, los elementos datos
relacionados se agrupan para formar los registros lógicos, o simplemente registros. Por
ejemplo el Número de Legajo del Empleado, el Nombre y el Estado Civil están agrupados para
formar el registro del empleado.
En el nivel siguiente nivel de la jerarquía los registros que tienen el mismo elemento
dato están combinados para formar un archivo. Por ejemplo el archivo contiene el Número de
Legajo, el Nombre y el Estado Civil de todos los empleados de la empresa.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 6
1234 Daniel Casado
1245 Mariela Casada
1253 Raúl Soltero
1253 Raúl Soltero
1253
Atributo. Entidad. Conjunto de Entidades.
Como veíamos anteriormente, los datos se organizan jerárquicamente en campos,
registros y archivos. Para hacer estos términos más precisos, introduciremos una terminología
adicional.
Una entidad es algo que posee ciertos atributos o propiedades a los cuales se les
puede asignar valores. Estos valores pueden ser numéricos o no. Por ejemplo, los siguientes son
posibles atributos de la entidad "empleado de la empresa", con los correspondientes valores:
Atributos: Nombre Edad Sexo DNI
Valores: Juan García 34 M 18.457.987
Entidades con atributos iguales (por ejemplo, todos los empleados de la empresa)
forman un conjunto de entidades. Cada atributo de un conjunto de entidades tiene un rango de
valores, que es el conjunto de valores posibles que pueden asignársele a ese atributo.
El término información a veces se usa al referirse a datos con atributos
determinados. La forma en que los datos se organizan en la jerarquía: campos, registros y
archivos refleja la relación entre atributos, entidades y conjuntos de entidades. Así un campo
es una unidad elemental de información que representa un atributo de una entidad, un registro
es una colección de campos de una entidad y un archivo es una colección de registros de las
entidades contenidas en un conjunto de entidades.
Elementos simples. Grupo de elementos.
La palabra datos hace referencia a valores simples o conjuntos de valores.
Denominamos elemento a una unidad básica de valores. A aquellos elementos que pueden
dividirse en otros reciben el nombre de grupo de elementos. Por el contrario, los no
subdivisibles reciben el nombre de elementos simples. Por ejemplo el nombre de un empleado
Campo
(dato)
Registro
lógico
Archivo
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 7
puede ser subdividido en tres subunidades: nombre, primer apellido y segundo apellido, pero el
número de documento debe ser tratado como una unidad simple.
Tipos de Datos:
Los diferentes lenguajes de programación como así también los sistemas encargados
de administrar y manipular datos, coinciden en utilizar los siguientes tipos de datos:
Texto: es el más común, también denominados carácter, son utilizados para el
almacenamiento de caracteres alfanuméricos (letras, números, símbolos).
Numérico: Se puede introducir números enteros o fraccionarios.
Lógico: sólo pueden contener el valor verdadero o falso. El valor 1 representa
verdadero y el valor 0 falso.
Tipos de Registros:
Los registros pueden clasificarse por su longitud. Un archivo puede tener registros
de longitud fija o variable. En los registros de longitud fija, todos ellos contienen los mismos
elementos con la misma cantidad de espacio asignado a cada uno. En los registros de longitud
variable los registros del archivo pueden tener distintas longitudes. Por ejemplo, los registros
de estudiantes normalmente tienen longitud variable, puesto que estudiantes diferentes
pueden cursar distintas materias. En general los registros de longitud variable tienen
longitudes mínimas y máximas.
Clave primaria:
Cada registro de un archivo puede contener muchos campos elementales, aunque el
valor de un determinado campo puede determinar unívocamente el registro dentro del archivo.
Este campo K recibe el nombre de clave primaria y los valores k1, k2,... de dichos campos
reciben el nombre de claves o valores de clave.
Por ejemplo supongamos que un vendedor de automóviles lleva un archivo de inventario
donde cada campo del mismo contiene los siguientes datos:
Número de Serie Tipo Modelo Precio Accesorios
El campo Número de Serie puede servir como clave primaria para el archivo, puesto
que cada automóvil tiene un único número de serie.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 8
Supongamos que un Club mantiene un archivo de socios, donde cada registro contiene
los siguientes datos:
Nombre Dirección Teléfono Cuotas que debe
Aunque hay cuatro unidades de dato, nombre y dirección pueden ser grupos de
unidades. Aquí el nombre es una clave primaria. Nótese que la dirección y el teléfono no sirven
como clave primaria, puesto que algunos socios pueden pertenecer a la misma familia y tener la
misma dirección y teléfono.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 9
UNIDAD I: TRABAJOS PRÁCTICOS
Los trabajos prácticos han sido formulados con la intención de que los conceptos
teóricos sean llevados al campo experimental, al de la resolución de los problemas. Se busca
enfatizar la formación práctica de los alumnos privilegiando el “saber - hacer”.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 10
Objetivo:
A fin de realizar un reconocimiento de la organización elemental de los datos: datos,
campos, registros, archivos, atributos, entidades, conjunto de entidades, tipos de datos, tipos
de registros, claves primarias y mediante la utilización de herramientas informáticas tales
como la Planilla de Cálculos Excel o el Sistema de Gestión de Base de Datos Access,
desarrollaremos los trabajos prácticos N° 1, 2, 3, 4, 5 y 6.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 11
Trabajo Práctico Nº 1
1. Mediante la Planilla de Cálculos Excel, genere un archivo con los siguientes registros,
validando los datos de la tercera y cuarta columna. Guárdelo en su disco y carpeta de trabajo.
Gallardo, Laura Catamarca 1176-BºGral.Paz F 17 49 1,52
Albareda, Juan Sarachaga 123-BºAlta Cba. M 16 65 1,69
Bastide, José L. 9 de Julio 2987-BºAlto Alberdi M 17 70 1,82
Socca, Diego Independencia 1165-BºNva.Cba. M 17 72 1,85
González, Fabiana Ferreyra 1165-BºP.V.Sarsfield F 16 53 1,63
Tissera, Florencia Aconcagua 213-BºPque.Capital F 17 60 1,70
Alonso, Javier Lamarca 3212-BºUrca M 16 75 1,72
Dahabar, Juan La Cordillera 3399-BºCentenario M 17 59 1,63
Martínez, Mónica Av.Colón 31-BºCentro F 16 69 1,72
Benavídez, Claudia Av.Sabattini 432-BºMaipú F 17 47 1,50
Cáceres, Santiago Entre Ríos 1876-BºSan Vicente M 17 62 1,64
Dalmacio, Joaquín Dean Funes 1234-BºAlberdi M 16 82 1,75
Villada, Susana Neuquén 678-BºProvidencia F 16 54 1,60
Echauri, Lorena Juan B.Justo 3645-BºAyacucho F 17 68 1,72
Montoya, Lorenzo Manuel Reyna 654-BºCerveceros M 17 60 1,60
2. Asígnele a cada conjunto de entidades el atributo correspondiente. 3. Genere con los datos anteriores un nuevo archivo, desagrupando aquellos atributos
conformados por grupos de elementos. Guárdelo en su disco y en su carpeta de trabajo. 4. Indique cuales son los campos que conforman este nuevo archivo. 5. Defina para cada archivo la clave primaria. 6. Con la clave definida para cada archivo realice un ordenamiento de los registros que los
conforman. 7. En el primero de los archivos aplique filtro avanzado para separar los registros
considerando el Sexo. 8. En el otro archivo aplique filtro avanzado para separar los registros teniendo en cuenta la
Edad. 9. Guarde las modificaciones realizadas sobre ambos archivos.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 12
Trabajo Práctico Nº 2 1. Crear una Base de Datos:
a) Ejecute Access. b) Seleccione la opción Base de datos en blanco. Pulse el botón Aceptar. c) El cuadro Archivo nueva base de datos que aparece en pantalla, nos permite seleccionar
la unidad de disco en la cual queremos guardar nuestra base de datos y el nombre que queremos asignarle a la misma. Elija Guardar en: su disco y carpeta de trabajo y como nombre de archivo coloque VIDEO.
d) Pulse el botón Crear. En su pantalla aparecerá la ventana de Base de datos. 2. Creación de Tablas:
En este punto va a crear la primera tabla de la base de datos VIDEO.
a) Pulse sobre el botón Nuevo. En su pantalla aparecerá la ventana Nueva Tabla. b) Seleccione la opción Vista Diseño y pulse el botón Aceptar.
3. Definición de los campos:
a) Sitúe el cursor en la primera fila de la columna Nombre de campo. b) Teclee Código de Socio. Pulse la tecla Tab para pasar a la columna Tipo de Datos. c) Elija Tipo de dato, Numérico. Pulse la tecla Tab para pasar a la columna Descripción.
Teclee Código de socio. d) Continúe cargando los siguientes campos:
Nombre de campo Tipo de dato Descripción Nombre Texto Nombre del cliente Apellido Texto Apellido del cliente DNI Numérico D.N.I del cliente Domicilio Texto Dirección del cliente Ciudad Texto Ciudad donde reside Código Postal Numérico Teléfono Texto Teléfono del cliente Observaciones Memo Otros datos de interés.
4. Propiedades de los campos:
Utilizando el Mouse, sitúese en el campo denominado Código de Socio. Observe el cuadro de Propiedades del campo situada en la parte inferior izquierda de la pantalla. Coloque las siguientes propiedades a los campos.
Nombre de campo
Tamaño Formato Lugares Decimales
Título Requerido Indexado
Código de Socio
Entero Largo
Estándar 0 Código sí si (sin dup.)
Nombre 20 Nombre sí no Apellido 30 Apellido sí si (con dup.) DNI Entero
Largo Estándar 0 D.N.I. sí si (sin dup.)
Domicilio 30 Dirección sí no Ciudad 20 Ciudad no no
Código Postal Entero largo
Número General
0 Código Postal no no
Teléfono 20 Teléfono no no
Observaciones Otros datos de Interés. no no
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 13
5. Clave principal: Seleccione el campo Código de Socio. Luego desde la barra de herramientas elija el icono Clave Principal y presione sobre él, o en el menú Edición seleccione la opción Clave Principal.
6. Guarde la tabla con el nombre Socios. Cierre la Aplicación. 7. Modificar el Diseño de una tabla:
a) Seleccione la Tabla Socios y presione sobre el botón Diseño. b) Ubique el campo Código Postal. En Tipo de campo, cámbielo a Texto. c) Modifique las siguientes Propiedades: Tamaño 8. d) Guarde las modificaciones realizadas, cierre la tabla y salga de la aplicación.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 14
Trabajo Práctico Nº 3 1. Añadir registros a una Tabla:
a) Ejecute Access. b) Pulse sobre la opción Abrir una base de datos Existente. y seleccione la base de datos
VIDEO de la lista de archivos. Presione el botón Abrir c) Seleccione la tabla socios y presione el botón Abrir. d) Ubíquese en el campo Código de socio y cargue los siguientes registros:
Código Socio
Nombre Apellido DNI Domicilio Ciudad Código Postal
Teléfono Observaciones
10008 Daniela Castillo 21.987.987 Betania 234 Córdoba 5009 4236587
10001 José Juncos 5.980.567 Sucre 345 Córdoba 5000 4879854
e) Guarde la tabla y ciérrela. f) Cierre la aplicación.
2. Resuelva el Práctico Nº 4. 3. Seleccione el Formulario SOCIOS y ábralo. Utilizando el mismo termine de cargar los datos
de la tabla VIDEO. Código Socio
Nombre Apellido DNI Domicilio Ciudad Código Postal
Teléfono Observaciones
10014 Emilia Martínez 18.089.567 San Martín 908
Córdoba 5000 4908765
10005 Diego Perez 25.456.967 Sarmiento 345
Córdoba 5001 4567090 Suele devolver las fuera de término
10012 Mónica Ruiz 19.777.909 Castro Barros 367
Córdoba 5009 4223677
10002 Ana Mercado 4.678.987 Salta 56 Córdoba 5001 4098723 10004 Santiago Sánchez 13.567.789 Mendoza 34
4º B Córdoba 5000 03543-
4879892
10016 Carlos Ferrero 8.098.987 Coronel Olmedo 896
Córdoba 5009 4876500
10000 Juan Barrios 7.980.980 Colón 234 Córdoba 5000 4567898
10015 Juan Alberto
Ferreyra 22.984.345 Tablada 34 Córdoba 5000 4667565
10009 Lorena Parnisa 13.984.098 Mariano Larra 234
Córdoba 5009 4239800
10013 Mario Odone 14.980.065 Mariano Moreno 456
Córdoba 5000 4870978
10018 Ana María Garay 17.985.456 Tucumán 65
Córdoba 5000 4662443 Buena clienta
10006 Roberto Meratto 23.345.678 Dean Funes 678
Córdoba 5000 4229856
10010 María Prado 15.677.877 Las Palmeras 45
Córdoba 5009 400866 Todas las semanas lleva 2 películas
10007 Luis Castro 14.567.890 Lafinur 56 Córdoba 5009 4879809 10019 Rodrigo García 13.765.679 Entre Ríos
67 Córdoba 5000 4098766
10003 Laura Suarez 12.345.678 9 de Julio 567 2º A
Córdoba 5000 4986543 Buena Clienta
10011 Sandra Paez 16.987.098 Maipú 190 Córdoba 5000 4556890 10017 Estela Gómez 9.987.098 Martín
Coronado 345
Córdoba 5009 4321212
4. Cierre el formulario y la aplicación.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 15
Trabajo Práctico Nº 4 1. Formulario.
a) Abra la base de datos VIDEO. b) Seleccione la pestaña Formulario. Pulse el botón Nuevo. c) Elija la opción Asistente para formularios. d) Seleccione la Tabla Socios. Presione sobre el botón Aceptar. e) Seleccione haciendo doble clic sobre los mismos, los campos: Código de Socio, Nombre,
Apellido, DNI, Domicilio, Ciudad, Código Postal, Teléfono, Observaciones. Pulse el botón Siguiente.
f) Elija la opción En Columnas y Pulse el botón Siguiente. g) Seleccione un estilo y pulse el botón Siguiente. h) Coloque como título SOCIOS y pulse el botón Terminar. i) Maximice la ventana del formulario. Verifique que esté seleccionado el modo Vista
Diseño. j) Si fuera necesario, aumente la sección del encabezado, para ello ubique el puntero del
Mouse en la línea que separa el Encabezado del formulario de la sección Detalle, el puntero se transformará en una doble flecha arrastre el mouse hasta conseguir el ancho deseado. Utilizando el icono Etiqueta, de la barra Cuadro de herramientas, coloque como Encabezado de Formulario su apellido y nombre y como Pié de Formulario la fecha del día.
k) Guarde el Formulario y cierre el mismo. l) Presione el botón Abrir y chequee todos los registros. Cierre nuevamente el Formulario.
2. Continúe con la resolución del Trabajo Práctico N°3, punto 3).
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 16
Trabajo Práctico Nº 5 1. Ejecute Access. Continuaremos trabajando con el Sistema de Gestión de Base de Datos,
generado en el Trabajo Práctico Nº2. 2. Pulse sobre la opción Abrir una base de datos Existente y seleccione la base de datos
VIDEO de la lista de archivos. Presione el botón Abrir. 3. En la ventana Base de datos, en la Pestaña Tabla, presione el botón Nuevo. 4. Cree las siguientes tablas. Defina Tipo de campos, propiedades y clave principal para las
mismas, teniendo en cuenta los datos que contendrán. 5. Genere para cada una de ellas un formulario, y desde allí cargue los datos. Tabla TEMA Código de tema
Tema
1 Suspenso 2 Terror 3 Bélica 4 Oeste 5 Comedia 6 Musical 7 Drama 8 Ciencia-Ficción 9 Policial 10 Histórica 11 Aventuras 12 Erótica
6. Guarde la Tabla con el nombre TEMA. Cargue los datos mediante el Formulario. 7. Utilizando el mismo procedimiento anterior cree las tablas PELÍCULAS y ALQUILER. Tabla PELÍCULAS Código de
Película
Título Intérprete 1 Intérprete 2 Director Productora Código de
tema
Año produc-ción
Dura-ción
1 De Aquí a la eternidad
Burt Lancaster
Montgomery Clif
Fred Zinnemann
Warner Bros
7 1965 130
2 Superman Christopher Reeve
Margot Kidder Richard Donner
Universal 8 1978 137
3 Sed de Mal Charton Heston
Janet Leigh Orson Welles
Universal 9 1965 110
4 J.K.F Kevin Costner Sissi Spacek Oliver Stone Warner Brose
10 1991 189
5 Uno, Dos, Tres
James cagney
Horst Bucholz Billy Wilder United Artist 5 1960 95
6 El Mago de Oz
Judy Garland Frank Morgan Victor Fleming
Universal 6 1939 94
7 Un Horizonte Lejano
Tom Cruise Nicole Kidman
Ron Howard
Paramount Pictures
7 1992 134
9 Misión Explosiva
Tom Berenger
Erika Eleniak Dennis Hopper
Paramount Pictures
5 1993 97
10 El Color Púrpura
Danny Glover Whoopi Goldberg
Steven Spielberg
Warner Bros
8 1985 148
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 17
Tabla ALQUILER:
Código de Alquiler
Código de Socio
Código de película
Fecha de Alquiler
Fecha de devolución
Devuelto
1101 10000 4 10/02/13 12/02/13 Sí 1102 10009 1 20/02/13 22/02/13 Sí
1103 10011 5 05/02/13 08/02/13 Sí 1107 10002 9 30/01/13 04/02/13 Sí
1112 10005 10 24/02/13 26/02/13 Sí 1117 10000 2 06/02/13 10/02/13 Sí
1118 10013 7 01/02/13 03/02/13 Sí 1122 10008 7 26/02/13 28/02/13 Sí 1124 10008 1 27/02/13 01/03/13 No
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 18
Trabajo Práctico Nº 6 1. Realice la siguiente consulta: � CONSULTA1 (tabla PELÍCULAS)
a) Abra la base de datos VIDEO. b) Seleccione la pestaña Consultas. c) Haga Clic en el botón Nuevo. d) Elija la opción Vista Diseño. e) La primera opción que aparece nos pregunta que tabla vamos a utilizar en la Consulta,
en este caso seleccione PELÍCULAS y pulse el botón agregar. f) Pulse el botón Cerrar para indicarle a Access que la consulta sólo se compone de una
tabla. g) En la parte Inferior de la ventana, en el registro Campo, elija en la primera columna,
Código de Película, en la segunda, Título, en la tercera, Director y en la cuarta, Productora.
h) En el registro Criterios, ubíquese en la columna Productora y tipee Universal. i) En el registro Mostrar, verifique que todos los casilleros estén tildados j) Guarde la consulta con el nombre de CONSULTA1. Ciérrela. k) Para visualizar el resultado de la Consulta, presione sobre el botón Abrir. Cierre
nuevamente la Consulta 2. Realice las siguientes consultas, tenga en cuenta los Criterios a utilizar, de acuerdo a los
resultados que se muestran a continuación. � CONSULTA2 (tabla SOCIOS). RESULTADO:
Código Nombre Apellido Domicilio
Teléfono
10003 Laura Suarez 9 de Julio 567 2º A 4986543 10004 Santiago Sánchez Mendoza 34 4º B 03543-4879892 Guarde la consulta como CONSULTA2 � CONSULTA3 (tabla ALQUILER , PELÍCULAS y SOCIOS). RESULTADO: Código de Socio
Apellido Socio
Nombre Socio
Código de película
Título Devuelto
10008 Castillo Daniela 7 Un Horizonte Lejano
Sí
10008 Castillo Daniela 1 De Aquí a la eternidad
No
Guarde la consulta como CONSULTA3.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 19
UNIDAD II: Estructura de Datos
Estructura de Datos
Los datos pueden organizarse de muchas formas diferentes; el modelo matemático o
lógico de una organización particular de datos recibe el nombre de estructura de datos. La
elección de un modelo de datos en particular, depende de dos cuestiones. Primero, debe ser lo
suficientemente complejo para mostrarnos la relación entre los datos y lo que representan y
por el contrario, la estructura debe ser lo suficientemente simple para que los datos puedan
ser procesados de forma eficiente cuando sea preciso.
Dentro de las estructuras de datos posibles encontramos:
Arrays
La estructura de datos más simple es el array lineal (o unidimensional). Un array
lineal es una lista de un número finito de datos simples, referenciados por medio de un
conjunto de n números consecutivos, normalmente 1, 2, 3,...., n. Si designamos el array con la
letra A, los elementos de A los denotamos por medio de la notación subindicada
a1, a2, a3,....., an
o a través de notación parentizada
A(1), A(2), A(3),....., A(n)
o por corchetes
A[1], A[2], A[3],....., A[n]
donde el número n en A[n] recibe el nombre de índice y A[n] el de variable subindicada.
Comentario: las notaciones parentizadas o con corchetes son las que se utilizan para
computadoras ya que los lenguajes de programación no suelen permitir letras minúsculas con
subíndices.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 20
Array Lineal. Ejemplo:
El array lineal ESTUDIANTES consta de los nombres de siete estudiantes (Figura 1).
Aquí ESTUDIANTE 1 representa a Juan Arnau, ESTUDIANTE 2 a Federico Bodo, y así
sucesivamente.
ESTUDIANTE 1 Juan Arnau 2 Federico Bodo 3 Gastón Gutiérrez 4 Cecilia Luna 5 Gabriela Pignata 6 José Silva 7 Ricardo Villegas
Figura 1 Los arrays lineales reciben el nombre de arrays unidimensionales debido a que cada
elemento del mismo se referencia a través de un solo índice. Un array bidimensional es una
colección de datos pertenecientes a una misma entidad, donde cada elemento se referencia
por dos índices (tales arrays reciben el nombre de matrices en matemáticas y de tablas en
aplicaciones comerciales). De forma análoga se definen los arrays multidimensionales.
Array Bidimensional. Ejemplo:
Una cadena de 7 Sucursales, compuestas por 3 Depósitos cada una, puede
representar sus ventas mensuales, como se muestra en la Figura 2. Estos datos pueden
almacenarse en una computadora, utilizando un array bidimensional en el que el primer índice
representa una Sucursal y el segundo un Depósito. Si elegimos VENTAS como nombre para el
array , tendremos que:
VENTAS[1, 1] = 111500 VENTAS[1, 2] = 113200 VENTAS[1, 3] = 110700 . . . . VENTAS[7, 3] = 117632
Decimos que el tamaño del array es de 7 x 3, puesto que contiene 7 filas
(horizontales) y 3 columnas (verticales).
Depósito Sucursal
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 21
Depósito Sucursal
1
2
3
1 111500 113200 110700 2 125750 121754 132230 3 117170 118340 115730 4 18970 112760 17760 5 127547 125876 113765 6 131131 127541 120787 7 114287 116784 117632
Figura 2
Listas enlazadas
Nos introduciremos en el tema mediante un ejemplo. Supongamos que un
concesionario de automóviles mantiene un archivo donde cada registro contiene el nombre de
un Cliente y su correspondiente Vendedor, como se muestra a continuación:
Cliente Vendedor 1 Antonietti Lozada 2 Brizuela Venturi 3 Carreño Palacios 4 Dávila Lozada 5 Fernández Venturi 6 Martínez Lozada 7 Pedrotti Palacios 8 Sánchez Venturi 9 Vilches Lozada
Figura 3 Claramente este archivo puede ser almacenado en la computadora por medio de una
tabla compuesta por dos columnas con nueve nombres cada una. Sin embargo esta puede no ser
la forma más útil de almacenar los datos (Figura 3).
Otra forma de almacenar los datos es mediante dos arrays separados. En uno se
podrían almacenar los nombres de los clientes, junto con una entrada llamada puntero que nos
indicaría la localización del Vendedor correspondiente, y estos estarían almacenados en el
segundo array. La estructura descripta se muestra en la Figura 4, donde algunos punteros son
representados por una flecha que tiene su origen en el campo puntero del primer array y el
destino en el Vendedor asociado. En la práctica, el uso de un entero como puntero utiliza menos
espacio que un nombre, por lo tanto esta representación economiza espacio, sobre todo si cada
Vendedor tiene cientos de Clientes.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 22
Cliente Puntero Vendedor 1 Antonietti 1 Lozada 1 2 Brizuela 3 Palacios 2 3 Carreño 2 Venturi 3 4 Dávila 1 5 Fernández 3 6 Martínez 1 7 Pedrotti 2 8 Sánchez 3 9 Vilches 1
Figura 4
Supongamos que la Gerencia de Comercialización necesita una lista de Clientes de un
Vendedor determinado. Usando la representación de datos de la Figura 4, habrá que buscar en
toda la lista de Clientes. Una forma de simplificar la búsqueda es utilizar los punteros de otra
forma; cada Vendedor puede tener un conjunto de punteros que dan la posición de sus Clientes,
como se muestra en la Figura 5. La principal desventaja de esta representación es que cada
Vendedor puede tener muchos punteros y que el conjunto de estos cambiará cuando
agreguemos o eliminemos Clientes.
Vendedor Puntero 1 Lozada 1, 4, 6, 9 2 Palacios 3, 7 3 Venturi 2, 5, 8
Figura 5
Otra forma de almacenar los datos de la Figura 3, se muestra a continuación (Figura
6). Aquí cada Vendedor posee un puntero que apunta a su primer Cliente. En la lista Cliente el
campo enlace apunta al siguiente Cliente del mismo Vendedor, indicando el último Cliente
asociado con un 0. Esto queda reflejado en la Figura 6, para el Vendedor Lozada. Usando esta
representación es más fácil obtener la lista de Clientes para un Vendedor determinado, e
insertar y eliminar Clientes.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 23
Cliente Enlace Vendedor Puntero 1 Antonietti 4 Lozada 1 1 2 Brizuela 5 Palacios 3 2 3 Carreño 7 Venturi 2 3 4 Dávila 6 5 Fernández 8 6 Martínez 9 7 Pedrotti 0 8 Sánchez 0 9 Vilches 0
Figura 6
Las formas anteriores de representación son ejemplos de Listas enlazadas. Aunque
los términos puntero y enlace son usados indistintamente, trataremos de utilizar el término
puntero cuando un elemento de una lista apunta a otro de una lista distinta y el término enlace
cuando lo hace hacia otro, pero de la misma lista.
Árboles
Los datos presentan frecuentemente relaciones de jerarquía entre ellos. Las
estructuras de datos que refleja esta relación recibe el nombre de grafo en árbol o
simplemente árbol. Indicaremos a continuación algunas de sus propiedades básicas mediante
dos ejemplos.
Ejemplo de Estructura de Registro
Mientras que un archivo puede representarse mediante uno o más arrays, un registro
que contiene grupos de elementos o elementos simples, puede describirse mejor mediante una
estructura de árbol.
Un registro perteneciente a la entidad Empleado, puede contener los siguientes
atributos ó campos:
Legajo, Nombre, Dirección, Edad, Sueldo, Subordinados
Sin embargo, Nombre puede ser un grupo de elementos compuesto por Apellido y
Nombre de pila. También Dirección puede estar conformada por los ítems Calle, Número, Zona
donde a su vez ésta última puede estar compuesta por los subítems Barrio, Localidad,
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 24
Provincia, Código Postal. Esta estructura jerárquica se muestra en la Figura 7a. Otra forma de
representar la estructura de árbol es mediante niveles como se muestra en la Figura 7b.
Figura 7a
Figura 7b
Ejemplo de Expresiones Algebraicas
Sea la expresión algebraica:
(2x + y) (a - 7b)3
Usando la flecha vertical (�) para expresar la exponenciación y el asterisco (*) para
la multiplicación, podemos representar esta expresión mediante el árbol de la Figura 8.
Observe que el orden en que deben realizarse las operaciones quedan reflejadas en el
diagrama: la exponenciación debe realizarse después de la resta, y la multiplicación situada en
la cúspide del árbol debe ejecutarse al último.
Empleado
Sueldo Edad Nombre Legajo Subordinados Dirección
Nombre de Pila Apellido Calle Número Zona
01 Empleado
02 Legajo
02 Nombre
03 Apellido
03 Nombre de pila
02 Dirección
03 Calle
03 Número
03 Zona
04 Barrio
04 Localidad
04 Provincia
04 Código Postal
02 Edad
02 Sueldo
02 Subordinados
Barrio Localidad Provincia Código
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 25
*
+ ����
* y - 3
2 x a *
7 b
Figura 8
Pila
Una pila, también denominada sistema último-dentro primero-fuera (LIFO), es una
lista lineal de registros, en la cual las inserciones y extracciones tienen lugar sólo por un
extremo llamado cúspide. Esta estructura es similar en su operación a una pila de platos como
los de la Figura 9. En ella los platos son siempre agregados o retirados por la cúspide de la
misma.
Figura 9
cúspide
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 26
Cola
Una cola, también denominada sistema primero-dentro primero-fuera (FIFO), es una
lista lineal en la cual las extracciones se realizan siempre por un extremo, llamado frente y las
inserciones por el extremo contrario llamado final de la lista. Esta estructura opera de la
misma forma que un grupo de personas esperando el ómnibus, la primera persona en la cola es
la primera en subir al ómnibus.
Grafos
Los datos contienen, en algunos casos, relaciones entre ellos que no son
necesariamente jerárquicas. Por ejemplo supongamos que una empresa aérea realiza vuelos
sólo entre las ciudades conectadas por líneas. La estructura de datos que refleja esta relación
recibe el nombre de grafo.
• Jujuy
• Salta
• Rosario
• Córdoba • Buenos Aires
• Mendoza
Nota:
Se suelen usar muchos nombres al referirse a los elementos de una estructura de
datos, algunos de ellos son: elemento, ítem, registro, nodo y objeto. El nombre que se utiliza
depende del tipo de estructura, del contexto en el que se usa esa estructura y de quién la
utiliza.
Parada
de
ómnibus
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 27
UNIDAD II: TRABAJOS PRÁCTICOS
Objetivo:
Definir la estructura de datos más adecuada (arrays, listas enlazadas, árboles, colas,
pilas, grafos) para el almacenamiento de los datos que se dan a continuación. Resuelva
los Trabajos Prácticos N° 7, 8, 9 y 10.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 28
Trabajo Práctico Nº 7
1. Dados los siguientes datos, que representan CANTIDAD de ALUMNOS por Curso y por Sección, realice mediante la Planilla de Cálculos el almacenamiento de los mismos. Indique la estructura de datos utilizada.
[8, 8] =35 [3, 7] =31 [2, 4] =35 [7, 2] =34 [8, 2] =34 [8, 5] =35 [2, 3] =32 [5, 2] =34
[6, 1] =32 [7, 1] =33 [4, 5] =35 [4, 4] =35 [7, 3] =34 [6, 5] =34 [6, 7] =31 [1, 1] =32
[5, 7] =31 [8, 1] =32 [1, 8] =36 [8, 4] =35 [5, 3] =34 [7, 4] =35 [1, 6] =34 [4, 7] =31
[3, 1] =33 [4, 6] =30 [3, 6] =34 [4, 8] =36 [1, 2] =34 [8, 3] =32 [4, 1] =32 [5, 8] =36
[2, 6] =30 [5, 1] =33 [8, 7] =31 [6, 3] =34 [2, 8] =36 [6, 4] =36 [7, 8] =36 [1, 3] =34
[3, 4] =35 [8, 6] =30 [2, 5] =35 [2, 1] =33 [1, 4] =36 [3, 3] =34 [1, 5] =34 [5, 4] =36
[6, 2] =35 [4, 3] =34 [4, 2] =34 [5, 5] =35 [3, 8] =36 [2, 2] =35 [6, 6] =30 [7, 6] =34
[1, 7] =35 [5, 6] =34 [3, 2] =34 [7, 5] =35 [7, 7] =31 [3, 5] =35 [2, 7] =31 [6, 8] =36
2. Mediante la utilización de funciones, determine:
a) Total de Alumnos por Curso
b) Promedio de Alumnos por Curso.
c) Cantidad mayor de alumnos para cada Curso.
d) Cantidad menor de alumnos para cada Curso.
e) Cantidad Total de Alumnos. 3. Guarde el archivo en su carpeta y disco de trabajo.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 29
Trabajo Práctico Nº 8
1. Dados los siguiente datos, y utilizando la estructura de datos más adecuada para economizar espacio de almacenamiento, proponga todas las formas posibles de almacenar los datos, con la estructura de seleccionada. Utilice para ello la Planilla de Cálculos. Guarde todo lo realizado, en un archivo dentro de su carpeta y disco de trabajo.
Paciente Médico Abregú, Marcelo Gómez Centurión Boccelli, Mario Arévalo Colombres, Francisco Fernández Constanzo, Fabiana Fernández Dionissi, Laura Mantovani Duarte, Aníbal Soria Echegaray, Pedro Gómez Centurión Farías, Claudia Mantovani García, Silvia Gómez Centurión Gómez, Pablo Fernández Huerta, Mariela Arévalo Juárez, Sandra Mantovani Klotz, Eva Gómez Centurión López, Angélica Fernández Llorens, Sandra Soria Mercier, Lorena Mantovani Murta, Rosa Arévalo Ninci, Esteban Gómez Centurión Ortiz, Eduardo Mantovani Otobre, Fernanda Fernández Pascetti, Elena Arévalo Paschini, Soledad Fernández Quiroga, Miriam Soria Ramírez, Osvaldo Arévalo Robledo, Raúl Gómez Centurión Sánchez, Carlos Fernández Soria, David Mantovani Suárez, Jorge Fernández Taborda, Ernesto Arévalo Tobares, Mariza Gómez Centurión Uboldi, Marcos Arévalo Vivas, Horacio Mantovani Winkel, Marcela Gómez Centurión
2. Agregue una columna para numerar los registros, denomínela Nº de Paciente, complétela mediante el procedimiento de rellenar automáticamente, incrementando el contenido de la celda.
3. Mediante el procedimiento de Filtro Avanzado, genere una tabla para cada Médico, con los
pacientes que cada uno de ellos atiende. 4. Indique a que tipo de estructura se asemeja, lo realizado en el paso anterior.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 30
Trabajo Práctico Nº 9 1. Dada la siguiente estructura de datos: 01 Empleado
02 Nombre del Empleado 03 Nombre 03 Apellido 02 Sueldo 03 Sueldo Básico 03 Sueldo Bruto 02 Sindicato 03 Afiliado 03 Aporte 2. Los datos que debería almacenar en la misma, son:
GARCIA, LAURA, 11350, 11645, Sí, 1% ALVAREZ, LUIS, 11550, 11780, No, 0% BARROS, ARMANDO, 11670, 11875, Sí, 1% SANCHEZ, ISMAEL, 12100, 12650, Sí, 1% CACERES, EFRAIN, 11870, 12130, No, 0% CORNEJO, DANIEL, 11935, 12298, No, 0% DIAZ, ALDO, 11645, 11878, Sí, 1% FARIAS, JUAN, 11780, 12120, Sí, 1% BUSTOS, ENRIQUE, 11458, 11623, Sí, 1% GASPO, GENOVEVA, 11618, 11895, Sí, 1% LUNA, CECILIA, 11950, 12250, Sí, 1% ALONSO, JAVIER, 12250, 12743, Sí, 1% PARDO, CRISTINA, 11590, 11780, No, 0% RODRIGUEZ, GABRIEL, 11450, 11660, No, 0% MORENO, LUIS, 11359, 11487, No, 0%
3. Mediante la Planilla de Cálculos, realice el almacenamiento de los datos y guárdelo en su
carpeta y disco de trabajo. Para determinar el Aporte del empleado al Sindicato, resuélvalo mediante el uso de Funciones, si el Empleado es Afiliado al Sindicato, deberá calcular el 1% sobre el Sueldo Básico, caso contrario, no realizará Aporte (0%).
4. Indique el tipo de estructura utilizado.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 31
Trabajo Práctico Nº 10
Bs. As. Córdoba Sta. Fe Entre Ríos La Pampa
Pop 540750
Rock 178000
Clásica 50000
Folclore 89000
Tango 250750
Jazz 98700
Melódica 219570
Totales:
1. Con los datos anteriores, almacenados mediante la Planilla de Cálculos, obtenga la Cantidad
de Discos Vendidos por Estilo musical en cada Provincia, teniendo en cuenta lo siguiente:
En Córdoba se vendió un 30% menos que en Bs. As. En Sta. Fe se vendió un 37.5% menos que en Bs. As. En Entre Ríos se vendió un 45% menos que en Bs. As. En La Pampa se vendió un 10% más que en Entre Ríos.
2. Mediante funciones calcule Totales para cada Provincia. 3. Indique la estructura de datos utilizados. 4. Señale los valores que le corresponden a los siguientes índices:
Cantidad de Discos Vendidos[7, 1] Cantidad de Discos Vendidos[3, 5] Cantidad de Discos Vendidos[1, 4] Cantidad de Discos Vendidos[5, 5] Cantidad de Discos Vendidos[7, 5] Cantidad de Discos Vendidos[2, 4] Cantidad de Discos Vendidos[6, 2] Cantidad de Discos Vendidos[4, 1] Cantidad de Discos Vendidos[4, 5] Cantidad de Discos Vendidos[1, 1]
Provincia
Estilo
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 32
UNIDAD III: Operaciones con Estructura de Datos
Operaciones con Estructura de Datos
Los datos que contiene una estructura se procesan por medio de determinadas
operaciones. De hecho, generalmente elegimos una determinada estructura de datos, en
función de las operaciones que realizamos sobre ella.
Las que se describen a continuación son las que se utilizan con mayor frecuencia:
Recorrido: implica acceder a cada registro una única vez aunque uno o más ítems
del registro sean procesados. Este acceso y procesamiento también se denomina a
veces con el término "visitar el registro".
Búsqueda: implica la localización de un registro caracterizado por una determinada
clave o también el acceso a los registros que cumplen una o más condiciones.
Inserción: implica añadir nuevos registros a la estructura de datos.
Eliminación: esta operación implica borrar un registro de la estructura de datos.
Modificación: esta operación implica un cambio o actualización de los datos
contenidos en un registro.
Ordenamiento: esta operación implica clasificar los registros conforme a un orden
lógico determinado.
Mezcla: esta operación implica combinar dos archivos previamente ordenados en
uno único que también lo está.
Con frecuencia dos o más de estas operaciones se usan conjuntamente, por ejemplo,
cuando queremos eliminar un registro con una clave determinada, primero debemos buscarlo
para luego recién eliminarlo.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 33
UNIDAD III: TRABAJOS PRÁCTICOS
Objetivo:
Analizar el comportamiento de las estructura de datos (arrays, listas enlazadas,
árboles, colas, pilas, grafos) ante las operaciones de inserción, modificación,
eliminación, ordenamiento, búsqueda, mezcla o recorrido. Resuelva los Trabajos
Prácticos 11, 12, 13 y 14.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 34
Trabajo Práctico Nº11
Objetivo:
Realizar recorrido, búsqueda, inserción, eliminación, modificación, ordenamiento y
mezcla de los datos, contenidos en diferentes estructuras de datos.
Utilizaremos el Sistema de Gestión de Base de Datos Video.
1. Recorrido:
a) Para realizar un recorrido por los datos contenidos en cada una de las tablas, prepare un
informe para Socios, Tema, Películas y Alquiler. Coloque en cada uno de ellos como
Encabezado: Video: Tabla de xxxxxxx, donde xxxxxxx será el nombre de la tabla
respectiva, y como pie de página la fecha actual y el nº de página.
2. Búsqueda:
a) Mediante Consulta, localice en la Tabla Socios, todos aquellos que tengan Código Postal 5001
ó 5009.
b) En la Tabla Películas y mediante Consulta, encuentre las películas de la productora
Universal, realizadas entre 1960 y 1980.
c) En la Tabla Alquiler utilizando Consulta, muestre cuantas veces fue alquilada la película De
aquí a la eternidad, durante el 1/2/13 y el 20/2/13.
3. Inserción:
a) Agregue a la Tabla Socios, Películas y Alquiler, los siguientes registros:
Código Socio
Nombre Apellido DNI Domicilio Ciudad Código Postal
Teléfono Observaciones
10020 Mateo Pedreira 28.097.187 Perú 234 Córdoba 5001 4681254 Alquila por 5 días
10021 Diego Pérez 31.950.564 Jujuy 1435 Córdoba 5003 4738853
10022 Olga Sánchez 6.254.871 Urquiza 331 Córdoba 5000 4221458
10023 Ariadna Murcia 27.351.241 Murcia 814 Córdoba 5012 4551778 10024 Marcelo Romero 20.354.167 Garzón 191 Córdoba 5011 4519547
Código de
Película
Título Intérprete 1 Intérprete 2 Director Productora Código de tema
Año producción
Duración
8 Cinema Paradiso
Philippe Noiret
Jacques Perrin
Giuseppe Tornatore
Franco Cristaldi
7 1988 123
11 Superman II Christopher Reeve
Margot Kidder Richard Donner
Universal 8 1980 137
12 La Misión Robert de Niro Jeremy Irons Roland Joffe
Goldcrest 7 1986 120
13 El lado oscuro del corazón
Darío Grandinetti
Sandra Ballesteros
Eliseo Subiela
Fernado Socolowickz
7 1992 110
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 35
Código de Alquiler Código de Socio Código de película Fecha de Alquiler Fecha de devolución Devuelto 1125 10022 8 17/03/13 19/03/13 Sí
1126 10024 12 21/03/13 23/03/13 No
1127 10013 8 05/04/13 08/04/13 Sí
1129 10021 12 30/04/13 02/05/13 Sí 1130 10020 1 02/05/13 04/05/13 Sí
4. Eliminación:
a) En la tabla Socios, ubique los siguientes y elimínelos: 10001, 10003, 10006, 10012 y 10015.
5. Modificación:
a) En la tabla Socios y mediante la opción Reemplazar que se encuentra en el menú Edición,
modifique los siguientes datos:
Código Socio
Nombre Apellido DNI Domicilio Ciudad Código Postal
Teléfono Observaciones
10000 Colón 1234 5000 4267898 10008 Pagó abono para
todo el año 2013.
10020 Pereyra 10022 4.254.871
10023 Mircó
6. Ordenamiento:
a) En la tabla Socios, realice un ordenamiento ascendente por el campo Apellido.
b) En la tabla Tema, realice un ordenamiento ascendente por el campo Tema.
c) En la tabla Películas, realice un ordenamiento ascendente por el campo Año producción.
d) En la tabla Alquiler, realice un ordenamiento descendente por el campo Código de Alquiler.
7. Mezcla:
a) Genere en Excel la siguiente tabla, guárdela en su carpeta y disco de trabajo con el nombre
Socios.
Código Socio
Nombre Apellido DNI Domicilio Ciudad Código Postal
Teléfono Observaciones
10025 Alejandro Fonseca 14.898.342 Petorutti 21 Córdoba 5009 4811254 Paga con Tarjeta
10026 Lucía Ibañez 17.958.564 Cornejo 349 Córdoba 5009 4818851
10027 Hugo Loza 4.299.831 Urquiza 931 Córdoba 5000 4251957 Abonado 10028 Guillermo Murcia 14.360.181 Galeano 79 Córdoba 5009 4811787 Abonado 10029 Mónica Arceloni 28.150.314 Gorriti 1917 Córdoba 5011 4569547
b) Desde Access, cerciórese que la base de datos Video esté abierta, seleccione la tabla
Socios (no la abra).
c) Desde la barra de menú seleccione Archivo, en ella la opción Obtener datos externos y
luego Importar.
d) En la ventana Importar ingrese los siguiente datos: en Buscar en: seleccione su disco y
carpeta de trabajo, en Tipo de archivo: seleccione Microsoft Excel (*.xls), en Nombre de
archivo: tipee Socios, presione luego en el botón Importar.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 36
e) Aparecerá la ventana del Asistente para importación de hojas de cálculo, en ella se
presentará seleccionada la opción Mostrar hoja de cálculos (Socios), presione entonces el
botón Siguiente.
f) En la ventana siguiente sólo deberá seleccionar en la casilla de verificación Primera fila
contiene títulos de columnas, presione luego sobre el botón Siguiente.
g) En esta ventana deberá elegir la opción En una tabla existente y allí seleccionar la tabla
Socios, presione el botón Siguiente.
h) En la última ventana aparecerá seleccionada la tabla Socios, presione el botón Terminar.
i) Una vez finalizada la importación de los datos, aparecerá un cuadro de diálogo indicándolo,
presione en el botón Aceptar. Ahora puede abrir la tabla Socios y corroborar la operación
de Mezcla realizada.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 37
Trabajo Práctico Nº12
Objetivo:
Analizar el comportamiento de los datos en una pila, ante las operaciones de inserción
y eliminación.
1. Dada la siguiente información, utilice para el almacenamiento de la misma la estructura de
datos denominada pila. Realice esta actividad mediante Access, llame la base de datos
como EMPRESA y la tabla como PERSONAL.
2. Utilice un formulario para la carga de los datos.
LegajoApellidoNombre D.N.I. Dirección Teléfono Fecha Ingreso
Tiene Hijos?
Sueldo Básico
Antecedentes Laborales
1190 Asis Ana 27.158.195 Fragueiro 1219 422-1118 01/02/99 Sí $ 11.850 Trabajó en empresas de telefonía y correo.
1105 Barzola Lorenzo 18.186.125 Tejeda 1876 481-6212 10/11/05 No $12.200 Trabajó en empresa autopartista.
1118 Córdoba Sergio 11.947.521 La Pampa 89 425-1247 08/09/02 Sí $11.630 Trabajo en medios de comunicación.
1182 Córdoba Claudia 28.189.125 Reyna 765 462-1587 01/01/00 No $11.875 Trabajó en instituciones bancarias.
1196 Espada Mónica 19.157.117 Valladolid 435 455-1247 10/02/04 Sí $ 11.945 Trabajó en empresa de servicios
1119 Filguera Josefina 21.128.147 Betania 874 489-4712 15/05/03 No $ 12.100 1157 García Manuel 23.524.116 Galeano 234 01/03/02 Sí $ 11.750 Trabajó en industria
electrónica. 1113 Huergo Manuel 28.341.774 9 de Julio 987 425-8791 01/08/00 Sí $ 11.580 1125 Juárez Sandra 24.258.241 Junín 234 421-1145 14/05/05 Sí $ 11.725 1171 León Horacio 17.181.145 Artigas 131 423-4112 30/11/04 No $ 11.670 Trabajó en empresa
autopartista. 1110 Luna Nicolás 27.541.377 Richieri 1987 465-4157 01/10/01 No $12.250 Trabajo en medios de
comunicación. 1131 Montes Carmen 29.166.165 Mendoza 1432 471-5874 15/07/02 Sí $ 11.770 Trabajó en instituciones
educativas. 1155 Nieto Federico 17.151.191 Mercedarios 91 464-1177 10/06/05 Sí $ 11.675 Trabajó en empresas
gastronómicas. 1188 Piñeiro Laura 26.317.119 Tablada 914 428-1290 01/11/99 Sí $ 11.725 1103 Roldán Manuel 16.125.135 Pinzón 327 15/04/07 No $ 11.875 Trabajó en empresa de
servicios 1168 Sánchez Gabriela 18.168.165 Lafinur 1587 481-5557 01/02/06 No $11.675 Trabajó en instituciones
financieras. 1173 Taborda Silvina 25.654.251 Corro 314 422-3331 02/08/02 Sí $ 11.580 1116 Teruel Santiago 15.115.122 Tosno 2319 469-2547 01/01/00 Sí $ 11.850 Trabajó en empresa
autopartista. 1183 Uria Diego 10.191.541 Baigorrí 775 473-1254 01/09/05 No $ 11.875 Trabajó en empresa de
servicios 1121 Vivas Walter 27.125.125 Urquiza 2518 01/02/00 Sí $ 11.945 Trabajó en empresas
gastronómicas.
3. Analice y resuelva la siguiente situación: "como consecuencia de la recesión económica la
empresa debe reducir el 50% de su personal". ¿Cuáles serán los empleados que deberá
despedir, considerando la estructura de datos empleada?
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 38
4. Analice como es el comportamiento de la operación de inserción de registros en una
estructura de pila.
5. Antes de eliminar los registros de la tabla PERSONAL genere otra de características
similares a la anterior, denomínela PERSONAL DESPEDIDO. Una vez eliminados los
registros de la primera almacénelos en esta última. Utilice para ello las herramientas
Copiar, Pegar (solamente estructura) y Pegar datos anexados.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 39
Trabajo Práctico Nº13
Objetivo:
Analizar el comportamiento de los datos en una lista enlazada, ante las operaciones
de ordenamiento, inserción y eliminación.
1. Dada la siguiente información, utilice para el almacenamiento de la misma la estructura de
datos denominada lista enlazada. Realice esta actividad mediante Excel, llame al archivo
PAISES.
Continente País
Europa Suecia
América Argentina
Asia India
África Argelia
Europa España
Australia y Oceanía
Australia
África Nigeria
América Cuba
Asia Mongolia
Australia y Oceanía
Nueva Zelanda
Europa Austria
Europa Italia
Europa Bélgica
África Marruecos
América Colombia
América Brasil
Asia Irán
África Sudáfrica
Asia Irak
África Egipto
Asia Afganistán
Asia China
Europa Portugal
América Venezuela
América Canadá
2. Una vez almacenada la información en la lista enlazada, realice un ordenamiento alfabético
de la misma utilizando como clave de ordenamiento el campo países. Analice el
comportamiento de los datos enlazados ante la operación realizada.
3. Elimine de la lista enlazada, los registros que corresponden a los siguientes países:
Mongolia, Nueva Zelanda, Austria, Colombia y Egipto. Analice el comportamiento de los
datos enlazados ante esta operación.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 40
4. Inserte en la lista enlazada los siguientes registros, cuide mantener el ordenamiento
anterior. Analice el comportamiento de los datos restantes de la lista al efectuar esta
operación.
Continente País
Asia Pakistán
Australia y Oceanía
Papua Nueva Guinea
Europa Francia
América Bolivia
África Mozambique
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 41
Trabajo Práctico Nº14
Objetivo:
Analizar el comportamiento de los datos en una cola, ante las operaciones de inserción
y eliminación.
1. Utilice para el almacenamiento de la siguiente información, la estructura de datos
denominada cola. Hágalo mediante Access, cree la base de datos CONSULTORIO y dentro
de ella la tabla TURNO PACIENTES.
2. Mediante formulario realice la carga de los datos.
Nº de Turno
Nº Historia Clínica
Apellido y Nombre
D.N.I. Edad Teléfono Tiene Mutual?
Nombre de la Mutual
Motivo de la consulta
10 1521 ARDILES, Sara 4.998.775 65 472-3318 Sí PAMI Dolor de cabeza y mareos.
2 1570 BORIOLI, Luis 18.186.125 31 489-9612 No Estado febril. 7 1573 CAMARA, Delia 7.998.775 52 425-1247 Sí DASPU Decaimiento,
fatiga y mareos. 14 1501 DAVILA, Hernán 3.189.228 72 482-1587 Sí PAMI Congestión nasal
y fiebre. 11 1597 EREÑU, Mónica 19.157.117 28 455-1214 Sí DASPU Dolor de
garganta y fiebre
9 1591 FANTINI, José 21.128.147 25 469-4712 No Decaimiento y fiebre.
1 1547 FERRARI, Manuel 23.524.116 26 Sí APROSS Estado gripal. 3 1553 HUERTA, Miguel 6.341.777 425-8791 No Dolor de oídos y
fiebre. 6 1525 JALIL, Marta 14.258.241 39 489-1145 Sí OSECAC Chequeo general. 18 1517 LERDA, Rodolfo 17.181.145 33 425-6512 Sí APROSS Dolor lumbar. 15 1560 LIPARI, Ariel 11.541.377 45 465-1547 No Decaimiento,
dolor de garganta, fiebre.
13 1531 MONTT, Gloria 10.116.165 47 481-5174 Sí IOSEP Decaimiento y mareos.
5 1585 MUNS, Jorge 17.151.191 464-7711 Sí OSECAC Estado gripal. 12 1548 PANERO, Raúl 16.173. 911 482-9120 Sí OSPLAD Dolor de cabeza
y náuseas. 8 1568 ROSEN, Silvia 6.125.135 56 No Chequeo médico. 17 1508 SANTIAGO,
Claudia 13.168.165 40 489-4457 Sí DASPU Estado febril.
4 1519 TEJAS, Samuel 8.654.251 51 425-1333 Sí OSECAC Fiebre y dolor de garganta.
16 1546 UBALDO, Teresa 5. 511.122 60 473-5247 Sí APROSS Dolor de oídos, garganta y fiebre.
3. Todos los pacientes anotados asistieron a la consulta. Hasta el momento el médico lleva
atendido 8 pacientes, ¿cuáles serán los registros que deberán ser dados de baja de
acuerdo a la estructura de datos utilizada?
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 42
4. Antes de eliminar los registros de la tabla TURNO PACIENTES genere otra de
características similares a la anterior, denomínela PACIENTES ATENDIDOS. Una vez
eliminados los registros de la primera almacénelos en esta última. Utilice para ello las
herramientas Copiar, Pegar (solamente estructura) y Pegar datos anexados. Exporte la
tabla PACIENTES ATENDIDOS a la Planilla de Cálculos Excel con el mismo nombre.
5. Analice como es el comportamiento de la operación de inserción de registros en una
estructura de cola.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 43
UNIDAD IV: Algoritmos Algoritmos. Complejidad y Relación espacio-tiempo.
Un algoritmo es una secuencia de operaciones o pasos perfectamente definidos que
conducen a la resolución de un problema. Desarrollar algoritmos que manipulen eficientemente
los datos será uno de nuestros objetivos. El tiempo y el espacio utilizado en ello miden la mayor
o menor eficiencia de un algoritmo. La complejidad de un algoritmo es aquella función que da el
tiempo y/o el espacio utilizado por el algoritmo en función de los datos de entrada.
Cada algoritmo guarda una estrecha relación con una estructura de datos. Por ello, no
siempre es posible utilizar el algoritmo más eficiente, puesto que la elección de la estructura
de datos depende de varias cuestiones, incluida la de qué tipo de datos administramos y la
frecuencia con que se realizan diferentes operaciones sobre ellos. Así deberemos encontrar
una situación de compromiso entre tiempo y espacio utilizados. En general, si aumentamos el
espacio necesario para almacenar los datos, conseguiremos un mejor rendimiento en el tiempo y
viceversa. Estas ideas quedan reflejadas en los siguientes ejemplos.
Algoritmos de búsqueda
Supongamos tener un archivo que contiene, entre otros datos, el nombre y el número
de teléfono de sus miembros y que dado el nombre de un miembro queremos conocer su número
telefónico. Una forma de hacer esto es buscarlo secuencialmente en el archivo, es decir
aplicando el siguiente algoritmo:
Búsqueda secuencial: Recorre cada registro del archivo, uno a uno, hasta
encontrar el nombre buscado y a partir de él el correspondiente número de teléfono.
Es evidente que el tiempo necesario para ejecutar el algoritmo es proporcional al
número de comparaciones realizadas. También suponiendo que todos los nombres del
archivo tienen la misma probabilidad de ser encontrados o no, en un determinado
momento, es claro que el promedio de comparaciones que realizaremos para esta
búsqueda es n/2, donde n es el número de registros del archivo. Es decir la
complejidad de la búsqueda secuencial viene dada por C(n)=n/2.
Este algoritmo puede resultar inviable en la práctica si la lista consta de miles de
nombres como en una guía telefónica. Sin embargo si los nombres están ordenados
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 44
alfabéticamente podremos utilizar un algoritmo más eficiente, denominado de
búsqueda binaria.
Búsqueda binaria: Comparar el nombre buscado con el que se encuentra en mitad
de la lista. Con ello dividimos la lista en dos partes y determinamos en cual de las dos
se encuentra el nombre buscado. Nuevamente repetimos el mismo proceso en la parte
seleccionada hasta que encontramos el nombre deseado, o no.
Se puede expresar que la complejidad del algoritmo de búsqueda binaria viene dada
por C(n)=log2n
De esta forma no se necesitan más que 15 comparaciones para encontrar un nombre
de una lista que contiene 25.000 nombres.
Aunque el algoritmo de búsqueda binaria es muy eficiente, presenta algunos
inconvenientes. Concretamente el algoritmo implica la posibilidad de acceder
directamente al elemento mitad de una lista. Por tanto la lista debe ser almacenada
en algún tipo de array. Desgraciadamente para este tipo de estructura, la inserción
de un elemento en ella implica el movimiento de un gran número de datos, al igual que
ocurre cuando deseamos borrar o extraer algún dato del array.
La compañía telefónica soluciona este problema editando una nueva guía cada año y
manteniendo un archivo temporal para los clientes que se dan de alta durante ese
período. Esto quiere decir que la compañía de teléfonos actualiza casi
instantáneamente su lista de clientes. En este caso una lista secuencial puede no ser
la estructura más adecuada.
Ejemplo de la relación espacio-tiempo
Supongamos que un archivo contiene en sus registros nombres, números de documento
y más información adicional. Ordenar el archivo alfabéticamente y utilizar la búsqueda binaria
es un buen método si lo que deseamos es encontrar un registro que contiene un determinado
nombre. Por el contrario, supongamos que lo que conocemos es el número de documento. En
este caso debemos realizar una búsqueda secuencial en todo el archivo, lo que implica gran
cantidad de tiempo cuando el archivo es largo. ¿Cómo resolver este problema? Una forma es
tener otro archivo igual, pero ordenado por número de documento. Esta solución duplica el
espacio necesario para el almacenamiento de datos. Otra solución representada en la Figura 10
es la de tener el archivo principal ordenado de acuerdo al número de documento y
adicionalmente un array auxiliar con dos columnas, la primera de ellas conteniendo la lista
alfabética de los nombres y la segunda punteros que indiquen la dirección de los registros
correspondiente en el archivo principal. Esta forma de resolver el problema es una de las más
utilizadas, puesto que el espacio adicional necesario es mínimo frente a la información extra
que proporciona.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 45
Nombre Puntero Documento Nombre Datos adicionales 1 Avalos, Mara 3 1 17.158.125 Marín, Claudia xxxxxxxxxxxxxxx 2 Brunelli, Oscar 71 2 18.339.451 Cordi, Silvia xxxxxxxxxxxxxxx 3 Cordi, Silvia 2 3 21.125.144 Avalos, Mara xxxxxxxxxxxxxxx 4 Cuevas, Delia 29 4 22.154.147 Tulián, José xxxxxxxxxxxxxxx 5 Dávila, Ana 57 5 24.254.717 Soro, Carlos xxxxxxxxxxxxxxx 6 Lobos, Isabel 7 6 28.119.154 Brandán, Luis xxxxxxxxxxxxxxx 7 Luna, Nicolás 17 7 29.178.112 Lobos, Isabel xxxxxxxxxxxxxxx
Figura 10
Lo mostrado en la figura anterior es similar al procedimiento de indexar un campo,
crea un índice para ese campo indicando en que registro se encuentra el dato buscado.
Comentario: Supongamos que un archivo está ordenado de acuerdo al número de
Documento. Cuando añadimos nuevos registros los datos deben cambiar de posición para
mantener el orden. Una forma sencilla de minimizar el número de movimientos es utilizar el
número de Documento como dirección del registro. Con esto no sólo es innecesario el
movimiento de registros cuando insertamos uno nuevo, sino que además el acceso a los mismos
es instantáneo. La desventaja de este método de almacenamiento es que necesita de un gran
número de posiciones de memoria para pocos cientos o a lo sumo unos pocos miles de registros.
Claramente la relación espacio-tiempo obtenida no es muy ventajosa.
Diseño de algoritmos
Algunos algoritmos pueden ser muy complejos. Sin embargo, los programas que
implementan los algoritmos más complejos pueden ser diseñados fácilmente, si organizamos los
mismos en una estructura de módulos jerárquica, como la que se muestra en la Figura 11. En la
organización descripta, cada programa contiene un módulo principal que representa una
descripción general del algoritmo. Este módulo principal contiene llamadas a submódulos que
contienen información más detallada que el principal. Cada submódulo puede hacer referencia a
su vez a más submódulos, así sucesivamente. La organización de un programa en una estructura
jerárquica de este tipo requiere el uso de ciertos criterios de flujo y de estructuras lógicas
asociadas con el concepto de programación estructurada.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 46
Figura 11
Notación algorítmica
El formato para representar formalmente un algoritmo se compone de dos partes. La
primera consiste en una descripción de los propósitos del algoritmo, la descripción de las
variables que intervienen en el mismo y de los valores de entrada de éstas. La segunda parte
consiste en la secuencia de pasos que deben ser ejecutados para la consecución del resultado.
Sea el array DATOS compuesto por valores numéricos y contenido en la memoria de la
computadora. Deseamos encontrar la posición de memoria LUG y el valor del elemento mayor
de DATOS. Sin conocer otra información, una forma de resolver el problema es la siguiente:
Inicialmente comenzamos con LUG=1 y MAX=DATOS[1], a continuación comparamos MAX
con los elementos siguientes de DATOS, representados por DATOS[K]. Si DATOS[K] es
mayor que MAX, actualizaremos LUG y MAX de tal forma que ahora serán LUG=K y
MAX=DATOS[K]. Los valores buscados se encontrarán en LUG y MAX al final del algoritmo.
Una representación formal del algoritmo descrito, y cuyo diagrama de flujo se
muestra en la Figura 12, es la siguiente:
Módulo
principal
Algoritmo para encontrar el elemento mayor de un Array.
Tiene como entrada un array no vacío, DATOS compuesto de � valores
numéricos. El algoritmo localiza el mayor de todos los datos contenidos en
MAX y el lugar que ocupa LUG. Utilizamos la variable K como contador.
Paso 1: [Inicialización]. K:=1, LUG:=1 y MAX =DATOS[1]. Paso 2: [Incrementar el contador]. K:=K+1.
Paso 3: [Test del contador]. Si K >�, entonces:
Escribir LUG y MAX y salir.
Paso 4: [Comparar y actualizar]. Si MAX<DATOS[K], entonces:
LUG:=K y MAX:=DATOS[K].
Paso 5: [Repetición del ciclo]. Ir al paso 2.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 47
Figura 12
Componentes de un algoritmo
Pasos, control y salida
Los pasos de los que consta un algoritmo son ejecutados uno detrás de otro,
comenzando por el paso 1, salvo que se indique lo contrario. No obstante, el control puede
transferirse a un paso n a través de la sentencia Ir a o Saltar al paso n. Por ejemplo en el
algoritmo descrito anteriormente el paso 5 transfiere el control al paso 2. En la mayoría de los
casos la sentencia puede ser eliminada si usamos convenientemente algunas estructuras de
control.
Si aparecen varias sentencias en el mismo paso, por ejemplo:
K:=1, LUG:=1 y MAX:=DATOS[1]
se ejecutan siempre de izquierda a derecha.
El algoritmo termina cuando en los sucesivos pasos ejecutamos la sentencia Salir.
Esta sentencia es equivalente a la STOP utilizada en FORTRAN o PARAR en los diagramas de
flujo.
Comienzo
K ← 1
LUG ← 1
MAX ← DATOS[1]
K ← K+1
¿Es K>N?
¿Es MAX<DATOS[K]?
LUG ← K
MAX ← DATOS[K]
Si
Si
No
No
Escribir: LUG, MAX
Parar
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 48
Comentarios
Cada paso puede contener un comentario que estará limitado por corchetes, para
indicar que operaciones realiza dicho paso. Los comentarios pueden aparecer al principio o al
final del mismo.
Nombres de variables
Los nombres de variables estarán compuestos siempre por letras mayúsculas como
MAX o DATOS. Asimismo designaremos también con mayúsculas las variables de una sola letra
o los contadores que utilicemos.
Sentencias de asignación
La operación de asignación de valores a variables las simbolizaremos mediante los dos
puntos-igual := que se usa en Pascal. Por ejemplo:
MAX:=DATOS[1]
asigna el valor contenido en el DATOS[1] a la variable MAX. También se utilizan la
flecha ← o el signo = para simbolizar esta operación.
Entrada y salida
Los datos pueden ser introducidos y asignados a las variables por medio de la
sentencia Leer con el formato siguiente:
Leer: Nombres de variables
Análogamente, mensajes acotados por comillas y los valores de las variables se pueden
escribir mediante las sentencias Escribir o Imprimir. Su formato es el siguiente:
Escribir: Mensajes y/o nombres de variables
Procedimientos
El término procedimiento lo utilizaremos para referirnos a módulos que resuelven
algoritmos completos, pero que son utilizados por otros que resuelven un problema general. Por
tanto, la utilización de los términos módulos o procedimientos es una cuestión de nomenclatura.
En ese sentido reservaremos la palabra algoritmo para la resolución de problemas generales. El
término procedimiento lo utilizaremos también al describir cierto tipo de subalgoritmos.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 49
Estructuras de Control
Los algoritmos y los correspondiente programas que los ejecutan en una computadora
son fácilmente inteligibles si en su diseño utilizamos módulos internos (definidos dentro del
mismo) y son diseñados de acuerdo a las reglas impuestas por los tres tipos de lógicas
siguientes:
Lógica secuencial o flujo secuencial.
Lógica selectiva o flujo condicional.
Lógica iterativa o flujo repetitivo.
Lógica secuencial o flujo secuencial
En la lógica secuencial implica que los módulos sean ejecutados uno a continuación del
otro, excepto que alguna instrucción indique lo contrario. La secuencia puede indicarse
explícitamente numerando los sucesivos pasos, o implícita en el que el orden lo impone la
ubicación de las sentencias.
Lógica selectiva o flujo condicional
La lógica selectiva utiliza un conjunto de condiciones que implican la ejecución de
alguna alternativa entre varias. Las estructuras que implementan este tipo de lógica reciben el
nombre de estructuras condicionadas o estructuras Si. Para una mayor claridad, se indica el
final de tal estructura mediante el comentario
[Fin de la estructura condicional]
o alguno equivalente. Estas estructuras condicionales pueden ser de tres tipos:
a) Alternativa simple. Tiene la forma:
Si condición, entonces:
[Módulo A]
[Final de la estructura condicional]
El diagrama de flujo de esta estructura se muestra en la Figura 13 a). En este caso si
la condición se cumple, se ejecuta el Módulo A, que puede estar compuesto por varias
sentencias. En cualquier otro caso el Módulo A no se ejecuta y se transfiere el
control al paso siguiente del algoritmo.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 50
b) Alternativa doble. Esta estructura tiene la forma:
Si condición, entonces:
[Módulo A]
Si No:
[Módulo B]
[Final de la estructura condicional]
El diagrama de flujo de esta estructura se muestra en la Figura 13 b). Como se indica
en el mismo, si la condición se cumple, se ejecuta el Módulo A. En caso contrario, se
ejecutará el B.
a) Alternativa simple b) Alternativa doble
Figura 13
c) Alternativa múltiple. Tiene la forma:
Si condición (1), entonces:
[Módulo A1]
Si No Si condición (2), entonces:
[Módulo A2]
:
Si No Si condición (M), entonces:
[Módulo AM]
Si No:
[Módulo B]
[Final de la estructura condicional]
La lógica de esta estructura permite la ejecución de un solo módulo, concretamente
el módulo siguiente a la primera condición que se cumpla o el módulo que sigue al Si No
final.
¿Condición?
Módulo A
¿Condición?
Módulo A Módulo B
No
Si
No
Si
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 51
Lógica iterativa o flujo repetitivo
El tercer tipo de lógica hace referencia a aquel tipo de estructura que implica la
utilización de lazos o ciclos. Fundamentalmente pueden ser de dos tipos, ambas comienzan con
la sentencia repetir seguida de un módulo que recibe el nombre de cuerpo del ciclo. El final del
ciclo se indica mediante la sentencia
[Fin de ciclo]
o alguna equivalente.
a) Ciclo Repetir-Desde utiliza una variable índice, por ejemplo K, para controlar el
ciclo. Este tendrá la forma:
Repetir-Desde K=R hasta S de T:
[Módulo ]
[Fin del ciclo]
El diagrama de flujo de esta estructura puede verse en la Figura 14 a). R recibe el
nombre de valor inicial, S el de valor final o valor de prueba y T el de incremento. El
cuerpo del ciclo se ejecuta primero para un valor de K=R. La primera vez para K=R+T,
la siguiente para K=R+2T, y así sucesivamente hasta que K>S. El diagrama de flujo
presentado asume que el incremento T es positivo. Si T fuese negativo, el ciclo
terminaría cuando K<S.
b) Ciclo Repetir-Mientras utiliza una condición para controlar el mismo. Tiene la
forma:
Repetir-Mientras condición:
[Módulo ]
[Fin del ciclo]
El diagrama correspondiente puede verse en la Figura 14 b). Obsérvese que el ciclo
continúa hasta que la condición exigida sea falsa. Es evidente que previa a la
estructura expuesta debe existir una sentencia que inicialice la condición que rige el
ciclo. Asimismo dentro del módulo que se ejecuta dentro de este debe haber alguna
sentencia que pueda cambiar la condición, para que el ciclo pueda terminar.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 52
a) Estructura repetir-desde b) Estructura repetir-mientras
Figura 14
¿Es K>S? ¿Condición?
No
Si No
Si
K ← R
Módulo
(cuerpo del ciclo)
K ← K+T
Módulo
(cuerpo del ciclo)
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 53
UNIDAD IV: TRABAJOS PRÁCTICOS
Objetivo:
Determinar la complejidad en algoritmos de búsqueda secuencial y binaria.
Reconocer los componentes de un algoritmo. Crear algoritmos con estructuras de
control, de flujo condicional. Resuelva el Trabajo Práctico N° 15.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 54
TRABAJO PRÁCTICO N° 15
1. Mediante Excel, determinar la complejidad en algoritmos de búsqueda secuencial y binaria, para los siguientes archivos.
Complejidad Nombre del
archivo Cantidad
de registros Búsqueda Secuencial Búsqueda Binaria Afiliados 1000 Artículos 20 Empleados 250 Alumnos 5000 Asociados 15000 Abonados 25000
2. En el siguiente algoritmo, identifique los componentes que integran el mismo: 3. Mediante un diagrama de flujo plantee un algoritmo, en el que incluya una estructura de
control de lógica selectiva o flujo condicional, del tipo alternativa múltiple. Resuélvalo utilizando la Planilla de Cálculos Excel.
Comienzo
K ← 1
LUG ← 1
MAX ← DATOS[1]
K ← K+1
¿Es K>N?
¿Es MAX<DATOS[K]?
LUG ← K
MAX ← DATOS[K]
Si
Si
No
No
Escribir: LUG, MAX
Parar
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 55
UNIDAD V: Cadenas Procesamiento de cadenas
En la actualidad es muy frecuente el uso de las computadoras para el procesamiento
de datos no numéricos llamados datos de caracteres, o de texto.
La terminología informática utiliza preferentemente el término cadena para una
secuencia de caracteres en lugar del término palabra, puesto que a este último le asigna otro
significado. Por este motivo y para evitar confusiones el procesamiento de textos es
referenciado por los términos "procesamiento de cadenas", "manipulación de cadenas" o
"edición de textos".
Una de las aplicaciones más importantes es el procesamiento de textos. Dicho
procesamiento implica, generalmente, algún tipo de reconocimiento de muestras, tales como
comprobar si una determinada palabra, aparece en un determinado texto.
Terminología básica
Cada lenguaje de programación posee un conjunto de caracteres que utiliza para
comunicarse con la computadora. Este conjunto incluye generalmente a los siguientes:
Alfabético: A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
Dígitos: 0 1 2 3 4 5 6 7 8 9
Caracteres especiales: + - / * ( ) , . $ = ´
El conjunto de caracteres especiales que generalmente incluye el blanco,
frecuentemente simbolizado por , varía de un lenguaje a otro.
� Una secuencia finita S, compuesta por cero ó más caracteres, recibe el nombre
de cadena.
� El número de caracteres presente en una cadena constituye su longitud.
� Una cadena con cero caracteres recibe el nombre de cadena vacía o cadena nula.
Las cadenas las indicaremos incluyendo los caracteres que las componen entre
comillas simples, estas comillas servirán también como delimitadores de cadenas.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 56
Son cadenas:
´EL FINAL´ ´SER O NO SER´ ´´ ´ ´
cuyas longitudes respectivas son 8, 12, 0 y 2. Insistimos en que el blanco es un
carácter y por tanto contribuye a la longitud de la cadena. En algunos casos las comillas pueden
omitirse si el contexto deja ver claramente que la expresión es una cadena.
Sean S1 y S2 dos cadenas. La cadena obtenida colocando a continuación de los
caracteres de S1 los de S2, recibe el nombre de concatenación de S1 y S2 y se expresa así:
S1//S2. Evidentemente la longitud de S1//S2 es igual a la suma de las longitudes de S1 y S2.
Decimos que una cadena Y es una subcadena de la cadena S si existen dos cadenas X y
Z tales que:
S = X//Y//Z
Si X no es una cadena vacía decimos que es la subcadena inicial de S. Si Z no es una
cadena vacía decimos que es la subcadena terminal de S.
Lógicamente si Y es una subcadena de S, su longitud no puede ser mayor que la de S.
Almacenamiento de Cadenas
Generalmente una cadena puede almacenarse en algunos de estos tipos de estructura:
� Estructuras de longitud fija.
� Estructuras de longitud variable pero con máximo fijado.
� Estructuras enlazadas.
Almacenamiento de longitud fija u orientada al registro:
En el almacenamiento de estructura fija cada registro tiene la misma longitud, es
decir contiene el mismo número de caracteres. Puesto que los datos suelen introducirse a
través de terminales que poseen un ancho de 80 columnas, los registros serán de una longitud
de 80 caracteres.
Las principales ventajas de este tipo de almacenamiento son: el poder acceder
fácilmente a cualquier registro y la facilidad a la hora de actualizar los datos de un
determinado registro.
Las desventajas en cambio son: se emplea mucho tiempo al leer los registros si la
mayoría de la información en ellos almacenada consiste en blancos que no tienen una misión
específica y algunos registros pueden necesitar más espacio que el disponible.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 57
Almacenamiento de longitud variable con máximo establecido:
Aunque las cadenas pueden almacenarse en celdas de memoria, de longitud fija, puede
ser ventajoso el conocer la longitud actual de la cadena. Por ejemplo no es necesario leer todo
el registro cuando la cadena ocupa únicamente la primera parte de la celda de memoria.
También algunas operaciones con cadenas dependen de la existencia de cadenas de longitud
variable.
El almacenamiento de cadenas de longitud variable en celdas de memoria de longitud
fija puede realizarse de dos maneras:
� Utilizando una marca, como dos símbolos $$ consecutivos, para indicar el final de
la cadena.
� Incluir la longitud de la cadena como un ítem adicional en un array de punteros.
Estas marcas de separación, tales como el $$ o el array de punteros si bien ahorran
espacio y son utilizadas con frecuencia en el almacenamiento de registros en memorias
secundarias (discos) ya que son relativamente permanentes y precisan pocos cambios; suelen
ser poco eficientes cuando las cadenas y su longitud están sometidas a cambios frecuentes.
Almacenamiento enlazado: Una lista enlazada es una secuencia ordenada de celdas
de memoria, llamadas nodos, donde cada nodo contiene un elemento llamado enlace, el cual
apunta al siguiente nodo de la lista, es decir que contiene la dirección del siguiente elemento de
la lista.
Operaciones con Cadenas
Subcadenas: cuando queremos acceder a una subcadena contenida en una
determinada cadena, debemos conocer las siguientes elementos: el nombre de la cadena o la
cadena misma, la posición que ocupa el primer carácter de la subcadena en la cadena a la que
pertenece y la longitud de la subcadena. Llamaremos a esta operación Subcadena y
escribiremos:
SUBCADENA(cadena, inicial, longitud)
Por ejemplo: SUBCADENA(´EL FINAL´,4,5) = ´FINAL´
Indexación: el término indexación o localización de secuencias hace referencia a la
operación de encontrar la posición en que aparece por primera vez una secuencia de caracteres
P dentro de un texto T. Simbolizamos esta operación de la siguiente forma:
INDEX(texto, secuencia)
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 58
Si la secuencia no se encuentra dentro del texto, entonces INDEX nos devuelve el
valor 0.
Por ejemplo: INDEX(´EL FINAL´, ´AL´)=7
Concatenación: Sean las cadenas S1 y S2. La concatenación de S1 y S2, simbolizada
por S1//S2 es aquella obtenida colocando a continuación de los caracteres de S1 los de S2.
Por ejemplo: Sea S1 = ´PABLO´ y S2 = ´NERUDA´
S1//S2 = ´PABLONERUDA´
ó
S1/´ ´/S2 = ´PABLO NERUDA´
Longitud: el número de caracteres que componen una cadena recibe el nombre de
longitud de la cadena y se simboliza así:
LONGITUD(cadena)
Por ejemplo: LONGITUD(´PABLO´)=5
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 59
UNIDAD V: TRABAJOS PRÁCTICOS
Objetivo:
Reconocer dentro de los tipos de datos, las cadenas. Operar con ellas, respetando
su sintaxis con el propósito de obtener la información requerida. Resuelva el
Trabajo Práctico N° 16.
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 60
Trabajo Práctico N°16 Objetivo:
Encontrar subcadenas, determinar la posición de una subcadena, concatenar textos, y determinar la longitud de determinadas cadenas.
1. En la hoja 1 de la planilla de cálculos, realice una tabla como la que se muestra a continuación:
Apellido Nombre Tipo de
Documento N° de Documento Lugar de Procedencia
Marín, Matías D.N.I. 27.451.311 Argentina-Buenos Aires Hadad, Manuel D.N.I. 29.115.131 Argentina-Córdoba Alvarez, Eduardo Pas. 90.485.219 Bolivia-La Paz Trombotto, Ricardo Pas. 91.744.932 Bolivia-Sucre Torello, Laura D.N.I. 25.541.112 Argentina-Salta Fernández, Emilia Pas. 92.451.711 Bolivia-Potosí Garzón, Marcela C.I. 95.210.175 Brasil-San Pablo Fonseca, Alejandra C.I. 2.455.320 Uruguay-Montevideo Patrito, Raúl C.I. 98.119.475 Brasil-Porto Alegre Luna, Federico D.N.I. 28.545.512 Argentina-Córdoba Farías, Roberto C.I. 3.518.425 Uruguay-Colonia Furcade, Martina Pas. 90.444.312 Bolivia-La Paz Mozzini, Susana C.I. 95.115.476 Brasil-San Pablo Lazarte, Fabián D.N.I. 13.151.541 Argentina-Salta Quintana, Claudio C.I. 5.720.015 Uruguay-Montevideo Carmona, Fernando C.I. 99.775.459 Brasil-Porto Alegre Ortiz, Lorenzo Pas. 90.911.515 Bolivia-Sucre Brie, Felipe D.N.I. 17.454.553 Argentina-Buenos Aires Gardella, Lorena D.N.I. 29.991.141 Argentina-Córdoba Boccelli Cecilia D.N.I. 29.341.181 Argentina-Buenos Aires 2. En la hoja 2 de la planilla, utilizando funciones de texto, concatene las cadenas de
caracteres de las columnas Apellido y Nombre, Tipo de Documento y N° de Documento, de forma tal que la tabla quede así:
Apellido y Nombre Tipo y N° de Documento Lugar de Procedencia
3. Agregue a la tabla anterior, una columna denominada País de Procedencia. Para obtenerla
extraiga mediante una función de texto, de la columna Lugar de Procedencia, la subcadena correspondiente al país. Sería conveniente que antes ordenara la tabla por esta clave.
4. A continuación de las anteriores, agregue las siguientes columnas: País de Destino
Fecha de Traslado
Para determinar Lugar de Destino, considere lo siguiente: Si el País de Procedencia es Argentina, el País de Destino será Francia Si el País de Procedencia es Bolivia, el País de Destino será Alemania Si el País de Procedencia es Brasil, el País de Destino será Portugal Si el País de Procedencia es Uruguay, el País de Destino será España
Universidad Nacional de Córdoba Analista de Sistemas Informáticos
Escuela Superior de Comercio Manuel Belgrano Estructura de Datos
Nivel Terciario 1º Año
Realizado por María del Valle Aranda pág. 61
Para determinar Fecha de Traslado, considere lo siguiente: Si el País de Destino es Alemania ó Portugal, la Fecha de Traslado será el 01/07/13 Si el País de Destino es Francia ó España, la Fecha de Traslado será el 01/08/13
5. Mediante funciones de texto, determine la longitud de las cadenas de caracteres, de las columnas Apellido y Nombre y Lugar de Procedencia.