Monografias | Estructura de datos

Una base de datos de red esta formado por una colección de registros, loscuales están conectados entre sí por medio de enlaces.
Registro.- Es una colección de campos (atributos)
Campos.- Contiene almacenado solamente un valor.
Enlace.- Asociación entre dos registros, así que podemos verla como unarelación estrictamente binaria.
Estructura de datos de red, abarca más que la estructura de árbol porque unnodo "hijo" en la estructura de red puede tener más de un padre.

Diagramas de estructura de datos.
Es un esquema que representa el diseño de una base de datos de red. Este modelose basa en representaciones entre registros por medio de ligas, existenrelaciones en las que participan solo dos entidades(binarias) y relaciones enlas que participan más de dos entidades (generales) ya sea con o sin atributodescriptivo en la relación.
La forma de diagramado consta de dos componentes básicos:
Celdas: representan a los campos del registro.
Líneas: representan a los enlaces entre los registros. 
su representación gráfica se basa en el acomodo de los campos de un registro en un conjunto de celdas que se ligan con otro(s) registro(s)
Las estructuras de datos según la cardinalidad se representan en los siguientescasos:

Conceptos básicos.
Algoritmo.- Es un conjunto de reglas que permiten obtener un resultadodeterminado a partir de ciertas reglas definidas.
Algoritmo.- Es una secuencia finita de instrucciones, cada una de las cualestiene un significado preciso y puede ejecutarse con una cantidad finita deesfuerzo en un tiempo finito. Ha de tener las siguientes características:Legible, correcto, modular, eficiente, estructurado, no ambiguo y a ser posiblese ha de desarrollar en el menor tiempo posible.

Características de un algoritmo de computador:
Correcto
Legible
eficiente
Diseño de algoritmos.
Fases:
Diseño: se dan las especificaciones en lenguaje natural y se crea un primermodelo matemático apropiado. La solución en esta etapa es un algoritmoexpresado de manera muy informal.
Implementación: El programador convierte el algoritmo en código, siguiendoalguna de estas 3 metodologías.
* TOP-DOWN se alcanza el programa sustituyendo las palabras del palabras delpseudocódigo por secuencias de proposiciones cada vez mas detalladas, en unllamado refinamiento progresivo.
* BOTTON-UP parte de las herramientas mas primitivas hasta que se llega alprograma.
Pruebas: Es un material que se pasa al programa para detectar posibleserrores.Esto no quiere decir que el diseño no tenga errores, puede tenerlospara otros datos.

Definición.
Hablamos de recursividad, tanto en el ámbito informático como en el ámbitomatemático, cuando definimos algo (un tipo de objetos, una propiedad o unaoperación) en función de sí mismo. La recursividad en programación es unaherramienta sencilla, muy útil y potente.

Tipos.
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 norecursiva y una condición de terminación. La parte recursiva y la condiciónde terminación siempre existen. En cambio la parte no recursiva puede coincidircon la condición de terminación.
Algo muy importante a tener en cuenta cuando usemos la recursividad es que esnecesario asegurarnos que llega un momento en que no hacemos más llamadasrecursivas. Si no se cumple esta condición el programa no parará nunca.

Ventajas e inconvenientes.
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 escorrecta.
El principal inconveniente es la ineficiencia tanto en tiempo como en memoria,dado que para permitir su uso es necesario transformar el programa recursivo enotro 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 lacomponen son del mismo tipo.Son estáticas, no crecen ni decrecen en tiempo deejecución y tienen un límite preestablecido antes de la compilación.
Para acceder a los elementos de una tabla se utilizan los "índices" yestos pueden ser de cualquier tipo escalar de PASCAL (enumerados, INTEGER, CHAR,subrango, BOOLEAN).Por ello las tablas son estructuras de acceso directo oacceso 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 delalmacenamiento 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óncontiene un elemento y un campo adicional con el comienzo de la lista deelementos con los que existe colisión.Es decir, las posibles colisiones seresuelven 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 parapunteros lo que significa un desaprovechamiento de memoria en el "manejo delista".

Zona de Overflow. 
Se reserva espacio en cierta zona de externa a la propia tabla, deaproximadamente el 10% de su tamaño, para introducir las colisiones.Cada sinónimose almacena en la primera celda disponible de la zona de overflow.
Inconveniente: Desaprovechamiento de memoria (poco).Es poco eficiente cuando sehan producido colisiones, ya que la búsqueda en la zona de overflow essecuencial.
Ventajas: Ocupa menos memoria que el anterior.El algoritmo de búsqueda y deinserción es mas sencillo.

Almacenamiento interno
Cuando el espacio usado para almacenar las colisiones esta dentro de los límitesde la tabla.Dentro del almacenamiento interno están:Encadenamiento directo yencadenamiento vacío.

Encadenamiento directo. 
Se usa dentro de la tabla un campo de tipo puntero para que apunte al siguientecolisionado, que estará dentro de la tabla.En ese campo se guarda la direccióndel siguiente colisionado.
En el encadenamiento directo con zona de overflow podemos sobredimensionar latabla para almacenar las colisiones, en esta zona las casillas estaránencadenadas con una variable que apunte al primer espacio libre de la zona deoverflow.Consiste en enlazar todos los elementos cuyas claves generan igualindice primario por medio de enlaces dentro de la tabla a las nuevas posicionesocupadas 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úsquedasecuencial.
Ocupación de memoria: Depende del método usado.El primer caso ocupa menosmemoria, y el segundo es más rápido.

Concepto.
Una lista es una estructura de datos homogénea y dinámica, que va a estarformada por una secuencia de elementos, donde cada uno de ellos va seguido deotro 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 nuestrasnecesidades.
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, noestá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únsu información de acceso.

Modo De Acceso.
Atendiendo a este, se dividen en densas y enlazadas. El modo de acceso esindependiente de la implementación realizada.
Listas densas
Se caracterizan porque los elementos siguen una secuencia física. Sabemoscuales es el siguiente elemento porque para acceder a él hemos tenido que pasarpor 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 utilizandoficheros, ARRAYS y punteros.
Listas enlazadas
Son aquellas en las que cada elemento que los compone contiene la informaciónnecesaria para acceder al elemento siguiente. La localización de un elementocualquiera será:
Un elemento de la lista tendrá la dirección K si K es el primero y K esconocido (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 identificanpor el orden de llegada.El acceso a un elemento es por su orden o posiciónrelativa 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 lasegunda depende de la clave.

Pilas.
Una pila es una lista ordinal en la que el modo de acceso a sus elementos es deltipo LIFO. Los añadidos y extracciones de elementos de una estructura serealizan solo por un extremo, luego el único elemento accesible de la pila esel que se encuentre en la cima. Esto exigirá que la manipulación sobre unelemento, necesite que el mismo ocupe la posición de cima.
Sobre una estructura de tipo pila, surgen de forma natural las operaciones quepermiten añadir elementos y quitar elementos.

Implementación utilizando tablas 
Esta realización consiste en ir guardando consecutivamente los elementos de lapila en un vector de tamaño fijo. Un índice marcará la posición del últimoelemento que se ha añadido a la pila. Por tanto, las inserciones en laestructura se realizarán en la posición inmediatamente siguiente a la posiciónmarcada como cima, pasando a ser esta nueva posición ocupada la nueva cima dela pila.
El hecho de utilizar un vector para almacenar los elementos, puede conducir a lasituació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 altamaño del vector.

Otros Tipos De Listas
Listas reorganizables.- Son aquellas listas en las que el último elementoconsultado 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 loscuales 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 elnombre de árboles binarios. Se define un árbol binario como un conjunto finitode 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 utilizanfrecuentemente para representar conjuntos de datos cuyos elementos seidentifican por una clave única. Si el árbol está organizado de tal maneraque 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 esejecutar una determinada operación con cada uno de los elementos del árbol.Estaoperación se considera entonces como un parámetro de una taré más generalque es la visita de todos los nodos o, como se denomina usualmente, delrecorrido del árbol.
Si se considera la tarea como un proceso secuencial, entonces los nodosindividuales se visitan en un orden específico, y pueden considerarse comoorganizados según una estructura lineal. De hecho, se simplificaconsiderablemente la descripción de muchos algoritmos si puede hablarse delproceso 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 elrecorrido en profundidad.
Recorrido en amplitud.- Es aquel recorrido que recorre el árbol por niveles, enel último ejemplo sería:
12 - 8,17 - 5,9,15
Recorrido en profundidad.- Recorre el árbol por subárboles. Hay tresformas: 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

Estructura de datos
Variables
Las variables son estructura de datos usados para almacenar información. Haydos tipos de información que puede ser almacenada: Números y texto. Antes deusar una variable ésta, deberá primero ser definida:
Dim nombre_de_variable As Tipo
Ejemplo:
Dim precio As Long
Dim nombre_de_articulo As String

Una vez que una variable se ha creado, se le puede asignar un valor. Paraesto se usa el operador ' = '. En el primer ejemplo de abajo a una variable sele asigna un valor constante, mientras que en el segundo se le asigna elcontenido de una variable multiplicada por 10.
Ejemplo 1: precio = 29.95
Ejemplo 2: precio_total = precio * 10
El Alcance de una variable es definido como su rango de operación. Hay trestipos de alcance en una variable:

1. Local - La variable solo puede ser usada en el procedimiento actual ( use Dim dentro del procedimiento requerido).
2. Módulo - La variables pueden ser accesadas desde cualquier procedieminento de la forma actual (use Dim dentro de la sección de Declaraciones Generales de la forma).
3. Global - Pueden ser accesados desde cualquier procedimiento y desde cualquier forma. (usa Global dentro de la sección de Declaraciones Generales de un módulo).

Variables Estáticas
El declarar variables y arreglos como local en un procedimieneto/función es muyusado, porque esto minimíza los efectos extraños que pueden ocurrir cuando seusan variables globales. Sin embargo, cuando usamos una variable local en unprocedimiento VB crea un espacio de memoria para mantener el valor de estavariable , esto sucede cuando lee el estatuto Dim, pero cuando llega al finaldel procedimiento (End Sub) VB libera el espacio asigndo para el valor de lavariable local. Agrega el siguiente código a un botón de comando y observa quevalores son impresos:
Sub Command1_Click ()
Dim numero As Integer ' Crea una variable Local normal
numero = numero + 1
Print numero
End Sub

Después de dar clic varias veces al botón de comando deberás ver unacolumna de unos en el lado izquierdo de la forma. El valor nunca será arriba deuno a pesar de que el valor de la variable se incrementa en uno cada vez. Estoes porque cada vez que el procediemineto es llamado, haciendo clic en el botón,VB esta trabajan con una variable diferente. Esta tiene exactamente el mismonombre en el programa pero es una variable completamente diferente. Para queesto no suceda así, introduce Staticen el lugar de Dim:
Sub Command1_Click ()
Static numero As Integer ' Crea una variable estática local
numero = numero + 1
Print numero
End Sub

Ahora en vez de que el valor de la variable se pierda cuando el procedimientotermina, con este cambio (static) su valor permanecerá hasta que todo elprograma termine. De esta manera, podemos ver una lista de números que seincrementan en uno cada vez que se le da clic al botón de comando.
Nota: La nueva variable estática es una variable de alcance local, si cualquierprocedimiento trata de accesar esta variable no prodrá lograrlo. Agrega a laforma un nuevo botón de comando, el cual deberá tener un nuevo procedimiento'Click', y trata de corregir o imprimir el valor de la variable estática quecontiene el primer botón.
El contenido de un arreglo local, también puede mantenerse mientras el programase ejecute. Para hacer esto agrega el estatuto 'Static' en lugar de 'Dim' comolo hicimos en el ejemplo de arriba.
Static salarios(199) As Long

Las constantes son similares a una variable pero tienen un valor determinadoque se mantiene igual en toda la ejecución del programa. El contenido de unavarible puede cambiar tantas veces sea necesario. ¿Porque usar una constante sino puede cambiar de valor?. Hacemos esto cuando deseamos usar un mismo número ouna palabra (string) varias veces. Por ejemplo, en un programa para calcular losimpuestos de todo el año, deberá hacer referencia a un valor en varias partesdel programa, que puede ser el por ciento de impuesto mensual con respecto a lasganancias. Par ello podemos usar una variable llamada IMP, que mantendrá elvalor en el evento Form_Load.
En el siguiente ejemplo definimos una contante llamada ' IMP ' y le asignamos elvalor de 1.175. Ese es usado en estatuto Print con la variable pago_total paracalcular la cantidad total a pagar. Note que en lugar de escribir 1.175 en la fórmulanos referimos a el nombre de la constante.

Ejemplo:
Const IMP = 1.175 ' Declara y asigna un valor a la constante
Dim pago_total As Currency ' Declara una variable local para almacenar el totala pagar
pago_total = 560.95
Print "Total = "; pago_total * IMP
Como las variables las constantes también tiene reglas de alcance. Hayconstantes globales que pueden ser accesadas por cualquier módulo o cualquierforma del proyecto, las constantes de módulo solo son accesadas por la foma quelos contiene, y las contantes locales son accesadas solamente por el objetoactual o procedimiento/función.

1. Local - usa 'Const' dentro del procedimiento requerido.
2. Módulo - usa 'Const' dentro de la sección deDeclaraciones Generales de una forma o módulo.
3. Global - usa 'Global Const' dentro de la sección deDeclaraciones Generales de un módulo (ésto es Module1.bas).

Arreglos (arrays)
La variables son muy usadas para lamacenar pequeñas cantidades de información,pero no son convenientes para grandes cantidades de información muy similar.Por ejemplo, para almacenar los salarios de doscientos empleados, necesitaremos200 variables diferentes. Una mejor forma de almacenar esta información seráusra una estructura de datos llamada arreglos array.
Un arreglo es similar a las celdas en un panal de abejas. Todo el arreglo tieneun nombre, y cada celda tiene una dirección. Para el problema de los salariosplanteado arriba, un arreglo el cual tiene 200 elementos (celdas) , usaremos elcomando Dim para cerar un nueva variable, pero marcaremos también el tamaño deesta variable .
Dim nombre_del_arreglo (tamaño) [As Tipo]
Ejemplo: Dim salarios(199) As Long
En el ejemplo de arriba creamos un arreglo con 200 elementos. El tamaño marcadoes de 199 porque por default VB empieza la numeración con 0.
Si sabemos que el nombre 'Jaime ' es el empleado número 24 y tiene un salariode 25,000 pesos mensuales, podemos lintroducir esta cantidad en el arreglo de lasiguiente forma:
salarios(23) = 25000
Contrario a lo anterior, si deseamos saber cula es el salario del empleado número189, podemos usar:
lblvalor.Caption = salarios(188)
Nota: En los dos ejemplos anteriores, para accesar un elemento es necesariocolocar el número del elemento anterior (si deseamos el 150, pedimos el 149).esto es VB empieza un arreglo de 0, no de 1. Sin embargo VB pude ser forzado aempezar con 1, agregando el estatuto 'Option Base 1' en la sección dedeclaraciones generales de la forma o el módulo.