Estructura de Datos utilizados en el proceso electrónico de datos

Estructura de Datos utilizados en el proceso electrónico de datos ArreglosSon una agrupación de datos homogéneos, es decir, con un mismo tipo de dato básico asociado. Se almacenan en forma contigua en la memoria y son referenciados con un nombre común y una posición relativa. Ejemplos:Arreglo Lineal (1 dimensión ó vector)Vista gráfica [1] [2] [3] [4] [5] Definición de tipo Type Linea: Array [1..5] of TipoBasico;VarMiArreglo:Linea; Arreglo Bidimensional (matriz)Vista gráfica [1,1] [1,2] [1,3] [1,4] [2,1] [2,2] [2,3] [2,4] [3,1] [3,2] [3,3] [3,4] Definición de tipo TypeTipoTabla:Array[1..3,1..4] of TipoBasico;VarMiTabla: TipoTabla; Pilas o colas Lifo:Imagina un montón de platos "apilados" o bien fichas de dominó formando una torre e intenta eliminar una desde el centro, ¿qué ocurre?, naturalmente esta operación no está permitida si queremos mantener intactos a los platos o a la torre construida. Por esta razón, una pila se asocia a una estructura de datos LIFO (LAST IN FIRST OUT). En base a lo anterior, construye la definición de una PILA y discútela con el profesor.En general, podemos definir para cada una de las estructuras de datos una representación estática y otra dinámica según el método de asignación de memoria utilizado. Clasificacióna.)Pila estática:Sin duda tendremos que utilizar arreglos o registros que como ya sabemos son la base para estructuras de datos más complejas. Considerando la siguiente figura: Vista gráfica Suponiendo que Dato pertenece a un mismo tipo de datos y Cuenta Dato corresponde a un entero que se incrementa a medida que un nuevo elemento se incorpora a la pila. Intenta construir la definición de tipo para la estructura Pila. TYPE__________________________________________________________________________________________END;b.)Pila Dinámica:Sin duda tendremos que utilizar nodos con punteros. Considera la siguiente figura: Suponiendo que los punteros que aparecen en la figura son capaces de apuntar a un nodo y que Dato pertenece a cualquiera de los tipos básicos o estructurados, la definición de tipo sería: TYPEPuntero=^NodoPila;NodoPila=RecordInfo:AlgunTipo;sgte:Puntero;End;Var tope:Puntero; Un concepto por introducir es el de encapsulamiento, que significa que una vez definida la estructura e implementadas las operaciones básicas, uno se remite a utilizarlas sin importar su codificación interna, es decir, las llamadas a PUSH(pila, x) o POP(pila, y) empilarán a x o desempilarán en y sin importar cómo lo hagan. c.)Listas Enlazadas:Corresponde a una estructura lineal compuesta por una colección de datos homogéneos con alguna relación entre ellos. Dicha estructura se crea a través del método dinámico de memoria.En una lista enlazada el orden de los elementos está determinado por un campo enlace (puntero) explícito en cada elemento, por ejemplo: pilas y filas dinámicas.La representación de lista enlazada es la más óptima debido a que cualquier proceso de actualización (modificación inserción o eliminación) se realiza en base a reasignación de punteros. En este capítulo trataremos sólo con las listas enlazadas ya que las listas secuénciales ya son bien conocidas por ustedes. Tipos de Listas Enlazadas · Listas lineales simplemente enlazadas · Listas Circulares · Listas doblemente enlazadas · Listas múltiplemente enlazadas ÁrbolesEs una estructura de datos no lineal que posee raíz, ramas y hojas, técnicamente constituye un grafo finito y sin ciclos. Un árbol define ciertos niveles jerárquicos precedidos por la raíz (1er. nivel), en donde las hojas constituyen el nivel más bajo. ComponentesRaíz: Nodo que constituye la única entrada a la estructura (por ello es necesario tener un puntero sobre él).Ramas o Arcos: Conexión entre dos nodos del árbol que representa una relación de jerarquía.Hojas: Nodo sin hijos. CaracterísticasNivel o profundidad de un nodo: Longitud del camino para ir desde la raíz al nodo. Por definición la raíz está en el nivel 0. Por ejemplo: profundidad(Y)=2, profundidad(raíz)=0, profundidad(árbol)= profundidad(hoja más profunda). Altura de un nodo: Longitud del camino más largo desde el nodo a una hoja. Por ejemplo:Altura(X)=1, Altura(Y)=0, Altura(arbol)=Altura(raíz)=profundidad(árbol) Grado de nodo: Cantidad de hijos de un nodo cualquiera.Grado de árbol: Cantidad máxima de hijos posibles de asociar a un nodo del árbol Clasificacióna.)Según Número de Hijos: b.)Según Estructura de Niveles:Arbol completo: Es un árbol binario en el cual cada nodo es una hoja o posee exactamente 2 hijos. Arbol lleno: Es un árbol binario con hojas en a lo más dos niveles adyacentes l-1 y l, en las cuales los nodos terminales se encuentran ubicados en las posiciones de más a la izquierda del árbol. Si un árbol binario es completo, necesariamente es llenoc.)Según Funcionalidad:Árbol binario de búsqueda (ABB) Árbol binario de expresión Archivos:Es una es estructura de datos que reside en memoria secundaria o almacenamiento permanente (cinta magnética, discomagnético, disco óptico, disco láser, etc.). La forma de clasificación más básica se realiza de acuerdo al formato en que residen estos archivos, de esta forma hablamos de archivos ASCII (de texto) y archivos binarios. En este capítulo nos centraremos en estos últimos. Definición archivo binario:Estructura de datos permanente compuesto por registros (filas) y éstos a su vez por campos (columnas). Se caracteriza por tener un tipo de dato asociado, el cual define su estructura interna. Definición archivo texto:Estructura de datos permanente no estructurado formado por una secuencia de caracteres ASCII. Tipos de Acceso a los Archivosa.)Secuencial:Se accesan uno a uno los registros desde el primero hasta el último o hasta aquel que cumpla con cierta condición de búsqueda. Se permite sobre archivos de Organización secuencial y Secuencial Indexada. b.)Random:Se accesan en primera instancia la tabla de índices de manera de recuperar la dirección de inicio de bloque en donde se encuentra el registro buscado. (dentro del rea primaria o de overflow). Se permite para archivos con Organización Sec.Indexada. c.)Dinámico:Se accesan en primera instancia la tabla de índices de manera de recuperar la dirección de inicio de bloque en donde seencuentra el registro buscado. (dentro del rea primaria o de overflow). Se permite para archivos con Organización Sec.Indexada. d.)Directo:Es aquel que utiliza la función de Hashing para recuperar los registros. Sólo se permite para archivos con Organización Relativa. ConstantesLas constantes son similares a una variable pero tienen un valor determinado que se mantiene igual en toda la ejecución del programa. El contenido de una variable puede cambiar tantas veces sea necesario. ¿Porque usar una constante si no puede cambiar de valor?. Hacemos esto cuando deseamos usar un mismo número o una palabra (string) varias veces. VariablesMagnitud que puede tomar diferentes valores y se representa con una letra o letras. La variable real es el conjunto de los números reales, y se puede representar por cualquier letra o conjunto de letras y nos sirve para poder utilizar dicha letra para calculos o para obtener resultados.