Monografias.com > Computación > Programación
Descargar Imprimir Comentar Ver trabajos relacionados

Estructura de datos




Enviado por germany0116



    Indice
    1. Base
    De Datos

    2. Recursividad
    3. Lista
    4. Árboles
    binarios.

    5. Variables
    Constantes

    1. Base De
    Datos

    Una base de datos de
    red esta formado
    por una colección de registros, los
    cuales 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 una relación
    estrictamente binaria.
    Estructura de
    datos de red, abarca más que
    la estructura de
    árbol porque un nodo "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 modelo se basa
    en representaciones entre registros por medio de ligas, existen
    relaciones en las que participan solo dos entidades(binarias) y
    relaciones en las que participan más de dos entidades
    (generales) ya sea con o sin atributo descriptivo 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 siguientes
    casos:

    Conceptos básicos.
    Algoritmo.- Es
    un conjunto de reglas que permiten obtener un resultado
    determinado a partir de ciertas reglas definidas.
    Algoritmo.- Es
    una secuencia finita de instrucciones, cada una de las cuales
    tiene un significado preciso y puede ejecutarse con una cantidad
    finita de esfuerzo en un tiempo finito. Ha
    de tener las siguientes características: Legible, correcto,
    modular, eficiente, estructurado, no ambiguo y a ser posible se
    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 primer modelo
    matemático apropiado. La solución en esta etapa es
    un algoritmo expresado de manera muy informal.
    Implementación: El programador convierte el algoritmo en
    código,
    siguiendo alguna de estas 3 metodologías.
    * TOP-DOWN se alcanza el programa
    sustituyendo las palabras del palabras del pseudocódigo
    por secuencias de proposiciones cada vez mas detalladas, en un
    llamado refinamiento progresivo.
    * BOTTON-UP parte de las herramientas
    mas primitivas hasta que se llega al programa.
    Pruebas: Es un
    material que se pasa al programa para detectar posibles
    errores.Esto no quiere decir que el diseño no tenga
    errores, puede tenerlos para otros datos.

    2.
    Recursividad

    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.
    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.
    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.

    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.

    3. Lista

    Concepto.
    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.

    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 tablas 
    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

    4. Árboles
    binarios.

    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.

    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.

    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. 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

    Una vez que una variable se ha creado, se le puede
    asignar un valor. Para
    esto se usa el operador ' = '. En el primer ejemplo de abajo a
    una variable se le asigna un valor constante, mientras que en el
    segundo se le asigna el contenido 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 tres tipos 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
    muy usado, porque esto minimíza los efectos
    extraños que pueden ocurrir cuando se usan variables
    globales. Sin embargo, cuando usamos una variable local en un
    procedimiento VB crea un espacio de memoria para mantener el
    valor de esta variable , esto sucede cuando lee el estatuto Dim,
    pero cuando llega al final del procedimiento (End Sub) VB libera
    el espacio asigndo para el valor de la variable local. Agrega el
    siguiente código
    a un botón de comando y observa que valores 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 una columna de unos en el lado
    izquierdo de la forma. El valor nunca será arriba de uno a
    pesar de que el valor de la variable se incrementa en uno cada
    vez. Esto es 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 mismo nombre en el
    programa pero es una variable completamente diferente. Para que
    esto 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 procedimiento termina, con este cambio
    (static) su valor permanecerá hasta que todo el programa
    termine. De esta manera, podemos ver una lista de números
    que se incrementan 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 cualquier procedimiento
    trata de accesar esta variable no prodrá lograrlo. Agrega
    a la forma 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 que
    contiene el primer botón.
    El contenido de un arreglo local, también puede mantenerse
    mientras el programa se ejecute. Para hacer esto agrega el
    estatuto 'Static' en lugar de 'Dim' como lo hicimos en el ejemplo
    de arriba.
    Static salarios(199) As
    Long

    5. Variables
    Constantes

    Las 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 varible 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. Por ejemplo, en un programa para calcular los
    impuestos de
    todo el año, deberá hacer referencia a un valor en
    varias partes del programa, que puede ser el por ciento de
    impuesto
    mensual con respecto a las ganancias. Par ello podemos usar una
    variable llamada IMP, que mantendrá el valor en el evento
    Form_Load.
    En el siguiente ejemplo definimos una contante llamada ' IMP ' y
    le asignamos el valor de 1.175. Ese es usado en estatuto Print
    con la variable pago_total para calcular la cantidad total a
    pagar. Note que en lugar de escribir 1.175 en la fórmula
    nos 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 total a pagar
    pago_total = 560.95
    Print "Total = "; pago_total * IMP
    Como las variables las constantes también tiene reglas de
    alcance. Hay constantes globales que pueden ser accesadas por
    cualquier módulo o cualquier forma del proyecto, las
    constantes de módulo solo son accesadas por la foma que
    los contiene, y las contantes locales son accesadas solamente por
    el objeto actual 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, necesitaremos 200 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 tiene un nombre, y cada celda tiene una dirección.
    Para el problema de los salarios planteado arriba, un arreglo el
    cual tiene 200 elementos (celdas) , usaremos el comando Dim para
    cerar un nueva variable, pero marcaremos también el
    tamaño de esta 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 marcado es 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 salario de 25,000
    pesos mensuales, podemos lintroducir esta cantidad en el arreglo
    de la siguiente forma:
    salarios(23) = 25000
    Contrario a lo anterior, si deseamos saber cula es el salario del
    empleado número 189, podemos usar:
    lblvalor.Caption = salarios(188)
    Nota: En los dos ejemplos anteriores, para accesar un elemento es
    necesario colocar 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 a empezar con 1,
    agregando el estatuto 'Option Base 1' en la sección de
    declaraciones generales de la forma o el
    módulo.

     

     

     

    Autor:

    Ist Cepea Lima – Perú
    Bermúdez Moncada, Isabel
    Chumpitaz Heirisman, Roel

    Guevara Retamozo Miguel
    Salazar Beaumont Blanco, Enrique

    Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.

    Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

    Categorias
    Newsletter