ESTRUCTURAS
1. Base De DatosUna
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:CorrectoLegibleeficienteDiseñ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.
RecursividadDefinició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ónUna
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 externoUsamos 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 internoCuando 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. ListaConcepto.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 densasSe
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 enlazadasSon
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
ordinalesLos 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 calificadasLos 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 tablasEsta 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 ListasListas 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,15Recorrido 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
- 47Orden central: 2 - 5 - 7 - 12 - 13 - 15 - 20 - 30 - 35 - 40 -
47Postorden: 2 - 7 - 5 - 15 - 13 - 12 - 35 - 30 - 47 - 40 -
20Ejemplo:Preorden: / + a b * c d Notación polacaOrden central: a +
b / c * d Notación infijaPostorden: a b + c d * / Notación polaca
inversaEstructura de datosVariablesLas 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 TipoEjemplo:Dim
precio As LongDim 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.95Ejemplo 2:
precio_total = precio * 10El Alcance de una variable es definido como su
rango de operación. Hay tres tipos de alcance en una variable:
Local - La variable solo puede ser usada en el
procedimiento actual ( use Dim dentro del
procedimiento requerido).
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).
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áticasEl 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 normalnumero = numero
+ 1Print numeroEnd SubDespué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 localnumero = numero + 1Print
numeroEnd SubAhora 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
