CLASE 12: Punteros y Estructuras dinámicas de datos: Pilas, Colas y Listas
Estructuras dinámicas de Datos
Los punteros son variables cuyos contenidos son una dirección en la memoria interna de la computadora. Si bien apuntan a una dirección de memoria, para que 2 punteros puedan ser comparados, o asignar la dirección que contiene una variable puntero a otra, deben ser ambos del mismo tipo de dato al que apuntan, para que no se genere un error de incompatibilidad de tipo o type mismatch -Error: 26 informado por Turbo Pascal-. Por lo tanto, los punteros en Turbo Pascal son punteros a un tipo de dato específico. No obstante, existe la posibilidad de poder definir punteros genéricos por medio del identificador pointer.
MAPA DE MEMORIA
A continuación se pasará a detallar como divide el lenguaje Turbo Pascal las regiones de memoria interna, al cargarse un programa.
Memoria Superior D.O.S.
Estructuras dinámicas de Datos
Los punteros son variables cuyos contenidos son una dirección en la memoria interna de la computadora. Si bien apuntan a una dirección de memoria, para que 2 punteros puedan ser comparados, o asignar la dirección que contiene una variable puntero a otra, deben ser ambos del mismo tipo de dato al que apuntan, para que no se genere un error de incompatibilidad de tipo o type mismatch -Error: 26 informado por Turbo Pascal-. Por lo tanto, los punteros en Turbo Pascal son punteros a un tipo de dato específico. No obstante, existe la posibilidad de poder definir punteros genéricos por medio del identificador pointer.
MAPA DE MEMORIA
A continuación se pasará a detallar como divide el lenguaje Turbo Pascal las regiones de memoria interna, al cargarse un programa.
Memoria Superior D.O.S.
La memoria interna está dividida en segmentos, en donde cada segmento tiene un tamaño de 64Kbytes. Algunos de estos segmentos cumplen un rol específico a la hora de correr o ejecutar un programa. Estos segmentos especiales son 3 más una región de memoria restante que representan lo siguiente:
- Segmento de DATOS –DATA-: El lenguaje Turbo Pascal utiliza este segmento para reservar espacio para las variables de ámbito o alcance global. Las variables definidas en este segmento son variables estáticas y deben ser definidas en tiempo de compilación, ocuparán el espacio reservado mientras la ejecución del programa está en marcha. Todas las variables del módulo principal más todas las variables de las unidades empleadas por el módulo principal ocuparán el único segmento de datos, que no podrá exceder los 64Kbytes.
- Segmento de CÓDIGO -CODE-: El lenguaje Turbo Pascal utiliza este segmento para el código del programa (bloque principal + módulos definidos), pero el tamaño total no está limitado a un segmento de 64Kbytes. La manera de ampliar el tamaño de código por encima de los 64Kbytes es empleando unidades. Cada unidad tiene su propio segmento de código, en donde, cada uno de ellos no puede exceder los 64Kbytes, pero el tamaño total de código está limitado solamente por el tamaño de la memoria disponible.
- Segmento de la PILA –STACK-: El lenguaje Turbo Pascal utiliza este segmento para guardar la dirección de retorno al invocar a un módulo, los parámetros y las variables de alcance o ámbito local. El valor asignado por defecto es de 16Kbytes, pero puede ser ampliado a 64Kbytes por medio de la directiva al compilador $M. El stack crece desde dirección de memoria más alta hacia direcciones de memoria más bajas.
- Área de memoria del MONTÍCULO –HEAP-: El lenguaje Turbo Pascal utiliza esta región de memoria, en realidad son varios segmentos, para la creación de variables dinámicas, esto es, variables que se crearán y se eliminarán cuando ya no se las necesite, en tiempo de ejecución. Esto permite ampliar los 64Kbytes del segmento de datos; por lo tanto, está región de memoria estará disponible para poder extender la cantidad de variables en caso de requerir más nuestro proceso en ejecución. El tamaño real del heap estará establecido por un valor mínimo, que puede ser cero (valor por defecto) u otro valor mayor y por un valor máximo, que pueden ser los 640Kbytes (valor por defecto) u otro valor menor, que puede ser establecido por medio de la directiva al compilador $M. Si la cantidad mínima de memoria no está disponible, el programa no se ejecutará. El heap crece desde una dirección de memoria baja hacia direcciones de memoria más altas.
En conclusión, si un programa requiere más espacio para variables que los 64Kbytes que ofrece el segmento de datos, se debe emplear el área del heap.
Por otro lado para ampliar el tamaño del código de programa por encima de los 64Kbytes que ofrece el segmento de código, se deben emplear las unidades, cada una de las cuales pueden utilizar un máximo de 64Kbytes y cada una de ellas tiene su propio segmento de código, pero las variables que utilicen se ubicarán en el segmento de datos empleado por el módulo principal. Esto significa que la totalidad de variables (bloque principal + las variables definidas en c/u. de las unidades) se ubican en un solo segmento de datos, por lo tanto no podrá superar los 64Kbytes.Si se divide el bloque principal en módulos podremos ahorrar el espacio del segmento de datos, debido a que ciertas variables de trabajo temporal estarían definidas dentro de cada módulo ubicándose en el segmento de la pila o stack y dejarían de estar ubicadas en el segmento de datos. De esta manera se consigue aliviar para que no recaigan todas las variables al segmento de datos, sino que se distribuyan en el segmento de la pila. Esto es cada vez que se invoca a un módulo tanto los parámetros como las variables locales se guardan en la pila, es decir se crean en el momento de invocar al módulo y son destruidas al abandonarlo.
Por otro lado para ampliar el tamaño del código de programa por encima de los 64Kbytes que ofrece el segmento de código, se deben emplear las unidades, cada una de las cuales pueden utilizar un máximo de 64Kbytes y cada una de ellas tiene su propio segmento de código, pero las variables que utilicen se ubicarán en el segmento de datos empleado por el módulo principal. Esto significa que la totalidad de variables (bloque principal + las variables definidas en c/u. de las unidades) se ubican en un solo segmento de datos, por lo tanto no podrá superar los 64Kbytes.Si se divide el bloque principal en módulos podremos ahorrar el espacio del segmento de datos, debido a que ciertas variables de trabajo temporal estarían definidas dentro de cada módulo ubicándose en el segmento de la pila o stack y dejarían de estar ubicadas en el segmento de datos. De esta manera se consigue aliviar para que no recaigan todas las variables al segmento de datos, sino que se distribuyan en el segmento de la pila. Esto es cada vez que se invoca a un módulo tanto los parámetros como las variables locales se guardan en la pila, es decir se crean en el momento de invocar al módulo y son destruidas al abandonarlo.
Una unidad es una colección de diferentes objetos. Estos objetos pueden ser Unidades, Constantes, Tipos, Procedimientos, Funciones y Variables. Las unidades presentan las características más interesante para la descomposición de un proyecto grande en módulos más pequeños. Permiten la compilación independiente, ya que cada unidad es compilada en forma separada del programa principal. A través de las unidades se pueden construir grandes programas. Por otro lado al dividir el proyecto en módulos independientes cuando surja la necesidad de realizar algún cambio, solo se deberá recurrir el módulo correspondiente. Las unidades requeridas por el programa principal son indicadas en la cláusula uses las que se enlazarán con el código del programa principal, en el momento de compilar solo se compilarán las sentencias del bloque principal y los módulos definidos en él, pero no las unidades, debido a que se encuentran ya compiladas. Por lo tanto se conseguirá un ahorro en tiempo de compilación. La compilación de una unidad se realiza una sola vez y luego de haberla creado y habiéndola depurado de posibles errores. Luego estará lista para ser usada en diferentes programas que requieran de su uso.
Al crear una unidad debemos tener en cuenta cual es su objetivo de uso, ya que sabiendo esto se construiran las unidades para un tema específico. Por ejemplo unidades para funciones matemáticas, para tratamiento de cadenas, para operaciones de entrada y salida, etc..
Turbo Pascal brinda diferentes colecciones de unidades cada una de las cuales cumple una tarea concreta, algunas de las cuales son:
CRT: Unidad dedicada al manejo de la pantalla y el teclado, brinda diferentes posibilidades para manejar la pantalla y el teclado de manera sencilla por medio de los objetos definidos en esta unidad, algunos de los cuales son: gotoxy(x,y) que ubica al puntero de la pantalla en las coordenadas (x, y); clrScr que borra la pantalla y ubica al puntero de la pantalla en x=1, y=1; wherex y wherey son funciones que informan la posición del cursor indicando la columna y fila respectivamente; delay(n) que realiza una espera de n milisegundos; keypressed avisa se se oprimió una tecla; textcolor(n) cambia el color a los caracteres; textbackground(n) cambia el color de fondo del carácter; readkey lee una la tecla presionada; windows(x1,y1,x2,y2) crea una ventana; sound(n) genera un sonido de n hercios y nosound desactiva el sonido, entre otros.
PRINTER: Unidad dedicada al manejo de la impresora, brinda servicios para el fácil manejo de la impresora ya que no requiere realizar la asignación de nombres físico y lógico, abrir la impresora o cerrarla, además define la variable lst para ser utilizada como nombre lógico del archivo de la impresora, para poder ser empleada en las sentencia write y writeln como nombre del dispositivo al que se destinará la salida impresa.
DOS: Unidad dedicada al manejo de los servicios brindados por el D.O.S., entre los cuales contamos getdate(aa,mm,dd,ds) el cual obtiene la fecha del sistema; gettime(hh,mm,ss,cs) el cual obtiene la hora del sistema; exec(NomProg, LineaCdo) ejecuta una aplicación desde Turbo Pascal; diskFree(n) retorna el espacio disponible en el disco de la unidad n, entre otros.
Otras unidades predefinidas por Turbo Pascal son GRAPH que define un conjunto de diferentes objetos relacionados con aplicaciones gráficas.
La unidad SYSTEM es una unidad un tanto especial ya que jamás debe ser indicada en la cláusula uses debido a que esta unidad, dada su importancia, se incluye directamente en todo programa Turbo Pascal que se desarrolle. En esta unidad encontramos todas las funciones numéricas, como ser, sqrt(x), sqr(x), exp(x), ln(x), sin(x), cos(x), abs(x), int(x), trunc(x), round(x), random(x), randomize, frac(x), funciones para el tratamiento de cadenas alguna de las cuales son length(cad), upcase(car), copy(subcad,pos_ini,cant), manejo de las operaciones de entrada y salida de archivos como ser assign(nl, nf), reset(nl), rewrite(nl), close(nl), read(nl, nr), write(nl, nr), filepos(nl), seek(nl, dir), entre otros.
Turbo Pascal reúne varias unidades en un solo archivo denominado TURBO.TPL el cual forma una librería.
Unidades definidas por el usuario
Turbo Pascal da la posibilidad de que el programador pueda crear sus propias unidades. Para poder confeccionar una unidad debemos conocer su composición o esquema lógico.
Una unidad de Turbo Pascal consta de las siguientes partes:
- Una cabecera precedida por la palabra reservada Unit, el identificador IdUnidad debe tener el mismo nombre que el archivo en disco de la unidad.
- Una parte de interfaz precedida por la palabra reservada interface que tiene carácter público, es decir los objetos aquí definidos pueden ser accedidos desde un ámbito externo a la unidad, esto es, los programas que requieran el servicio de la unidad pueden utilizar estos objetos. En el caso de los módulos, funciones y procedimientos, solo de definen las cabeceras, por lo cual solo se indicará el nombre del módulo, la lista de parámetros formales con sus tipos de datos, como son pasados por valor o por referencia y en el caso de las funciones el tipo de valor devuelto por la función.
- Una parte de implementación precedida por la palabra reservada implementation que tiene carácter privado, es decir los objetos aquí definidos y que no fueron indicados en la parte de interface no podrán ser accedidos desde un ámbito externo a la unidad, solo podrá acceder la unidad para un requerimiento de uso local necesario para el desarrollo del proceso interno a la misma. En el caso de los módulos, funciones y procedimientos, además de establecer la cabecera de los mismos, se desarrollan en forma completa el conjunto de las sentencia que deban de realizarse para la actividad del módulo como así tambien los objetos propios y locales del módulo.
Una última parte de inicialización de la unidad encerrada entre las palabras reservadas begin y end. Por ejemplo, inicializar las variables definidas en la unidad, ejecutar algunas sentencias o invocaciones a los módulos definidos en la unidad.
Una vez que la unidad ha sido probada con éxito se procede a realizar la compilación por única vez, a menos que en el futuro debamos efectuar algún cambio. El programa que haga uso de la unidad, solo deberá enlazarla a su propio código, el único que deberá compilarse. Las ventajas de usar unidades es que permiten la construcción de grandes programas, dividen las tareas en problemas menores, son más fáciles de corregir, se pueden clasificar de acuerdo a su temática y formar librerías para ser empleadas por diferentes programas.
A continuación se presenta la estructura de una unidad:
1:Unit IdUnidad; { Encabezado o cabecera de la unidad } 2:interface { Parte pública }
3: uses { Objetos públicos }
4: const
5: type
6: procedure
7: function
8: var
9:
10:implementation { Parte privada }
11: uses { Objetos privados }
12: const
13: type
14: procedure
15: function
16: var
17:
18:begin { Inicialización de la unidad }
19: sentencias(s)
20:end.
21:Direccionamiento de memoria bajo el D.O.S.
El D.O.S. –Sistema Operativo en Disco- puede direccionar hasta 1Mbyte de memoria, esto es 220 = 1.048.576 bytes. El Turbo Pascal fue desarrollado para correr bajo el DOS y bajo la familia de procesadores 8088 y 8086. El esquema de la memoria permite direccionar hasta 1Mbyte a pesar de que el cableado de la circuitería interna de los registros sean de 16 bits. Para poder acceder a las direcciones de 20 bits debe utilizar un método de direccionamiento que encaje en el formato de 16 bits.
Direccionamiento segmentado
El espacio de memoria está dividio en segmentos, cada uno de los cuales tiene 64Kbytes de memoria. Para poder acceder a cada posición dentro de un segmento se utiliza un desplazamiento. Debido a que el desplazamiento se mide siempre en relación al segmento, este método se conoce como direccionamiento relativo.
La combinación de un segmento y un desplazamiento forma una dirección segmentada que puede hacer referencia a un byte del espacio de memoria de un total de 1Mega byte. Una dirección segmentada de 32 bits es convertida por el procesador en una dirección de 20 bits utilizando la dirección del segmento como un párrafo adicionando la dirección del desplazamiento. En realidad se desplaza la dirección del segmento 4 bits hacia la izquierda y se le suma el valor del desplazamiento, dando como resultado una dirección de 20 bits.
El siguiente ejemplo ilustra lo dicho anteriormente, si tomamos 1234H como una dirección de segmento y 4321H como una dirección de desplazamiento, la notación empleada para indicar una dirección segmentada sería 1234H:4321H. El número de la parte izquierda de los 2 puntos indica el segmento y el número de la parte derecha de los 2 puntos indica el desplazamiento. La letra H indica que el número está expresado en el sistema de numeración en base hexadecimal. Para calcular la dirección real en memoria se procede a realizar las siguientes operaciones:
12340H se agrega un cero por el extremo derecho a la dirección del segmento
+ 4321H se suma la dirección del desplazamiento relativo
16661H es la dirección real en memoria
Cualquier dirección de memoria puede ser establecida con diferentes combinaciones de direcciones segmentadas, por ejemplo la dirección real de memoria 16661H puede ser establecida no solo como 1234:4321, sino también como 1666:0001, 1665:0011, 1664:0021 y así sucesivamente.
A continuación se presenta otro ejemplo utilizando notación binaria
Ejemplo:
Direccionamiento segmentado
El espacio de memoria está dividio en segmentos, cada uno de los cuales tiene 64Kbytes de memoria. Para poder acceder a cada posición dentro de un segmento se utiliza un desplazamiento. Debido a que el desplazamiento se mide siempre en relación al segmento, este método se conoce como direccionamiento relativo.
La combinación de un segmento y un desplazamiento forma una dirección segmentada que puede hacer referencia a un byte del espacio de memoria de un total de 1Mega byte. Una dirección segmentada de 32 bits es convertida por el procesador en una dirección de 20 bits utilizando la dirección del segmento como un párrafo adicionando la dirección del desplazamiento. En realidad se desplaza la dirección del segmento 4 bits hacia la izquierda y se le suma el valor del desplazamiento, dando como resultado una dirección de 20 bits.
El siguiente ejemplo ilustra lo dicho anteriormente, si tomamos 1234H como una dirección de segmento y 4321H como una dirección de desplazamiento, la notación empleada para indicar una dirección segmentada sería 1234H:4321H. El número de la parte izquierda de los 2 puntos indica el segmento y el número de la parte derecha de los 2 puntos indica el desplazamiento. La letra H indica que el número está expresado en el sistema de numeración en base hexadecimal. Para calcular la dirección real en memoria se procede a realizar las siguientes operaciones:
12340H se agrega un cero por el extremo derecho a la dirección del segmento
+ 4321H se suma la dirección del desplazamiento relativo
16661H es la dirección real en memoria
Cualquier dirección de memoria puede ser establecida con diferentes combinaciones de direcciones segmentadas, por ejemplo la dirección real de memoria 16661H puede ser establecida no solo como 1234:4321, sino también como 1666:0001, 1665:0011, 1664:0021 y así sucesivamente.
A continuación se presenta otro ejemplo utilizando notación binaria
Ejemplo:
Distintas combinaciones de Segmento:Desplazamiento pueden obtener la misma direccion real de memoria, por ejemplo:
0020:0100 = 0030:0000 = 0010:0200 = 0000:0300 = ...
Punteros cercanos:
Los punteros cercanos –NEAR- son punteros que solamente pueden apuntar a su propio segmento, utilizan solo la parte de desplazamiento para poder acceder dentro de los 64Kbytes o 65536 posiciones de memoria dentro del segmento. Por lo tanto 2 bytes serán necesarios, es decir, con 16 bits o 216 para poder direccionar a cada byte de un segmento.
Punteros lejanos:
Los punteros lejanos –FAR- son punteros que pueden no solo apuntar a su propio segmento sino también pueden apuntar a otros segmentos, por lo tanto, estos tipos de punteros requieren 4 bytes, es decir, 2 bytes para la parte de segmento y 2 bytes para la parte de desplazamiento.
Modelos de Memoria
Los modelos de memoria surgen de la combinación entre punteros cercanos y lejanos por un lado y por otro con respecto a la región de almacenamiento para los datos y para el código del programa.
Seis combinaciones se presentan a continuación:
- TINY –Diminuto-:
Código, datos y pila en un solo segmento de memoria de 64Kb. Utiliza punteros cercanos, es el más rápido de ejecución tanto para acceder al código como para acceder a los datos, ya que la aritmética que debe emplear para punteros cercanos es más simple que para punteros lejanos y además son los programas de menor tamaño. Puede ser convertido a .COM. - SMALL –Pequeño-:
Código en un segmento de 64Kb, datos y pila en otro segmento de memoria de 64Kb, por lo que el tamaño total será de 128 Kb. Es tan rápido como el modelo anterior, ya que utiliza punteros cercanos, tanto para el código como para acceder a los datos. - COMPACT –Compacto-:
Código en un segmento de 64Kb, datos en varios segmentos de memoria de 64Kb. Es tan rápido como los modelos anteriores, debido a que requiere de punteros cercanos, aunque el acceso a los datos es más lento, debido a que requiere asignar a los registros del sistema, el segmento y el desplazamiento de la dirección de memoria, por lo que utiliza punteros lejanos, pero se obtiene como ventaja poder tener más espcaio de almacenamiento para los datos. - MEDIUM –Medio-:
Código en varios segmentos de memoria, datos en un solo segmento de memoria de 64Kb. La ejecucion es mas lenta que en los modelos anteriores, al invocar a los modulos, debido a que requiere de punteros lejanos, aunque el acceso a los datos es tan rapido como en los dos primeros modelos, ya que requiere solo de asignar el desplazamiento solamente por lo que usa punteros cercanos. Utilizado para programas grandes pero que usan pocos datos. - LARGE –Grande-:
Código en varios segmentos de memoria, datos en varios segmentos de memoria, aunque no se permite utilizar estructuras de datos de más de 64Kb. Tanto el código como los accesos a los datos lo hacen más lentos que en los modelos anteriores, ya que utiliza punteros lejanos en ambos casos. Requerido cuando se requiere gran cantidad de código y de datos. - HUGE –Enorme-:
Código en varios segmentos de memoria, datos en varios segmentos de memoria y se permite utilizar estructuras de datos de más de 64Kb. Tanto el código como los accesos a los datos lo hacen más lentos que en los modelos anteriores, ya que utiliza punteros lejanos.
PUNTEROS EN TURBO PASCAL
Turbo Pascal presenta dos clases de punteros:
- Genéricos
- A un tipo de datos
Los punteros genéricos se definen por medio del identificador pointer, el cual establece que las variables definidas con este identificador contendrán direcciones de memoria. Este tipo de punteros es más ampliamente utilizado para el soft de base o de sistema, no tanto para programas de aplicaciones.
Los punteros que apuntan a un tipo de datos se definen por medio del símbolo ^ y a continuación al tipo de dato al que apuntarán. El símbolo ^ se lee acento circunflejo. Las variables definidas como puntero a un tipo de dato determinan la cantidad de bytes a que hace referencia el puntero. Este tipo de puntero es el que se utilizará para desarrollar los diferentes problemas a resolver. En la sección type se definirán los tipos punteros. A continuación presentamos diferentes ejemplos de tipos punteros a tipos de datos simples:
type
cadn = string[20]; { se lee }
ptrEnt = ^integer; { ptrEnt es un tipo igual a puntero a un tipo de dato integer }
ptrLong = ^longint;
ptrReal = ^real;
ptrChar = ^char;
ptrCadn = ^cadn;
ptrBool = ^boolean;
ptrWord = ^word;
ptrByte = ^byte;
ptrShort = ^shortint;
Los siguientes ejemplos muestran definiciones de tipos punteros a tipos de datos estructurados:
type
RegAlu = record
NroLeg : longint;
ApeNom : cad20;
FecNac : longint
end;
ptrRec = ^RegAlu; { ptrRec es un puntero a un tipo de dato RegAlu }
Las variables de tipo puntero se definirán de la siguiente manera:
var
ptr1, ptr2 : ptrWord;
ptr3 : ptrRec;
ptr4 : ptrlong;
ptr5 : pointer;
Los punteros ptr1 y ptr2 apuntan a tipos de datos word y se referirán en consecuencia a dos bytes, el puntero ptr3 apunta a un tipo de dato RegAlu y se referirá a 29 bytes, el puntero ptr4 apunta a un tipo de dato longint y se refiere a 4 bytes, por último el puntero ptr5 apunta a una región de memoria y se refiere de una forma genérica es decir no se refiere a ningún tipo de dato en particular.
A continuación se presentan otros tipos de estructuras de datos y punteros:
type
VecPtr = array[1..10] of ptrRec;
ptrVector = ^VecPtr;
var
Vec : VecPtr;
ptrVec : ptrVector;
rAlu : RegAlu; { Está definido más arriba }
i : byte;
begin
for i:= 1 to 10 do
Vec[i]:= nil;
rAlu.NroLeg:= 112345;
rAlu.ApeNom:= ‘Martinez, Inés’;
rAlu.FecNac:= 23051981
Vec[1]:= @rAlu;
ptrVec:= Addr(Vec);
writeln(ptrVec^[1]^.NroLeg,’ ‘,ptrVec^[1]^.ApeNom,’ ‘,ptrVec^[1]^.FecNac)
end.
Un puntero puede apuntar a cualquier región de memoria, esto es, al segmento de datos, (como en los ejemplos dados anteriormente) o a los segmentos de código o al segmento de pila o al heap o como a cualquier otro segmento.
Turbo Pascal brinda de varias herramientas para el manejo de punteros y de acceder a diferentes posiciones de memoria incluso a los propios puertos de entrada y/o salida. A continuación se indican y explican estos diferentes elementos.
@Objeto: Operador de dirección. Es un operador unario, lo que significa que requiere de un solo operando y que debe ser una variable o un identificador de módulo, escribiéndose a continuación del símbolo arroba. Ej.: @a obtiene la dirección de la variable a, es decir, su resultado está formado por el Segmento y el Desplazamiento en donde está alojada la variable indicada. El resultado de esta operación podría ser asignada a una variable de tipo puntero compatible con el tipo de dato con la variable a. Si a se la definió de tipo word y ptrW es un puntero a un tipo de dato de tipo word, entonces es válida la siguiente asignación:
ptrW := @a;
El resultado de esta asignación es que ptrW apunta a la dirección en donde está ubicada la variable a. Luego se podría asignar algún valor de tipo word a dicha dirección, por medio del puntero, como se indica a continuación:
ptrW^ := 5237;
La variable a, pasa a contener el valor 5237.
Ejemplo:
El siguiente ejemplo muestra como pasar un parámetro por referencia desde el punto de la llamada al módulo.
type
ptrWord = ^word;
procedure suma(x : ptrWord);
begin
x^:= x^ + 2
end;
var
sum : word;
i : byte;
begin
sum:= 0;
for i:= 1 to 10 do
suma(@sum);
writeln(‘Suma: ‘,sum)
end.
Addr(Objeto): La función Addr(Objeto) retorna la dirección de Objeto. El valor devuelto es un puntero genérico compatible con cualquier tipo de puntero al igual que nil (valor para indicar que un puntero no apunta a nada).
La función Addr tiene el mismo significado que el operador @ visto en los párrafos previos.
Ejemplo:
var
ptr : pointer;
begin
ptr:= Addr(ptr) {hace que ptr apunte a sí mismo}
if ptr = @ptr then {la dirección que contiene ptr es = a la dirección donde está ubicada ptr}
writeln(‘si’)
else
writeln(‘no’)
end.
Absolute var o Absolute Seg:Ofs: Se puede definir una variable solapada sobre la definición de otra variable sin importar el tipo de dato de c/u. de ellas. La palabra reservada absolute define una variable en una región de memoria indicada por un segmento y un desplazamiento, como se indica en el siguiente ejemplo:
Los punteros que apuntan a un tipo de datos se definen por medio del símbolo ^ y a continuación al tipo de dato al que apuntarán. El símbolo ^ se lee acento circunflejo. Las variables definidas como puntero a un tipo de dato determinan la cantidad de bytes a que hace referencia el puntero. Este tipo de puntero es el que se utilizará para desarrollar los diferentes problemas a resolver. En la sección type se definirán los tipos punteros. A continuación presentamos diferentes ejemplos de tipos punteros a tipos de datos simples:
type
cadn = string[20]; { se lee }
ptrEnt = ^integer; { ptrEnt es un tipo igual a puntero a un tipo de dato integer }
ptrLong = ^longint;
ptrReal = ^real;
ptrChar = ^char;
ptrCadn = ^cadn;
ptrBool = ^boolean;
ptrWord = ^word;
ptrByte = ^byte;
ptrShort = ^shortint;
Los siguientes ejemplos muestran definiciones de tipos punteros a tipos de datos estructurados:
type
RegAlu = record
NroLeg : longint;
ApeNom : cad20;
FecNac : longint
end;
ptrRec = ^RegAlu; { ptrRec es un puntero a un tipo de dato RegAlu }
Las variables de tipo puntero se definirán de la siguiente manera:
var
ptr1, ptr2 : ptrWord;
ptr3 : ptrRec;
ptr4 : ptrlong;
ptr5 : pointer;
Los punteros ptr1 y ptr2 apuntan a tipos de datos word y se referirán en consecuencia a dos bytes, el puntero ptr3 apunta a un tipo de dato RegAlu y se referirá a 29 bytes, el puntero ptr4 apunta a un tipo de dato longint y se refiere a 4 bytes, por último el puntero ptr5 apunta a una región de memoria y se refiere de una forma genérica es decir no se refiere a ningún tipo de dato en particular.
A continuación se presentan otros tipos de estructuras de datos y punteros:
type
VecPtr = array[1..10] of ptrRec;
ptrVector = ^VecPtr;
var
Vec : VecPtr;
ptrVec : ptrVector;
rAlu : RegAlu; { Está definido más arriba }
i : byte;
begin
for i:= 1 to 10 do
Vec[i]:= nil;
rAlu.NroLeg:= 112345;
rAlu.ApeNom:= ‘Martinez, Inés’;
rAlu.FecNac:= 23051981
Vec[1]:= @rAlu;
ptrVec:= Addr(Vec);
writeln(ptrVec^[1]^.NroLeg,’ ‘,ptrVec^[1]^.ApeNom,’ ‘,ptrVec^[1]^.FecNac)
end.
Un puntero puede apuntar a cualquier región de memoria, esto es, al segmento de datos, (como en los ejemplos dados anteriormente) o a los segmentos de código o al segmento de pila o al heap o como a cualquier otro segmento.
Turbo Pascal brinda de varias herramientas para el manejo de punteros y de acceder a diferentes posiciones de memoria incluso a los propios puertos de entrada y/o salida. A continuación se indican y explican estos diferentes elementos.
@Objeto: Operador de dirección. Es un operador unario, lo que significa que requiere de un solo operando y que debe ser una variable o un identificador de módulo, escribiéndose a continuación del símbolo arroba. Ej.: @a obtiene la dirección de la variable a, es decir, su resultado está formado por el Segmento y el Desplazamiento en donde está alojada la variable indicada. El resultado de esta operación podría ser asignada a una variable de tipo puntero compatible con el tipo de dato con la variable a. Si a se la definió de tipo word y ptrW es un puntero a un tipo de dato de tipo word, entonces es válida la siguiente asignación:
ptrW := @a;
El resultado de esta asignación es que ptrW apunta a la dirección en donde está ubicada la variable a. Luego se podría asignar algún valor de tipo word a dicha dirección, por medio del puntero, como se indica a continuación:
ptrW^ := 5237;
La variable a, pasa a contener el valor 5237.
Ejemplo:
El siguiente ejemplo muestra como pasar un parámetro por referencia desde el punto de la llamada al módulo.
type
ptrWord = ^word;
procedure suma(x : ptrWord);
begin
x^:= x^ + 2
end;
var
sum : word;
i : byte;
begin
sum:= 0;
for i:= 1 to 10 do
suma(@sum);
writeln(‘Suma: ‘,sum)
end.
Addr(Objeto): La función Addr(Objeto) retorna la dirección de Objeto. El valor devuelto es un puntero genérico compatible con cualquier tipo de puntero al igual que nil (valor para indicar que un puntero no apunta a nada).
La función Addr tiene el mismo significado que el operador @ visto en los párrafos previos.
Ejemplo:
var
ptr : pointer;
begin
ptr:= Addr(ptr) {hace que ptr apunte a sí mismo}
if ptr = @ptr then {la dirección que contiene ptr es = a la dirección donde está ubicada ptr}
writeln(‘si’)
else
writeln(‘no’)
end.
Absolute var o Absolute Seg:Ofs: Se puede definir una variable solapada sobre la definición de otra variable sin importar el tipo de dato de c/u. de ellas. La palabra reservada absolute define una variable en una región de memoria indicada por un segmento y un desplazamiento, como se indica en el siguiente ejemplo:
Seg(Objeto): La función Seg(Objeto) retorna un valor de tipo word indicando la dirección del segmento en donde se localiza el objeto indicado en su parámetro formal. Objeto puede ser una variable o el nombre de un módulo.
Ofs(Objeto): La función Ofs(Objeto) retorna un valor de tipo word indicando la dirección del desplazamiento en donde se localiza el objeto indicado en su parámetro formal. Objeto puede ser un variable o el nombre de un módulo.
Ejemplos:
El siguiente ejemplo muestra el uso de las funciones Seg y Ofs.
uses
newdelay, crt;
Procedure Proc;
begin
writeln(‘Módulo Proc’)
end;
Function Func:byte;
begin
Func:= 5
end;
var
a : longint;
begin
writeln(‘Segmento(a): ‘,Seg(a));
writeln(‘Desplazamiento(a): ‘,Ofs(a));
writeln(‘Segmento(Proc): ‘,Seg(Proc));
writeln(‘Desplazamiento(Proc): ‘,Ofs(Proc));
writeln(Seg(Func),’:’,Ofs(Func));
writeln(Seg(ClrScr),’:’,Ofs(ClrScr)); {Oops, es otro segmento de código}
writeln(Seg(gotoxy),’:’,Ofs(gotoxy));
writeln(Seg(PatchCrt),’:’,Ofs(PatchCrt)); {Oops, y este otro segmento de código}
end.
Mem[Seg:Ofs]: Turbo Pascal implementa tres arreglos predefinidos para acceder directamente a la memoria: mem, memW y memL, cada una de las componentes es de tipo byte, word y longint respectivamente. Los arreglos de memoria utilizan una sintaxis especial para los índices: dos expresiones de palabra de tipo-entero, separadas por dos puntos, indican el segmento base y el desplazamiento para acceder a la locación en la memoria.
Ejemplo:
El siguiente ejemplo ilustra como acceder a la memoria de video:
mem[$B800:0] := 65;
mem[$B800:1] := 1;
En la pantalla de texto en las coordenadas (1, 1) se visualiza el carácter ‘A’ en color azul para el carácter y con fondo negro. La dirección $B800:$0000 representa la memoria de video en modo texto para la primer página de un total de ocho, Las direcciones de inicio de las siete restantes páginas se ubican en los desplazamientos $1000, $2000, $3000, $4000, $5000, $6000 y $7000 respectivamente. La ventaja de tener varias páginas se destaca al momento de cambiar los datos presentes en la pantalla; en vez de cambiar los datos sobre la misma página se podría utilizar otra página y luego mostrar los datos de esa otra página, el resultado será verlos más rápidamente. Los desplazamientos pares representan caracteres y los desplazamientos impares representan los atributos de esos caracteres. En el ejemplo, el valor 65 representa el carácter ‘A’ asignado a una posición par, mientras que el valor 1 representa el color azul para ese carácter y color de fondo negro, asignado a la posición impar adyacente, por lo tanto, un par de bytes indican una posición en la pantalla de video en modo texto, el primer byte –par- representa el carácter o símbolo y el segundo byte –impar- representa el atributo de ese carácter. Los valores de atributos de 0 a 15, el color de fondo es el negro, de 16 a 31, el color de fondo es el azul, de 32 a 47, el color de fondo es el verde y siguiendo así con otros colores. En total, los colores para el carácter son 16 y para los de fondo del carácter son 8. Una pantalla de texto presenta 80 columnas por 25 filas, lo que da un total de 80 x 25 = 2000 posiciones en la pantalla. Esto requiere 2000 posiciones en memoria para el carácter y 2000 posiciones de memoria para el atributo intercalados, en donde, la primer componente de cada par es el carácter y la segunda componente de cada par representa el atributo.
Ejemplo:
mem[$B800:2] := 66;
mem[$B800:3] := 18;
En las coordenadas (2, 1), se representa el carácter ‘B’ con color verde para el símbolo y de color azul para el fondo. Para establecer una posición en la memoria de video para una coordenada (x, y), se procede a aplicar la siguiente expresión:
Para la representación del carácter:
posMemCar := ((y-1) * 80 + (x-1)) * 2
Mientras que para el atributo es:
posMemAtrib := ((y-1) * 80 + (x-1)) * 2 + 1
Ejemplo:
El siguiente ejemplo muestra como cambiar el valor de una posición de memoria representado por una variable.
var
a : byte;
begin
mem[Seg(a):Ofs(a)]:= 5;
writeln(‘a= ‘,a,’ = ‘,mem[Seg(a):Ofs(a)]);
readln
end.
El código anterior asigna el valor 5 en la dirección de memoria en donde está alojada la variable a, luego se emite el contenido de la variable a y el contenido de la dirección en donde está ubicada la variable a, por lo que el programa emite dos veces el valor 5.
Ejemplo:
El siguiente ejemplo obtine de la lectura en la posición de memoria $0040:$0050 y $0040:$0051 la ubicación del cursor de la primer página en la pantalla de texto.
var
x, y : byte;
begin
gotoxy(20, 5);
x:= mem[$0040:$0050] + 1; {Equivalente a wherex}
y:= mem[$0040:$0051] + 1; {Equivalente a wherey}
writeln(‘Posición del cursor: x= ‘,x,’ y= ‘,y)
end.
Ptr(Seg:Ofs): La función ptr(Seg,Ofs) retorna un valor de tipo pointer, es decir, una dirección de memoria a partir de un segmento base y de un desplazamiento dados. El tipo de cada uno de los parámetros formales son word.
Ejemplo:
Port[dir]: Para accesos a los puertos de datos del microprocesador. Turbo Pascal implementa dos arreglos predefinidos de una dimensión, port y portW, y cada elemento representa un puerto de datos, en donde las direcciones de los puertos corresponden a sus índices. El tipo de indice es una palabra de tipo entero. Las componentes del arreglo de puerto son componentes de tipo Byte y de tipo word para el arreglo de portw.
Cuando un valor es asignado a la componente de port o portw, el valor es una salida al puerto seleccionado. Cuando una componente de port o portw es referenciado en una expresión, su valor es leído del puerto seleccionado. El uso de los arreglos port y portw está limitado a asignaciones y referencias en expresiones solamente; esto es, las componentes de port y portw no pueden ser utilizados como parámetros variables. También, las referencias completas a los arreglos port o portw (referencias sin el índice) no son permitidas.
Ejemplos:
valor:= port[$60]; {Puerto del controlador del teclado}
port[$3D0]:= valor; {Puerto del adaptador gráfico avanzado EGA}
Se debe tener mucho cuidado al trabajar con los puertos en forma directa, ya que un valor mal asignado podría ocasionar ciertos problemas, como por ejemplo bloquearse el sistema. Las direcciones de un puerto no tienen nada que ver con las direcciones de memoria, es decir, ante un mismo valor de dirección son dos lugares físicos diferentes si uno se refiere a un puerto y el otro se refiere a la memoria R.A.M.
nil: La palabra reservada nil es utilizada para asignar un valor nulo a cualquier variable puntero, como por ejemplo, ptr := nil. Es válido comparar el valor de un puntero para averiguar si no apunta a nada o bien si apunta a una dirección específica, como por ejemplo, ptr = nil o bien ptr ≠ nil. Si un puntero no apunta a nada o tiene un valor indefinido será error hacer una desreferencia del mismo.
new(ptr): El procedimiento new(ptr) crea una variable dinámica en el heap y que pasará ser apuntada por el puntero ptr indicado en su parámetro actual. La región de memoria asignada debe ser contigua, es decir, no fragmentada, por lo tanto, se debe encontrar un bloque de memoria lo suficientemente grande como para poder abastecer el pedido solicitado, de acuerdo al tamaño del nodo. En caso de encontrar espacio suficiente contiguo, se descuenta del heap la cantidad de memoria solicitada y ptr pasa a apuntar el primer byte de esa región de memoria. La cantidad de bytes a descontar se determina por el tipo de dato al que apunta ptr. Si no se llegara a encontrar un bloque de memoria contiguo lo suficientemente requerido, entonces ptr quedará indefinido.
El siguiente ejemplo crea una variable dinámica en el heap:
dispose(ptr): El procedimiento dispose(ptr) libera la región de memoria en el heap apuntada por ptr. Se producirá un error si ptr no apunta a nada o si no apunta al heap. Luego de realizar esta acción ptr quedará indefinido y hacer una desreferencia ocasionará en un error
[1]. La región de memoria liberada queda nuevamente disponible al heap y se incrementa el tamaño disponible de acuerdo a la magnitud del tipo de dato al que apuntaba el puntero ptr.
MemAvail: La función memavail retorna un valor de tipo longint que indica la cantidad de memoria libre en el heap.
MaxAvail: La función maxavail retorna un valor de tipo longint que indica el bloque de memoria contigua más grande.
Las estructuras dinámicas de datos pueden dividirse en dos grandes grupos:
MemAvail: La función memavail retorna un valor de tipo longint que indica la cantidad de memoria libre en el heap.
MaxAvail: La función maxavail retorna un valor de tipo longint que indica el bloque de memoria contigua más grande.
Las estructuras dinámicas de datos pueden dividirse en dos grandes grupos:
En esta cátedra se llega hasta las estructuras lineales.
NODO: El nodo es una unidad de información y que contiene básicamente dos campos, un campo INFO y un campo SGTE. El campo INFO puede ser de tipo estructurado para que pueda contener más de un valor.
Estructura lineal dinámica del tipo PILA
PILAS
Una pila esta compuesta por una superposición de elementos, como por ejemplo una pila de platos. En los procesos de Sistemas computacionales una pila es utilizada, por ejemplo, cuando el bloque principal invoca a un módulo A y éste a otro módulo B, cuando el módulo B finaliza debe retornar a quien lo llamó y una vez que finaliza el módulo A debe retornar a quien lo llamó que es el bloque principal. Para saber esto el sistema guarda en una pila las direcciones de retorno y va retirando en la medida que finaliza un módulo. La última dirección guardada en la pila es la primera en ser retirada. Otra situación que puede presentarse es en el caso de las expresiones, el proceso debe transformar una notación infija (esto es los operadores están ubicados entre sus operandos) a otra forma de notación más adaptada para el proceso computacional como lo es la notación prefija o sufija (esto es el operador aparece antes de sus operandos o bien después de sus operandos respectivamente). En estas dos últimas formas no son necesarios el uso de los paréntesis. Estos tipos de notaciones se deben a los trabajos realizados por el matemático polaco Lukasiewicsz.
Ejemplos:
a+b {notación infija}
+ab {notación prefija}
ab+ {notación postfija}
Las estructuras dinámicas de datos del tipo pila presentan restricciones en cuanto a su manejo. Esto es, cada nuevo elemento que se incorpore a la pila debe de realizarse por la parte superior o tope o cima, y cada elemento que se retire de la pila debe efectuarse tambien por la parte superior o tope o cima. Esto hace que este tipo de estructura el último elemento en ingresar sea el primer elemento en salir, a este movimiento de los elementos que entran y salen se lo conoce como método L.I.F.O.. Por lo tanto, está terminantemente prohibido recorrer la pila, es decir, acceder a los elementos del mismo sin haber retirado los que se encontraban por el tope. Todo elemento que se incorpore o retire debe de hacerse si o si por el tope. Un puntero externo estará apuntando siempre al elemento que se encuentre en el tope. Una vez que se incorpore un nuevo elemento, el puntero externo apuntará al nuevo elemento incorporado. Por otro lado, cada vez que se retire un elemento, el puntero externo apuntará al elemento que haya quedado en el tope, siempre y cuando haya otro elemento en la pila, caso contrario la pila quedará vacía y el puntero externo no apuntará a nada. El primer elemento incorporado a la pila no apunta a nada y cada nuevo elemento que se incorpore posteriormente apuntará al elemento que se encontraba en el tope antes de la incorporación del nuevo elemento. La primer acción que debemos realizar con una pila será asignar el valor nil al puntero externo a la pila. El valor nil es un valor genérico para que un puntero no apunte a nada, en realidad le asigna la dirección de segmento = 0 y desplazamiento = 0. Es decir, si Pila es el puntero externo a la pila, hacer Pila:= nil, es lo mismo que hacer Pila:= ptr(0,0).
En general un elemento de la pila estará constituido por 2 componentes. Una componente indicará la información de ese elemento y la otra componente un puntero empotrado el cual apuntará al elemento anterior ubicado en la pila. Por lo tanto el puntero externo a la pila y cada uno de los punteros empotrados apuntan a una misma estructura de datos del tipo pila.
La estructura idónea para representar un elemento de la pila es el tipo registro que tendrá básicamente dos campos, un campo INFO que contiene un valor de información y un campo SGTE que contendrá la dirección del elemento anterior en la pila, salvo que sea el primero en cuyo caso contendrá el valor nil.
type
TipoInfo = string[30]; {puede ser un registro}
TipoPila = ^TipoNodo;
TipoNodo = Record
Info : tipoInfo;
Sgte : tipoPila
end;
var
Pila : TipoPila;
Los procesos para el manejo de la estructura del tipo pila son:
1. CrearPila(var Pila:tipoPila); o en su lugar Pila:= nil
2. Meter(var Pila:tipoPila; valor:tipoInfo);
3. Sacar(var Pila:tipoPila; var valor:tipoInfo);
4. PilaVacia(var Pila:tipoPila): boolean; o en su lugar preguntar si Pila = nil.
5. PilaLlena(MagnitudNodo: word): boolean; o en su lugar MaxAvail MENOR SizeOf(Nodo)
A continuación se presenta un proceso que ingresa tres elementos a la pila y posteriormente los retira.
NODO: El nodo es una unidad de información y que contiene básicamente dos campos, un campo INFO y un campo SGTE. El campo INFO puede ser de tipo estructurado para que pueda contener más de un valor.
Estructura lineal dinámica del tipo PILA
PILAS
Una pila esta compuesta por una superposición de elementos, como por ejemplo una pila de platos. En los procesos de Sistemas computacionales una pila es utilizada, por ejemplo, cuando el bloque principal invoca a un módulo A y éste a otro módulo B, cuando el módulo B finaliza debe retornar a quien lo llamó y una vez que finaliza el módulo A debe retornar a quien lo llamó que es el bloque principal. Para saber esto el sistema guarda en una pila las direcciones de retorno y va retirando en la medida que finaliza un módulo. La última dirección guardada en la pila es la primera en ser retirada. Otra situación que puede presentarse es en el caso de las expresiones, el proceso debe transformar una notación infija (esto es los operadores están ubicados entre sus operandos) a otra forma de notación más adaptada para el proceso computacional como lo es la notación prefija o sufija (esto es el operador aparece antes de sus operandos o bien después de sus operandos respectivamente). En estas dos últimas formas no son necesarios el uso de los paréntesis. Estos tipos de notaciones se deben a los trabajos realizados por el matemático polaco Lukasiewicsz.
Ejemplos:
a+b {notación infija}
+ab {notación prefija}
ab+ {notación postfija}
Las estructuras dinámicas de datos del tipo pila presentan restricciones en cuanto a su manejo. Esto es, cada nuevo elemento que se incorpore a la pila debe de realizarse por la parte superior o tope o cima, y cada elemento que se retire de la pila debe efectuarse tambien por la parte superior o tope o cima. Esto hace que este tipo de estructura el último elemento en ingresar sea el primer elemento en salir, a este movimiento de los elementos que entran y salen se lo conoce como método L.I.F.O.. Por lo tanto, está terminantemente prohibido recorrer la pila, es decir, acceder a los elementos del mismo sin haber retirado los que se encontraban por el tope. Todo elemento que se incorpore o retire debe de hacerse si o si por el tope. Un puntero externo estará apuntando siempre al elemento que se encuentre en el tope. Una vez que se incorpore un nuevo elemento, el puntero externo apuntará al nuevo elemento incorporado. Por otro lado, cada vez que se retire un elemento, el puntero externo apuntará al elemento que haya quedado en el tope, siempre y cuando haya otro elemento en la pila, caso contrario la pila quedará vacía y el puntero externo no apuntará a nada. El primer elemento incorporado a la pila no apunta a nada y cada nuevo elemento que se incorpore posteriormente apuntará al elemento que se encontraba en el tope antes de la incorporación del nuevo elemento. La primer acción que debemos realizar con una pila será asignar el valor nil al puntero externo a la pila. El valor nil es un valor genérico para que un puntero no apunte a nada, en realidad le asigna la dirección de segmento = 0 y desplazamiento = 0. Es decir, si Pila es el puntero externo a la pila, hacer Pila:= nil, es lo mismo que hacer Pila:= ptr(0,0).
En general un elemento de la pila estará constituido por 2 componentes. Una componente indicará la información de ese elemento y la otra componente un puntero empotrado el cual apuntará al elemento anterior ubicado en la pila. Por lo tanto el puntero externo a la pila y cada uno de los punteros empotrados apuntan a una misma estructura de datos del tipo pila.
La estructura idónea para representar un elemento de la pila es el tipo registro que tendrá básicamente dos campos, un campo INFO que contiene un valor de información y un campo SGTE que contendrá la dirección del elemento anterior en la pila, salvo que sea el primero en cuyo caso contendrá el valor nil.
type
TipoInfo = string[30]; {puede ser un registro}
TipoPila = ^TipoNodo;
TipoNodo = Record
Info : tipoInfo;
Sgte : tipoPila
end;
var
Pila : TipoPila;
Los procesos para el manejo de la estructura del tipo pila son:
1. CrearPila(var Pila:tipoPila); o en su lugar Pila:= nil
2. Meter(var Pila:tipoPila; valor:tipoInfo);
3. Sacar(var Pila:tipoPila; var valor:tipoInfo);
4. PilaVacia(var Pila:tipoPila): boolean; o en su lugar preguntar si Pila = nil.
5. PilaLlena(MagnitudNodo: word): boolean; o en su lugar MaxAvail MENOR SizeOf(Nodo)
A continuación se presenta un proceso que ingresa tres elementos a la pila y posteriormente los retira.
Estructura lineal dinámica del tipo COLA
COLAS
El término cola es aplicado a muchos aspectos de la realidad, por citar algunos, una cola de espera en la parada del colectivo, en la sala de espera de un consultorio, en la caja de un supermercado o para la atención de la primer caja que se desocupe en un banco. En los procesos de Sistemas computacionales una cola es utilizada, por ejemplo, cuando distintas tareas requieran el uso de un periférico no compartido, como lo es la impresora, en estos casos cada tarea que requiera el uso de la impresora, y estando ocupada atendiendo a un proceso previo, el Sistema Operativo redirecciona la salida hacia un archivo, de manera tal que, cada tarea en curso puede continuar su proceso. Cada una de las salidas enviadas a archivos en disco se ubican en una cola de espera, para que reciban en su momento oportuno la asignación de la impresora. El primero en ingresar a la cola será el primero en ser atendido al liberarse el recurso de la impresora.
Las estructuras dinámicas de datos del tipo cola presentan restricciones en cuanto a su manejo. Esto es, cada nuevo elemento que se incorpore a la cola debe de realizarse por la parte posterior o final o atrás, y cada elemento que se retire de la cola debe efectuarse por la parte del frente o por delante o inicio. Esto hace que este tipo de estructura el primer elemento en ingresar sea el primer elemento en salir, a este movimiento de los elementos que entran y salen se lo conoce como método F.I.F.O.. Está en consecuencia terminantemente prohibido recorrer la cola, es decir, acceder a los elementos del mismo sin haber retirado los que se encontraban por el frente. Todo elemento que se incorpore debe de hacerse si o si por el final y cada elemento que se retire debe de hacerse si o si por el frente. Un puntero externo estará apuntando siempre al primer elemento de la cola y un segundo puntero externo estará apuntando siempre al último elemento de la cola. Una vez que se incorpore un nuevo elemento, el puntero externo final apuntará al nuevo elemento incorporado. Por otro lado, cada vez que se retire un elemento, el puntero externo frente apuntará al nuevo elemento que haya quedado al inicio, siempre y cuando haya otro elemento en la cola, caso contrario la cola quedará vacía y los punteros externos no apuntarán a nada. Cada nuevo elemento incorporado a la cola el campo Sgte no apunta a nada y el elemento anterior dejará de no apuntar a nada para pasar a apuntar al nuevo elemento incorporado a la cola. La primera acción que debemos realizar será asignar el valor nil a los punteros externos a la cola, esto es, ColaFrente y ColaFin, si estos fueran los nombres de los punteros externos. El valor nil es un valor genérico para que un puntero no apunte a nada, en realidad le asigna la dirección de segmento = 0 y desplazamiento = 0. Es decir, si ColaFrente y ColaFin son los punteros externos a la cola, hacer ColaFrente:= nil, y ColaFin:= nil, es lo mismo que hacer ColaFrente:= ptr(0,0) y ColaFin:= ptr(0,0).
En general un elemento de la cola estará constituido por 2 componentes. Una componente indicará la información de ese elemento y la otra componente un puntero empotrado el cual apuntará al elemento siguiente ubicado en la cola. Por lo tanto los punteros externos a la cola y cada uno de los punteros empotrados apuntan a una misma estructura de datos del tipo cola.
La estructura idónea para representar un elemento de la cola es el tipo registro que tendrá básicamente dos campos, un campo INFO que contiene un valor de información y un campo SGTE que contendrá la dirección del elemento siguiente en la cola, salvo que sea el último en cuyo caso contendrá el valor nil.
type
TipoInfo = string[30]; {puede ser un registro}
TipoCola = ^TipoNodo;
TipoNodo = Record
Info : tipoInfo;
Sgte : tipoCola
end;
var
ColaFrente, ColaFin : TipoCola;
Los procesos para el manejo de la estructura del tipo Cola son:
1. CrearCola(var ColaFrente, ColaFin:tipoCola); o ColaFrente:= nil; ColaFin:= nil;
2. Agregar(var ColaFrente, ColaFin:tipoCola; valor:tipoInfo);
3. Suprimir(var ColaFrente, ColaFin:tipoCola; var valor:tipoInfo);
4. ColaVacia(var ColaFrente:tipoCola):boolean; o en su lugar preguntar si Pila = nil.
5. ColaLlena(MagnitudNodo:word):boolean; o en su lugar MaxAvail MENOR SizeOf(Nodo)
A continuación se presenta un proceso que ingresa tres elementos a la pila y posteriormente los retira.
Agregar(ColaFrente, ColaFin, x)
Las estructuras dinámicas de datos del tipo cola presentan restricciones en cuanto a su manejo. Esto es, cada nuevo elemento que se incorpore a la cola debe de realizarse por la parte posterior o final o atrás, y cada elemento que se retire de la cola debe efectuarse por la parte del frente o por delante o inicio. Esto hace que este tipo de estructura el primer elemento en ingresar sea el primer elemento en salir, a este movimiento de los elementos que entran y salen se lo conoce como método F.I.F.O.. Está en consecuencia terminantemente prohibido recorrer la cola, es decir, acceder a los elementos del mismo sin haber retirado los que se encontraban por el frente. Todo elemento que se incorpore debe de hacerse si o si por el final y cada elemento que se retire debe de hacerse si o si por el frente. Un puntero externo estará apuntando siempre al primer elemento de la cola y un segundo puntero externo estará apuntando siempre al último elemento de la cola. Una vez que se incorpore un nuevo elemento, el puntero externo final apuntará al nuevo elemento incorporado. Por otro lado, cada vez que se retire un elemento, el puntero externo frente apuntará al nuevo elemento que haya quedado al inicio, siempre y cuando haya otro elemento en la cola, caso contrario la cola quedará vacía y los punteros externos no apuntarán a nada. Cada nuevo elemento incorporado a la cola el campo Sgte no apunta a nada y el elemento anterior dejará de no apuntar a nada para pasar a apuntar al nuevo elemento incorporado a la cola. La primera acción que debemos realizar será asignar el valor nil a los punteros externos a la cola, esto es, ColaFrente y ColaFin, si estos fueran los nombres de los punteros externos. El valor nil es un valor genérico para que un puntero no apunte a nada, en realidad le asigna la dirección de segmento = 0 y desplazamiento = 0. Es decir, si ColaFrente y ColaFin son los punteros externos a la cola, hacer ColaFrente:= nil, y ColaFin:= nil, es lo mismo que hacer ColaFrente:= ptr(0,0) y ColaFin:= ptr(0,0).
En general un elemento de la cola estará constituido por 2 componentes. Una componente indicará la información de ese elemento y la otra componente un puntero empotrado el cual apuntará al elemento siguiente ubicado en la cola. Por lo tanto los punteros externos a la cola y cada uno de los punteros empotrados apuntan a una misma estructura de datos del tipo cola.
La estructura idónea para representar un elemento de la cola es el tipo registro que tendrá básicamente dos campos, un campo INFO que contiene un valor de información y un campo SGTE que contendrá la dirección del elemento siguiente en la cola, salvo que sea el último en cuyo caso contendrá el valor nil.
type
TipoInfo = string[30]; {puede ser un registro}
TipoCola = ^TipoNodo;
TipoNodo = Record
Info : tipoInfo;
Sgte : tipoCola
end;
var
ColaFrente, ColaFin : TipoCola;
Los procesos para el manejo de la estructura del tipo Cola son:
1. CrearCola(var ColaFrente, ColaFin:tipoCola); o ColaFrente:= nil; ColaFin:= nil;
2. Agregar(var ColaFrente, ColaFin:tipoCola; valor:tipoInfo);
3. Suprimir(var ColaFrente, ColaFin:tipoCola; var valor:tipoInfo);
4. ColaVacia(var ColaFrente:tipoCola):boolean; o en su lugar preguntar si Pila = nil.
5. ColaLlena(MagnitudNodo:word):boolean; o en su lugar MaxAvail MENOR SizeOf(Nodo)
A continuación se presenta un proceso que ingresa tres elementos a la pila y posteriormente los retira.
Agregar(ColaFrente, ColaFin, x)
Suprimir(ColaFrente, ColaFin, x);
Estructura lineal dinámica del tipo LISTA
LISTAS
Una lista esta compuesta por una serie de elementos, como por ejemplo una lista de personas, o animales o cosas. En general, trabajaremos con listas ordenadas por el valor de un campo clave o llave.
Las estructuras dinámicas de datos del tipo lista no presentan ningún tipo de restricciones en cuanto a su manejo. Esto es, cada nuevo elemento que se incorpore a la lista puede realizarse por cualquier parte, y cada elemento que se retire de la lista puede efectuarse tambien por cualquier parte. Un puntero externo estará apuntando siempre al primer elemento que se encuentre en la lista en un momento determinado. La primer acción que debemos realizar con una lista será asignar el valor nil al puntero externo a la lista. El valor nil es un valor genérico para que un puntero no apunte a nada, en realidad le asigna la dirección de segmento = 0 y desplazamiento = 0. Es decir, si Lista es el puntero externo a la lista, hacer Lista:= nil, es lo mismo que hacer Lista:= ptr(0,0).
En general un elemento de la lista estará constituido por 2 componentes. Una componente indicará la información de ese elemento y la otra componente un puntero empotrado el cual apuntará al elemento siguiente ubicado en la lista. Por lo tanto el puntero externo a la lista y cada uno de los punteros empotrados apuntan a una misma estructura de datos del tipo lista.
La estructura idónea para representar un elemento de la lista es el tipo registro que tendrá básicamente dos campos, un campo INFO que contiene un valor de información y un campo SGTE que contendrá la dirección del elemento siguiente en la lista, salvo que sea el último en cuyo caso contendrá el valor nil.
type
TipoInfo = string[30]; {puede ser un registro}
TipoLista = ^TipoNodo;
TipoNodo = Record
Info : tipoInfo;
Sgte : tipoLista
end;
var
Pila : TipoLista;
Los procesos para el manejo de la estructura del tipo lista son:
1. CrearLista(var Lista:tipoLista); o en su lugar Lista:= nil
2. InsertaNodo(var Lista:tipoLista; valor:tipoInfo);
3. InsertaPrimero(var Lista:tipoLista; valor:tipoInfo);
4. InsertaDelante(var Lista:tipoLista; valor:tipoInfo);
5. InsertaEnMedio(var Lista:tipoLista; valor:tipoInfo);
6. SuprimeNodo(var Lista:tipoLista; var valor:tipoInfo);
7. ListaVacia(var Lista:tipoLista): boolean; o en su lugar preguntar si Lista = nil.
8. ListaLlena(MagnitudNodo: word): boolean; o en su lugar MaxAvail MENOR SizeOf(Nodo)
El módulo InsertaPrimero es invocado cuando el puntero a la Lista es nil y esto sucede una vez, en cambio el módulo InsertaDelante es invocado cuando un nuevo nodo se incorpora a la lista al inicio, debido a que el valor del campo clave es menor al valor del primer nodo en la lista. Solo una sentencia difiere en ambos módulos, esto es, cuando se asigna al campo Sgte del nuevo nodo el valor nil o el valor del puntero externo de Lista, pero tanto en un caso como en el otro se podría asignar el valor del puntero externo de Lista, debido a que cuando la lista está vacía se asignará el valor nil y cuando ya exista algún nodo en la lista se le asignará la dirección del nodo que está siendo apuntado por el puntero externo Lista. Por lo tanto, se reemplazarán los módulos InsertaPrimero e InsertaDelante por el módulo InsertaInicio(var Lista:tipoLista; valor:tipoInfo); en el cual la sentencia ptr^.Sgte:= nil o ptr^.Sgte.Lista establecida en los módulos InsertaPrimero e InsertaDelante respectivamente se reemplará por ptr^.Sgte.Lista.
El módulo InsertaNodo(Lista, valor); también se reemplazará por otras sentencias. En lugar de realizar tres decisiones solo serán necesarias tomar dos decisiones, en la cual, la primera decisión tendrá una condición compuesta, siendo ellas (Lista = nil) or (valor MENOR Lista^.Info), en los casos en que sea verdadero se invocará al módulo InsertaInicio y en caso contrario, se invocará a InsertaEnMedio.
A continuación se presenta un proceso que ingresa cinco elementos a la lista manteniendo siempre un orden por el valor del campo Info en forma ascendente y posteriormente los retira.
Lista:= nil;
for i:= 1 to 5 do begin
write(‘Ing. valor: ‘);
Hacer doble clic readln(x); {20, 50, 10, 30, 70}
InsertaNodo(Lista,x)
SuprimeNodo(Lista,x);
Estructura lineal dinámica del tipo LISTA
LISTAS
Una lista esta compuesta por una serie de elementos, como por ejemplo una lista de personas, o animales o cosas. En general, trabajaremos con listas ordenadas por el valor de un campo clave o llave.
Las estructuras dinámicas de datos del tipo lista no presentan ningún tipo de restricciones en cuanto a su manejo. Esto es, cada nuevo elemento que se incorpore a la lista puede realizarse por cualquier parte, y cada elemento que se retire de la lista puede efectuarse tambien por cualquier parte. Un puntero externo estará apuntando siempre al primer elemento que se encuentre en la lista en un momento determinado. La primer acción que debemos realizar con una lista será asignar el valor nil al puntero externo a la lista. El valor nil es un valor genérico para que un puntero no apunte a nada, en realidad le asigna la dirección de segmento = 0 y desplazamiento = 0. Es decir, si Lista es el puntero externo a la lista, hacer Lista:= nil, es lo mismo que hacer Lista:= ptr(0,0).
En general un elemento de la lista estará constituido por 2 componentes. Una componente indicará la información de ese elemento y la otra componente un puntero empotrado el cual apuntará al elemento siguiente ubicado en la lista. Por lo tanto el puntero externo a la lista y cada uno de los punteros empotrados apuntan a una misma estructura de datos del tipo lista.
La estructura idónea para representar un elemento de la lista es el tipo registro que tendrá básicamente dos campos, un campo INFO que contiene un valor de información y un campo SGTE que contendrá la dirección del elemento siguiente en la lista, salvo que sea el último en cuyo caso contendrá el valor nil.
type
TipoInfo = string[30]; {puede ser un registro}
TipoLista = ^TipoNodo;
TipoNodo = Record
Info : tipoInfo;
Sgte : tipoLista
end;
var
Pila : TipoLista;
Los procesos para el manejo de la estructura del tipo lista son:
1. CrearLista(var Lista:tipoLista); o en su lugar Lista:= nil
2. InsertaNodo(var Lista:tipoLista; valor:tipoInfo);
3. InsertaPrimero(var Lista:tipoLista; valor:tipoInfo);
4. InsertaDelante(var Lista:tipoLista; valor:tipoInfo);
5. InsertaEnMedio(var Lista:tipoLista; valor:tipoInfo);
6. SuprimeNodo(var Lista:tipoLista; var valor:tipoInfo);
7. ListaVacia(var Lista:tipoLista): boolean; o en su lugar preguntar si Lista = nil.
8. ListaLlena(MagnitudNodo: word): boolean; o en su lugar MaxAvail MENOR SizeOf(Nodo)
El módulo InsertaPrimero es invocado cuando el puntero a la Lista es nil y esto sucede una vez, en cambio el módulo InsertaDelante es invocado cuando un nuevo nodo se incorpora a la lista al inicio, debido a que el valor del campo clave es menor al valor del primer nodo en la lista. Solo una sentencia difiere en ambos módulos, esto es, cuando se asigna al campo Sgte del nuevo nodo el valor nil o el valor del puntero externo de Lista, pero tanto en un caso como en el otro se podría asignar el valor del puntero externo de Lista, debido a que cuando la lista está vacía se asignará el valor nil y cuando ya exista algún nodo en la lista se le asignará la dirección del nodo que está siendo apuntado por el puntero externo Lista. Por lo tanto, se reemplazarán los módulos InsertaPrimero e InsertaDelante por el módulo InsertaInicio(var Lista:tipoLista; valor:tipoInfo); en el cual la sentencia ptr^.Sgte:= nil o ptr^.Sgte.Lista establecida en los módulos InsertaPrimero e InsertaDelante respectivamente se reemplará por ptr^.Sgte.Lista.
El módulo InsertaNodo(Lista, valor); también se reemplazará por otras sentencias. En lugar de realizar tres decisiones solo serán necesarias tomar dos decisiones, en la cual, la primera decisión tendrá una condición compuesta, siendo ellas (Lista = nil) or (valor MENOR Lista^.Info), en los casos en que sea verdadero se invocará al módulo InsertaInicio y en caso contrario, se invocará a InsertaEnMedio.
A continuación se presenta un proceso que ingresa cinco elementos a la lista manteniendo siempre un orden por el valor del campo Info en forma ascendente y posteriormente los retira.
Lista:= nil;
for i:= 1 to 5 do begin
write(‘Ing. valor: ‘);
Hacer doble clic readln(x); {20, 50, 10, 30, 70}
InsertaNodo(Lista,x)
SuprimeNodo(Lista,x);
Los módulos presentados anteriormente son solo un modelo que resuelven algunas de las situaciones que podrán presentarse en diferentes procesos. Por ejemplo, los procesos anteriormente indicados ordenan una lista en forma creciente, siempre genera una nueva variable dinámica al invocarlos, y en casos de repetición del campo clave, se inserta como segundo nodo si el valor de la clave que se repite es el valor del primer nodo de la lista, pero se incorporará delante de los valores de las otras claves correspondientes. Tal vez este comportamiento sea el esperado para ciertos procesos pero no para otros. En ciertos casos algunos ligeros cambios modificarán esos comportamiento y en otros casos debamos realizar modificaciones más drásticas. Hay situaciones en la cual no queremos repetir el valor de un campo clave, lo que hacemos es buscar si existe ese valor en la lista, en caso de no encontrarse creamos el nodo, pero si existe no. En el primer caso al no existir el nodo, si invocamos al módulo InsertaNodo, se volverá a recorrer nuevamente la lista hasta el punto de inserción, pero si ya habíamos recorrido la lista, porque no optimizar el proceso enlazando el nuevo nodo con aquellos nodos dentro de su entorno localizados en la búsqueda previa. Si queremos enlazar los nodos en una lista pero ordenada en forma decreciente, ¿qué debemos modificar de los módulos mencionados más arriba?. Si el campo Info debemos almacenar más de un valor, entonces deberá ser de un tipo estructurado de datos, como ser del tipo registro y en estos casos también vale la siguiente pregunta ¿cuáles son los cambios a realizar en los módulos indicados precedentemente? Estas y otras cuestiones más podrían presentarse en los diferentes procesos y que deberíamos replantearnos acerca de utilizar o no esos módulos o reemplazarlos por otros.
Para los procesos que requieran no repetir nodos para el valor de una misma clave, a continuación se presentan dos módulos adicionales a los establecidos previamente:
1. ExisteNodo(var Lista.tipoLista; valor:tipoInfo): tipoLista;
El módulo ExisteNodo busca un nodo con un valor en cuyo campo clave coincida con el valor pasado, en ese caso informa la dirección de memoria del nodo con valor igual a valor, caso contrario retorna la dirección del nodo previo o si no existe un valor nil.
1. CrearNodo(var Lista, ptrNodoAnt:tipoLista; valor.tipoInfo);
El módulo CrearNodo crea un nuevo nodo enlazado a continuación del nodo apuntado por ptrNodoAnt si es distinto de nil, caso contrario lo inserta por el inicio de la lista.
En los casos de requerir la localización ordinal de un nodo en la lista, se presenta el siguiente módulo:
BuscarNodo(var Lista:tipoLista; pos:longint) : tipoLista;
Ejemplo: Se tiene una lista, en donde cada nodo representa un día de un mes. Buscar el nodo que se corresponde con un día informado se procederá a recorrer la lista tantos nodos como lo indique el número del día conocido, es decir, si el día dado es el primero la función BuscarNodo retorna el puntero al primer nodo de la lista, si el día dado es el segundo entonces la función retorna el puntero al segundo nodo y así sucesivamente.
La diferencia con el módulo ExisteNodo está dada por el hecho de que en la lista mencionada en el ejemplo anterior no necesitamos guardar el dato del número del día, ya que en la lista existe un nodo por cada día del mes, en cambio cuando no aseguramos encontrar un nodo por cada día de un mes, -según este ejemplo- en estos casos debemos guardar en el nodo el número del día, la función ExisteNodo buscará si el nodo visitado en un momento determinado su campo clave coincide con el valor buscado.
A continuación se presentará una estructura dinámica combinada con otra estructura dinámica. En estos casos podemos encontrarnos con una lista de listas o una lista de pilas o una lista de colas. Por un lado tenemos una lista principal y por otro una lista secundaria o sublista o subpila o subcola por cada uno de los nodos de la lista principal. El campo INFO del nodo en la lista principal deberá contar con un sub-campo de tipo puntero el cual apuntará a la sub-estructura de datos dinámica.
Buscar un sub-nodo requerirá primero buscar un nodo en la lista principal y una vez localizado ese nodo, buscar el sub-nodo en la sub-estructura dinámica que cuelga de ese nodo en la lista principal.
Gráficamente lo podemos representar de la siguiente manera:
El siguiente ejemplo representa una estructura estática de punteros a estructuras dinámicas de datos y de esta una sub-estructura también dinámica de datos.
Un nodo sin el campo Sgte.
Un nodo en que el campo Info es de tipo registro.
Un nodo en que el campo Info es un arreglo.
Un nodo con el campo Info que es un puntero a un tipo registro. ¿Cuál sería la utilidad?
CONCLUSIÓN:
Las variantes que podemos formar con las estructuras de datos aprendidas en la cursada de “Algoritmos y Estructuras de Datos”, solo dependerán de nuestra imaginación, creatividad, o el ingenio, para representar al mundo real.
El uso de una metodología para resolver problemas, como fue analizada en las primeras clases, nos brindará de un cimiento sólido para encarar la solución. Es imprescindible primero comprender el problema, luego de lo cual, elaboraremos una estrategia, en la cual destacaremos las partes relevantes, y por refinamiento sucesivo iremos ampliando nuestro grado de detalles; por lo tanto, siempre iniciaremos nuestra solución desde lo general hacia lo particular. Luego construiremos nuestro algoritmo el cual dará la solución a nuestro problema. Por último, codificaremos el algoritmo con un lenguaje de computadora, para que pueda ser ejecutado por la máquina.
Es importante elaborar una muestra de datos bien pensada para la situación, que contemple todas las posibilidades, incluso las más extremas y de los resultados que esperaríamos obtener para luego compararlo con los resultados conseguidos con la ejecución del programa por la computadora.
Definimos Algoritmo como la concatenación de sentencias de asignaciones internas y/o externas que son regidas por estructuras de control de programa –concatenación, selección y repetición-, que determinan el orden de ejecución de esas sentencias. Por lo tanto, la solución no solo correcta, sino, óptima dependerá mucho de las estructuras de control seleccionadas, es decir, debemos plantearnos que tipo de estructura de control debemos utilizar, en el caso de repetición, un ciclo mientras o hasta o exacto; en una selección una selección simple o múltiple, ciclos anidadas o en secuencia, decisiones anidadas o en secuencia.
El uso adecuado de las estructuras elegidas, tanto para los datos como para el control de programa harán que nuestro algoritmo sea más sencillo, simple, compacto, más rápido para ejecutar, y esto no es poca cosa.
Encontrar alternativas de solución para un mismo problema nos va a permitir seleccionar la más adecuada, oportuna, en otras palabras, la solución óptima. El que encontremos diferentes alternativas, no implica que no existan otras. Lo importante es obtener un abanico de posibilidades y decidir cual elegir y no quedarnos con la primera solución encontrada.
[1] Debo aclarar que en Turbo Pascal esto no es tan así, en realidad, se sigue apuntando a la misma región de memoria y por otro lado, en ese lugar sigue almacenada la misma información anterior al dispose.
Anterior: Arreglos
Enviar comentarios y sugerencias a: Lic. Hugo Cuello
2 comentarios:
Si guardás las imágenes en JPG desde el Paint, pierden calidad. Te conviene imprimir la pantalla de lo que tenés en Paint (antes de guardarlo) y pegarlo en Photoshop, Corel u otro.
De última en el Paint lo guardás en PNG pero te va a ocupar más.
(...)
No puedo acceder a los procedimientos de listas, me dice que el enlace esta roto, estoy haciendo algo mal?.
Gracias
Publicar un comentario