PowerPoint Template

Estructuras de DatosEscuela Militar de IngenieraAplicaciones de Software a la IndustriaIntroduccinLa informacin que se procesa en la computadora consiste en un conjunto de datos, que pueden ser simples o estructurados.Los datos simples son aquellos que ocupan slo una localidad de memoria, mientras que los estructurados son un conjunto de casillas de memoria a las cuales se hace referencia mediante un identificador nico.Estructuras de DatosAplicaciones de Software a la IndustriaIntroduccinLa informacin que se procesa en la computadora consiste en un conjunto de datos, que pueden ser simples o estructurados.Los datos simples son aquellos que ocupan slo una localidad de memoria, mientras que los estructurados son un conjunto de casillas de memoria a las cuales se hace referencia mediante un identificador nico.Estructuras de DatosAplicaciones de Software a la IndustriaIntroduccinDebido a que por lo general se tienen que tratar con conjuntos de datos y no con datos simples (enteros, reales, booleanos, etc.) que por s solos no denotan nada, ni sirven de mucho, es necesario tratar con estructuras de datos adecuadas a cada necesidad.Estructuras de DatosAplicaciones de Software a la IndustriaQu es un Dato?El dato (del latn datum), es una representacin simblica (numrica, alfabtica, algortmica etc.), atributo o caracterstica de una entidad.El dato no tiene valor semntico (sentido) en s mismo, pero convenientemente tratado (procesado) se puede utilizar en la realizacin de clculos o toma de decisiones. Estructuras de DatosAplicaciones de Software a la IndustriaQu es un Dato?El dato es de empleo muy comn en el mbito informtico.En humanidades, especficamente en el mbito de las ciencias de la informacin y la bibliotecologa, se considera que un dato es una expresin mnima de contenido sobre un tema.Estructuras de DatosAplicaciones de Software a la IndustriaQu es un Dato?Ejemplos de datos son: la altura de una montaa, la fecha de nacimiento de un personaje histrico, el peso especfico de una sustancia, el nmero de habitantes de un pas, etc.La informacin representa un conjunto de datos relacionados que constituyen una estructura de menos complejidad (por ejemplo, un captulo de un libro de ciencias).Estructuras de DatosAplicaciones de Software a la IndustriaDiferencia entre el Dato y la InformacinEstructuras de DatosAplicaciones de Software a la IndustriadatodatodatodatoProcesoInformacinEstructura de DatosLas estructuras de datos son una coleccin de datos cuya organizacin se caracteriza por las funciones de acceso que se usan para almacenar y acceder a elementos individuales de datos.

Una estructura de datos se caracteriza por lo siguiente:Pueden descomponerse en los elementos que la forman.La manera en que se colocan los elementos dentro de la estructura afectar la forma en que se realicen los accesos a cada elemento.La colocacin de los elementos y la manera en que se accede a ellos puede ser encapsulada.Estructuras de DatosAplicaciones de Software a la IndustriaEstructura de DatosEn programacin, una estructura de datos es una formade organizar un conjunto de datos elementales (un datoelemental es la mnima informacin que se tiene en elsistema) con el objetivo de facilitar la manipulacin deestos datos como un todo o individualmente.Una estructura de datos define la organizacin e interrelacionamiento de stos, y un conjunto de operaciones que se pueden realizar sobre l. Las operaciones bsicas son:Alta, adicionar un nuevo valor a la estructura. Baja, borrar un valor de la estructura. Bsqueda, encontrar un determinado valor en la estructura para realizar una operacin con este valor, en forma SECUENCIAL o BINARIA (siempre y cuando los datos estn ordenados). Estructuras de DatosAplicaciones de Software a la IndustriaEstructura de DatosOtras operaciones que se pueden realizar son:Ordenamiento, de los elementos pertenecientes a la estructura. Apareo, dadas dos estructuras originar una nueva ordenada y que contenga a las apareadas. Cada estructura ofrece ventajas y desventajas en relacin a la simplicidad y eficiencia para la realizacin de cada operacin.De esta forma, la eleccin de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operacin sobre los datos.Estructuras de DatosAplicaciones de Software a la IndustriaTipos de Datos ElementalesBinarios Bit ByteNumricos Entero Real Alfanumricos Carcter Cadena

Estructuras de DatosAplicaciones de Software a la IndustriaTipos de Estructura de DatosVectores (matriz o array) Registro (estructura de datos) Tipo de datos algebraco Listas Enlazadas (simples, dobles, circulares, etc.)Pilas (stack) Colas (queue) rboles rboles Binarios rboles Multicamino (Multirrama) Conjuntos (set) Grafos Tablas Hash Montculos (o heaps)

Estructuras de DatosAplicaciones de Software a la IndustriaEstructuras de DatosUna Estructura de Datos es una coleccin de datos que se caracteriza por su organizacin y las operaciones que se definen en ella.Los datos de tipo estndar pueden ser organizados en diferentes estructuras de datos: estticas y dinmicas.Estructura de Datos estticas:Son aquellas en las que el espacio ocupado en memoria se define en tiempo de compilacin y no puede ser modificado durante la ejecucin del programa.Corresponden a este tipo los arrays y registrosEstructuras de Datos Dinmicas:Son aquellas en las que el espacio ocupado en memoria puede ser modificado en tiempo de ejecucin. Corresponden a este tipo las listas, rboles y grafos . La eleccin de la estructura de datos idnea depender de la naturaleza del problema a resolver y, en menor medida, del lenguaje. Las estructuras de datos tienen en comn que un identificador, nombre, puede representar a mltiples datos individuales.Estructuras de DatosAplicaciones de Software a la IndustriaClasificacin de los Tipos de Datos:Tipos de DatosEstticosSimplesDinmicosCadena Estructu-radosPuntero-Ordinales:IntegerBoleanCharEnumeradosSubrango

-No OrdinalesReales

Arrays RegistrosArchivosProcedi-mientosEstructuras de DatosAplicaciones de Software a la IndustriaArrays (Arreglo Unidimensional)

Estructuras de DatosAplicaciones de Software a la IndustriaArrays (Arreglo Bidimensional)

Estructuras de DatosAplicaciones de Software a la IndustriaArchivo

Estructuras de DatosAplicaciones de Software a la IndustriaArchivo (Arrays Separados)

Estructuras de DatosAplicaciones de Software a la Industria Archivo (Otra forma de presentacin)

Estructuras de DatosAplicaciones de Software a la Industria Archivo (Otra forma de presentacin)

Estructuras de DatosAplicaciones de Software a la IndustriaEstructura de Registro

Estructuras de DatosAplicaciones de Software a la IndustriaExpresiones Algebraicas

Estructuras de DatosAplicaciones de Software a la IndustriaPilas, Colas, rboles y Grafos

Estructuras de DatosAplicaciones de Software a la IndustriaRelacin Tiempo-Espacio

Estructuras de DatosAplicaciones de Software a la IndustriaArreglos o ArraysUn arreglo (array) es una coleccin de datos del mismo tipo, que se almacenan en posiciones consecutivas de memoria y reciben un nombre comn. Para referirse a un determinado elemento de un array se deber utilizar un ndice, que especifique su posicin relativa en el array. Un arreglo es una coleccin finita, homognea y ordenada de elementos.Finita: Todo arreglo tiene un lmite; es decir, debe determinarse cul ser el nmero mximo de elementos que podrn formar parte del arreglo.Homognea: Todos los elementos del arreglo deben ser del mismo tipo.Ordenada: Se puede determinar cul es el primer elemento, el segundo, el tercero,.... y el n-simo elemento.Los arreglos se clasifican de acuerdo con el nmero de dimensiones que tienen. As se tienen los:Unidimensionales (vectores)Bidimensionales (tablas o matrices)Multidimensionales (tres o ms dimensiones) Estructuras de DatosAplicaciones de Software a la IndustriaTipos de Arreglos

Estructuras de DatosAplicaciones de Software a la IndustriaArreglos UnidimensionalesEstn formados por un conjunto de elementos de un mismo tipo de datos que se almacenan bajo un mismo nombre, y se diferencian por la posicin que tiene cada elemento dentro del arreglo de datos. Al interior del arreglo, los programas especifican el nombre de ste y el nmero del elemento, colocndolo dentro de corchetes, como en calificacin[3].Al declarar un arreglo, se debe inicializar sus elementos antes de utilizarlos.Para declarar un arreglo tiene que indicar su tipo, un nombre nico y la cantidad de elementos que va a contener. Por ejemplo, las siguientes instrucciones declaran tres arreglos distintos:float costo_partes[50];int edad_empleados[100];float precios_acciones[25];Estructuras de DatosAplicaciones de Software a la IndustriaEjemplo de Arreglo UnidimensionalPara acceder a valores especficos del arreglo, use un valor de ndice que apunte al elemento deseado. Por ejemplo, para acceder al primer elemento del arreglo calificaciones debe utilizar el valor de ndice 0 (calificaciones[0]). Los programas en C++ siempre indizan el primer elemento de un arreglo con 0 y el ltimo con un valor menor en una unidad al tamao del arreglo.

Estructuras de DatosAplicaciones de Software a la IndustriaInicializacin y Asignacin deValoresAntes de utilizar un arreglo es necesario inicializarlo:Para inicializar todos los elementos de una vez, se colocan dentro de una estructura for que va del primer elemento al ltimo que contiene el arreglo.Para asignar un valor a un elemento del arreglo se hace por ejemplo: Calificaciones[0] 100;Cuando se usan arreglos, una operacin comn es usar una variable ndice para acceder a los elementos de un arreglo. Suponiendo que la variable ndice I contiene el valor 3, la siguiente instruccin asigna el valor 400 a valores[3]: valores[I] 400;Partes de un arreglo:Los componentes. Hacen referencia a los elementos que forman el arreglo, es decir, a los valores que se almacenan en cada una de las casillas del mismo.Los ndices. Permiten hacer referencia a los componentes del arreglo en forma individual, especifican cuntos elementos tendr el arreglo y adems, de qu modo podrn accederse a esos componentes.Estructuras de DatosAplicaciones de Software a la IndustriaOperaciones Con VectoresLas operaciones que se pueden realizar con vectores durante el proceso de resolucin de un problema son:Lectura/ escrituraAsignacinActualizacin (insercin, eliminacin, modificacin)Recorrido (acceso secuencial)OrdenacinBsquedaEstructuras de DatosAplicaciones de Software a la IndustriaLectura y Escritura de VectoresLecturaEl proceso de lectura de un arreglo consiste en leer y asignar un valor a cada uno de sus elementos. Normalmente se realizan con estructuras repetitivas, aunque pueden usarse estructuras selectivas.Se usa los ndices para recorrer los elementos del arreglo: desde i = 1 hasta 70 hacer leer ( arre[i]) fin_desde

Escritura:Es similar al caso de lectura, slo que en vez de leer el componente del arreglo, lo escribimos. leer (N) desde i = 1 hasta N hacer escribir (arre[i]) fin_desdeEstructuras de DatosAplicaciones de Software a la IndustriaAsignacin e Inicializacin de vectoresAsignacin:No es posible asignar directamente un valor a todo el arreglo; sino que se debe asignar el valor deseado en cada componente. Con una estructura repetitiva se puede asignar un valor a todos los elementos del vector.Por ejemplo: arre[1] 120 (asignacin de un valor constante nico a una casilla del vector) arre[3] arre[1] / 4 (asignar una operacin)Se puede asignar un valor constante a todos los elementos del vector: desde i = 1 hasta 5 hacer arre[i] 3 fin_desdeO bien arre 3 (con arre del tipo arreglo)

InicializacinPara inicializar con cero todos los elementos del arreglo: desde i = 1 hasta 70 hacer arre[i] 0 fin_desdeEstructuras de DatosAplicaciones de Software a la IndustriaAcceso Secuencial y Actualizacin de VectoresAcceso Secuencial. (Recorrido)El acceso a los elementos de un vector puede ser para leer en l o para escribir (visualizar su contenido).Recorrido del vector es la accin de efectuar una accin general sobre todos los elementos de ese vector.Actualizacin.Incluye aadir (insertar), borrar o modificar algunos de los ya existentes. Se debe tener en cuenta si el arreglo est o no ordenado.Aadir datos a un vector consiste en agregar un nuevo elemento al final del vector, siempre que haya espacio en memoria.Estructuras de DatosAplicaciones de Software a la IndustriaRegistros es un tipo de datos formado por una coleccin finita de elementos no necesariamente homogneos.El acceso se realiza a travs de una referencia al nombre del registro seguido del campo especfico al que se desea acceder y delimitado por un punto.RegistrosEstructuras de DatosAplicaciones de Software a la IndustriaREGISTRO Auto codigo : entero marca : cadena precio : realFIN_REGISTRO

Var:AUTOMOVILES : AutoCAMPOSNombre RegistroTipo DatoVariable Referencia a RegistroNotacin Algortmica de un RegistroEstructuras de DatosAplicaciones de Software a la Industriacodigo marcaprecio4054OPEL CORSA SWING 1.45.150.00CampoRegistroAUTOMOVILES.codigoAUTOMOVILES.marcaAUTOMOVILES.precioAcceso a Campo de RegistroVista Grfica de un Registro y Acceso a Campos de RegistroEstructuras de DatosAplicaciones de Software a la IndustriaModule Module1 Structure alumno Dim nombre As String End Structure

Sub Main() Dim RegAlu As alumno

RegAlu.nombre = Fabricio

Console.WriteLine(RegAlu.nombre)

Console.Read() End Sub

End ModuleDefine Estructura alumno (Registro)Variable de Referencia a EstructuraAcceso a Campo de EstructuraEjemplo en Visual Basic

Estructuras de DatosAplicaciones de Software a la IndustriaArchivos1Los archivos consisten en conjuntos de datos estructurados, que se encuentran almacenados sobre un dispositivo de almacenamiento externo.3Los archivos son un conjunto de registros relacionados entre s y los registros un conjunto de campos.2Es posible establecer una jerarqua en la que las bases de datos, ocuparan el nivel ms alto y estarn formadas por un conjunto de archivos que contienen datos relacionados.Estructuras de DatosAplicaciones de Software a la IndustriaEjemplos de Archivos y Base de DatosNombreTelfonoSaldoDepartamentoGregorio Bernal Yaez2864039150010Elizabeth Saucedo Chalup2481526100020David Arratia Paco279312520030Elsie Ayarde Lpez6641773200010Mirtha Rosas Cardozo664199610020EmpleadoNmeroNombreLocalizacin10PresidenciaLa Paz20FinanzasSucre30OperacionesCobijaDepartamentoBase de DatosArchivos4Un campo puede estar dividido en subcampos, pero cuando no se encuentra dividido, constituye el nivel ms bajo en dicha jerarqua desde el punto de vista lgico.6En sntesis: los archivos estn formados por una coleccin de registros y stos, a su vez, por campos, caracterizados por su tamao o longitud y su tipo de datos.5Como estructura de datos, los archivos posibilitan el almacenamiento permanente y la manipulacin de un gran nmero de datos.Estructuras de DatosAplicaciones de Software a la IndustriaRegistro Fsico y Lgico de un ArchivoRegistro Lgico. Lo define el programador y lo usual es que sea menor o igual que el registro fsico.Registro Fsico. Es la cantidad de datos que pueden transferirse en una operacin de entrada/salida a travs del buffer (memoria temporal). Su tamao viene impuesto por el equipo material,ArchivoEstructura de DatosAplicaciones de Software a la IndustriaCampo, Registro, Archivo y Base de DatosCampo: Propiedad, atributo o cualidadde un objeto real o intangible, tal como el nombre de un empleado o el precio de un artculo.Registro: Conjunto completo de datos relacionados o campo pertenecientes a una entrada, tal como un cheque bancario. Archivo: Coleccin de registros relacionados. Se incluye cada registro en un archivo ya que pertenece a la misma entidad. Base de DatosColeccin o depsito de datos integrados o archivos, almacenados en soporte secundario(no voltil) y con redundancia controlada. Estructuras de DatosAplicaciones de Software a la IndustriaOrganizacin y Modo de Acceso de ArchivosSequentialRandomIndexedOrganizacinSecuencialOrganizacinDirecta oAleatoriaOrganizacinSecuencialIndexadaEstructuras de DatosAplicaciones de Software a la IndustriaOrganizacin Secuencial1Los registros se almacenan consecutivamente sobre el soporte externo y se pueden designar por nmeros enteros consecutivos, los que, empero, no pueden usarse como funciones de acceso.3Los ficheros organizados secuencialmente tienen un registro particular, el ltimo, que contiene una marca de fin de archivo y no puede abrirse simultneamente para lectura y escritura.2Para realizar el acceso a un registro resulta obligatorio pasar por los que le preceden.Esta forma de organizacin puede emplearse tanto en soportes informticos como en direccionables.

Estructuras de DatosAplicaciones de Software a la IndustriaOrganizacin Directa1El orden fsico de los registros no tiene por qu corresponder con aquel en el que han sido introducidos.3Esta organizacin slo se puede usar en soportes direccionables.Los archivos con organizacin directa se abren para lectura y escritura simultneamente.2Los registros son directamente accesibles mediante la especificacin de un ndice, que da la posicin del registro respecto al origen del archivo.

Estructuras de DatosAplicaciones de Software a la IndustriaOrganizacin Secuencial Indexadarea dendicesreaPrincipalreade Desbor-damientoSoportesEs un archivo secuencial que contiene las claves del ltimo registro de cada bloque fsico del archivo y la direccin de acceso al primer registro del bloque.Estructuras de DatosAplicaciones de Software a la IndustriaUn archivo secuencial indexado, se compone de:Contiene los registros de datos, clasificados en orden ascendente por el campo clave.O rea de Excedentes, almacena los nuevos registros que no se puedan situar en el rea principal en las actualizaciones.Permiten el acceso directo.Organizacin Secuencial IndexadaEstructuras de DatosAplicaciones de Software a la IndustriaClaveDireccin2400194100295600309200402450090ClaveDatos00106001000111800200012200030004000192400202800900021290029410030430090245rea de ndicesrea de DatosOrganizacin Secuencial Indexada1Se puede acceder a la informacin de forma secuencial o a travs del ndice.A travs del ndice, se lee secuencialmente el archivo ndice hasta encontrar una clave mayor o igual a la buscada; el otro campo proporciona la posicin del primer registro del bloque donde se encuentra la informacin.3Como desventajas, tiene al desaprovechamiento del espacio, por quedar huecos intermedios en las actualizaciones del archivo, y la necesidad de espacio adicional para el rea de ndices.2Los archivos secuenciales indexados tienen como ventajas un rpido acceso y su sistema de gestin de archivos que se encarga de relacionar la posicin de cada registro con su clave mediante la tabla de ndices.Estructuras de DatosAplicaciones de Software a la IndustriaOperaciones con ArchivosCreacinAperturaClausuraLectura de datosConsiste en definir el archivo mediante un nombre y unos atributos, nombre externo del archivo, nombre de dispositivo, tamao, tamao de bloque y organizacin. Si el archivo existiera, esta operacin lo destruira.Estructuras de DatosAplicaciones de Software a la IndustriaLas operaciones con archivos estn referidas con la propia estructura del archivo:Establece la comunicacin de la Unidad Central de Procesamiento con el dispositivo de soporte fsico del fichero, de esta manera los registros se vuelven accesibles. La operacin de abrir archivos se puede aplicar para operaciones de entrada, salida o entrada/salida.Constituye el cierre de la conexin entre el identificador del archivo y el dispositivo de almacenamiento externo.Copia los registros del fichero sobre variables en memoria central.Escritura de datosCopia la informacin contenida en variables sobre un registro del fichero. Borrado del ficheroBorra el fichero del soporte fsico, liberando el espacio. Mantenimiento de ArchivosConsultaActualizacin: Altas, bajas y modificacionesMantenimientoEstructuras de DatosAplicaciones de Software a la IndustriaLas operaciones de mantenimiento de archivos suelen constituir mdulos independientes del programa principal y su diseo se efecta con subprogramas.Mantenimiento de Archivos Secuenciales1Es la accin de eliminar un registro del archivo.

La baja del registro puede ser lgica o fsica.3La baja fsica implica el borrado y desaparicin del registro y se requerir crear un nuevo archivo que no incluya al registro dado de baja2La baja lgica supone el borrado del registro en el archivo y se efecta colocando en un determinado campo del registro una bandera, indicador o flag que lo marque como que ha sido borrado, o rellenando de espacios en blanco algn campo del registro.Estructuras de DatosAplicaciones de Software a la IndustriaBajasMantenimiento de Archivos Secuenciales4Como no es posible abrir un archivo secuencial para lectura y escritura y, adems, cuando se abre para escritura, el puntero de datos se coloca al final del archivo, la baja lgica tambin necesitar realizar la creacin de un nuevo archivo con todos los registros y la marca correspondiente sobre el que haya sido borrado.6Si se desea incorporar nuevos registros en una determinada posicin, que no sea el final del archivo, se requera tambin la creacin de un archivo auxiliar y el renombrado final del archivo auxiliar como el inicial 5El proceso de modificar la informacin almacenada en un determinado registro de un archivo secuencial es similar a la baja lgica.

Estructuras de DatosAplicaciones de Software a la IndustriaBajasModificacionesAltasEl registro es un tipo de dato estructurado constituido por un conjunto de elementos (campos) que pueden ser de diferentes tipos de datos, ejemplo:Registro: Empleado Elementos del registro empleado:Numero (Entero) Nombre (Cadena[30]) Departamento (Entero) Puesto (Entero) Sueldo (Real)Definicin de registros: Declaraciones Variables NomRegistro: Registro Dato1: Tipo de dato Dato2: Tipo de dato . DatoN: Tipo de dato FinRegistroManejo de Registros y Archivosen PseudocdigoEstructuras de DatosAplicaciones de Software a la IndustriaAbrir archivo Escritura XLeer datos A , BDO ESCRIBIR REGISTRO CON DATOS A Y B EN EL ARCHIVO X Leer datos A, BWHILE A 0 El siguiente algoritmo permite agregar registro a un archivo previamente creado:Abrir archivo Agregacin X Leer datos A , B DO AGREGAR REGISTRO CON DATOS A Y B EN EL ARCHIVO X Leer datos A, B WHILE A 0Creacin de ArchivosSecuenciales en PseudocdigoEstructuras de DatosAplicaciones de Software a la Industria INICIOAbrir el archivo para lectura X.LEER REGISTRO DEL ARCHIVO. WHILE no sea fin de archivo 1. IF es una bandera de control THEN A. Imprimir resumen y pie de pgina 2. ENDIF 3. Imprimir detalle para este registro 4. Acumular a totales 5. Leer siguiente registro DEL ARCHIVOENDWHILEImprimir resumen y pie de pginaFin

Recuperacin de ArchivosSecuenciales en PseudocdigoEstructuras de DatosAplicaciones de Software a la IndustriaDiversidad de algoritmos requieren una representacin apropiada de los datos para lograr ser eficientes.Una estructura de datos es una representacin de datos junto con las operaciones permitidas sobre dichos datos.Tpicamente las estructuras de datos permiten inserciones arbitrarias.Las estructuras de datos varan en como permiten el acceso a miembros de grupo. Algunas permiten tanto accesos como operaciones de borrado arbitrarios.Otras imponen restricciones, tales como permitir el acceso slo al elemento ms recientemente insertado, o al menos recientemente insertado del grupo.Las estructuras de datos pueden ser estticas si su tamao no puede modificarse durante su procesamiento, y dinmicas en caso contrario.Las estructuras de datos pueden ser lineales si a un elemento antecede y sucede uno y solo un elemento, y no lineales en caso contrario.ConclusionesEstructuras de DatosAplicaciones de Software a la Industria