Estructuras de Datos - Funciones y Procedimientos

Estructuras de Datos:

Conjunto de Datos, reunidos bajo un único nombre colectivo.
Las diferentes estructuras se diferencian por: a)Relación entre sus componentes, b) El tipo de los componentes.
Entre las diferentes estructuras, se encuentran a) los Tipos de datos definidos por el usuario, b) Los Arreglos,(entre otros).
A) Tipos de datos definidos por el usuario: Almacenan un conjunto de variables de distintos tipos o tipos iguales (dependiendo la necesidad), bajo un mismo nombre.
Ejemplo: Private Type T_Registro
Var1 as integer
Var2 as string
End Type

B) Arreglos: Almacenan un conjunto de variables del mismo tipo, bajo un mismo nombre. Un índice distingue cada elemento de los demás.
Tenemos arreglos de una dimensión (vectores) y de dos o más dimensiones (matrices).

(Arreglos unidimensionales) Vectores: La conversión de su organización conceptual, a la disposición real dentro de la memoria, es bastante directa.
Si se conoce la dirección de la primera celda de la secuencia, un algoritmo simple, nos permite conocer la ubicación del dato. Para hallar la dirección real, basta restar uno a la posición de entrada y sumar el resultado ala dirección de la primera celda de la secuencia. Si la primera celda está en la dirección 13, tendremos lo siguiente:

Ej: 13 + (4-1)=16
Ejemplo de utilización de un vector:

Estas estructuras, deben dimensionarse antes de ser utilizadas, para que el sistema, reserve un espacio o bloque de memoria consecutivo acorde al tamaño definido:
Dim vec(10) as Tipo de dato
Carga: For a=1 to 10
Vec(a)=a*5
Next



(Arreglos multidimensionales): Matrices: Como ejemplo, imaginemos un arreglo para registrar las ventas de una compañía. Los datos estarían situados en filas y columnas. El primer valor de una fila indica el nombre de un vendedor, los valores del resto de las columnas de cada fila, representan las ventas realizadas. Por tanto, para extraer información de esta tabla, es preciso hallar los datos de una cierta fila y una cierta columna.
La memoria de la máquina no está organizada como un patrón rectangular, por tanto, es necesario simular la estructura rectangular requerida. Lo primero, es calcular el área de almacenamiento requerido, reservando un bloque de celdas de memoria contiguas de ese tamaño.
Si luego almacenamos los datos en la celdas fila por fila, se dice que el arreglo sigue un orden principal por filas, en contraste con un orden por columnas, donde los datos se almacenan por columnas.
















Por ejemplo, para recuperar una entrada situada en fila 3 columna 4, si nos situamos en la entrada del bloque, para llegar a XX debemos avanzar 11 entradas.
Ej de polinomio de dirección:

C= Numero de entradas por fila
I= I esima fila
J= J esima columna
[C x (I - 1)] + (J - 1) => 4 x (3 - 1) + (4 - 1) = 11

La estructura CONCEPTUAL aquí es concebir los datos organizados en una tabla.
La estructura REAL, los datos están almacenados linealmente.

LISTAS

Debido a que los arreglos tienen formas y tamaño constantes, su simulación en la memoria de la máquina, consiste en convertir la posición conceptual de un elemento a su posición real.
En cambio, las estructuras dinámicas son distintas ya que su tamaño y formas, varían. Ej: La lista de miembros de una organización, crece cuando se incorporan nuevos miembros y se encoje cuando la abandonan.
Punteros: Mantienen un rol importante en el uso y mantenimiento de estructuras dinámicas.
La posición de memoria, se representa mediante direcciones numéricas. Conociendo la dirección de un dato, podemos hallarlo sin dificultad. De esta manera, podemos guardar un dato en una celda y almacenar su dirección en otra. Luego, si queremos recuperar el dato y tenemos acceso a la celda que almacena la dirección, podemos hallar el dato, consultando dicha dirección. A esta celda que contiene la dirección de un dato, la llamamos PUNTERO. Algunos lenguajes de programación permiten el uso de punteros.
Ejemplo: Una biblioteca, representa su contenido en la memoria de la máquina, en orden alfabético sus títulos. Un problema que podría presentarse aquí, sería localizar las obras de un mismo autor. Para resolver este problema, podemos reservar una celda de memoria adicional del tipo puntero dentro del bloque de celdas que representa a cada libro, y colocar en ella la dirección del otro bloque que representa a un libro escrito por un mismo autor, de modo que una vez que encontramos un libro de un autor dado, podremos encontrar todos los demás siguiendo los punteros de un libro a otro.



LISTAS DENSAS:

Una técnica para almacenar una lista de nombres en la memoria de la máquina, es guardarlos en bloques consecutivos. A este de organización se le llama: Lista Densa. Sin embargo, pueden surgir problemas cuando tratamos de modificar la lista almacenada de esta manera. Al eliminar un nombre, debemos desplazar los nombres para rellenar el hueco. Otro problema más grave es el de agregar un nombre, ya que además de generar un hueco y desplazar los nombres, debemos comprobar que haya espacio en la memoria, en caso de no haber, debemos desplazar todo el bloque hacia otra área más grande.




Pasos a seguir para AGREGAR nombres a una lista ordenada:
1) Validar elementos a ingresar.
2) Verificar que la lista no esté vacía.
3) Ubicar el índice de un nuevo elemento y verificar que no existe.
4) Desplazar desde allí todos los elementos un lugar hacia arriba.
5) Ingresar el nuevo elemento en el lugar correspondiente.
6) Fin.
(Programa realizado en clase)
Pasos a seguir para ELIMINAR nombres de una lista ordenada:
1) Validar elemento a eliminar.
2) Verificar que la lista no esté vacía.
3) Ubicar en la lista el nombre a eliminar, si no existe, mostrar mensaje “No Existe”
4) Si se encontró, avisar con un mensaje que el elemento fue eliminado.
5) Si es el último, lo elimino, sino, a partir de allí, subo todos los elementos restantes un lugar.
(Programa realizado en clase)
Listas Enlazadas.
Cuando debamos agregar nombres a la lista y no hubiere lugar en el bloque de memoria asignado, se puede salvar este inconveniente, si almacenamos o valores en diferentes áreas de memoria. Para ello almacenamos cada nombre o valor y un puntero en un bloque de memoria. El puntero se usará para indicar la dirección del siguiente nombre o valor, de la lista. Este tipo de organización, se llama “Lista Enlazada”. Para saber donde está la primera entrada de una lista enlazada, apartamos una celda de memoria en la que guardamos la dirección de la primera entrada. Esta celda suele llamarse “Puntero al Inicio”.



El puntero del final dela lista, en lugar de una dirección, llevará llevará la inscripción NIL (nulo), para indicar que no hay más entradas en la lista. Cada rectángulo representa un bloque de memoria disperso en áreas distintas de la misma.

Ejemplo de Eliminar un elemento:
El empleo de punteros, reduce el movimiento de nombres que era necesario cuando se almacenaba en un bloque continuo. Observemos que es posible eliminar un nombre con solo alterar un puntero. Modificamos el puntero que antes apuntaba al nombre eliminado, de modo que ahora apunta al nombre que apuntaba aquel. Cuando se recorra la lista, se pasará por alto el nombre eliminado, porque ya no forma parte de la cadena.



Ej de Inserción:
Primero, se localiza un bloque de celdas desocupado, almacenamos el nombre y la dirección del nombre de la lista que debe ir después del nombre añadido. Por último modificamos el puntero asociado al nombre que le debe preceder al nuevo, de modo que apunte a este último.



Una técnica para seguir la pista delos bloques disponibles para reutilización, consiste en mantener un registro de punteros de bloques reutilizables. Entonces si eliminamos un bloque de la lista principal, lo añadiremos a la lista de bloques disponibles y cuando necesitamos agregar entradas nuevas, lo eliminaremos de la lista. El proceso de reunir espacio de memoria reutilizable se denomina “Recolección de Basura”.
Listas Doblemente Enlazadas.
Las listas anteriores podían recorrerse de izquierda a derecha o sea, en un solo sentido. Existen otras listas, que pueden recorrerse en ambas direcciones. Para ello, cada entrada de la lista tendrá dos punteros, uno que apunte al posterior y otro al anterior. El puntero de la primera entrada tendrá un valor NIL y el puntero de la última entrada también.



Si la última entrada, en lugar de tener un puntero NIL, tuviese la dirección de la primera entrada, la lista sería CIRCULAR.
PILAS (STACK)
Una de las propiedades de las listas que hacen más convenientes el empleo de una estructura enlazada en vez de una densa, es la necesidad de insertar y eliminar entradas en el interior de la lista. Recordemos que en el caso de las listas densas, tales operaciones, podían requerir movimientos masivos de nombres para crear o llenar huecos. Si restringimos esas operaciones a los extremos de la estructura, vemos que el empleo de estructuras densas, se convierte en un sistema más conveniente. Un ejemplo de este fenómeno es la PILA. Una Pila es una estructura en la que todas las inserciones y eliminaciones, se realizan por el mismo extremo de la estructura, el cual se llama Cima o Tope de la pila. El otro extremo de la pila recibe el nombre de Base de la pila. Esta estructura recibe el nombre también de LIFO (last in first out) último entrado primero salido.
Aplicaciones de las Pilas.
Un ejemplo común se encuentra dentro de un lenguaje de alto nivel, donde se utiliza una pila para controlar la ejecución de subprogramas. Cuando se solicita la ejecución de un subprograma, la máquina debe transferir su atención al subprograma que llama, pero al completarse el mismo, deberá volver a la posición original desde donde se hizo la llamada. Cuando se realiza la transferencia inicial, debe existir un mecanismo que permita encontrar la posición de retorno (al finalizar el subprograma). Puede complicarse aun más, por el hecho de que el subprograma puede a su vez, solicitar la ejecución de otro y así sucesivamente. En consecuencia, las posiciones de retorno que se deben recordar, comienzan a acumularse. De esta forma, al concluir cada uno de estos subprogramas, la ejecución debe continuar en el lugar correcto, dentro de la unidad de subprograma donde se hizo la llamada. Por tanto, se requiere un sistema para almacenar las posiciones de retorno y recuperarlas después en el orden correcto. La Pila, es una estructura ideal para este sistema. Al invocarse cada subprograma, el intérprete se limita a empilar en la cima de la pila, un puntero a la posición de retorno pertinente, y al completarse cada subprograma, el intérprete extrae la entrada superior de la pila, con la certeza de obtener un puntero a la posición de retorno correcta. Las posiciones de retorno, se requieren en el orden inverso al de la invocación de los subprogramas, ya que el ‘ultimo subprograma invocado, es el primero que termina.
Implantación de Pilas.
Para implantar una estructura de Pila en la memoria de una computadora, se reservan celdas de memoria contiguas, de un tamaño suficiente como para que la pila pueda caber mientras crece y se encoje. Este es un problema crucial, ya que si se asigna demasiado espacio, podría desperdiciarse memoria, y si se reserva un bloque demasiado pequeño, la pila podría exceder el espacio de almacenamiento, destinado a ella. Una vez reservado el espacio de memoria, seleccionamos un extremo que haga de base de la pila. Aquí colocamos la primera entrada de la pila y el resto de de las entradas irán a continuación. Necesitamos saber en todo momento, cual es la dirección del último elemento empilado, ya que la pila crece y se encoje. Necesitamos entonces apartar otra celda que contenga la dirección de la cima de la pila, llamado Puntero de Pila.
Ejemplo:



El sistema funciona así: Para empilar, primero ajustamos el puntero de la Pila para hacer que apunte a la celda vacante y luego colocaremos la nueva entrada en esa posición. Para des empilar, leemos los datos de la dirección a la que apunta el puntero y luego ajustamos el valor de este, de modo que apunte a la siguiente entrada. Cuando el espacio contiguo es demasiado pequeño, se puede recurrir a implementar una pila como una lista doblemente enlazada, para utilizar espacios de memoria vacíos, aunque esto requiere un esfuerzo mayor de mantenimiento. Las Pilas suelen desbordarse con el mensaje “OVERFLOW STACK”.
COLAS.
Una cola, es una lista de acceso restringido. Las colas restringen todas las inserciones a un extremo y todas las eliminaciones al extremo opuesto. Las colas responden al concepto FIFO (first in first out), primero entrado primero salido. El extremo donde se extraen elementos se denomina FRENTE, el extremo donde se ingresan nuevos elementos, se llama Final de la Cola.
Implantación de Colas:
Para implementar una cola en la memoria, podemos hacerlo con bloques de celdas contiguas, similar a como almacenamos una pila, pero como tenemos que efectuar operaciones en ambos en ambos extremos, debemos reservar dos celdas para usarlas como puntero. Por lo tanto, habrá un puntero al frente y otro al final. Al estar la cola vacía, ambos punteros apuntan a la misma dirección. Cada vez que se ingresa un dato, habrá que reacomodar el puntero que apunta “al final” . Para eliminar una entrada, extraemos el elemento al que apunta el puntero “al frente” y luego ajustarlo para que apunte a la entrada que seguía a la que se eliminó.






Con este sistema, si no se controla, la cola avanzará lentamente por la memoria, destruyendo cualquier dato que se encuentre en su camino. Una solución a esto, consiste en desplazar todos los datos hacia adelante, cada vez que se elimine un dato, pero esta solución implica movimiento masivo de datos, cada vez que se elimina un dato. Una solución a este dilema, consiste en apartar un bloque de memoria para la cola, y dejar que la cola migre hacia el otro extremo. Cuando el final de la cola, llegue al final del bloque, comenzaremos a insertar entradas al principio del bloque, que para entonces estará vacío. Así, la cola se persigue a sí misma en vez de vagar por la memoria. Esta técnica se conoce como circular. La última celda del bloque será adyacente a la primera.







Procedimientos y Funciones.
Los Procedimientos y Funciones son rutinas de código que cumplen una determinada tarea. Cuando llamamos a un Procedimiento o una Función, ésta se ejecuta completamente y luego el programa continúa desde la línea siguiente desde donde se hizo el llamado.
Ventajas:
• Contribuyen a una buena organización del código en nuestros programas.
• Permite dividir un problema grande en varios pequeños más fáciles de resolver.
• Se puede probar por separado.
• Evitan tener que repetir el mismo código en varias partes del programa.
• Permiten reutilizar el código en varios proyectos diferentes. Mediante los Módulos de códigos, podemos agrupar una gran cantidad de procedimientos y funciones reutilizables.
Diferencias entre Procedimientos y Funciones: Las funciones devuelven un valor como resultado. Los Procedimientos, en Gral. NO devuelven valores.


Procedimientos:

Antes de ingresar el código en un procedimiento, debemos declararlo adecuadamente. Declarar un procedimiento, implica darle un nombre e indicar todos los parámetros que tiene (si los tuviere), junto con el tipo de dato de cada uno. Creamos un procedimiento, situándonos en la ventana de código, fuera de todo procedimiento. Si lo hiciéramos dentro de un procedimiento, sería UNA SUB RUTINA (go to a una etiqueta / return).

Sub miprocedimiento()

End sub

Deberemos definir también si es público o privado.
Parámetros:
Por lo gral. Los procedimientos tienen parámetros. Un parámetro, permite pasarle valores o variables a la rutina, para que ésta actúe en base a ellos. La idea de usar parámetros, es hacer que el procedimiento sea más gral., es decir, que no utilice siempre los mismos valores, variables u objetos, sino que pueda variar la forma en que se lo llame.

Sub Miprocedimiento(parámetro1 as tipo1, parámetro2 as tipo2)

Ens Sub

Sub Abrir(Nombrearchivo as String)
End sub

Private sub command1_click()
Abrir Datos.Doc“
End Sub




Escribir el código del procedimiento:
Una vez que declaramos un procedimiento, estamos en condiciones de escribir su código. Los parámetros que puede recibir un procedimiento, son tratados como variables locales del mismo.

Llamar a un procedimiento:

Una vez definidos los procedimientos, están en condiciones de ser invocados desde otras partes del programa. Tenemos dos formas de llamar un procedimiento.

• CALL Nombre_Procedimiento([Parametros])
• Nombre_Procedimiento Parametros

La diferencia entre ambas, es la utilización de paréntesis si se utiliza CALL, de la otra forma, solo se invoca el nombre y el/los parámetros (si los hubiere), sin paréntesis.
Ej:
Mostrar 20,4

Sub Mostrar (a AS Integer, b AS Integer)
Msgbox a
Msgbox b
End Sub

Pasar Datos por Valor y por Referencia.
Cuando se pasa un parámetro por valor, se envía a la rutina, una copia de la variable. Por este motivo, cualquier cambio realizado en el procedimiento, no afecta a la variable original. Cuando se pasa un parámetro por referencia, se envía un puntero a la variable original y cualquier cambio dentro de la rutina, afecta la variable original.
Ej:

Sub Mostrar(Byval altura AS Integer, Ancho AS Integer)

En este ejemplo, solo el parámetro altura fue pasado por VALOR. El ancho fue pasado por defecto por REFERENCIA. Si esa variable sufriera algún cambio dentro del procedimiento, permanecerá fuera de él.
Ej:

Dim A As Integer
Dim B As Integer
A=25
B=50
Mostrar A,B

Sub Mostrar(Byval altura As Integer, Ancho As Integer)
Altura=altura * 100
Ancho=ancho * 100
Msgbox altura
Msgbox ancho
End Sub

Al salir del procedimiento las variables originales (A y B), valdrán:
A seguirá valiendo 25
B vale ahora 5000 porque fue pasada por referencia y su valor cambió dentro del procedimiento.
Cuando una variable es pasada por referencia, la variable con la que trabaja el procedimiento (ancho), y la variable original(B), hacen referencia a la misma zona de memoria, con lo cual todos los cambios producidos dentro del procedimiento, se mantendrán al salir. Hay dos formas de pasar un parámetro por referencia: 1) sin especificar nada, 2) utilizando la palabra Byref.
EJ: Private sub command1_click()
Dim cadena As string
Cadena=”Hoy es un día soleado”
Cadena_V cadena
Label1 = cadena
Cadena_R cadena
LAbel2 = cadena
End Sub

Sub cadena_V (Byval texto As string)
Texto=”Hoy es un dia lluvioso”
End Sub

Sub cadena_R(texto As String)
Texto = “Hoy es un dia lluvioso”
End Sub

Label1 será igual a: “Hoy es un día soleado”, ya que el parámetro fue pasado por valor, y solo se modifico dentro del procedimiento, NO la variable original.
En cambio Label2, será igual a: “Hoy es un día lluvioso”, ya que el parámetro fue pasado por referencia, y como fue modificado dentro del procedimiento, la variable original, cadena, ha sido modificada.

Salir de un procedimiento.

El procedimiento termina cuando aparece la palabra END SUB, aunque a veces es necesario salir de un procedimiento antes que finalice, con EXIT SUB.
Ej

Sub dividir(operador1 As Integer, operador2 As Integer )
Dim resultado As Integer
If operador1 <=0 or operador2 <=0 then Exit sub Resultado=operador1 / operador2 endif End Sub

Funciones:

Las funciones son exactamente iguales a los procedimientos, salvo por un detalle: Siempre devuelven un valor. Ese valor puede ser asignado a una variable o utilizado en una expresión. El valor que devuelve una función define el tipo de la misma, por ejemplo, podemos crear funciones, de cadenas o de cualquier tipo de dato válido. Las funciones pueden devolver arreglos y tipos de datos definidos por el usuario. Crear una función: Function mi_funcion() AS Integer End Function Si observamos, la función, a diferencia de un procedimiento, en su declaración debemos indicar que TIPO de valor devuelve. (AS Integer) Las funciones pueden recibir parámetros y estos pueden ser por valor y por referencia. Ejemplo: Function sumar(Byval op1 as Integer, Byref op2 as Integer) AS integer Dim Resultado as integer Resultado=op1 + op2 Sumar=resultado End Function Para devolver un valor en una función, este se suele cargar antes en una variable y justo antes de terminar, asignárselo a la función.

Ejecutar una función: Al ejecutar una función, se suele utilizar una variable para capturar el valor devuelto por la misma. También, se pueden llamar instrucciones mediante expresiones (sin utilizar variables). Ejemplo: Private sub Command1_click() Dim resultado as Boolean Resultado=mayor(9,7) ‘AQUI RESULTADO=TRUE Resultado=mayor(5,5) ‘ AQUI RESULTADO =FALSE If mayor(6,9) then ‘TODO EL CODIGO AQUI INCLUIDO NO SE VA A EJECUTAR ‘ YA QUE LA FUNCION MAYOR NO ES TRUE End If End Sub Function Mayor(Byval op1 as Integer, Byval op2 as Integer) AS Boolean ‘ESTA FUNCION SOLO DEVUELVE TRUE CUANDO ‘EL PRIMER OPERADOR ES MAYOR QUE EL SEGUNDO If op1 > op2 then
Mayor= true
Else
Mayor=false
End If
End Function

Devolver Arreglos.

Private Command1_click()
Dim nuevoarray() as string
Nuevoarray=generararreglo(20)
End Sub

Function generararreglo(n as Integer) as string()
Dim i as integer
Dim temp() as string
Redim temp(n)
For i=1 to n
Temp(i)=”Cadena ” & format(i)
Next
Generararreglo = Temp
End Function

Observe que al final de la declaración de la función aparece: as string () . El uso de los paréntesis indica que la función devolverá un arreglo.

Devolver Tipos de datos definidos por el usuario.

Private Type Mitipo
Nom as string * 15
Dir as string * 15
Tel as string * 10
End Type

Private sub Command1_click()
Dim as Mitipo
Resultado = Mifuncion
End Sub

Function Mifuncion() AS Mitipo
Mifuncion.nom=”Juan”
Mifuncion.dir = “Belgranos 141”
Mifuncion.tel = “1234-5478”
End Function

Alcance de los Procedimientos y Funciones

Mediante la palabra clave Public, podemos hacer que una función o procedimiento sea público, es decir que esté disponible desde cualquier parte del código del programa.
Public Sub generarlistado(nombre as string)
End Sub

Public Function Sumar(op1 as integer, op2 as integer)
End function

Funciones y Procedimientos PRIVADOS.

Declarar funciones y procedimientos como PRIVADOS, hace que se puedan acceder a la rutina solo desde el mismo módulo o formulario desde la que fue definida. La principal ventaja de las funciones y procedimientos Privados, es que residen en memoria mientras el módulo o formulario que las contiene, está en memoria.
Private Sub generarlistado(nombre as string)
End Sub

Private Function Sumar(op1 as integer, op2 as integer) as double
End function

FIN UNIDAD II