Upload
miguel-collington
View
140
Download
0
Embed Size (px)
Citation preview
República Bolivariana de VenezuelaRepública Bolivariana de VenezuelaMinisterio del Poder Popular para la Educación SuperiorMinisterio del Poder Popular para la Educación Superior
I.U.P. “Santiago Mariño”I.U.P. “Santiago Mariño”Sistemas OperativosSistemas Operativos
ESTRUCTURA DE DATOS Y SU RELACIÓN CON LOS ESTRUCTURA DE DATOS Y SU RELACIÓN CON LOS SISTEMAS OPERATIVOSSISTEMAS OPERATIVOS
Integrantes:Integrantes:Ing. Miguel Ramírez C.I. 21.354.096Ing. Miguel Ramírez C.I. 21.354.096Ing. Alejandro Pérez C.I. 18.285.681Ing. Alejandro Pérez C.I. 18.285.681
Maracaibo, Junio 2013Maracaibo, Junio 2013
Ing. Miguel Ramírez
C.I. 21.354.096
Ing. Alejandro Pérez
C.I. 18.285.681
Estructura de Datos
La información que se procesa en la computadora es un conjunto de datos, que pueden ser simples o estructurados. Los datos simples son aquellos que ocupan sólo una localidad de memoria, mientras que los estructurados son un conjunto de casillas de memoria a las cuales hacemos referencia mediante un identificador único.
Debido a que por lo general tenemos que tratar con conjuntos de datos y no con datos simples (enteros, reales, booleanos, etc.) que por sí solos no nos dicen nada, ni nos sirven de mucho, es necesario tratar con estructuras de datos adecuadas a cada necesidad.
Ing. Miguel Ramírez
Estructura de Datos
Las estructuras de datos son una colección de datos cuya organización 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 colocación de los elementos y la manera en que se accede a ellos puede ser encapsulada.
Ing. Miguel Ramírez
Estructura de Datos
Otras 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
relación a la simplicidad y eficiencia para la realización de cada operación. De esta forma, la elección de la estructura de datos apropiada para cada problema depende de factores como la frecuencia y el orden en que se realiza cada operación sobre los datos.
Ing. Miguel Ramírez
Tipos de datos elementales
Binarios
• Bit
• Byte Numéricos
• Entero
• Real Alfanuméricos
• Carácter
• Cadena Ing. Miguel Ramírez
Estructura de Datos
Vectores (matriz o array) Registro (estructura de datos) Listas Enlazadas
• Listas Simples • Listas Dobles • Listas Circulares • Listas por saltos (Skip lists)
Pilas (stack) Colas (queue) Árboles
Tipos de Estructura de Datos
Estructuras de datos estáticas
Estructuras de datos dinámicas
Clasificación de los Tipos de Datos
Tipos de Datos
Estáticos
Simples
Dinámicos
Cadena Estructu-rados
Puntero
-Ordinales:IntegerBoleanCharEnumeradosSubrango
-No OrdinalesReales
Arrays RegistrosArchivos
Procedimientos
Vectores (Matriz o array)Es una zona de almacenamiento continuo, que contiene una serie de elementos del mismo tipo, los
elementos de la matriz. Desde el punto de vista lógico una matriz se puede ver como un conjunto de elementos ordenados en fila (o filas y columnas si tuviera dos dimensiones).
En principio, se puede considerar que todas las matrices son de una dimensión, la dimensión principal, pero los elementos de dicha fila pueden ser a su vez matrices (un proceso que puede ser recursivo), lo que nos permite hablar de la existencia de matrices multidimensionales, aunque las más fáciles de imaginar son los de una, dos y tres dimensiones.
Arreglo Unidimensional
Arreglo Bidimensional
Ing. Alejandro PérezAtrás
Registro (estructura de datos)
Registros es un tipo de datos formado por una colección finita de elementos no necesariamente homogéneos.
El acceso se realiza a través de una referencia al nombre del registro seguido del campo específico al que se desea acceder y delimitado por un punto.
Atrás
Ing. Alejandro Pérez
Atrás
Listas enlazadas
En una lista enlazada, los datos se almacenan dinámicamente y cada nodo se crea conforme se necesita. Las listas de datos pueden almacenarse en arreglos, pero las listas enlazadas proporcionan varias ventajas. Una lista enlazada es adecuada cuando es impredecible el número de datos a almacenar en la estructura. Las listas enlazadas pueden mantenerse de forma ordenada simplemente insertando cada nuevo dato en el punto adecuado de la lista sin necesidad de mover los elementos existentes en la lista.
Las listas enlazadas tienen la desventaja que por cada dato de la lista requiere de un espacio de memoria para el enlace al próximo dato, adicionalmente la asignación dinámica de memoria incurre en la sobrecarga de llamadas a función a diferencia del acceso a un elemento de un arreglo, que se realiza directamente calculando la posición del elemento con respecto a la dirección de inicio del arreglo.
Ing. Miguel Ramírez
Atrás
Pilas (stack)
Una pila (stack) es un tipo especial de una lista enlazada, ya que los nuevos nodos sólo pueden agregarse o eliminarse por la cabecera de la lista, generalmente llamado tope o cima de la pila. Se caracteriza por ser una estructura LIFO (último en entrar primero en salir, Last Input First Output).
A la derecha podemos observar la implementación de una pila en una lista enlazada.
Ing. Miguel Ramírez
Atrás
Colas (queue)
Una cola (queue) es similar a una cola de personas para comprar entradas al cine, la primera persona que está en la cola, es la primera en ser atendida, las nuevas personas que lleguen deben agregarse al final de la cola. En una cola implementada con una lista enlazada, los nodos de una cola se eliminan solamente desde el inicio de la lista y se insertan solamente al final de la lista. Se caracteriza por ser una estructura FIFO (primero en entrar primero en salir, First Input First Output).
Atrás
Árboles Pueden usarse los árboles para
representar la información en una estructura jerárquica. Los árboles pueden procesarse en forma recursiva y son muy adaptables a pruebas matemáticas. El estudio de árboles ilustra las conexiones entre varios temas de la matemática discreta y ofrece oportunidades para aprovechar la matemática formal en la programación práctica. La idea de estructura jerárquica es muy usada en la práctica. Por ejemplo, los libros son a menudo organizados como una sucesión de capítulos cada uno de los cuales son una sucesión de secciones que puede tener subdivisiones, y así sucesivamente. Una empresa puede organizarse como las colecciones de unidades comerciales cada uno de las cuales pueden tener varias secciones. Las secciones, a su vez, pueden tener secciones múltiples, y así sucesivamente.
Ing. Alejandro Perez
Atrás
Tipos de estructura de datos• Estructura de Datos Estáticas:
Son aquellas en las que el tamaño ocupado en memoria se define antes de que el programa se ejecute y no puede modificarse dicho tamaño durante la ejecución del programa.
Estas estructuras están implementadas en casi todos los lenguajes.Su principal característica es que ocupan solo una casilla de memoria, por lo tanto una variable simple hace referencia a un único valor a la vez, dentro de este grupo de datos se encuentra:
- Enteros- Reales- Caracteres- Boléanos- Enumerados- SubrangosNota: Los últimos no existen en algunos lenguajes de programación.
Ing. Miguel Ramírez
Tipos de estructura de datos
• Estructura de Datos Dinámicas:
No tienen las limitaciones o restricciones en el tamaño de memoria ocupada que son propias de las estructuras
estáticas.Mediante el uso de un tipo de datos especifico, denominado puntero, es posible construir estructuras de datos dinámicas que no son soportadas por la mayoría de los lenguajes, pero que en aquellos que si tienen estas características ofrecen soluciones eficaces y efectivas en la solución de problemas complejos.Se caracteriza por el hecho de que con un nombre se hace referencia a un grupo de casillas de memoria, es decir un dato estructurado tiene varios componentes.
Ing. Alejandro Pérez