En programación, una estructura de datos es una forma de organizar un conjunto de datos elementales con el objetivo de facilitar su manipulación. Un dato elemental es la mínima información que se tiene en un sistema.
Una estructura de datos define la organización e interrelación de estos y un conjunto de operaciones que se pueden realizar sobre ellos. Las operaciones básicas son:
- Alta, adicionar un nuevo valor a la estructura.
- Baja, borrar un valor de la estructura.
- Búsqueda, encontrar un determinado valor en la estructura para realizar una operación con este valor, en forma secuencial o binario (siempre y cuando los datos estén ordenados).
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.
Estructuras de datos
Definición.
Hablamos de recursividad, tanto en el ámbito informático como en el ámbito matemático, cuando definimos algo (un tipo de objetos, una propiedad o una operación) en función de sí mismo. La recursividad en programación es una herramienta sencilla, muy útil y potente.
Tipos: Hablamos de recursividad, tanto en el ámbito informático como en el ámbito matemático, cuando definimos algo (un tipo de objetos, una propiedad o una operación) en función de sí mismo. La recursividad en programación es una herramienta sencilla, muy útil y potente.
Podemos distinguir dos tipos de recursividad:
Directa: Cuando un subprograma se llama a si mismo una o mas veces directamente.
Indirecta: Cuando se definen una serie de subprogramas usándose unos a otros.
Características.
Un algoritmo recursivo consta de una parte recursiva, otra iterativa o no recursiva y una condición de terminación. La parte recursiva y la condición de terminación siempre existen. En cambio la parte no recursiva puede coincidir con la condición de terminación.
Algo muy importante a tener en cuenta cuando usemos la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos más llamadas recursivas. Si no se cumple esta condición el programa no parará nunca.
Ventajas e inconvenientes.Un algoritmo recursivo consta de una parte recursiva, otra iterativa o no recursiva y una condición de terminación. La parte recursiva y la condición de terminación siempre existen. En cambio la parte no recursiva puede coincidir con la condición de terminación.
Algo muy importante a tener en cuenta cuando usemos la recursividad es que es necesario asegurarnos que llega un momento en que no hacemos más llamadas recursivas. Si no se cumple esta condición el programa no parará nunca.
La principal ventaja es la simplicidad de comprensión y su gran potencia, favoreciendo la resolución de problemas de manera natural, sencilla y elegante; y facilidad para comprobar y convencerse de que la solución del problema es correcta.
El principal inconveniente es la ineficiencia tanto en tiempo como en memoria, dado que para permitir su uso es necesario transformar el programa recursivo en otro iterativo, que utiliza bucles y pilas para almacenar las variables.
Estructura Representación
Una tabla es una estructura homogénea en la que todos los elementos que la componen son del mismo tipo.Son estáticas, no crecen ni decrecen en tiempo de ejecución y tienen un límite preestablecido antes de la compilación.
Para acceder a los elementos de una tabla se utilizan los "índices" y estos pueden ser de cualquier tipo escalar de PASCAL (enumerados, INTEGER, CHAR, subrango, BOOLEAN).Por ello las tablas son estructuras de acceso directo o acceso por índice.
Búsqueda secuencial.
Búsqueda secuencial con centinela.
Almacenamiento externo
Usamos espacios fuera de las de la tabla para colocar las colisiones. Dentro del almacenamiento externo hay varios tipos.
Encadenamiento directo y zona de overflow.
Encadenamiento directo.
Esta realización considera la tabla como un vector en el que cada posición contiene un elemento y un campo adicional con el comienzo de la lista de elementos con los que existe colisión.Es decir, las posibles colisiones se resuelven construyendo una lista de elementos cuya imagen hash coincida.
Ventajas: eficientes y rápidos.
Inconvenientes: Para cada elemento de la lista se debe reserVAR un espacio para punteros lo que significa un desaprovechamiento de memoria en el "manejo de lista".
Zona de Overflow.
Se reserva espacio en cierta zona de externa a la propia tabla, de aproximadamente el 10% de su tamaño, para introducir las colisiones.Cada sinónimo se almacena en la primera celda disponible de la zona de overflow.
Inconveniente: Desaprovechamiento de memoria (poco).Es poco eficiente cuando se han producido colisiones, ya que la búsqueda en la zona de overflow es secuencial.
Ventajas: Ocupa menos memoria que el anterior.El algoritmo de búsqueda y de inserción es mas sencillo.
Almacenamiento interno
Cuando el espacio usado para almacenar las colisiones esta dentro de los límites de la tabla.Dentro del almacenamiento interno están:Encadenamiento directo y encadenamiento vacío.
Cuando el espacio usado para almacenar las colisiones esta dentro de los límites de la tabla.Dentro del almacenamiento interno están:Encadenamiento directo y encadenamiento vacío.
Encadenamiento directo.
Se usa dentro de la tabla un campo de tipo puntero para que apunte al siguiente colisionado, que estará dentro de la tabla.En ese campo se guarda la dirección del siguiente colisionado.
En el encadenamiento directo con zona de overflow podemos sobredimensionar la tabla para almacenar las colisiones, en esta zona las casillas estarán encadenadas con una variable que apunte al primer espacio libre de la zona de overflow.Consiste en enlazar todos los elementos cuyas claves generan igual indice primario por medio de enlaces dentro de la tabla a las nuevas posiciones ocupadas por estos elementos.
Inconvenientes: Espacio reservado en cada elemento para el enlace.
Ventajas: Más rápido que el externo con zona de overflow ya que evita la búsqueda secuencial.
Ocupación de memoria: Depende del método usado.El primer caso ocupa menos memoria, y el segundo es más rápido.
Concepto.Se usa dentro de la tabla un campo de tipo puntero para que apunte al siguiente colisionado, que estará dentro de la tabla.En ese campo se guarda la dirección del siguiente colisionado.
En el encadenamiento directo con zona de overflow podemos sobredimensionar la tabla para almacenar las colisiones, en esta zona las casillas estarán encadenadas con una variable que apunte al primer espacio libre de la zona de overflow.Consiste en enlazar todos los elementos cuyas claves generan igual indice primario por medio de enlaces dentro de la tabla a las nuevas posiciones ocupadas por estos elementos.
Inconvenientes: Espacio reservado en cada elemento para el enlace.
Ventajas: Más rápido que el externo con zona de overflow ya que evita la búsqueda secuencial.
Ocupación de memoria: Depende del método usado.El primer caso ocupa menos memoria, y el segundo es más rápido.
Una lista es una estructura de datos homogénea y dinámica, que va a estar formada por una secuencia de elementos, donde cada uno de ellos va seguido de otro o de ninguno.
Homogénea: Todos los elementos que la forman tienen el mismo tipo base.
Dinámica: Puede crecer o decrecer en tiempo de ejecución según nuestras necesidades.
dos listas pueden ser diferentes si:
No tienen el mismo número de elementos:
L1: gato, perro.
L2: gato, canario, cerdo.
Cuando, aun teniendo el mismo número de elementos, estos son distintos:
L1: gato, perro.
L2: gato, cerdo.
Cuando, aun teniendo el mismo número de elementos y siendo estos los mismos, no están dispuestos en el mismo orden.
L1: gato, perro.
L2: perro, gato.
Hay varios criterios para clasificar las listas: según su modo de acceso o según su información de acceso.
Modo De Acceso.
Atendiendo a este, se dividen en densas y enlazadas. El modo de acceso es independiente de la implementación realizada.
Listas densas
Se caracterizan porque los elementos siguen una secuencia física. Sabemos cuales es el siguiente elemento porque para acceder a él hemos tenido que pasar por todos los anteriores.
La localización de un elemento cualquiera será:
El primero si es el primer elemento de la lista.
N-esimo si para llegar a el hemos pasado por N-1 elementos.
Siguen una estructura física secuencial luego se pueden implementar utilizando ficheros, ARRAYS y punteros.
Listas enlazadas
Son aquellas en las que cada elemento que los compone contiene la información necesaria para acceder al elemento siguiente. La localización de un elemento cualquiera será:
Un elemento de la lista tendrá la dirección K si K es el primero y K es conocido (dirección de inicio).
Estará en la dir. J si J está contenida en el elemento anterior.
Informacion de acceso.
Listas ordinales
Los elementos se van colocando en la lista a medida que llegan y se identifican por el orden de llegada.El acceso a un elemento es por su orden o posición relativa dentro de la lista.
Listas calificadas
Los elementos se clasifican por una clave y pueden estar ordenados o no estarlo. A un elemento se accede por la información contenida en un campo clave.
Diferencias: En la primera clase importa en orden de llegada, mientras que en la segunda depende de la clave.
Los elementos se clasifican por una clave y pueden estar ordenados o no estarlo. A un elemento se accede por la información contenida en un campo clave.
Diferencias: En la primera clase importa en orden de llegada, mientras que en la segunda depende de la clave.
Pilas.
Una pila es una lista ordinal en la que el modo de acceso a sus elementos es del tipo LIFO. Los añadidos y extracciones de elementos de una estructura se realizan solo por un extremo, luego el único elemento accesible de la pila es el que se encuentre en la cima. Esto exigirá que la manipulación sobre un elemento, necesite que el mismo ocupe la posición de cima.
Sobre una estructura de tipo pila, surgen de forma natural las operaciones que permiten añadir elementos y quitar elementos.
Implementación utilizando tablasUna pila es una lista ordinal en la que el modo de acceso a sus elementos es del tipo LIFO. Los añadidos y extracciones de elementos de una estructura se realizan solo por un extremo, luego el único elemento accesible de la pila es el que se encuentre en la cima. Esto exigirá que la manipulación sobre un elemento, necesite que el mismo ocupe la posición de cima.
Sobre una estructura de tipo pila, surgen de forma natural las operaciones que permiten añadir elementos y quitar elementos.
Esta realización consiste en ir guardando consecutivamente los elementos de la pila en un vector de tamaño fijo. Un índice marcará la posición del último elemento que se ha añadido a la pila. Por tanto, las inserciones en la estructura se realizarán en la posición inmediatamente siguiente a la posición marcada como cima, pasando a ser esta nueva posición ocupada la nueva cima de la pila.
El hecho de utilizar un vector para almacenar los elementos, puede conducir a la situación en que la pila esté llena, es decir, que no quepa ningún elemento más. Esto se producirá cuando el índice que señala la cima de la pila sea igual al tamaño del vector.
Otros Tipos De Listas
Listas reorganizables.- Son aquellas listas en las que el último elemento consultado se sitúa al principio.
Listas circulares.- En ellas el último elemento apunta al primero.
Listas doblemente enlazadas.- Cada elemento tiene dos punteros, uno de los cuales apunta al elemento siguiente y otro al anterior.
Listas circulares doblemente enlazadas
Los árboles de grado 2 tienen una especial importancia. Se les conoce con el nombre de árboles binarios. Se define un árbol binario como un conjunto finito de elementos (nodos) que bien está vació o está formado por una raíz con dos árboles binarios disjuntos, llamados subárbol izquierdo y derecho de la raíz.
En los apartados que siguen se considerarán únicamente árboles binarios y, por lo tanto, se utilizará la palabra árbol para referirse a árbol binario. Los árboles de grado superior a 2 reciben el nombre de árboles multicamino.
Árbol binario de búsqueda.- Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subárbol izquierdo, y menor que todas las claves del subárbol derecho se dice que este árbol es un árbol binario de búsqueda.
En los apartados que siguen se considerarán únicamente árboles binarios y, por lo tanto, se utilizará la palabra árbol para referirse a árbol binario. Los árboles de grado superior a 2 reciben el nombre de árboles multicamino.
Árbol binario de búsqueda.- Los árboles binarios se utilizan frecuentemente para representar conjuntos de datos cuyos elementos se identifican por una clave única. Si el árbol está organizado de tal manera que la clave de cada nodo es mayor que todas las claves su subárbol izquierdo, y menor que todas las claves del subárbol derecho se dice que este árbol es un árbol binario de búsqueda.
Ejemplo:
Operaciones básicas.- Una tarea muy común a realizar con un árbol es ejecutar una determinada operación con cada uno de los elementos del árbol.Esta operación se considera entonces como un parámetro de una taré más general que es la visita de todos los nodos o, como se denomina usualmente, del recorrido del árbol.
Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente.
Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.
Recorrido en amplitud.- Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:
12 - 8,17 - 5,9,15
Recorrido en profundidad.- Recorre el árbol por subárboles. Hay tres formas: Preorden, orden central y postorden.
Preorden: Raiz, subárbol izquierdo y subárbol derecho.
Orden central: Subarbol izquierdo, raiz, subarbol derecho.
Postorden: Subarbol izquierdo, subarbol derecho, raiz.
Si se considera la tarea como un proceso secuencial, entonces los nodos individuales se visitan en un orden específico, y pueden considerarse como organizados según una estructura lineal. De hecho, se simplifica considerablemente la descripción de muchos algoritmos si puede hablarse del proceso del siguiente elemento en el árbol, según un cierto orden subyacente.
Hay dos formas básicas de recorrer un árbol: El recorrido en amplitud y el recorrido en profundidad.
Recorrido en amplitud.- Es aquel recorrido que recorre el árbol por niveles, en el último ejemplo sería:
12 - 8,17 - 5,9,15
Recorrido en profundidad.- Recorre el árbol por subárboles. Hay tres formas: Preorden, orden central y postorden.
Preorden: Raiz, subárbol izquierdo y subárbol derecho.
Orden central: Subarbol izquierdo, raiz, subarbol derecho.
Postorden: Subarbol izquierdo, subarbol derecho, raiz.
Ejemplo:
Preorden: 20 - 12 - 5 - 2 - 7 - 13 - 15 - 40 - 30 - 35 - 47
Orden central: 2 - 5 - 7 - 12 - 13 - 15 - 20 - 30 - 35 - 40 - 47
Postorden: 2 - 7 - 5 - 15 - 13 - 12 - 35 - 30 - 47 - 40 - 20
Ejemplo:
Preorden: / + a b * c d Notación polaca
Orden central: a + b / c * d Notación infija
Postorden: a b + c d * / Notación polaca inversa
Preorden: 20 - 12 - 5 - 2 - 7 - 13 - 15 - 40 - 30 - 35 - 47
Orden central: 2 - 5 - 7 - 12 - 13 - 15 - 20 - 30 - 35 - 40 - 47
Postorden: 2 - 7 - 5 - 15 - 13 - 12 - 35 - 30 - 47 - 40 - 20
Ejemplo:
Preorden: / + a b * c d Notación polaca
Orden central: a + b / c * d Notación infija
Postorden: a b + c d * / Notación polaca inversa
Estructura de datos
Variables
Las variables son estructura de datos usados para almacenar información. Hay dos tipos de información que puede ser almacenada: Números y texto. Antes de usar una variable ésta, deberá primero ser definida:
Dim nombre_de_variable As Tipo
Ejemplo:
Dim precio As Long
Dim nombre_de_articulo As String
Variables
Las variables son estructura de datos usados para almacenar información. Hay dos tipos de información que puede ser almacenada: Números y texto. Antes de usar una variable ésta, deberá primero ser definida:
Dim nombre_de_variable As Tipo
Ejemplo:
Dim precio As Long
Dim nombre_de_articulo As String
| Tipo | Rango permitido |
| Integer | -32,768 a 32,767 |
| Long | -2,147,483,648 a 2,147,483,647 |
| Single | -3.402823E38 a -1.401298E-45 |
| 1.401298E-45 a 3.402823E38 | |
| Double | -1.79769313486232D308 a -4.94065645841247D-324 |
| 4.94065645841247D-324 a 1.79769313486232D308 | |
| Currency | -922337203685477.5808 a 922337203685477.5807 |
| String | 0 a 65,000 bytes |
| Variant | Valores de fechas: 1/1/0000 a 12/32/9999 |
| Numérico: igual que Double | |
| Texto: Igual que String | |
| | |
| | |
| | |
| Si una nueva variable es declarada sin especificación VB por default la deberá tomar como tipo Variant | |
| | |
No hay comentarios:
Publicar un comentario