Conceptos Clave sobre Tipos de Datos Abstractos y Estructuras de Datos
Enviado por Programa Chuletas y clasificado en Informática y Telecomunicaciones
Escrito el en español con un tamaño de 18,85 KB
1. Abstracción y sus Tipos
La abstracción es un proceso mental que se utiliza para comprender fenómenos o situaciones que involucran una gran cantidad de detalles. Consta de dos aspectos:
- Destacar los detalles más relevantes del objeto en estudio.
- Ignorar los detalles irrelevantes del objeto (en ese nivel de abstracción).
La abstracción es fundamental para diseñar programas más cortos, legibles, fáciles de mantener y fiables, es decir, software de calidad.
Los lenguajes de programación son la herramienta usada por los programadores para poder implementar dichos modelos abstractos. Se dividen en dos tipos:
- Abstracción operacional: Se basa en el uso de procedimientos y/o funciones sin preocuparnos en cómo están implementadas. Se destaca qué hace y se ignora cómo se hace.
- Abstracción de datos: Es la técnica de programación que permite inventar o definir nuevos tipos de datos adecuados a la aplicación que se desea realizar.
2. Ocultación en C
Mediante la abstracción de las implementaciones de las operaciones, debería ser también la ocultación de los tipos de datos, pero esto en C no es posible ya que no podemos ocultar el archivo cabecera “*.h”. Las implementaciones se introducen en un archivo “*.c” oculto (que sería el archivo “.o” de ese fichero) y se le proporcionaría al usuario del TAD especificándole las operaciones que puede utilizar.
3. Relación entre Ocultación e Independencia de la Información
Sí, ya que gracias a la ocultación de la información conseguimos que sea independiente su especificación de su implementación.
4. Origen de la Utilización de Ficheros
Por tres causas:
- Volatilidad de la memoria principal (cuando finaliza el programa, toda la información y el contenido de las variables que se han utilizado en él desaparecen).
- Su escaso tamaño.
- Su coste por Byte.
5. Representación Pseudoestática de un TAD Pila
Cuando sea conveniente emplear pilas de diferentes tamaños en un programa. En esta representación el tamaño máximo de una pila no es el mismo para todas las pilas y se fijará en tiempo de ejecución en el momento de crearla, es decir, se preguntará al usuario el tamaño de la pila que en ese momento vaya a crear. Pero este tamaño será fijo durante todo el tiempo de la pila.
6. Representación Dinámica de un TAD Pila
Cuando no sabemos de antemano el número de elementos que podría tener una pila, es decir, cuando el tamaño de las pilas creadas en nuestra aplicación sea variable con lo cual se incrementará o decrementará su tamaño conforme sea necesario en tiempo de ejecución.
7. Representación Estática de un TAD Pila
Cuando el tamaño de todas las pilas que necesitemos en nuestra aplicación sea el mismo. La representación estática requiere saber el tamaño máximo en tiempo de compilación (de antemano sabremos la cantidad de elementos que van a tener las pilas empleadas en dicha aplicación).
8. Representación Dinámica de un TAD Pila como Puntero
La razón de introducir un puntero es hacer que el paso de parámetros a las operaciones del TAD sea por referencia, de modo que los cambios en los parámetros formales sean reflejados en los parámetros reales.
9. Paso por Referencia en Representaciones Estática y Pseudoestática de un TAD Pila
Esto es debido al principio de independencia de la representación. Una forma de hacerlo es definir un puntero a las estructuras de datos diseñadas. Así se obtienen dos ventajas:
- El paso por referencia queda oculto a la implementación del TAD y es transparente para el usuario del mismo.
- Se ahorra la memoria de los datos que se duplican mientras que se ejecuta una función debido a que, cuando se ejecuta la llamada a una función, la transferencia de parámetros se hace siempre por valor, lo cual provoca que los parámetros reales se copien en los formales.
Al definir el tipo pila como un puntero al registro que representa a la pila, solo se hace una copia de este puntero y no del registro completo.
10. Pila con Lista Doblemente Enlazada
No tiene sentido, ya que una lista doblemente enlazada requiere un doble puntero, uno para el elemento siguiente y otro para el anterior. Esto es un gasto innecesario ya que en la pila solo insertamos o eliminamos por el tope. Por lo tanto, con un solo puntero es suficiente.
Además, en una pila no tenemos el concepto de posición, ya que solo podemos insertar por la cima y eliminar por la misma, mientras que en la lista podemos hacer una inserción o eliminación en cualquier posición mientras que, como dijimos antes, en la pila sólo podemos por el tope, ya que es una condición necesaria del TAD pila.
11. Representación Pseudoestática: Ventajas e Inconvenientes
Ventajas: Relativo a la pila estática, la pila pseudoestática nos permite fijar distintos tamaños para las pilas de la aplicación en tiempo de ejecución, por lo que un tamaño inicial no determinará el tamaño de todas las pilas. Ocupa menos espacio que la implementación del TAD pila mediante celdas enlazadas ya que no requiere un puntero por elemento.
Inconvenientes: Tamaño constante durante la vida de cada pila, tamaño que tenemos que ir controlando para no sobrepasarlo.
12. Representación Circular del TAD Pila
Tal y como se define el TAD pila, una pila es una secuencia de elementos de un tipo determinado, en la cual se puede añadir y eliminar elementos sólo por uno de sus extremos llamado tope o cima, por lo tanto, carecería de sentido utilizar un puntero que se utilizara para apuntar a la base de la pila (primer elemento que se introduciría en ella). En cualquier caso, ese TAD lo utilizaríamos para obtener el elemento base de la pila, pero por otra parte, tendríamos que cambiar operaciones del TAD pila como la función FIN (habría que reimplementarla).
13. Nodo Cabecera en el TAD Cola
El nodo cabecera no se utiliza en el TAD cola, es innecesario dado que ésta surge para resolver un problema de independencia de la representación en el TAD lista, cuando definimos la posición en una lista.
14. Origen del Nodo Cabecera en las Listas
Cuando implementamos la lista con celdas enlazadas, se nos plantea un problema de independencia de la representación en lo que se referencia a la utilización de tipo de dato posición.
Por ejemplo, en la operación Insertar del TAD Lista, cuando vamos a insertar en la posición “p”, el elemento que ocupa dicha posición (si lo hubiera) pasaría a ser la posición “p+1” y el nuevo elemento que vamos a insertar, obviamente, ocuparía la posición “p”. Ocurre un problema y es que, además de hacer esta operación, la posición apuntaría al elemento que ocupa la posición “p+1” y esto no debe ser así, es decir, debería de apuntar a la posición insertada, a la posición “p”. Por esta razón, se debe de modificar dicho puntero para que apunte donde debería de apuntar y se pasaría en la cabecera de la función como “posición *p”, y no estaríamos cumpliendo con la especificación del TAD lista. Para arreglar este problema, hacemos que cada elemento de la lista se referencie mediante su nodo anterior, con lo que acarrea el problema de que, el primer elemento no tenga anterior, luego se crea el nodo cabecera y, en consecuencia, también respetaríamos la especificación del TAD lista.
15. Definición de Fichero
Es un lugar, en el que, con una cierta organización, se encuentra información sobre un tema en concreto. Desde el punto de vista informático, es un conjunto de registros homogéneos, almacenados en un soporte externo, que presentan entre sí una relación lógica y que pueden ser consultados individualmente de forma iterativa y sistemática.
16. Definición de Registro
Un registro es una colección de información relativa a una entidad particular.
17. Fichero Externo vs. Fichero Interno
Fichero externo: Estructura de datos utilizada para almacenar información en memoria secundaria.
Fichero interno: Variable que representa la estructura en memoria principal para poder procesar la información en una aplicación.
18. Organización de Ficheros y sus Tipos
La organización de un fichero es la forma particular en que los datos (los registros) son almacenados en el soporte de almacenamiento. El tipo de organización se decide durante la creación del fichero.
- Organización secuencial: Este tipo de organización se caracteriza porque los registros que forman un fichero que la utiliza (fichero secuencial), se escriben o se graban lógicamente (no tiene por qué ser físicamente) en posiciones contiguas en la misma secuencia u orden en que han sido introducidos. Para acceder al fichero “n”, habría que pasar por los “n-1” ficheros anteriores. El orden de esta operación sería lineal.
- Organización directa: Un fichero con organización directa se caracteriza porque es posible acceder a cualquier registro directamente mediante la posición que ocupa dentro del fichero.
- Hashing: La posición en la que se almacena un registro viene determinada por los valores de los campos del mismo mediante una función matemática.
- Organización secuencial indexada: En un fichero con esta organización los registros se organizan de forma secuencial, pero además se utiliza un índice que nos permite obtener la ubicación de un registro dentro del fichero sin tener que leer los ficheros que le preceden.
19. Especificación Semántica
La especificación semántica van a ser una serie de pautas las cuales van a expresar el significado de cada una de las operaciones de un TAD. Se puede expresar de múltiples formas:
- Mediante el lenguaje natural (aunque ello pueda producir ambigüedad).
- Mediante un lenguaje algebraico, que consiste en dar un conjunto de axiomas que verifican las operaciones asociadas a los objetos en cuestión.
- Mediante el uso de modelos abstractos (donde definimos el dominio y las operaciones de un tipo).
En cualquier caso, podemos hacerlo mediante precondiciones y postcondiciones, es decir, bajo el cumplimiento de las precondiciones, se puede realizar la operación y después de la ejecución de las misma, se deben cumplir las postcondiciones.
Especificación semántica:
Representa el escenario de prueba de comportamiento de cada uno de los métodos especificados en la especificación sintáctica, así como los valores o resultados que ellos deben arrogar en cada una de las invocaciones que se ejecuten sobre una instancia del tipo de dato abstracto.
20. Especificación Sintáctica
La especificación sintáctica van a ser una serie de reglas a seguir para realizar una determinada acción, es decir, consistirá en determinar la forma en que se han de escribir las operaciones, dando el orden y el tipo de operandos y resultado.
Especificación sintáctica
Se refiere a la definición formal del conjunto de métodos o procedimientos válidos capaces de acceder de manera única a los elementos de datos o estructura de datos del tipo de dato abstracto.
El conjunto de métodos se puede clasificar de la siguiente manera:
- Constructor por defecto: Inicializa la instancia con valores estáticos definidos por el usuario en el código del constructor. Aparta memoria principal.
- Constructor paramétrico: Permite inicializar la instancia con valores suministrados por el usuario por medio de parámetros.
- Método de acceso: Permite acceder a los valores almacenados en cada uno de los componentes de datos que conforman el tipo de dato abstracto.
- Método de transformación: Permite modificar y alterar el contenido actual de los componentes del tipo de dato abstracto.
- Método destructor: Permite liberar la memoria ocupada por una instancia del tipo de dato abstracto. Libera memoria principal.
Operaciones creadoras, consultoras, destructoras y modificadoras.
21. Escritura sobre un Registro Marcado como Borrado Lógico
Si no uso los TAD ficheros, puedo acceder al registro que quiera. Pero aquí estamos usando los TAD y la respuesta depende del TAD que usemos:
- Si la organización es secuencial no se puede pues el TAD ficheroSecuencial utiliza el borrado lógico para borrar un registro. Un vez borrado, no se puede acceder a él. Un registro borrado, si lo quieres dar de alta, lo añadirás al final de fichero.
- Si la organización es directa, si es posible, pues uno puede borrar o añadir un registro en una posición concreta tantas veces sea necesario. De hecho el fichero directo se inicializa a todo marcado como borrado.
- Si la organización es secuencial-indexada tampoco se puede pues una vez marcado como borrado, no se puede a acceder a esa posición ya que desaparece del índice.
22. Diferencia entre la Posición Activa en Secuencial y Secuencial Indexado
En el secuencial, la posición activa es el siguiente registro que no esté marcado como borrado. Estará algunos registros más 'abajo' de la posición actual. En la indexada es el siguiente registro según el orden que indique el índice, puede estar antes o después de la posición activa actual pues la siguiente posición dependerá del orden que indique el índice.
23. Acceso Directo sobre un Soporte Direccionable
Evidentemente. Para que haya acceso directo, el soporte debe ser direccionable. El soporte influye en la organización. Si el soporte no es direccionable, no puedes tener organización directa, sólo secuencial. Si el soporte es direccionable, puedes tener todas las organizaciones.
24. Evitar Coste O(n) en Inserciones y Borrados en los Extremos de una Lista (Vector)
Si es el los extremos, podría evitarse añadiendo a la estructura dos campos enteros indicando dónde están los extremos e inicializarlo a n/2 y (n/2+1) por ejemplo. A medida que se van insertando y borrando, se actualizan los valores de los extremos. Por ejemplo si quiero insertar al principio de la lista haría:
V[extremoDerecho]=Elemento;
extremoDerecho=extremoDerecho-1.
En todas las operaciones la lista estaría comprendida entre extremoDerecho e extremoIzquierdo y habría que controlar sus valores. Así para insertar en la posición 3 de la lista seria en extremoDerecho+3, siempre y cuando este valor esté en los límites adecuados.
25. Marcado de Registros Eliminados en Fichero Secuencial Indexado
Mira la operación EliminarFichSecInd. Verás que sólo se elimina en el índice.
26. Diferencias en la Activación de la Variable de Posición Activa en Ficheros Directos y Secuenciales Indexados
Mira la estructura de los dos TAD en el directo se define como int *activo y en el secuencial indexado es TipoIndice *indice. Su significado es distinto, el primero indica los registros que están o no borrados y en el segundo es un índice. De aquí sacas todas las diferencias.
27. Condición para Búsqueda Logarítmica en una Lista
¿Cómo vas a hacer en una lista que es una estructura secuencial, una búsqueda logarítmica?. No se puede. Ya que la inserción no tiene porque ordenarse además, para poder hacerlo de forma vectorial, el vector no va a estar lleno porque son las operaciones que están implementadas.
28. Orden de Inserción en Ficheros Indexados
En los ficheros indexados tienes un campo clave, los cuales están ordenados. Realizar su búsqueda seria en O( log n), porque se usa la búsqueda dicotómica pero al insertar el campo clave, hay que desplazarlos todos una posición hacia abajo, por tanto, ¿Qué ocurre si hay que insertarlo en la primera posición? Que hay que hacer “n” desplazamientos, luego es de O(n).
Si insertas, eso implica un desplazamiento de todos los elementos un lugar hacia abajo, y en el peor caso, que sea al inicio, habría que hacer “n-1” desplazamientos, es decir, O(n) como O ( n ) > O ( log n), este procedimiento es de O(n).
29. Lectura de un Registro Borrado en un Fichero Secuencial
Si el que lo utiliza es el usuario, no podrá leerlo, ya que no conoce la implementación, es decir, como queda oculta no puede leerlo. Sin embargo, si es el diseñador del TAD, si lo puede leer, ya que los borrados son lógicos, es decir, un campo que indique si el fichero se puede leer o no.
Como el borrado es lógico, si que se podría leer el registro, pero habría que conocer su implementación, es decir, habría que ser el diseñador del TAD y no el usuario, ya que este no tiene conocimiento de este, pues esta oculta.
30. Diferencia entre la Actualización de Posición Activa en Ficheros Directos e Indexados
En la actualización de ficheros directos, como su posición no tienen porque estar ordenados, ni seguir un orden, puede ser cualquiera la siguiente posición activa, mientras que, como los ficheros indexados si están ordenados, la posición activa es la siguiente del campo clave y si la hacemos circular, ademas, tampoco tenemos que tratar de forma distinta el nodo final, ya que todos tiene un sucesor.
31. Eliminación de un Elemento Cualquiera de una Cola/Pila
No se puede, en la cola se introduce por un extremo y se saca por el otro, en una pila se introduce y se saca por el mismo extremo.
32. Necesidad de la Función 'igual' en Listas
Para buscar la posición de un elemento compara los elementos, puede ser el tipo del elemento sea tipo estructurado y no se puedan comparar elementos con el operador ==.
33. Orden de Inserción en un Fichero Secuencial Indexado
Es O(n) ya que puede que se tenga que recorrer el vector al colocar el índice en el vector de indices.
34. Principio Fundamental de los TAD: Independencia de la Representación
Independientemente de cómo se represente el TAD, la especificación no cambia. Por ello un usuario puede usar un TAD sin importarle como está implementado o bien si la implementación cambia no afecta a la especificación.
35. Doble Puntero en la Definición del Tipo Listas
Porque si se inserta el primer elemento cuando la lista está vacía no se modificaría. Además de ésta forma se respeta la especificación.
36. Decisiones de Diseño ante la No Verificación de Precondiciones
Lo ideal sería que diese un error. Dependiendo de la gravedad que puede derivar el error al resto de la aplicación, recomendaría que si fuese alto, daría por concluida la continuidad de la aplicación y terminaría inminentemente con su ejecución.