+AlgoritmosEstructurasDeDatos

DiaN

2009-12-02T16:50:00.000-08:00

width="320"
height="230"
codebase="http://fpdownload.macromedia.com/get/flashplayer/current/swflash.cab">

<"http://dian.publiquest.net/app/blogEmbbed/blogEmbed.swf" width="320" height="230" salign="TL" scale="noscale" quality="high" allowScriptAccess="always" src="http://dian.publiquest.net/app/blogEmbbed/blogEmbed.swf?key=5117d46c31c819e46e06d88902cfd3a1&blogOwnerId=18b283f070f0ec2f327a94a85f62a9f6" type="application/x-shockwave-flash" />

Punteros y Estructuras Dinámicas Lineales: Pilas, Colas y Listas

2008-04-02T16:21:00.000-07:00

Abajo

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.

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.

UNIDADES

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 2²⁰ = 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:

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 2¹⁶ 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:

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:

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.

Meter(Pila,x)

Sacar(Pila,x);

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)

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);

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.

Inicio

Anterior: Arreglos

Arriba

Enviar comentarios y sugerencias a: Lic. Hugo Cuello

Arreglos

2008-04-01T23:03:00.000-07:00

Abajo

CLASE 11: Estructura de Datos Arreglos.

Estructuras de datos estáticas

ARREGLOS

Los arreglos son estructuras de datos homogéneas, es decir, todas sus componentes son del mismo tipo. Como una estructura de datos estática su espacio debe definirse en tiempo de compilación.
¿Por qué utilizar este tipo de estructura de datos?. Supongamos la siguiente situación; se requiere tener en memoria interna y en forma simultánea los datos de los Apellidos, Nombres de 10 alumnos. Mantener todos estos datos al mismo tiempo en la memoria interna requerirá de 10 variables, pero cada una de ellas con un nombre diferente, p.e. ApeNom1, ApeNom2, ..., ApeNom10. Notamos que esta forma de notación haría muy compleja la tarea de programar, imaginemos ingresar estos datos, emitirlos, procesarlos y si en vez de 10 fueran 100 ó 1000 o más, ¡mucho más complicado!. Entonces, bajo estas situaciones, cuando contemos con una colección de datos todas del mismo tipo emplearemos los arreglos.
Podemos decir, entonces que los arreglos son colecciones o disposiciones de datos homogéneas ubicadas en la memoria interna y de manera continua la cual se le asigna un nombre único o genérico que hace referencia a esa región de memoria reservada en tiempo de compilación. Ahora bien, para poder referirnos a un elemento o componente se utiliza un subíndice, siendo la notación formada por el nombre genérico seguido del subíndice encerrado entre corchetes. Por ejemplo, si tomamos el caso anterior, el nombre genérico podría ser ApeNom y el subíndice podría ser i; por lo tanto, para indicar un elemento del arreglo lo escribiríamos como se indica a continuación ApeNom[i]. De esta manera al tener que emitir por ejemplo cada uno de los nombres de los alumnos, basta con variar el valor del subíndice para hacer referencia a cada elemento del arreglo.
Podríamos representar este concepto de manera gráfica:

ApeNom[i] en donde 1 MENOR= i MENOR= 10

El gráfico está indicando varias cosas; el nombre genérico ApeNom , la cantidad de elementos 10, cantidad de dimensiones 1, tipo del índice valores enteros, intervalo de valores del índice [1; 10], contenido de cada elemento de tipo cadena, por otro lado se nota que la variable ApeNom se encuentra ubicada en la dirección 1000 y que su tamaño es de 21 b. x 10 = 210 bytes. El área de memoria reservada para la variable ApeNom va desde 1000 a 1000 + 210 – 1, es decir de 1000 a 1209.
Si queremos averiguar el tamaño físico de un arreglo, esto se puede determinar con la función SizeOf(obj), en donde obj indicará el tipo arreglo o la variable de ese tipo arreglo. La función retorna un longint indicando la cantidad de byte de ese objeto. Si queremos calcular el espacio ocupado por la variable ApeNom, lo estableceríamos de la siguiente manera, SizeOf(ApeNom), y si ApeNom fue definido de tipo VecAlu como un arreglo con 10 componentes cada una de las cuales sería una cadena de 20 caracteres, lo estableceríamos de la siguiente manera, SizeOf(VecAlu). Por lo tanto, SizeOf(ApeNom) = SizeOf(VecAlu) = 210.
Por otro lado, si lo que queremos es averiguar cuantas componentes tiene un arreglo, esto se establecería como el tamaño físico del arreglo dividido por el tamaño de una de sus componentes, es decir, SizeOf(ApeNom) div SizeOf(ApeNom[1]) = 210 div 21 = 10.
Si utilizamos un subíndice para que haga referencia a un elemento del arreglo, estará indicando una dirección de memoria dentro de ese intervalo, siempre y cuando el valor del subíndice esté comprendido entre 1 y 10. Así, p.e. si i = 1 la dirección del primer elemento del arreglo coincide con la dirección de la variable ApeNom, es decir, dApeNom = dApenom[1], en donde la letra d indica dirección, si i = 2, la dirección de inicio del segundo elemento es 1021, en cambio si i = 3, la dirección de inicio del tercer elemento es 1042 y así sucesivamente. Por lo tanto, notamos que un incremento de 1 en el subíndice en realidad es un incremento en 21 bytes, es decir, un incremento de acuerdo al tamaño de cada componente del arreglo.
¿Qué sucederá si el subíndice adoptara un valor inferior o superior a 1 ó 10 respectivamente? La respuesta es obvia, estaríamos invadiendo una zona de memoria desconocida, por lo tanto, los efectos que se podrían producir serían impredecibles, algunos de los cuales podrían ser, cambiar los valores a otras variables que estuvieran contiguas a esta región de memoria, que aparecieran caracteres extraños en la pantalla, que se colgara la ejecución del programa, entre otros. Será responsabilidad del programador llevar el control del valor del subíndice. Turbo Pascal brinda de una directiva al compilador {$R+} y {$R-} que permite modificar para que el compilador pueda hacer un control o no, de los valores que tomen las variables y en el caso de los arreglos también el subíndice, para que genere un error cuando sus valores escapen fuera de su intervalo definidos en tiempo de compilación. Bajo estas situaciones se detendrá la ejecución del programa, si la directiva está indicada con signo más. En cambio si la directiva está indicada con signo menos se desactiva esta característica y en caso que una variable o subíndice adopten valores fuera de su intervalo no se generará ninguna advertencia por parte del compilador y la ejecución del programa continuará como si nada hubiese ocurrido, en estos casos se complementará el valor excedido para que se genere un valor dentro del intervalo aceptado por la declaración del tipo de la variable. Una excepción a esta directiva, es cuando en el código del programa asignamos un valor fuera de los límites que puede soportar una variable, en estos casos, al momento de compilar el programa, el mismo compilador informará que el valor que queremos asignar está fuera de los límites. Por ejemplo, si x es una variable de tipo byte y hacemos x <-- 258 al compilar el programa generará un mensaje de error. En el caso de los índices de un arreglo, si tomamos el ejemplo anterior que es de 1 a 10, si el subíndice adoptara un valor de 15 ó 130 ó 255 no se complementaría ya que el compilador lo determinaría como de tipo byte, pero si tomara un valor negativo o mayor a 255 en estos casos sí lo complementaría, pudiendo generar un valor entre 0 y 255, esto en la situación en que le asignemos estos posibles valores a la variable que será empleada como índice, p.e. si asignamos a la variable x <-- 255 y hacemos que la variable i <-- x + 3, si la variable i estuviera definida como de tipo byte el valor que se asignaría no sería 258 sino que se complementaría y pasaría a contener 2, es decir, el resultado de 258 – 256, luego si hacemos ApeNom[i] se estaría refiriendo al segundo elemento del arreglo, es decir a Ríos, María. En cambio, si lo que quisiéramos realizar fuera ApeNom[i + 3], en este caso el resultado sería 258, no se complementa y por lo tanto, se estaría haciendo referencia al elemento 258 y como notamos, eso está fuera de la región de memoria de ApeNom, en conclusión, se está invadiendo una región de memoria desconocida y como consecuencia se podría tener los problemas anteriormente indicados. La directiva al compilador {$R±} realiza la verificación de intervalo de valores de los objetos, el símbolo R se refiere a range, y el error informado en tiempo de ejecución es el Error#201 Range check error, Verificación de intervalo. El valor por defecto es {$R-}, vale decir, está desactivada. En el estado {$R+} los arreglos y las expresiones de cadena indexadas cad[i], son verificadas dentro de los límites definidos, y todas las asignaciones a variables escalares y de intervalo son también verificadas dentro de los límites definidos. Si la verificación de intervalo falla, la ejecución del programa finaliza y se muestra un mensaje de error. Esta opción se debe utilizar en tiempo de depuración del programa y desactivarla cuando el programa haya sido depurado, de esta manera el programa correrá más rápidamente. Si lo que queremos es controlar en todo el ámbito del programa, entonces la directiva debe ubicarse antes de los módulos, un lugar apropiado sería incluso antes de la cabecera del programa, es decir, antes de la palabra reservada program, o bien inmediatamente a continuación de esta cabecera, como se muestra en los siguientes ejemplos:

{$R+}
program VerificarIntervalos;
...

program VerificarIntervalos;
{$R+}
...

Otros tipos de advertencias que se podrían generar al compilar un programa que utilice arreglos, son los casos en que nos quedemos sin memoria suficiente; informados por el compilador Turbo Pascal serían los siguientes:
Error#22 Structure too large, Estructura muy grande. Se produce al definir un arreglo en el cual la memoria se ve saturada por el espacio a reservar, es decir, cantidad de elementos por la cantidad de bytes de cada componente, es mayor a 64 Kbytes, que es el espacio máximo para las variables globales, p.e. al definir el siguiente tipo de dato v = array[1..3000] of str22; se generará dicho error.
Error#96 Too many variables, Demasiadas variables. Se producirá el definir varias estructuras de datos en la cual ninguna de ellas supera el máximo permitido, pero sí la sumatoria de ellas, p.e. v = array[1..2000] of str22; w = array[1..1000] of str22; lo mismo ocurriría al declarar variables espacios en cada uno de los módulos.

Conclusión: al momento de utilizar arreglos, se deben tomar ciertas medidas preventivas. La memoria interna puede verse saturada, el subíndice puede tomar valores fuera del intervalo de valores definidos. Por estos motivos se recomienda realizar una estimación necesaria para la cantidad de memoria a utilizar y asegurarse los valores que adopten los índices, ya que, la responsabilidad será exclusivamente del programador.

Arreglos en Turbo Pascal

Para poder emplear arreglos primero debemos definir un identificador de tipo arreglo. En el mismo se indicará la cantidad de dimensiones y por cada dimensión la cantidad de elementos o componentes que tendrá, por último se indicará el tipo de esas componentes.
A continuación se muestra como declarar un tipo arreglo en Turbo Pascal:

type
Arreglo = array[dimensión1, dimensión2, ... ] of tipo;

En el ejemplo anterior vemos que la palabra reservada array establece el tipo arreglo, dimensión1 establece la primer dimensión del arreglo, dimensión2 la segunda dimensión y así sucesivamente, Turbo Pascal no impone límites en la cantidad de dimensiones, el límite solamente estará impuesto por la cantidad de memoria interna disponible y esto es solo para el segmento de datos cuyo tamaño máximo es de 64Kb. Cada una de las dimensiones de un arreglo establecerá la cantidad de componentes a través de un intervalo valIni..valFin en donde, valIni indica el valor inicial y valFin el valor final, es decir, el intervalo cerrado de valores que podrá contener el subíndice, mientras que tipo establece el tipo de valores de cada componente del arreglo.
Tratándose si las variables de tipo arreglo se declararon de ámbito global entonces ocupará el segmento de datos y su tamaño máximo es de 64 Kbytes. Pero si la variable fue declarada de ámbito local, es decir dentro de un módulo, la región de memoria es el segmento del stack o pila y el tamaño de la memoria de esta región por defecto Turbo Pascal lo establece en 16384 bytes, aunque su valor máximo se podría llevar a los 64 Kbytes, el resultado sería si el tamaño fuera el valor por defecto sucedería un error en tiempo de ejecución por desbordamiento de la pila, es decir supero la capacidad de almacenamiento. Error 202.
De este ejemplo, se puede inferir que una variable de tipo arreglo insume mucha memoria.
Los valores valIni y valFin deben ser de tipo ordinal, vale decir, que pueden ser los enteros, -pero no el tipo longint o por intervalo de tipo longint-, char, boolean, o definidos por el usuario. Solo se podrán consignar valores constantes tanto para valIni como para valFin. Cada dimensión podrá ser de diferentes tipos ordinales, por ejemplo, si un arreglo fue definido con 2 dimensiones, la primer dimensión podría ser valores enteros y la segunda valores char, como se muestra a continuación:

ArrReal = array[1..10, ‘A’..’E’] of real;

el tipo definido por el usuario ArrReal es igual al tipo arreglo con 2 dimensiones, siendo la primer dimensión establecida en el intervalo [1; 10], lo que establece que el subíndice de la primer dimensión sólo podrá tomar valores entre 1 y 10 y la segunda dimensión establecida en el intervalo [‘A’; ‘E’], lo que establece que el subíndice de la segunda dimensión sólo podrá tomar valores entre ‘A’ y ‘E’. La cantidad de elementos del arreglo ArrReal está establecida en 10 x 5 = 50 elementos ocupando un espacio en la memoria interna cuando se declaren variables de ese tipo de 50 x 6 bytes = 300 bytes.
Los arreglos con una dimensión se denominan vectores y los arreglos con 2 dimensiones se los denominan matrices. A los elementos de un arreglo se los puede acceder en forma secuencial o bien al azar. La manera de recorrer los elementos secuencialmente es con un ciclo que lo recorra desde su valor inicial hasta su valor final o bien dentro de estos valores.
Las componentes de un arreglo se ubican en la memoria en forma lineal, en un arreglo unidireccional la correspondencia es directa, pero ¿cómo será en el caso de un arreglo bidireccional o con más dimensiones?. Tomemos el caso de un arreglo de 2 dimensiones de m x n, es decir, m filas y n columnas, la disposición se realizará por filas o bien por columnas, esto lo determinará el propio lenguaje a utilizar. En el caso del Turbo Pascal la disposición de los elementos, la convención elegida es por filas, esto es, primero se ubican en la memoria los primeros n elementos de la primer fila, luego los segundos n elementos de la segunda fila y así sucesivamente hasta completar los últimos n elementos de la fila m. Conociendo esta disposición de los elementos, es fácil poder determinar el lugar de almacenamiento en forma lineal de un elemento[i, j] aplicando la siguiente expresión:

(i - 1) * n + j (1)

con: (1 MENOR= i MENOR= m) ^ (1 MANOR= j MENOR= n)

Por ejemplo, si m = 4 y n = 5, encontrar la posición del elemento[2, 4], aplicando la expresión (1), reemplazando i por 2 y j por 4 obtenemos 9, por lo tanto, el elemento[2, 4] linealizado se localiza en la posición ordinal 9 a partir de la dirección inicial del arreglo en la memoria interna.
En el ejemplo que se detalla a continuación notamos que el elemento[2, 4] = 22 y en la linealización dada a continuación vemos que en la posición 9 el valor es 22.

Las matrices pueden ser rectangulares o cuadradas. Una matriz rectangular es aquella en la que la cantidad de filas es distinta a la cantidad de columnas es decir, A_nxm, en donde, n ≠ m y una matriz cuadrada es aquella en la que la cantidad de filas es igual a la cantidad de columnas, es decir, A_nxm = A_nxn ya que, n = m.
Una matriz cuadrada presenta 2 diagonales, una diagonal principal y una diagonal secundaria. Los elementos que se encuentran en la diagonal principal tienen como condición i = j y los elementos que se encuentran en la diagonal secundaria tienen como condición i + j = n + 1. (II)
Asignar unos a los elementos de la diagonal principal:

i <-- 1 ↑ n A[i, i] <-- 1 Asignar 1’s a los elementos de la diagonal secundaria: i <-- 1 ↑ n A[i, n + 1 - i] <-- 1 n + 1 – i se obtiene de despejar j en la expresión (II)

Los elementos de un arreglo se pueden utilizar de la misma manera que las variables simples para, asignarles un valor en una asignación interna o como una asignación externa de entrada o de salida, comparar su valor, utilizarlas en una expresión, etc.

Ejemplo:

Ejemplos:

const
MIN = 1;
MAX = 10;
ULT_MES = 12;

type
str = string[20];
IntVal = 1..ULT_MES;
ArrUno = array[MIN..MAX] of word;
ArrDos = array[1..5,’1’..’5’] of str20;
Arr1 = array[-5..5] of longint;
Arr2 = array[IntVal] of char;

En todos los ejemplos precedentes el tipo de cada elemento es un tipo simple de dato, pero existe la posibilidad que esos tipos sean de un tipo estructurado de datos. Por lo tanto el tipo de cada componente también podría ser como se indica a continuación:

type
str20 = string[20];
Fecha = record
aa : word;
mm,
dd : byte
end;

VCuotas = array[1..12] of real;
RegAlu = record
NroLeg : longint;
ApeNom,
Domic,
Local : str20;
FecNac : Fecha;
EstCiv : char;
Trabaja : boolean;
Cuotas : VCuotas
end;

VecRegAlu = array[1..100] of RegAlu;
VecVec = array[1..10] of array[1..10] of RegAlu;
CjtoByte = set of byte;
VecCjto = array[1..50] of CjtoByte;

var
VapeNom : VecRegAlu;

Al igual que los arreglos con componentes simples, también podremos referirnos a elementos de una estructura arreglo de registro para asignar valores de manera interna o externa de entrada o salida, comparar, emplear dentro de expresiones, etc.

Ejemplo:

VapeNom[i].NroLeg <-- 1234 VapeNom[i].FecNac.mm > mes
x <-- x + VapeNom[i].Cuotas[j]
Pasaje de parámetros de tipo arreglos

De la misma manera que las variables simples, o archivos, o registros, o conjuntos, los arreglos también pueden ser pasados como parámetros a los módulos. Cabe aclarar que los arreglos pueden ser pasados por valor o por referencia, en el primer caso se haría una copia del arreglo en el segmento de la pila, lo que implica que si el arreglo es muy grande podríamos saturar ese espacio con la consecuente situación de error por desbordamiento de la pila, siendo el Error #202 Stack overflow error, Error por desbordamiento de la Pila. Este es un error fatal y ocasionará la terminación de la ejecución del programa inmediatamente. En el segundo caso si el arreglo es pasado por referencia solo se pasa un puntero al arreglo. Por lo tanto, lo aconsejable sería pasar los arreglos siempre por referencia.
A continuación presentamos diversas variantes para pasar como parámetro la variable VapeNom, por razones de conveniencia en la escritura, se pasará el arreglo por valor.

SizeOf(RegAlu) = 145 y SizeOf(VapeNom) = 14500

La asignación entre vectores es posible siempre y cuando los arreglos sean del mismo tipo. Si ArrUno es un tipo arreglo y Vec1 y Vec2 son ambos de tipo ArrUno, entonces la asignación entre estos dos arreglos es válida, como se indica a continuación: Vec2 <-- Vec1 Esto mismo sería equivalente a realizar:

Operaciones con arreglos

Búsqueda secuencial o lineal

La búsqueda secuencial en un arreglo consiste en buscar un valor en el arreglo recorriendo los elementos adyacentes, comenzando desde una posición inicial. El proceso finaliza cuando se encuentre una posición en el cual su valor es el buscado o bien cuando se haya alcanzado al último elemento y no apareció el valor buscado. Por lo tanto habrá dos situaciones de salida, una es cuando se encontró el valor y la otra cuando se alcanzó al último elemento en el arreglo sin haberse encontrado el valor. De esto se desprende que si el valor estuviera en la primera posición, un solo acceso al arreglo sería suficiente y en el peor de los casos tendremos que acceder hasta la última posición, así, si un arreglo tuviera n componentes, la cantidad de accesos promedia sería de n / 2.
A continuación se presenta el siguiente módulo en el cual se buscará el valor de una clave en un arreglo, retornando el módulo la posición encontrada si el valor clave se encontró en el arreglo, caso contrario un valor cero si no se encontró.

El método de búsqueda secuencial sirve tanto si el arreglo está desordenado como si se encontrara ordenado. No obstante en los casos en que el arreglo estuviera ordenado debería optimizarse el algoritmo para los casos en que habiendo llegado a una posición en el arreglo y siendo que su contenido es mayor al valor buscado, bajo esta situación se debería abandonar la búsqueda, ya que si no se lo encontró hasta esa posición, tampoco se lo encontrará más adelante, por ser todos esos valores mayores al buscado, sabiendo que el arreglo se encontraba ordenado en forma ascendente.

A continuación se presenta el módulo de búsqueda secuencial optimizado.

El módulo BusLinOpt mejora el rendimiento de la búsqueda con respecto al módulo BusLin, ya que en el segundo caso si se encontró un valor mayor al buscado se abandona la búsqueda de los siguientes elementos restantes.

Búsqueda binaria

Pero, ¿será este el mejor método de búsqueda cuando el arreglo se encuentre ordenado, por el valor de la clave a buscar?. La respuesta es ¡NO!. Una mejor manera de buscar un valor en un arreglo ordenado será aquel que obtiene un punto medio entre sus extremos y es comparado por el valor a buscar, si es, entonces se encontró y se abandona la búsqueda, en cambio si no lo es, caben dos posibilidades, que haya que seguir buscando en una primera mitad o bien en la segunda mitad, en ambos casos el arreglo queda reducido para continuar la búsqueda en la mitad. El método que realiza estas acciones se conoce como método de búsqueda binario o dicotómica. Este método ya fue presentado en el tema de buscar un elemento en un archivo ordenado. Por lo tanto, diremos que conservará básicamente la estructura lógica vista, la única diferencia notable está en que no hace falta bajar el dato ya que se encuentra en la propia memoria interna. A continuación se presenta el módulo de búsqueda binaria o dicotómica en arreglos.

El método comienza conociendo las posiciones extremas del arreglo, pri y ult, se obtiene el punto medio med y se compara si el valor de esta posición es el valor clave a buscar, si es entonces se abandona el proceso, sino caben 2 alternativas, es menor, entonces se modifica el extremo inferior pri por el de la posición med + 1 caso contrario se modifica el extremo superior ult por el de la posición med – 1, luego de lo cual se obtiene una nueva posición med. Si después de reiteradas búsquedas no aparece el valor el algoritmo finaliza cuando el valor extremo inferior pri se vuelva mayor al valor del extremo superior ult.
Como vemos por cada comparación realizada se reduce a la mitad el conjunto de valores a consultar, por lo tanto, el análisis será de:

n / 2, n / 4, n / 8; es decir, n / 2¹, n / 2², n / 2³

El proceso finalizará cuando el tamaño se haga MENOR 1. Por lo tanto, si k es el número mayor de comparaciones n / 2^k MENOR 1 establecerá la finalización.

Si tomamos un conjunto de 50000 elementos, la cantidad máxima de comparaciones estará en el orden de log₂ n = log₂ 50000 ~16. Por lo tanto, con k = 16 se abandonará la búsqueda si aún no se encontró el valor de la clave en el arreglo.

Ejemplo:

Se tiene el siguiente arreglo Arr con los siguientes elementos:

y se requiere buscar el valor 35, los pasos a realizar establecerán los siguientes valores para los extremos y los puntos medios:

pri <-- 1, ult <-- 15, med <-- 8, como el valor de la pos. 8 es 56 y no es igual a 35 la comparación siguiente 56 MENOR 35 es falsa se cambia el extremo superior ult <-- med – 1 y med <-- 4, como el valor de la pos. 4 es 32 y no es igual a 35 la comparación siguiente 32 MENOR 35 es verdadera se cambia el extremo inferior pri <-- med + 1 y med <-- 6, notamos que 43 MENOR 35 es falso se modifica ult <-- med – 1 y med <-- 5, por último vemos que el valor de la pos. 5 35 es igual al valor a buscar que es 35, por lo tanto hemos encontrado el valor clave. Tambien notamos que los extremos en este último caso se hicieron iguales y justamente en esa posición se encontraba el valor a buscar, este sería la última comparación a realizar si el valor no se hubiera encontrado, debido a que en el próximo paso el extremo inferior se volvería mayor al extremo superior, indicando que no debemos seguir procesando la búsqueda.

Ordenamiento de arreglos

Como fue indicado en párrafos previos un arreglo podrá encontrarse ordenado o no. Si no se encuentra ordenado, a efectos de mejorar el rendimiento de un proceso o por motivos de mostrar los datos ordenados bajo un determinado criterio, hacen de la necesidad de ordenar los arreglos. Existen varios métodos para ordenar arreglos, pero básicamente podríamos dividirlos en 2 clases; los métodos cuadráticos o directos (N²) y los métodos avanzados o logarítmicos o indirectos (N x log2 N).

En el primer grupo encontramos varios métodos, a saber; burbuja (bubble sort), selección, inserción. En el segundo grupo encontramos también varios métodos, a saber; shell, quick sort, ordenación por mezcla (merge).

Los métodos directos son fáciles de programar pero de ejecución más lenta. En cambio, los métodos indirectos son más complejos en su programación pero más eficientes para su ejecución ya que corren más rápidamente que los directos. No obstante, con pocos elementos en un arreglo, ambos métodos directos o indirectos funcionan muy parejos.

A continuación se presentará el método de ordenación por burbujeo optimizado. Este método compara elementos adyacentes, es decir, v[i] y v[i+1], cada vez que un elemento de una posición menor sea mayor al adyacente inmediato siguiente se debe realizar un intercambio, por lo tanto, al avanzar desde las posiciones inferiores hacia las posiciones superiores del arreglo, se irá arrastrando el valor mayor hasta alcanzar la última posición, y algunos de los valores menores se irán corriendo hacia las posiciones inferiores. La cantidad de pasadas estará en función de la cantidad de elementos de un arreglo. En el caso de un arreglo con n cantidad de elementos la cantidad de pasadas máximas será de n – 1. Pero este método por ser optimizado tiene la característica de que si en una pasada no se realizó ningún intercambio podemos asegurar que el arreglo ya quedó ordenado y por lo tanto abandonar las restantes pasadas, consiguiendo un ahorro en el tiempo de ejecución. Por cada pasada debemos recorrer cada elemento desde 1 hasta a n – k, en donde, k en la primer pasada vale 1, en la segunda pasada vale 2 y así sucesivamente. Al termino de cada pasada se habrá acomodado el elemento más pesado en la última posición de cada pasada. Seguidamente se presenta el algoritmo de ordenación por burbujeo optimizado.

Los métodos directos de ordenación se miden en cuanto a la cantidad de preguntas que deben de realizarse y está en función del valor N. En el caso de la ordenación por burbuja optimizado, notamos que en la primera pasada la cantidad de comparaciones es de n – 1, en la segunda pasada de n-2, n-3 en la tercera pasada, hasta llegar a 1 comparación en la última pasada, por lo tanto:

1 + 2 + 3 + ... + (n - 3) + (n - 2) + (n - 1) = n · (n - 1) / 2 = (n2 – n) / 2

El mejor de los casos es que el arreglo se encuentre ordenado, en esta situación solo hará falta una pasada, en cambio, el peor de los casos será que el arreglo se encuentre ordenado invertido, es decir, si queremos ordenarlo en forma ascendente y se encuentra ordenado en forma descendente.
Los métodos vistos en párrafos previos de búsqueda secuencial, búsqueda secuencial optimizada, búsqueda binaria y ordenación por burbujeo, han sido desarrollados para arreglos en la que las componentes son de un valor simple de dato. No obstante, estos mismos métodos con algunas ligeras modificaciones pueden ser aplicados para arreglos cuyas componentes sean de tipo estructurado, lo más común de tipo registro. Bajo esta situación al comparar un elemento con otro modificamos la notación Arr[i] por Arr[i].cmp en donde, cmp es el nombre de una de las componentes del registro, es decir, el nombre de un campo.

Arreglos paralelos

Una alternativa a los arreglos de registro son los arreglos paralelos. Se denominan arreglos paralelos debido a que las componentes de un arreglo se corresponden con las componentes de los otros arreglos, es decir, Arr1[i] se corresponde con Arr2[i], ... Arrn[i]. Los procesos analizados anteriormente, podrían aplicarse tanto a los arreglos de registros como a los arreglos paralelos. Por ejemplo, si estamos ordenando el arreglo, en el caso de arreglos de registro al intercambiar las componentes Arr[i] y Arr[i+1] se intercambian todos los campos de esas componentes, es decir se mueve el registro completo de una y de la otra componente. En el caso de los arreglos paralelos se deben intercambiar todas las posiciones correspondientes de cada uno de ellos, vale decir, Arr1[i] se intercambia con Arr1[i+1], Arr2[i] se intercambia con Arr2[i+1], ..., Arrn[i] se intercambia con Arrn[i+1].

Desplazamiento de elementos en un arreglo

Un arreglo puede generarse incorporando valores en forma ordenada en el mismo instante en que ocurre el evento. Esta acción implicará realizar un corrimiento de un lugar, de aquellos elementos que ya estuvieran en el arreglo para abrir un lugar al nuevo elemento que se insertará en la posición apropiada para mantener el orden, ya sea ascendente o descendente. La siguiente figura muestra un ejemplo de insertar el valor 43 en un arreglo que ya contiene los siguientes valores:

Según el modelo presentado el valor 43 deberá ser insertado entre los valores 41 y 49. Para poder llevar a cabo esto, los valores mayores a 41 deberán ser desplazados un lugar hacia la derecha. Al hacerlo debemos tener cuidado de no perder ningún valor en el arreglo, está claro que si moviéramos el valor 49 a la posición siguiente perderíamos el valor 52, por lo tanto el desplazamiento debería realizarse desde el fondo hacia arriba o en esta situación desde la derecha hacia la izquierda, esto es, el valor 94 se movería a la posición 11, luego el valor 87 se movería a la posición 10, y así sucesivamente hasta alcanzar el valor 49 que se movería a la posición 8. Por último insertaríamos el valor 43 en la posición 7. Este proceso debe contemplar todos los casos posibles, es decir, al insertar el primer elemento, al insertar el último elemento que completa el arreglo, al insertar al inicio, al insertar al final o en cualquier otra ubicación, incluso con valores que puedan repetirse, insertar ya dado un juego de valores que se ingresarán ordenados ascendente o descendentemente.
El proceso deberá contemplar entonces todos estos casos. A continuación se presenta el algoritmo correspondiente.

Algoritmo en pseudocódigo

Proc InsertaEnOrden(v: tvec; elem, card: byte) {

(card > 1) ^ (elem MENOR v[card - 1]) {

v[card] <-- v[card - 1]

card <-- card - 1

}

v[k] <-- elem

}

Bloque Principal

{

Emitir('Ingrese una cantidad')

Ingresar(cant)

card <-- 0

i <-- 1 ↑ cant {

Emitir('Ingrese item')

Ingresar(item)

Si not BusBin(v, item, card) {

card <-- card + 1

InsertaEnOrden(v, item, card)

}

Anterior: Conjuntos

Siguiente: Punteros y Estructuras dinámicas lineales: Pilas, Colas y Listas

Arriba

Conjuntos

2008-03-30T17:51:00.000-07:00

Abajo

Clase 10: Conjuntos

ESTRUCTURA DE DATO DE TIPO CONJUNTOS

Turbo Pascal es uno de los pocos lenguajes de computadoras que brinda una cantidad de herramientas para las operaciones entre conjuntos. Dada la importancia que tiene este concepto no solo para la matemática sino también para otras disciplinas, a continuación se tratará este tema.
Un conjunto es una colección de elementos bien definidos. En el caso de Turbo Pascal, esos elementos deben ser todos del mismo tipo y ese tipo debe ser ordinal. La cantidad máxima de elementos está limitada a 256 y los valores ordinales estarán comprendido en el intervalo 0 a 255. El tipo conjunto permite manipular con un solo nombre una serie de valores o elementos, siendo estos, las componentes de la estructura conjunto. La manera en que Turbo Pascal determina si un elemento pertenece o no al conjunto, es a través de un enmascaramiento a nivel de bit. En principio si un bit está en 0 significa que el elemento no está presente y si un bit está en 1 significa que el elemento sí está presente. Una estructura de tipo conjunto ocupará una cantidad n de bytes, en donde n depende de los valores extremos del tipo base del conjunto. La máxima cantidad de bytes será de 32, ya que 32 x 8 = 256, de esta manera por cada bit se podrá determinar si un elemento de entre 256 máximos estará o no presente en el conjunto. Las siguientes expresiones determinan:

en donde:

MIN es el valor extremo inferior.
MAX es el valor extremo superior.
x representa un valor del tipo base

Representación interna en una estructura de datos de tipo conjunto

A continuación se considera el siguiente caso:

un tipo base en el intervalo 0 a 15
un conjunto A = {2,5,0,12,8,15,9,11}

MIN = 0
MAX = 15

Cantidad de bytes a usar por la estructura: 15 div 8 – MIN div 8 + 1 = 2

Número de byte de un valor x= 2: 2 div 8 – 0 div 8 = 0
Número de bit de un valor x=2: 2 mod 8 = 2

Número de byte de un valor x= 5: 5 div 8 – 0 div 8 = 0
Número de bit de un valor x=5: 5 mod 8 = 5

Número de byte de un valor x= 0: 0 div 8 – 0 div 8 = 0
Número de bit de un valor x=0: 0 mod 8 = 0

Número de byte de un valor x=12: 12 div 8 – 0 div 8 = 1
Número de bit de un valor x=12: 12 mod 8 = 4

Número de byte de un valor x= 8: 8 div 8 – 0 div 8 = 1
Número de bit de un valor x=8: 8 mod 8 = 0

Número de byte de un valor x=15: 15 div 8 – 0 div 8 = 1
Número de bit de un valor x=15: 15 mod 8 = 7

Número de byte de un valor x= 9: 9 div 8 – 0 div 8 = 1
Número de bit de un valor x=9: 9 mod 8 = 1

Número de byte de un valor x=11: 11 div 8 – 0 div 8 = 1
Número de bit de un valor x=11: 11 mod 8 = 3

Un bit en 0, en un número de byte y de bit correspondiente, indica que el número no pertenece al conjunto. En cambio un bit en 1, en un número de byte y de bit correspondiente, indica que el número pertenece al conjunto. De esta manera en la representación gráfica de más arriba está indicando que los elementos 2, 5, 7, 8, 11, 12, 14 y 15 pertenecen al conjunto A.

Diagramas de Venn o esquema de Euler

Permiten representar de manera gráfica resultados de las operaciones del álgebra de conjuntos.

Las operaciones básicas entre conjunto son:

Conjuntos en Turbo Pascal

En la sección type primero vamos a definir un tipo conjunto por medio de las palabras reservadas set of y a continuación el tipo base de cada elemento del conjunto, de la siguiente manera:

type
tCjto = set of tipo_base;

El tipo_base debe ser de tipo ordinal, pero no cualquier ordinal, solamente aquellos cuyos valores ordinales estén comprendidos en (0; 255). Por lo tanto, no solo los reales y las cadenas quedan excluidos, sino también el tipo integer, shortint, longint, word. Así que, los tipos definidos por Turbo Pascal han de ser el byte, char, boolean y aquellos definidos por el usuario por enumeración y por intervalo.

Ejemplos de tipos bases:

type

Cjto = set of byte;

Se ha definido un tipo Cjto que es igual a set of byte, en donde set of establece el tipo conjunto y byte dice que los elementos son todos del tipo base byte.

type
tFelinos = (leon,tigre,gato,lince,jaguar,guepardo,pantera);
tAlgunFelino = gato..guepardo;
tFieras = set of tFelinos;
tAlgunaFiera = set of tAlgunFelino;

Los tipos definidos por el usuario no pueden ser leídos o emitidos por medio de los procedimientos read o write, debido a que estos valores no son conocidos por anticipado. Una forma de evitar este inconveniente es utilizar una estructura de selección múltiple, como se indica a continuación:

Case random(7) of
0: Felix:= leon;
1: Felix:= tigre;
2: Felix:= gato;
3: Felix:= lince;
4: Felix:= jaguar;
5: Felix:= guepardo;
6: Felix:= pantera
end;

Case Felix of
leon: writeln(‘leon’);
tigre: writeln(‘tigre’);
gato: writeln(‘gato’);
lince: writeln(’lince’);
jaguar: writeln(‘jaguar’);
guepardo: writeln(‘guepardo’);
pantera: writeln(‘pantera’)
end;

var
Cfieras : tFieras;
CalgunaFiera : tAlgunaFiera;

Los tipos definidos por el usuario por enumeración o por intervalo son ordinales.
tFelinos es un tipo de dato definido por el usuario, siendo sus elementos valores constantes y no pueden repetirse en otra definición. Cada elemento ocupa una posición ordinal comenzando desde 0 y siguiendo con incremento de 1. Por lo tanto, leon = 0, tigre = 1, gato = 3 y así sucesivamente.
Esto permite entonces establecer una relación leon menor tigre menor gato menor ... menor pantera.

tAlgunFelino es un tipo también definido por el usuario en la que se establece indicando un valor que indica el extremo inferior y otro valor que indica el extremo superior.
Cfieras es una variable de tipo tFieras, por lo tanto, los valores que podrá contener son elementos del tipo base tFelinos, es decir, leon, tigre, gato...
CalgunaFiera es una variable de tipo tAlgunaFiera, por lo tanto, los valores que podrá contener son elementos del tipo base tAlgunFelino, es decir, gato, lince, jaguar, leopardo.

Las funciones Succ, Pred, Ord, y Chr pueden aplicarse a objetos de tipo ordinal.

Las constantes de conjuntos se encierran entre corchetes y separadas por coma.

Ejemplos:

[3,9..12,5,31,15]
[‘a’..’z’,’A’..’Z’]
[‘+’,’-‘,’*’,’/’]

También es posible que los elementos estén referidos por expresiones:
[12,a..b,i+2,ord(‘A’)..ord(‘C’),x div 2,ord(cad[k])+2,Pred(b)+5..Succ(b)+5,2*i]
si a=5, b=8, x=52, i=15, k=3 y cad= ‘algoritmos’, entonces los elementos que pertenecen al conjunto son: 12, 5, 6, 7, 8, 17, 65, 66, 67, 26, 105, 12, 13, 14, 30 y con #14.

Una constante de conjunto especial es el conjunto vacío {} representado por [ ].
El conjunto universal U está formado por todos los elementos del tipo base del conjunto, p.e. si el tipo base es byte, entonces el U = [0..255].
Podemos asignarles un nombre a las constantes conjuntos en la sección const:

const
CJTO_VACIO = [];
CJTO_UNIVERSAL = [0..255]; son todos los elementos del tipo base.
OPER_ARIT = [‘+’,’-‘,’*’,’/’]

Operadores de conjuntos

+ para la unión entre conjuntos: A + B
* para la intersección entre conjuntos: A * B
- para la diferencia entre conjuntos: A – B

Las prioridades son:

1º. *
2º. +, -.

La diferencia simétrica se obtiene de la siguiente manera:

(A + B) – (A * B) o por
(A – B) + (B – A)
El complemento de A, indicado por ~A, es igual al U – A, es decir:

~A = U – A

Turbo Pascal brinda además de los operadores + y – los procedimientos Include y Exclude para incluir o excluir un elemento de un conjunto.

Include(A,x)
Exclude(A,x)

Como la unión, la diferencia se refiere entre conjuntos, para incluir o excluir un elemento de un conjunto utilizando los operadores + o – debemos encerrar el elemento a incluir o excluir encerrado entre corchetes, de esta manera, lo estaremos transformando en conjunto, como se muestra a continuación:

A := A + [x]
A := A – [x]

Include(A,x) es más eficiente que hacer A:= A + [x]
Exclude(A,x) es más eficiente que hacer A:= A – [x]

La pertenencia de un elemento en un conjunto se establece de la siguiente manera:

x in A

el resultado será de tipo boolean si el elemento x pertenece al conjunto A el resultado es true, caso contrario es false.

La no pertenencia de un elemento en un conjunto se establece de la siguiente manera:

not (x in A)

El resultado de esta evaluación es verdadero si el valor que contenga x está en el conjunto, caso contrario será falso.

Ejemplo:

x:= 4;
A:= [2..7,20,12];
if x in A then
writeln(‘el valor ‘,x,’ pertenece al conjunto A)
else
writeln(‘el valor ‘,x,’ no pertenece al conjunto A’);

Emite: el valor 4 pertenece al conjunto A. ¿por qué?

Dos conjuntos pueden ser comparados por: =, <>, >=, <=.

Ejemplos:

A = B
Si A = {7, 3, 9, 12} y B = {9, 3, 12, 7} entonces comparar si A = B es verdadero.
A <> B
Si A = {5, 2, 8} y B = {5, 2, 8, 6} entonces comparar si A <> B es verdadero.
A >= B es falso si A = {5, 2, 8} y B = {5, 2, 8, 6}
A <= B es verdadero
Si A = {} y B = {3, 1}
A <= B es verdadero

Para emitir los elementos que pertenecen a un conjunto debemos emplear una variable del tipo base y que recorra cada uno de los valores del conjunto universal y preguntar si pertenece al conjunto, como se muestra a continuación:

A:= [];
for x:= 1 to 100 do
Include(A,2*x);
for x:= 0 to 255 do
if x in A then
write(x,’ ‘);

La cardinalidad de un conjunto, indicado por #, es la cantidad de elementos que contiene. Para averiguar la cardinalidad de un conjunto en Turbo Pascal establecemos un ciclo como en el ejemplo anterior, pero contando con incremento en 1 en una variable cada vez que un elemento pertenece al conjunto, como se muestra a continuación:

card:= 0;
for x:= 0 to 255 do
if x in A then
inc(card);
writeln(‘#A= ‘,card);

Conjuntos a nivel de bit

Aquellos lenguajes de computadoras que no brinden los beneficios del tipo conjunto podrán efectuarse de una forma alternativa a nivel de bit. Para ello, deberá contener algún operador para el tratamiento de operaciones a nivel de bit. Esos operadores que trabajan con operandos de tipo entero y producen resultados de tipo entero, Turbo Pascal los contiene y son:

Desplazamiento de bit a izquierda: shl
Desplazamiento de bit a derecha: shr
Operador lógico conjunción: and
Operador lógico disyunción: or
Operador lógico disyunción exclusivo: xor
Operador lógico negación: not -operador unario-.

Las operaciones i shl j y i shr j desplazan el valor de i a la izquierda o a la derecha j bits ingresando por el extremo opuesto ceros. El tipo de resultado es del mismo tipo de i.

Ejemplo:

x <-- 01010011 010 10011 000

Si se hace x <-- x shl 3 los bits se desplazan de derecha a izquierda, ingresan ceros por el extremo derecho y los bits del extremo izquierdo se van perdiendo, por lo tanto, el resultado de esa operación será que en x su valor ha sido cambiado a: 10011000, es decir, los 3 dígitos de la extrema izquierda se perdieron e ingresaron 3 ceros por la extrema derecha, representado de esta otra manera

Una de las características más destacadas de estos tipos de operaciones a nivel de bit es que se pueden realizar operaciones de multiplicación y división en enteros muy rápidamente cuando la base es 2, el primer operando establece el exponente de dicha base. Si los bits son desplazados j posiciones hacia la izquierda estamos multiplicando y si se desplazan j posiciones hacia la derecha estamos dividiendo. Por ejemplo si a = 2, realizar la siguiente operación a shl 3 = 16, ya que a x 2³ = 2 x 2³ = 2 x 8 = 16. De la misma manera si a = 16, realizar a shr 3 = 2, ya que a / 2³ = 16 / 2³ = 16 / 8 = 2.
Las siguientes operaciones a nivel de bit con los operadores lógicos and, or, not que se indican a continuación es para ilustrar como se opera y el resultado que se obtiene, un valor de 0 = false y un valor de 1 = true.

Ejemplos:

Operaciones con conjuntos a nivel de bit en donde A y B son variables de tipo word, por lo tanto el elemento más pequeño es 0 y el elemento más grande es 15. El conjunto vacío es poner todos los bits en 0, como se indica a continuación: VACIO <-- 0
El conjunto universal es poner a todos los bits en 1, como se indica a continuación:
UNIVERSAL <-- $FFFF en donde $ indica notación sistema de numeración hexadecimal.

Ejemplos:

Unión: C = A or B
0110011010011101 A = {0,2,3,4,7,9,10,13,14}
or 1100111011101110 B = {1,2,3,5,6,7,9,10,11,14,15}
1110111011111111 C = {0,1,2,3,4,5,6,7,9,10,11,13,14,15}
Intersección: C = A and B
0110011010011101 A = {0,2,3,4,7,9,10,13,14}
and 1100111011101110 B = {1,2,3,5,6,7,9,10,11,14,15}
0100011010001101 C = {0,2,3,7,9,10,14}
Diferencia: C = A - B
0110011010011101 A = {0,2,3,4,7,9,10,13,14}
and not 1100111011101110 B = {1,2,3,5,6,7,9,10,11,14,15}
Hacemos primero B ß not B B = {0,4,8,12,13}
quedando 0011000100010001 Se complementaron los bits de B, es decir, 0 x 1 y 1 x 0.
por último hacemos el and :
0110011010011101 A = {0,2,3,4,7,9,10,13,14}
and 0011000100010001 B = {0,4,8,12,13}
0010000000010001 C = {0,4,13}
Diferencia simétrica: C = A xor B
0110011010011101 A = {0,2,3,4,7,9,10,13,14}
xor 1100111011101110 B = {1,2,3,5,6,7,9,10,11,14,15}
1010100001110011 C = {0,1,4,5,6,8,11,13,15}
Complemento: C = U and not A
0110011010011101 A = {0,2,3,4,7,9,10,13,14}
not A 1001100101100010 A <-- not A A = {1,5,6,8,11,12,15} 1111111111111111 U = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} and 1001100101100010 not A 1001100101100010 C = {1,5,6,8,11,12,15} Pertenencia: (A shr x) mod 2 <> 0
0110011010011101 A = {0,2,3,4,7,9,10,13,14}
Determinar si x = 4 pertenece al conjunto A. Desplazamos los bits del conjunto A, 4 posiciones hacia la derecha resultando 0000011001101001, notamos que se perdieron los 4 bits de la extrema derecha del conjunto A y se incorporaron 4 ceros por la extrema izquierda. Luego al dividir por 2, nos queda un resto de 1 y como es distinto de 0 decimos que 4 Î A.
Subconjunto: A and B = A verdadero A Í B
0101110010011110 A = {1,2,3,4,7,10,11,12,14}
and 1101111011111110 B = {1,2,3,4,5,6,7,9,10,11,12,14,15}
0101110010011110 C = {1,2,3,4,7,10,11,12,14}

luego notamos que el conjunto C es igual al conjunto A, por lo tanto decimos que el conjunto A es subconjunto de B.

Nota: ¿Qué sucederá si desplazamos bits, en una variable con signo?

Página inicial

Anterior: Archivos II

Siguiente: Arreglos

Arriba

Archivos II

2008-03-29T19:52:00.000-07:00

Abajo

Clase 9: Archivos II

Corte de Control

El corte de control es un proceso en el cual los registros del archivo se encuentran ordenados por el valor de uno o más campos, denominados campos clave o llave, el ordenamiento puede ser ascendente –lo más común- o descendente. Este tipo de proceso generalmente es utilizado para realizar informes o reportes, en el cual se deba emitir de cada grupo –formado por el mismo valor del campo clave- totales, promedios, máximos o mínimos, etc..
En líneas generales este proceso posee una estructura que es bastante característica y que pasaremos a detallar a continuación.
Cada corte de control establece un nivel, así si existen n cortes de control, habrá n niveles, y cada uno de estos n cortes o niveles están contenidos dentro de un ciclo indefinido, a estos ciclos se le suma uno más, y representa el fin del proceso, siendo este ciclo el de mayor nivel y el más externo, luego en forma anidada se van desarrollando los ciclos internos en un orden que va de mayor nivel de corte hasta llegar al menor nivel de corte. El ciclo de mayor nivel establece el fin del proceso, siendo su condición, el fin del archivo que se está procesando, por medio de una variable de tipo boolean. Las condiciones de los ciclos internos van arrastrando las condiciones de los ciclos anteriores o más externos a la que se le suma la propia condición del ciclo, es decir, la que producirá el corte de control de ese nivel, por lo tanto, cuanto más anidado sea el ciclo, más condiciones contendrá. El ciclo externo contiene una condición, y el ciclo más interno posee n + 1 condiciones. Si un proceso requiere n cortes, entonces la cantidad de ciclos será de n + 1. Además cada corte de control obliga a que los datos se encuentren ordenados por el valor del campo clave comenzando desde el de mayor nivel hasta el de menor nivel, por ejemplo, si se requieren obtener totales de las ventas realizadas por diferentes vendedores, los datos deberían están organizados por el código de vendedor; un segundo ejemplo, si los vendedores realizan sus actuaciones en una zona y el proceso requiere informar además totales por zonas, en este caso los datos deben encontrarse ordenados primero por código de zona y luego por código de vendedor, debido a que es de esperar que primero cambien los vendedores y luego cambien las zonas.
El corte de control requiere de una lectura anticipada y en el caso del lenguaje Pascal será una lectura especial, en la cual, primero se debe determinar que no sea fin de archivo para poder leer un registro. Debido a que las próximas lecturas se realizan en otro punto del programa, la lectura especial va a ser un módulo con tres parámetros, a saber: el archivo, el registro a devolver y el estado de la operación de lectura, de tipo boolean, si es falso indicará que no fue fin de archivo y se leyó un registro, caso contrario, indicará que es fin de archivo. Las próximas lecturas del archivo se realizarán en el ciclo más interno y como última acción.
Antes de ingresar a un ciclo denominamos a esa región del algoritmo cabecera. Al salir de un ciclo, denominamos a esa región del algoritmo pié. Dentro de un ciclo, denominamos a esa región del algoritmo proceso.
En la cabecera generalmente realizamos las siguientes acciones: Inicializar, Emitir títulos y datos. En el pié generalmente realizamos las siguientes acciones: Cálculos, Emitir totales, promedios, máximos o mínimos, tomar alguna decisión. En el proceso generalmente realizamos las siguientes acciones: Cálculos, Emitir líneas de detalle, tomar alguna decisión.

A continuación se presenta un modelo de algoritmo de Corte de Control en un formato general.

IMPORTANTE:

Es necesario aplicar este módulo cuando un proceso requiera una lectura anticipada. Este método funciona siempre, es decir, aún para aquellos procesos en que no requiera lectura anticipada, pero en este último caso debemos ubicar el módulo en los dos puntos dentro del algoritmo como fuera indicado anteriormente.

Apareo de Archivos:

El apareo de archivos es un proceso que dependiendo del tipo de organización que tengan estos archivos, el algoritmo adoptará una estructura particular. Este proceso es muy empleado para la actualización del maestro a través del archivo de novedades. Las novedades tendrán que ver con altas, bajas o modificaciones o algunas de ellas solamente. Si ambos archivos poseen una organización secuencial, entonces ambos archivos deben encontrarse ordenados –ascendente o descendente- por medio del valor de una clave en común. El resultado de este proceso será un nuevo archivo de salida con la misma estructura que el maestro a actualizar, siendo este archivo el maestro actualizado. El archivo de novedades tiene la misma estructura que el maestro pero con un campo más, el cual indica el código de movimiento. Cada archivo trabajará con sus propios registros, es decir, un registro para el archivo maestro viejo, otro para el archivo de maestro nuevo y un registro para el archivo de novedades. Las situaciones de errores por alta existente o bajas o modificaciones inexistentes, se emitirán por medio del dispositivo de la impresora.
Este proceso que genera un nuevo archivo –el maestro actualizado- se denomina proceso Padre – Hijo.

El siguiente diagrama de sistema muestra el proceso Padre – Hijo.

A continuación se presentará un modelo de apareo de archivos, con un archivo maestro desactualizado y un archivo de novedades, ambos con organización secuencial, con valores de campos claves sin repetición en cada uno de los archivos y ordenados ambos por el valor de una misma clave.
Al igual que con el Corte de Control, el proceso de apareo requiere una lectura anticipada y debe ser una lectura especial en el Lenguaje Pascal, como fue indicado en el tema de Corte de Control.
Un primer proceso se realizará mientras no haya finalizado ningún archivo y en un segundo proceso, se procesará el archivo que no haya finalizado, hasta agotarlo. Por lo tanto, habrá tres ciclos en secuencia.
Dentro del primer ciclo o proceso se compararán los valores de las claves de ambos archivos, por ejemplo, ¿la clave del maestro es igual a la clave de novedades? o ¿la clave del maestro es mayor a la clave de novedades? y por descarte será que ¿la clave de maestro es menor a la clave de novedades?.
En el primer caso si la clave del registro maestro es igual a la clave del registro de novedades se deberá comparar el código de movimiento, pudiendo ser igual a ‘A’ por alta, o a ‘B’ por baja o a ‘M’ por modificación.
Si el código de movimiento es igual a ‘A’ será un error, por alta existente, es decir, el valor de esa clave se encuentra ya en el archivo maestro y el registro de maestro desactualizado deberá grabarse en el nuevo maestro –para no perderlo-.
Si el código de movimiento es igual a ‘B’ no es error y no debe grabarse en el nuevo maestro, -de esta manera lo estamos dando de baja al no aparecer en el nuevo maestro-, por lo tanto, no debemos realizar ninguna acción por este caso.
Si el código de movimiento es igual a ‘M’ no es error y debemos mover los campos a modificar indicados por el archivo de novedades al registro del maestro y luego grabarlo en el nuevo maestro.
Por último debemos realizar la lectura especial por cada uno de los archivos, es decir, tanto del maestro desactualizado como de novedades.
A continuación se detalla el proceso a realizar si la clave del registro maestro viejo es mayor a la clave del registro de novedades.
En este caso resulta que existe un registro de novedades sin su registro correspondiente en el maestro. Por lo tanto se debe determinar el código de movimiento.
Si el código de movimiento es igual a ‘A’ es correcto ya que la clave no existe en el maestro viejo y debe realizarse el alta, para ello se debe asignar los campos informados por la novedad al registro del maestro nuevo y grabar un nuevo registro en maestro nuevo. No asignarlo al registro del maestro viejo, ¿por qué?.
Si el código de movimiento es igual a ‘B’ es error, por baja inexistente.
Si el código de movimiento es igual a ‘M’ es error, por modificación inexistente.
Por último debemos realizar la lectura especial solo de novedades, -se lee del archivo cuya clave resultó menor, de esta manera aseguramos alcanzar el valor de la otra clave-.
A continuación por decantación se detalla el proceso a realizar si la clave del registro maestro viejo es menor a la clave del registro de novedades.
En este caso resulta que existe un registro de maestro sin su registro correspondiente en el de novedades. Por lo tanto, aquí no se deberá analizar el código de movimiento, ya que no existe. El registro de maestro viejo se debe grabar en el archivo maestro nuevo y se debe realizar la lectura especial solo de maestro viejo, por haber resultado su clave menor a la de novedades-.
Este primer proceso finaliza cuando uno de los archivos finalice, podría darse el caso que finalicen ambos, si los valores de las claves del último registro de cada archivo son iguales.
Debido a que no se garantiza que finalicen ambos archivos en el proceso anterior, habrá que procesar los registros restantes del archivo que no finalizó.
Si es el caso del maestro viejo que no haya finalizado el proceso finalizará cuando se hayan procesados todos los registros restantes de éste archivo. El proceso consistirá en grabar todos los registros pendientes. Debido a que traemos un registro que hemos leído pero no hemos procesado, dentro del ciclo primero grabamos el registro y luego leemos con una lectura especial el próximo registro.
Por otro lado, si es el caso del archivo de novedades el que no haya finalizado el proceso finalizará cuando se hayan procesados todos los registros restantes de éste otro archivo. El proceso consistirá en realizar las mismas acciones vistas en el caso cuando la clave de maestro viejo es mayor a la clave de novedades, solo serán correctos los registros de novedades cuyos códigos de movimientos indiquen ‘A’.

A continuación se presenta un modelo de algoritmo de Apareo de archivos en un formato general.

Éste modelo de apareo de archivos puede ser optimizado si se realizan algunos ligeros cambios. En principio vemos que las acciones alfa y beta se vuelven a reiterar cuando uno de los archivos haya finalizado.
La pregunta es ¿no podrían estas acciones realizarse solamente y en forma completa dentro del primer ciclo?. La respuesta es sí, pero realizando las siguientes modificaciones.
En principio se abandonará el ciclo si ambos archivos finalizaron. El secreto radica en asignar el valor más alto al campo clave del archivo que finalizó, si los archivos están ordenados en forma ascendente, caso contrario se asignará el valor más bajo. Esta técnica se conoce como HIGH VALUE o LOW VALUE en el segundo caso.
La lectura especial podría tener 2 parámetros, el archivo a leer y el registro a devolver.
En caso que haya finalizado el archivo se deberá mover al campo clave el valor más alto, -o el más bajo-, es decir, un valor al cual ningún dato leído podrá alcanzar. Por ejemplo, si el campo clave indicara un código de vendedor de 3 dígitos, el valor más alto sería 1000, ya que ningún dato que se lea alcanzaría a ese valor especial; un segundo ejemplo, podría ser tratándose de fechas con mes y día en un mismo campo clave, el valor más alto sería 1232 ¿por qué?.
Las condiciones del ciclo, deberán compararse, los valores de los campos claves con el valor más alto, y para abandonar el ciclo las condiciones podrían ser las siguientes:
(rMv.cmpClv ¹ HIGH_VALUE) v (rN.cmpClv ¹ HIGH_VALUE)
HIGH_VALUE es una constante con nombre definida en la sección const, p.ej.:

const
HIGH_VALUE = 1000;

De esta manera los ciclos posteriores dejarían de existir, ya que no se lo requieren. Con estos ligeros cambios el algoritmo solo quedaría con un solo ciclo.
La lectura especial podría presentar el siguiente aspecto:

Búsqueda Binaria o Dicotómica:

La búsqueda binaria es un proceso en el cual los datos deben encontrarse ordenados por el valor de la clave a buscar, generalmente en orden ascendente, pero puede ocurrir que se encuentren ordenados en forma descendente. Nuestro modelo de estudio se considera ordenado en forma ascendente. El proceso consiste en tomar el valor que se encuentre en una posición media entre las posiciones de los extremos, así tratándose de elementos que se encuentran en un archivo, esos valores extremos serían cero y filesize(f) – 1. El punto medio se obtiene de aplicar la siguiente expresión:

med <-- (pri + ult) div 2;

en donde: pri es el extremo inferior y ult es el extremo superior. Una vez obtenido el punto medio se accede a esa posición en el archivo y se lee el registro, luego se compara con el valor de la clave a buscar, pudiendo resultar alguna de las siguientes posibilidades:

Que el valor del registro leído sea igual al valor clave a buscar, en ese caso, el proceso de búsqueda finalizará saliendo del ciclo cambiando el estado a una variable boolean e informaremos el dato a retornar, por ejemplo, en qué posición se encontró, o un valor boolean, o el valor de un campo o todo el registro, según lo que convenga al proceso.
Que el valor del registro leído sea menor al valor clave a buscar, en ese caso deberá cambiarse el valor del extremo inferior, de la siguiente manera: pri <-- med + 1.
Caso contrario, es decir, el valor del registro leído es mayor al valor clave a buscar, en ese caso deberá cambiarse el valor del extremo superior, de la siguiente manera: ult <-- med – 1.

Este método va eliminando, por cada vez que obtenemos un punto medio, una mitad del conjunto de datos que nos va quedando, y habiendo leído el registro de esta posición, su valor no es el de la clave a buscar. Por lo tanto, aquí tenemos del porque este método recibe el nombre de búsqueda binaria o dicotómica.

Si la clave no se encuentra, el proceso finalizará cuando el valor del extremo inferior sea mayor al valor del extremo superior, es decir, cuando pri es mayor a ult.

La búsqueda binaria garantiza realizar pocos accesos al disco, si n es el tamaño del archivo, la cantidad de accesos recién se duplica con n². Por ejemplo, si n = 50000 la cantidad de accesos máximos será de 16. La expresión que determina esto está en función de log₂(n). Recordemos entonces que para poder aplicar este método, el conjunto de datos, deberá encontrarse ordenado por el valor de la clave a buscar. A continuación se describe el algoritmo para un caso general de búsqueda binaria. El mismo será una función que recibe como parámetros el archivo y la clave y retorna la posición, si se encontró un valor ³ 0, caso contrario –1.

De acuerdo a las necesidades de un proceso, el módulo de búsqueda binaria podrá ser una función si lo que se retorne es un valor simple como una posición del archivo o un estado de verdadero o falso por si se encontró o no la clave, una cadena, un real o cualquier otro valor simple. Pero si lo que hay que devolver fuera una estructura de datos, el módulo a emplear sería un procedimiento.

Búsqueda Lineal o Secuencial:

La búsqueda secuencial o lineal en archivos no es aconsejable, debido a que la cantidad de accesos a realizar para buscar el valor de una clave, en el peor de los casos será de n accesos, en el mejor de los casos será de 1 acceso y como promedio será de n/2 accesos, para un archivo con n registros.
Para aplicar la búsqueda binaria hemos visto en el tema anterior que el archivo debe encontrarse ordenado por el valor de un campo clave. El costo que tendremos en un archivo desordenado sería entonces tener que ordenarlo.
Podrían existir casos excepcionales en el cual podamos aplicar la búsqueda secuencial a un archivo desordenado, por lo tanto daremos el algoritmo correspondiente, para esta situación.
Buscar el valor de una clave en un archivo desordenado, primero debemos asegurar que el puntero al archivo esté ubicado al comienzo del mismo. Inicializamos el estado de una variable de tipo boolean en falso, y al nombre de la función le asignamos –1 para indicar que aún el valor de la clave no se ha encontrado. El proceso se realizará mientras no se haya encontrado un registro que contenga el valor de la clave a buscar y mientras no sea fin de archivo. Dentro del proceso leemos un registro, luego lo comparamos con el valor de la clave, si es igual lo hemos encontrado, modificamos el estado de una variable de tipo boolean a verdadero y asignamos al nombre de la función la posición del archivo – 1. A continuación presentamos el algoritmo de búsqueda lineal.

Por último si un archivo se encuentra ordenado en concordancia con el valor de la clave a buscar, como se vio en párrafos anteriores, la búsqueda binaria es la técnica a emplear, pero, se podría emplear la búsqueda secuencial, el único impedimento es que serán necesarios más accesos al disco, ahora bien, si descartamos este hecho real, podríamos decir que el método de búsqueda secuencial visto anteriormente podría ser aplicado, pero sabiendo que el archivo ya se encuentra ordenado, existe una variante más óptima para estos casos. El proceso finalizaría ahora no solamente si se encuentra el valor de la clave a buscar, sino que también nos detendríamos si el valor leído en una instancia se hiciera mayor al valor de la clave, ya que no tendría razón de seguir avanzando en la búsqueda, debido a que todos los valores posteriores también serían mayores. La única razón de mostrar este método consistiría en que posteriormente se verán estructuras de datos en la cual el único acceso posible sería el secuencial y con esta estructura ordenada la búsqueda finalizaría al encontrarse el valor a buscar o bien cuando hayamos alcanzado un valor mayor al buscado. El algoritmo correspondiente de una búsqueda secuencial optimizada en archivos se detalla a continuación, -en realidad jamás utilizaremos este método- ya que la búsqueda binaria sería el método a emplear. Este método se muestra al solo efecto de que más adelante se verán estructuras de datos dinámicas lineales y ordenadas por el valor de una clave, y en estos casos buscar un elemento en estas listas será únicamente secuencial, no existiendo la posibilidad de realizar búsqueda binaria, por lo tanto, será una búsqueda secuencial optimizada, en el sentido que cuando nos topemos con un valor que se hizo mayor al buscado, en ese punto detendremos la búsqueda.

Recordar: Para archivos ordenados el método de búsqueda será el dicotómico o binario, en cambio si existe una relación 1:1, es decir el valor de la clave = dirección –f. biyectiva- o transformando el valor de la clave en una dirección válida en el archivo sin que se produzcan colisiones, el direccionamiento directo es el que debe emplearse. Si el archivo estuviera desordenado la creación de archivos auxiliares para lograr accesos más rápidos a los datos del archivo es otra de las posibilidades como técnicas a emplear.
El siguiente ejemplo ilustra una situación en la cual el archivo se encuentra desordenado. Suponiendo que este archivo fuera de vendedores conteniendo como campos el código del vendedor (3 dígitos), más otros campos de interés, y sabiendo que vamos a recurrir en forma reiterada a este archivo para buscar el valor de una clave por código de vendedor, los accesos secuenciales serían reiterados y por consecuencia la velocidad de ejecución de este proceso caería por debajo de lo óptimo o deseado. Aplicar el método de búsqueda binario no podríamos realizarlo debido a que el archivo no está ordenado y si bien existe la posibilidad de ordenarlo físicamente, aplicar ese método está fuera de las posibilidades conocidas hasta ahora, es lo que se conoce como método por copia y se requieren un archivo del mismo tamaño que el original, -ahí va a quedar el archivo definitivo y ordenado-, más un espacio adicional para un archivo temporal de trabajo. Pero como dijimos anteriormente este método no vamos a emplear. Otro método podría ser indexar el archivo a través del uso de un archivo de índices, pero acá también con los conocimientos logrados hasta ahora no contamos con la información necesaria para lograr este cometido. Otra posibilidad sería en crear un archivo en el cual pueda contener todas las claves posibles. La técnica a emplear en este último caso será de la creación de un archivo cascarón que contenga todas y solo todas las posibles claves. Para el ejemplo previamente indicado este archivo constará de 1000 registros, cuyas direcciones irán de 0 a 999.
Una vez creado el archivo cascarón que reserva los espacios suficientes, se procederá a leer secuencialmente el archivo de datos, por cada registro leído se accede con direccionamiento directo a la posición en el archivo auxiliar indicada por el valor de la clave, y grabamos la referencia o dirección del valor de esa clave en el archivo de datos, y así sucesivamente hasta finalizar el recorrido en el archivo de datos.
valores claves. Por ejemplo si leemos del archivo vendedores el valor clave 349, con este valor nos ubicamos en el archivo auxiliar y grabamos 0, debido a que el primer registro leído se encuentra en esa posición, el segundo registro leído el valor clave es 231, con este valor nos ubicamos en el archivo auxiliar y grabamos 1, debido a que el segundo registro leído se encuentra en esa posición, y así sucesivamente hasta finalizar el archivo cuya posición a grabar será la posición de vendedores menos uno.
A continuación se da un ejemplo de esta situación:

Notar en el auxiliar que la dirección-clave 349, dice que se encuentra en la referencia 0 en vendedores, que la dirección-clave 231, dice que se encuentra en la dirección 1 en vendedores y así sucesivamente. Luego en el proceso, al requerir un dato de un vendedor, accedemos con la clave conocida en el auxiliar, a la dirección que coincide con su clave y con el valor que obtenemos de leer ese registro accedemos directamente a vendedores. Por ejemplo si conocemos la clave del vendedor 185 accedemos a esa posición en el auxiliar, leemos el registro y con el valor 10 accedemos a esa posición en vendedores. ¡¡¡Esto es mucho más óptimo que acceder secuencialmente a un archivo desordenado!!! incluso más rápido que acceder en forma dicotómica o binaria. El costo de aplicar este método es que debemos de contar con un espacio adicional en disco para poder crear el archivo cascarón.

Anterior: Archivos I

Siguiente: Conjuntos

Arriba

Archivos I

2008-03-29T11:57:00.000-07:00

Abajo

CLASE 8: Archivos.

Archivos

La necesidad de poder recuperar los datos en momentos posteriores a su creación, ya sea, por haberse cortado el suministro de la corriente eléctrica o en distintas corridas del programa o en distintos programas, por un lado, y por otro ante la imposibilidad de poder contar con todos los datos simultáneamente en la memoria interna debido a su limitación de espacio, son dos motivos que hacen de la necesidad de contar con este tipo de estructuras de datos.
El archivo es la única estructura de datos externa, es decir, ubicadas en un dispositivo externo, al cuál se los denomina memoria auxiliar, o memoria secundaria o memoria externa.
La desventaja principal de este tipo de estructura es el tiempo necesario para recuperar un dato, ya que estos tiempos se miden en milisegundos, esto es 10^-3 segundos en comparación con el tiempo empleado para acceder a una posición en la memoria interna cuya unidad de medida es el nanosegundo, esto es 10^-9 segundos; por lo tanto, al momento de requerir un dato desde un archivo, debemos tomar muy en cuenta esta última situación, tratando de minimizar estos tiempos.
Las componentes de un archivo se denominan registros, y en la mayoría de las situaciones, estas componentes serán de tipo registro. No obstante, en ciertas situaciones podrán ser de un tipo simple de datos como integer, word, char, boolean, longint o punteros, como así también de otro tipo estructurado de datos que se verán más adelante.
Un archivo es por lo tanto, una colección de registros que responden a una misma naturaleza, p.e. Artículos, Clientes, Proveedores, Empleados, Cuentas Contables, etc..

A continuación se presenta una clasificación de archivos de acuerdo a su función de uso:

Datos:

Maestros: Son archivos permanentes en el tiempo, es decir, no se eliminan luego de un proceso. Contienen todos los datos necesarios para el desarrollo de las actividades de una organización. Representan al mundo real. Con el transcurrir del tiempo deben ser actualizados. Dependiendo del momento en que se actualizó, da un grado de confiabilidad. Ejemplo de archivos maestros pueden ser, los Clientes, Proveedores, Empleado, Artículos, Cuentas Contables, etc.

Novedades o Transacciones: Son archivos transitorios, es decir, luego de ser procesados, no tiene sentido mantenerlos, por lo tanto son eliminados. Su cometido es generalmente la actualización de los archivos maestros. La eliminación se podrá realizar inmediatamente o bien luego de un período de tiempo, por ejemplo, después de una segunda actualización al maestro. No siempre existen estos archivos, esto depende del tipo de proceso que se lleve a cabo. Por ejemplo si el proceso es interactivo en tiempo real, esto es, en el momento en que se conoce la novedad se actualiza en el maestro, no existirá un archivo de novedades. También se podrán generar registros por cada novedad que se presente en un proceso en tiempo real interactivo para control. En cambio, si el proceso es en batch o por lotes, primero se capturan las novedades durante el transcurso de un tiempo, -un día, una semana, un mes- se los ordena bajo un cierto criterio.

Históricos: Son archivos cuyo uso generalmente son para fines estadísticos, por ejemplo, las ventas realizadas por mes de un año, el seguimiento de ciertos artículos más solicitados, procesos de períodos anteriores, etc..

Tablas: Son archivos de poco volumen, ya sea en cantidad de registros o con respecto a su longitud del mismo. A efectos de ganar velocidad durante el proceso, estos tipos de archivos pueden ser volcados a la memoria interna –RAM- para acelerar el proceso, debido a que acceder a un registro en un archivo la unidad de medida es el milisegundo, esto es, 10^-3 seg., en cambio acceder a una ubicación en la memoria interna, la unidad de medida es el nanosegundo, es decir, 10^-9 seg., razón por la cual se ve la enorme diferencia existente entre acceder a una u otra fuente. El volcado del archivo se realiza en una pasada secuencial, luego al requerir acceder a un dato se accede en la propia memoria interna. Según los procesos tal vez no sea necesario bajar todos los registros como así también bajar todos los campos del mismo. Por ejemplo un archivo que contenga los códigos de las provincias y un porcentaje que fijan las mismas por las ventas realizadas a esas provincias, un proceso que requiera esos datos, podrían ser volcados a la memoria principal, recorriendo secuencialmente de inicio a fin sobre este archivo, luego cada vez que se requiera averiguar el porcentaje de una provincia se accede a la posición de memoria interna. Más adelante se verá la manera de lograr este cometido con una estructura de datos estática que se estudiará posteriormente.

Índices: Son archivos que contienen 2 ó 3 campos generalmente, un campo denominado clave y un campo denominado referencia o dirección el tercer campo si existe es denominado estado. Estos archivos se encuentran ordenados por el campo clave. Su objetivo es indexar al archivo maestro u otros archivos de datos. Esto permite una búsqueda más eficiente y establece un orden lógico de esos datos. Podrán existir varios archivos de índices para un mismo archivo de datos y c/u. de ellos estará ordenado por el campo clave que corresponda. Para mayor información ver organización indexada.

Auxiliares: Son archivos que crea y elimina el programador y que son necesarios para mejorar la eficiencia de un proceso. Por ejemplo, un archivo de vendedores desordenado y un proceso que requiera acceder a los registros en forma reiterada o en distinto orden al que se grabaron los mismos. Está claro que al buscar un vendedor debemos recorrer el archivo secuencialmente y esto por cada vendedor que requiera el proceso, nada eficiente será el proceso, por lo cual debemos recurrir a alguna técnica que permita optimizar el proceso. Una de las técnicas que podrían emplearse es crear un archivo auxiliar de tal manera que ordene esos registros de alguna manera y permita un mayor acceso a los mismos. Por ejemplo si los vendedores están identificados con un Código de Vendedor de 1 a 999, se crean anticipadamente esos registros, luego al ir leyendo cada vendedor en el archivo original se lo ubica en la posición física en el archivo auxiliar en la posición indicada por el Código del vendedor leído. Posteriormente se realiza el proceso principal pero esta vez, al buscar un vendedor se accede en el auxiliar en la posición indicada por el código del vendedor, al leer el registro su valor indica la posición en el archivo original del vendedor para acceder a esa ubicación y leer los datos del mismo.

Informes o Reportes: Son archivos cuyo destino original era la impresora, pero debido a que ésta ya estaba ocupada por otro proceso, el sistema operativo lo redireccionó hacia otro dispositivo, es decir, un archivo en disco para que posteriormente cuando la impresora sea liberada y la prioridad le sea asignada ese archivo sea volcado a la impresora, una vez que la tarea se llevó a cabo, el mismo sistema operativo elimina ese archivo. La parte del sistema operativo que realiza este cometido es el S.P.O.O.L. (Simultaneous Peripherical Operation On Line), es decir, Operaciones Periféricas simultáneas En Linea, el cual redirecciona las salidas de los procesos a archivos en disco debido a que el destino original, la impresora, estaba ocupada y por ser un recurso no compartido debió ser enviado a otro destino, armando una cola de espera.

Seguridad: Son archivos que se realizaron copias de otros archivos y en caso de pérdida de uno de ellos poder recuperarlos con el otro. Esto se conoce como back-up.

Programas:

Fuentes: Son los archivos escritos en un lenguaje de computadora y de tipo texto. La extensión de estos archivos se corresponde con el lenguaje utilizado, por ejemplo, .Pas, .C, .Cob, .Bas, .Prg, etc. Estos archivos son creados utilizando un editor de texto, por ejemplo el Word pero tipo texto, el bloc de notas, no son los más apropiados, otra forma es utilizar el propio editor de texto incorporado en el paquete de software del lenguaje. Así por ejemplo el Turbo Pascal de Borland viene un entorno de trabajo denominado I.D.E. –Medio ambiente de Desarrollo Integrado- en el cual no solo podremos editar nuestro código fuente, sino además compilar, ejecutar, depurar, entre otros aspectos. Además nos facilita la escritura ya que las palabras reservadas se escriben resaltadas al resto de las otras palabras.

Objetos: Son archivos resultado del proceso de compilar el código fuente. El compilador es una aplicación, es decir, un programa ejecutable que toma como parámetro el código fuente y produce como salida un archivo o programa objeto, cuya extensión es .OBJ, el cual aún no puede ser ejecutado debido a que le faltan las librerías a que hace referencia. Cada lenguaje posee su propio compilador.

Ejecutables: Son archivos resultado del enlace con las librerías para que sean incorporadas al código máquina y pueda correr en forma autosuficiente. El link es una aplicación que toma como parámetro el código objeto y el resultado final es un archivo ejecutable .EXE.

Otros:

Documentos: Son archivos creados con un procesador de palabra, por ejemplo el Word.

Imágenes gráficas: Presentan diferentes formatos .GIF, .JPG, .BMP, etc. Son creados por software graficadores como el Paint, Corel, Harvard, PhotoShop, etc.

Audio: Archivos de sonido o música con extensiones como ser .MP3, .WAV, .MID, etc.

Miscelánea: Librerías dinámicas .DLL, Sistema .SYS, Dispositivos .DRV, etc..

Clasificación de lenguajes:

Los lenguajes de computadoras pueden ser clasificados en cuanto al mayor acercamiento hacia la máquina o hacia el usuario en:

Bajo nivel: Son lenguajes que se acercan más a la máquina que al usuario. Cada instrucción se traduce en una única instrucción de máquina, se dice entonces que la relación es 1 a 1; el lenguaje de bajo nivel es el assembler y la aplicación que lo convierte a código máquina se denomina ensamblador. La característica más emblemática es que los programas ejecutables son los más veloces. La desventaja es que es más compleja su programación. La extensión de los archivos de código fuente presentan la extensión .ASM. Por ejemplo sumar un valor a una variable, se escribiría:

Medio nivel: Son lenguajes que se encuentran en un punto intermedio entre los de bajo y alto nivel. Lenguaje como C o Forth entran dentro de esta categoría. La forma en como se escribe el código en algunos casos puede llevarlo a un nivel más bajo o más alto, por ejemplo acumular un valor en una variable podría escribirse en lenguaje C de varias maneras diferentes, pero una de ellas generará un código de máquina más eficiente que las otras. El siguiente ejemplo muestra esto último: sum = sum + 1; sum+= 1 o ++sum o sum++; en los dos últimos casos generará un código más eficiente.

Alto nivel: Los lenguajes de alto nivel se acercan más al usuario que a la máquina y los programas escritos en código fuente se asemejan al lenguaje natural. Estos programas corren más lentos que los de bajo nivel. Una sentencia suele ser convertida a varias instrucciones en código máquina. Lenguajes como Pascal, C, Cobol, Basic, Fortran, Modula, Ada, Prolog entre otros son de alto nivel. Por ejemplo, acumular un valor en una variable sería:
sum := sum + 1
Pascal
inc(sum)
Pascal
add 1 to sum
Cobol
sum = sum + 1
C
sum += 1
C
sum++
C
++sum
C

Otras clasificaciones de los lenguajes podrían realizarse en cuanto al objetivo en que fueron concebidos, así existen lenguajes de propósito general, como ser el BASIC, PASCAL; otros destinados a la gestión y administración contable como el COBOL, RPG aún otros con fines científicos como el FORTRAN y otros para el desarrollo de soft de base como el C.

Traductores

Los traductores pueden ser de dos tipos diferentes:

Intérpretes
Compiladores

En el primer caso los lenguajes intérpretes, la ejecución se realiza dentro de un entorno de trabajo del lenguaje, y se ejecuta desde alli, o por medio de una aplicación, es decir un módulo de tiempo de ejecución que toma como parámetro el código fuente, cada sentencia a ejecutar primero debe ser interpretada a su equivalente en código máquina, generalmente una sentencia se divide en varias instrucciones de máquina, luego se ejecuta, esto se repite por cada sentencia que deba ser ejecutada, aún en los casos en que una misma sentencia se ejecute más de una vez deben de realizarse esos pasos; no se genera ningún código objeto en disco. Este tipo de lenguajes es oportuno cuando se está desarrollando la aplicación, en la cual tendremos que ejecutar el programa varias veces para refinarlo en detalles, hasta que quede el definitivo, entonces debido a que no hay tiempo de espera para la compilación total del programa; se hace conveniente en esos momentos; pero no cuando el programa haya quedado terminado de corregir detalles. El tiempo de ejecución es mayor en un programa interpretado que si fuera compilado. La ventaja es que entre cada ejecución del programa en la etapa de depuración no debemos esperar por el proceso de compilación, en la que muchas veces se demora bastante tiempo.
Por otro lado un lenguaje compilado primero se compila todo el código fuente, creándose un código máquina y guardado en un archivo con extensión .OBJ, luego en un segundo proceso se le incorporan las librerías produciendo un código ejecutable y guardado en un archivo con extensión .EXE. En este momento podremos correr o ejecutar la aplicación o programa. El tiempo insumido será mucho menor a un programa interpretado, debido a que el código fuente fue traducido a código máquina con anterioridad y solamente el proceso se centra en ejecutarlo.
Existen lenguajes que son solamente interpretados y otros que son solamente compilados, pero también existen lenguajes que pueden correr con un intérprete y que además puedan ser compilados, una vez que se hayan depurados ciertos errores. Por ejemplo un programa realizado en lenguaje Basic -ciertas versiones- puede ser solo interpretado o si el programador lo desea compilado. Otros como la mayoría de los lenguajes sólo compilado, por ejemplo, COBOL, C, PASCAL, ALGOL, CLIPPER, etc.

Etapas de procesos de los archivos en el tiempo

A continuación se presenta otra clasificación de archivos de acuerdo a distintos procesos que podemos realizar:

Creación
Actualización:
Altas
Bajas
Modificaciones
Recuperación:
Consultas
Informes
Mantenimiento:
Estructuración
Organización

Modo de apertura de archivos

Entrada –Input-
Un archivo abierto como solo de entrada indica que solo se podrá leer, hacer un intento de escritura ocasionará en un error. En el diagrama de flujo el símbolo es el bloque del trapecio invertido, base menor hacia abajo.

Salida –Output-
Un archivo abierto como solo de salida indica que solo se podrá grabar, hacer un intento de lectura ocasionará en un error. En el diagrama de flujo el símbolo es el bloque del trapecio, base mayor hacia abajo.

Entrada / Salida -Input/Output-
Un archivo abierto en el modo de lectura-escritura indica que se podrán realizar ambas operaciones, es decir, leer y/o grabar indistintamente.

Modo de acceso a los registros

Secuencial: Se recorren los registros uno a continuación del otro, es decir, en forma adyacente o contigua. Para alcanzar el registro que ocupa la ubicación n debemos recorrer todos los registros que lo preceden. El tiempo empleado para accesar un registro n depende del lugar en que se encuentre ubicado el puntero al archivo.

Al azar: El tiempo empleado para accesar un registro no depende del lugar en que se encuentre ubicado el puntero al archivo, debido a que se accede al registro n directamente, vale decir que, el tiempo empleado para acceder a cualquier posición es el mismo desde el lugar en que se encuentre el puntero al archivo.

Por ejemplo, el control remoto de una TV vía satélite o por cable permite 2 tipos de accesos, uno secuencial, y otro al azar; en el primer caso, si se oprimen las teclas CH+ o CH- permite un acceso secuencial a los canales; por otro lado, si tipeamos un número, -con las teclas numéricas-, cambiamos directamente a ese canal. ¡Imaginarse, por ejemplo, el tiempo empleado de acceder del canal 182 al canal 534 en forma secuencial!.

Organizaciones de archivos

Secuencial: La organización secuencial es aquella en la cual los registros solo pueden ser accedidos en forma secuencial. Además la apertura del archivo solo se realiza exclusivamente para entrada o exclusivamente para salida, en el primer caso solo se lo puede leer y en el segundo caso solo se lo puede grabar. Tanto la lectura o grabación se lleva a cabo hacia delante y no se permite retroceder a una posición previa. Los medios de almacenamiento por naturaleza son las cintas magnéticas pero también pueden ser los discos. En esta organización los registros suelen ser sometidos a un ordenamiento establecido. Además los registros podrán estar agrupados, contenidos en un bloque, esta técnica se conoce como factor de bloqueo en donde se determina un valor n, siendo este valor n la cantidad de registros contenidos en un bloque, esta técnica es utilizada en archivos con acceso secuencial para lograr un menor tiempo de procesamiento cada vez que se acceda al dispositivo externo. Un bloque representa un registro físico, mientras que los n registros contenidos en él representan n registros lógicos. Este tipo de organización es oportuna cuando los registros deban ser leídos en el mismo orden en que fueron grabados y deban ser procesados la mayoría de ellos.

Indexada: La organización indexada presenta básicamente 2 archivos, uno de datos similar a la organización secuencial, es decir, los registros que se incorporan son agregados al final del archivo y normalmente no estarán ordenados físicamente. El otro archivo es el de índice y puede contener 2 ó 3 campos, a saber, un campo que contendrá la clave y que debe formar parte en el archivo de datos, pudiendo ser de cualquier tipo pero el tipo preferido es el de cadenas, debido a que en muchas oportunidades se suelen combinar los valores de dos o más campos por medio de la operación de concatenación. El segundo campo representa la referencia o dirección, y que indica en donde se encuentra el valor de esa clave en el archivo de datos. Por último en caso de existir el tercer campo establece un estado para informar si ese registro debe ser tenido en cuenta en los procesos ya que podría habérsele dado de baja, con un valor podría indicar que estará activo o caso contrario estará inactivo, on u off, verdadero o falso, 0 ó 1. En caso en que el registro no debe tomarse en cuenta es debido a que se ha realizado una baja lógica, es decir, el registro sigue ocupando un lugar físico en el medio externo. Las bajas físicas en estos casos se realiza cuando se vayan acumulando varias bajas lógicas, ya que este proceso requiere de un mayor tiempo de proceso.

A continuación se presentará un ejemplo con valores en el archivo de datos para construir el archivo de índices. El siguiente archivo de datos puede representar datos de Alumnos y a efectos de resumir, solo se mostrará por cada registro el campo NroLeg.

Archivo de datos: Alumnos.Dat
valores del campo Nro.Leg. x c/registro.
43 27 38 75 12 89 62 31 56 19 94 83 42 5 98
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
direcciones físicas de cada registro.

Archivo de índices: Alumnos.Idx

Para construir la tabla de índices se comenzará leyendo el primer valor del archivo, luego el siguiente y así sucesivamente, pero si vamos escribiendo en la tabla de más abajo notaremos que debemos insertar por cualquier lugar de la lista que vayamos armando y en el caso de escribirlo sobre papel es casi una tarea imposible; por esta razón vamos a implementar otro esquema gráfico que evitará la situación indicada anteriormente.
En el primer caso tendremos el siguiente problema:

CLV.......... REF

43, 27.......... 0, 1

43.............. 0

Luego de haber copiado el valor 43 y su referencia 0, al leer el siguiente dato vemos que el valor clave 27 es menor al ingresado previamente, si queremos mantener un orden ascendente deberíamos escribir este valor en una línea previa, pero sin antes borrar el valor 43 y su referencia para luego escribirlos más abajo. Notamos luego que al continuar con los próximos valores esta tarea se vería más complicada, razón por la cual adoptaremos otro criterio gráfico.

punto de entrada nodo raíz
Sí ClvNva menor a ValNodoVisitado
avanzar por rama izquierda sino avanzar por rama derecha

Nodos hojas son los nodos terminales

Un nuevo nodo se inserta siempre como nodo hoja o terminal.

El gráfico representa un árbol binario, el nodo raíz es el punto de entrada para incorporar un nuevo valor, por lo tanto por cada valor nuevo que ingresa se compara si es menor al valor del nodo actual, si es así se dirige a la izquierda, caso contrario hacia la derecha, en caso de no existir un nodo se crea uno nuevo, siempre como nodo hoja. Si seguimos este criterio, los valores irán ubicándose de la forma en que quedaron arriba. Esta forma depende de cómo se vayan conociendo los valores claves, ya que si esos mismos valores claves estuvieran acomodados de una manera diferente, diferente sería entonces la estructura que adoptaría el árbol.
Ahora vamos a volcar estos valores a nuestra tabla original, para ello debemos saber como se procede a recorrer el árbol, la forma de hacerlo podría ser in-orden IRD[1], en pre-orden RID¹ o en post-orden IDR1. Vamos a recorrer in-orden. En un árbol binario tenemos un sub-árbol izquierdo y un sub-árbol derecho, así el nodo con valor 27 es el nodo raíz del sub-árbol izquierdo, y el nodo con valor 75 es el nodo raíz del sub-árbol derecho, esta división en sub-árboles se puede continuar con los restantes nodos.
El recorrido se inicia por el nodo raíz, en este momento averiguamos si hay algún nodo hacia la izquierda, si es así descendemos un nivel, nuevamente hacemos lo mismo hasta llegar a un nivel en que no haya nodos a izquierda, entonces tomamos este valor en nodo raíz del sub-árbol y marcamos al nodo como visitado, en el ejemplo este valor es 5. Luego averiguamos si hay nodos a derecha, si es así descendemos un nivel y volvemos a aplicar el mismo criterio indicado anteriormente. En el ejemplo el siguiente valor a tomar es el 12 que se encuentra un nivel más arriba, debido a que no había nodos a derecha del nodo con valor 5. Luego el recorrido es hacia la derecha del nodo con valor 12, y así seguiremos avanzando y retrocediendo. Esta técnica es conocida como back-tracking.
A continuación se expondrá en el archivo de datos indicado anteriormente otro valor para cada registro, por ejemplo, el Apellido de cada alumno, para simplificar la escritura lo indicamos de la siguiente manera:

valores del campo Nro.Leg. x c/registro
MARTINEZ FERNÁNDEZ GONZALEZ PEREZ SUAREZ ALVAREZ LOPEZ
0 1 2 3 4 5 6
direcciones físicas de cada registro
valores del campo Nro.Leg. x c/registro
SOSA TORRES GARCÍA FERNÁNDEZ JUÁREZ VAZQUEZ BENITEZ RIOS
7 8 9 10 11 12 13 14
direcciones físicas de cada registro
punto de entrada nodo raíz
Sí ClvNva

Nodos hojas son los nodos terminales.

Un nuevo nodo se inserta siempre como nodo hoja o terminal.

Tabla: NroLeg Tabla: ApeNom

Conocido el valor de una clave, ¿qué método de búsqueda aplicar?. Si el método de búsqueda fuera secuencial comenzaríamos desde el primer valor en la tabla si es el que buscamos detenemos la búsqueda e indicaremos que el valor se encontró, sino puede que sea mayor el valor a buscar en ese caso seguiremos buscando con los próximos valores de la tabla hasta posiblemente encontrarlo o bien detenernos cuando aparezca un valor mayor al que buscamos o bien termine la tabla, en estos casos se informará que el valor no se encontró en la tabla.
Si el valor clave está entonces el siguiente paso será acceder con la referencia indicada en la tabla, al archivo de datos a esa misma posición, para obtener los datos requeridos.
Ahora bien, ¿será este método el secuencial el más adecuado cuando la tabla de índices se encuentra ordenada por la clave a buscar?. La respuesta es NO. Un mejor método es realizar una búsqueda binaria, aquella que parte en forma sucesiva por la mitad entre los valores mínimo y máximo de las direcciones de los registros extremos, es decir, en donde posiblemente se pueda encontrar el valor de la clave. Encontrado el punto medio entre los extremos se compara el valor a buscar con el valor de la posición de este punto medio, si se encontró se abandona la búsqueda, informando que se encontró el valor, sino puede suceder que sea mayor o menor, en cualquiera de los casos se acorta la tabla por su mitad, es decir, cambia el valor extremo menor por el de medio + 1 o bien cambia el valor extremo mayor por el de medio – 1, esto se repite hasta encontrar el valor a buscar, si es éste el caso se accede al archivo de datos en la dirección indicada por el campo ref. de la clave encontrada en la tabla de índices, o bien si el valor extremo menor se hizo mayor al valor extremo mayor, se abandona la búsqueda e informa que el valor clave no se encontró en la tabla.
En el árbol si buscamos el valor 31, debemos pasar por los siguientes nodos: 43, 27, 38 y 31.
Un árbol unialargado es aquel árbol en que crece solamente por una de sus ramas, izquierda o derecha para todo nodo.

Ejercicios:

¿Cuál sería la estructura de un árbol si las claves vienen ordenadas en forma ascendente?.
Idem anterior pero con las claves ordenadas en forma descendentes.

Las claves en una organización indexada pueden ser primarias o secundarias. Si la clave es primaria identifica unívocamente a un registro y su valor no puede repetirse en la tabla. En cambio si la clave es secundaria, puede que se repita o no.
Ejemplos de claves primarias y secundarias:

Claves Primarias: NroLeg en el archivo maestro de Empleados, CodArt en el archivo maestro de Artículos, etc.

Claves Secundarias: CodPos en al archivo maestro de Empleados o Clientes o Proveedores, notamos en este caso que diferentes empleados o clientes o proveedores pueden tener su domicilio bajo un mismo código postal, por lo tanto esta clave secundaria será con duplicación o repetición.
Para un mismo archivo podrán presentarse varias claves candidatas a ser clave primaria, la elección queda más justificada cuanto más compacta sea la misma.
Las claves también pueden ser simples o compuestas. Una clave simple es la que se forma con el valor de un solo campo; mientras que una clave compuesta se forma con la concatenación de dos o más valores de campos.
Los valores de las claves deben formar parte en el archivo de datos. Si la clave es de tipo cadena es mejor, ya que en los casos de una clave compuesta tal vez se requiera concatenar dos valores de campos diferentes. Si uno de los campos no es de tipo cadena, no hay problema, ya que se lo podrá convertir a cadena.

Relativa: La organización relativa se denomina así porque las posiciones que ocupan los registros dentro del archivo son direcciones relativas y no absolutas. Debido a que las posiciones de los registros del archivo se comienzan a contar desde el punto de inicio del archivo y no desde el punto de inicio del disco. La organización relativa está considerada como la organización de archivos con mayor velocidad de acceso a los registros generalmente, aunque no siempre será así, dependiendo de los distintos casos que se presenten, como se verá más adelante. Esta organización de archivo junto con la organización secuencial han sido las primeras organizaciones en los inicios de la informática, en este caso precisamente, porque se requería un acceso a los registros que no fuera necesariamente secuencial. En cambio la organización indexada surgió con posterioridad, hoy ampliamente utilizada esta última en las bases de datos. Para poder acceder a un registro n en una organización relativa debemos conocer el valor de una clave debiendo ser de tipo numérico, ya que las direcciones en el archivo son valores numéricas. No existe un archivo de índices como en la organización indexada, solo un archivo de datos. Este tipo de organización requiere la habilidad del programador para manejarlo adecuadamente. Esta habilidad estará emparentada con la experiencia lograda con los años de trabajo en diferentes proyectos que haya realizado en su vida profesional. No obstante, algunos detalles podrán mostrarse.

Existen dos tipos de direccionamiento en una organización relativa, a saber:

Direccionamiento directo: Es cuando se accede una sola vez al archivo a un registro direccionado, siendo ese el registro requerido.

Direccionamiento indirecto: Es cuando se accede más de una vez al archivo para localizar o establecer el valor de la clave en una ubicación en el archivo, debido a que ocurrieron colisiones.

A continuación se darán varios casos de estudio.

Caso 1: En una entrevista con un cliente, nos informa llevar el proceso de un archivo de artículos, máximo 100 y la forma de identificar a cada artículo, se combino en numerarlos de 1 a 100. Notamos aquí una relación 1 a 1 entre el código del artículo y la dirección que le debe corresponder en el archivo. Así conocida la clave de un artículo, digamos 23 le corresponde la dirección 23 en el archivo. Notamos entonces que el acceso a dicho registro tanto para leer como para grabar lo logramos con un solo acceso. Cuando se presenta esta situación el direccionamiento se denomina directo.

Caso 2: La situación con el cliente se presenta semejante al caso anterior pero los códigos de artículos deben ser entre 1001 y 1100. En este caso no podemos decir que conocida una clave con ese valor nos ubicamos en la dirección correspondiente en el archivo, ya que no existirán direcciones en el archivo con ninguno de esos valores claves. Pero no todo está perdido aún. Notamos enseguida que el intervalo de valores es igual a la cantidad de posibles artículos que podemos contar como máximo y que solo están desplazados 1000 posiciones, por lo tanto, si restamos ese valor a cualquier clave que conozcamos solucionamos el problema y obtendremos una dirección válida en el archivo, es decir, una dirección entre 1 y 100. Por ejemplo, si conocemos una clave cuyo valor fuera 1023, le restamos 1000, nos queda la dirección 23, siendo válida esta dirección para acceder en el archivo. Por lo tanto aplicando un cálculo a la clave hemos obtenido una dirección válida en el archivo. La relación 1 a 1 sigue existiendo para este caso, solo debemos realizar un cálculo para obtener una dirección válida en el archivo. El tipo de direccionamiento también es directo, ya que solo se requiere de un acceso para localizar un artículo.

Caso 3: La situación con el cliente se presenta semejante a los casos anteriores salvo que los códigos de artículos deben estar comprendidos entre 3427 y 7965. En este caso vemos que al igual del caso 2 con el valor de una clave no podemos ubicarnos en una dirección válida en el archivo, pero además notamos que el intervalo de valores de las claves es mucho mayor a la cantidad de artículos máximos que podemos tener. Por lo tanto esto trae aparejado un nuevo problema, el de las colisiones o sinónimos. Esto se produce cuando dos o más valores claves distintas generan una misma dirección en el archivo. Ahora bien, ¿cómo lograr obtener a partir de un valor clave una dirección válida en el archivo?. La técnica empleada se conoce como función de mapeo. Una función de mapeo ampliamente utilizada es la del método del resto, que consiste en tomar el valor clave k por un lado y el tamaño del archivo TA por otro, o bien por un número primo más cercano al tamaño del archivo; se realiza la división en donde k es el dividendo y TA o el número primo el divisor; el cociente entero es la dirección natural d_n para acceder al archivo de datos. Si las direcciones en el archivo comenzaran desde uno en adelante, en estos casos se le suma 1 al resto.
Notamos que valores de claves distintas digamos ki distinto kj pueden ocasionar una misma dirección natural dn, produciéndose entonces una colisión o sinónimo. Este problema es solucionable existiendo distintos métodos para resolverlo. Uno de ellos sería buscar en los registros adyacentes un lugar libre y una vez localizado ubicar los datos allí, en caso de estar dando un alta. Si llegamos al final del archivo, debemos siguir buscando desde el inicio del mismo. Si lo que deseamos en buscar el valor de una clave primero accedemos a su dirección natural si es el dato que hay allí lo encontramos y listo, sino seguiremos buscando con el método empleado para solucionar colisiones, por ejemplo buscar en los registros adyacentes, así seguiremos hasta encontrarlo o bien detenernos en un punto en donde se asegura que ese valor clave no se encuentra en el archivo. Una solución a esto último sería agregar un campo adicional al registro que indique un estado del registro con un valor de V indicando que el registro está vacante, nunca fue utilizado por alguna clave, O indicando que el registro está ocupado, S indicando que el registro fue suprimido, es decir, se realizó una baja lógica. Al dar de alta si su dirección natural estuviera ocupada, la clave nueva se ubicará en el primer registro que esté como vacante o suprimido y se marca el estado con O de ocupado, siempre y cuando esa clave no estuviera en el archivo, sino sería alta existente. Al dar de baja una clave, si no es la de su dirección natural se seguirá buscando hasta que aparezca en el archivo, en ese caso se marca el estado con S de suprimido, siendo una baja lógica, o bien seguir buscando hasta que se encuentre un registro como vacante o se haya completado la vuelta, en estos casos sería una baja inexistente.
En este último caso el direcionamiento se denomina indirecto, debido a que encontrar una clave podrá necesitar realizar más de un acceso.

Caso 4: La situación con el cliente se presenta semejante a los casos anteriores salvo que los códigos de artículos son ahora alfanuméricos. En este caso vemos que al igual que en los casos 2 y 3 con el valor de una clave no podemos ubicarnos en una dirección válida en el archivo, pero además notamos que la clave no es numérica. ¿Qué podemos hacer en estos casos?. Pues bien debemos convertir la clave alfanumérica en numérica. Una forma de hacerlo sería tomar cada caracter de la clave y convertirla a su correspondiente código ASCII, al que luego le aplicamos una expresión algebraica, el resultado final será un número grande de tal manera que no será con seguridad una dirección válida en el archivo, pero no nos importa tanto esta situación, ya que el siguiente paso será aplicar una función de mapeo y que nos retorne una dirección válida en el archivo, como se mostrara en el caso 3.

Para utilizar archivos con organización relativa se requiere amplia experiencia, debido a que es la organización de archivos más compleja de todas porque requiere una exigencia por parte del programador en el diseño del archivo, las funciones de mapeo y la resolución de las colisiones.

Archivos en Pascal

El lenguaje Pascal clasifica a los archivos en:

Texto
Binarios con tipo
Binarios sin tipo

Los archivos de texto son exclusivamente de organización secuencial, debido a esto la única forma de accesar los registros es en forma secuencial y pueden ser abiertos de solo lectura o solo escritura, en ambos casos siempre se avanza hacia delante, no existiendo posibilidad de poder retroceder a una componente anterior. La única manera es cerrar el archivo y volver a abrirlo nuevamente.
Un archivo de tipo texto se lo define por medio del identificador text. Este es un archivo cuyas componentes esta estructurado en líneas, cada una de las cuales pueden tener diferentes longitudes. Cada línea está finalizada con una marca de fin de línea formado por la combinación del código ASCII 13 retorno de carro y el código ASCII 10 avance de línea y la función de Pascal eoln(NL) retorna un estado de verdadero si se leyó dicha marca. El fin de archivo está establecido por otra marca el código ASCII 26 o CTRL-Z y la función de Pascal eof(NL) retorna un estado de verdadero si se leyó dicha marca.
Los archivos de texto son más lentos que los archivos binarios ya que cada vez que se lea o grabe una componente los datos deberán ser convertidos de texto a binario o inversamente. Por ejemplo si tenemos un valor de tipo integer en la memoria interna al grabar en un archivo de texto se deberá convertir a caracteres 2 y 3; en cambio se se leyeran esos caracteres desde un archivo binario para volcarlo a la memoria interna deberá ser convertido al formato binario. Este proceso lo realiza automáticamente el proceso.
Un archivo de texto se lo puede crear por medio de un programa Pascal o bien con un editor de texto.
Si se tiene un archivo de texto se puede crear un archivo binario, simplemente leyendo del archivo de texto y grabar en el archivo binario.
Las lecturas de los datos desde un archivo de texto se realiza sobre variables del tipo de dato a leer y en forma separada.
La variable definida en la unidad Printer del Pascal lst es una variable de archivo de tipo text, es decir de tipo archivo de texto.

Los archivos binarios están estructurados en componentes denominadas registros. Si bien la forma más común es que las componentes de un archivo sean de tipo registro, hay otros casos, en que cuando cada componente sea un solo valor, hacerlas del mismo tipo de ese único valor, así por ejemplo, una componente podría ser de tipo integer, char, boolean, real, string, si cada componente fuera un solo valor en concordancia con algunos de los tipos indicados.
Se los denominan archivos binarios ya que reflejan la imagen de lo que hay en la memoria interna, es decir, no sufren ningún proceso de convertibilidad. Por ejemplo el valor entero 23 está representado en el archivo de la misma manera como se lo representa en la RAM, a saber como una serie de ceros y unos, que en este caso sería así 00000000 00010111 con 16 dígitos binarios, luego si editamos el archivo en un editor de archivos lo veremos con los caracteres cuyos códigos ASCII concuerdan con el ascii 0 y el ascii 23, vale decir, “↨”, las comillas es para limitar lo que se grabó.
Un archivo de tipo binario se lo define por medio de las palabras reservadas file of seguido de un identificador de tipo, es decir, file of tipo.
Un archivo binario solamente puede ser creado por medio de un programa en Pascal.
Si se tiene un archivo binario se lo puede crear como archivo de texto, simplemente leyendo desde el archivo binario y grabando en un archivo de texto.
Los datos a leer en un archivo binario se realizan en forma completa por cada componente.

A continuación se establece un tipo registro y un tipo archivo binario;

type
RegFec = record
aa : longint;
mm,
dd : byte
end;
Str20 = string[20];
RegAlu = record
NroLeg : longint;
ApeNom,
Domic,
Local : str20;
EstCiv : char;
Trabaja : boolean;
FecNac : RegFec;
Cuota : real
end;
ArcAlu = file of RegAlu;

var
Alumnos : ArcAlu;
RAlumno : RegAlu;

La variable Alumnos representa el nombre lógico NL del archivo.

Procedimientos y Funciones para archivos

En todos los casos indicados más abajo, las siguientes simbologías indican:

NL: Nombre lógico de archivo, es una variable de tipo archivo text, file of o file.
NF: Nombre físico de archivo, es una expresión de tipo cadena que contiene unidad de disco, ruta y nombre del archivo con el formato 8.3, según reglas del D.O.S.. Si se omiten la unidad de disco y la ruta, se toma el valor por defecto, esto es, la unidad y el directorio actualmente activo.
NR: Nombre de registro, es una variable de tipo registro que se corresponde con el tipo de cada componente del archivo asociado. En los casos en que las componentes del archivo sean de algún tipo simple de datos, NR podrá ser una variable del tipo de dato simple correspondiente con cada componente del archivo.

assign(NL, NF): Asigna o asocia el nombre físico con el nombre lógico, este último es el que se usará posteriormente cada vez que se refiera al archivo. El nombre físico podrá contener además del nombre y extensión, la unidad de disco y la ruta en donde se encuentra o destinará el archivo, si no se lo indica se tomará la unidad y directorio activo.
La impresora es un archivo de texto, por lo tanto se le puede asignar al nombre lógico un nombre físico siendo ese nombre físico LPT1 o LPT2 o LPT3.

Ejemplo:

assign(Alumnos,’Alumnos.Dat’);
assign(Impresora,’LPT1’); en donde; Impresora es una variable de tipo text.

reset(NL): Abre un archivo y ubica al puntero del archivo al comienzo del mismo. El archivo deberá existir, caso contrario generará un error en tiempo de ejecución y se detendrá la ejecución del programa, si no se ha atrapado dicho error por medio de la directiva al compilador {$I+}. Una vez abierto el archivo se podrá leer o grabar si el archivo es binario esto es, file of o file; y si la variable de sistema filemode estuviera con el valor dos; sólo se podrá leer, si estuviera con el valor cero o sólo se podrá grabar si estuviera con el valor uno; en cambio, si el archivo es de tipo text solo se podrá leer.

Ejemplo:

reset(Alumnos)

rewrite(NL): Abre un archivo nuevo y si existe lo destruye y lo crea vacío, en ambos casos ubica al puntero al archivo coincidiendo con eof(NL), es decir, con la marca de fin de archivo. El tamaño del archivo en este momento es cero. La variable de sistema filemode no se tomará en cuenta, ya que el modo de apertura para rewrite es siempre lectura y grabación. Un archivo abierto con rewrite primero se deben grabar algunos registros, luego posicionarnos sobre un registro previamente grabado, para luego poder leerlo, esto indica entonces que no hace falta tener que cerrar el archivo y abrirlo con reset para poder leerlo en el mismo proceso, solo basta hacer lo indicado anteriormente. Para un archivo de texto rewrite lo crea solo para grabar.

Ejemplo:

rewrite(Alumnos)

En archivo de texto existe una tercer posibilidad para abrir un archivo para agregar más líneas al mismo. La sentencia que abre un archivo sin destruirlo y que permite agregar más componentes al final del archivo es append(NL).
La impresora que es un archivo de salida se puede abrir con rewrite(NL), por ejemplo rewrite(Impresora);

Operaciones de lectura o grabación

read(NL, NR): Realiza la operación de lectura. El registro a leer es en donde se encuentra el puntero al archivo; “luego de la lectura, el puntero avanza a la próxima componente”. Al leer en un archivo binario se lee la componente completa, no hay posibilidad de leer una parte. La lectura de un registro en un archivo binario se realiza en forma directa desde el dispositivo de almacenamiento. Es decir, cada intento de leer se debe acceder al disco. En cambio en un archivo de texto se lee desde un buffer en la memoria interna, si hay algo para leer, sino, se accede al disco.
Intentar leer en una ubicación fuera del límite del archivo ocasionará en un error de lectura, indicado por el compilador pascal con el número 100. Estamos fuera de los límites del archivo cuando el puntero está más allá del tamaño del archivo, o bien cuando el puntero al archivo haya quedado posicionado antes de la dirección cero, hacer un intento de lectura en estos casos provocará el error anteriormente indicado.
En un archivo de texto readln luego de leer realiza un salto a la próxima línea.

Ejemplo:

read(Alumnos, rAlumno); rAlumno es la variable de tipo compatible con cada componente del tipo de archivo binario, no se podrá leer solamente una parte de dicha componente, es decir hacer read(Alumnos, rAlumnos.NroLeg) está mal.

write(NL, NR): Realiza la operación de grabación. El registro a grabar es en donde se encuentra el puntero al archivo en ese momento; “luego de la grabación, el puntero avanza a la próxima componente”. Al grabar en un archivo binario se graba la componente completa, no hay posibilidad de grabar una parte. La grabación en un archivo binario se realiza en forma directa hacia el dispositivo de almacenamiento. Es decir, por cada intento de grabar se debe acceder al disco. En cambio en un archivo de texto se graba hacia un buffer en la memoria interna, si se llena entonces es enviado al dispositivo externo, o sea, al disco. Si el puntero al archivo se encuentra sobre un registro existente, se actualizará con la información en el momento de realizar la grabación; en cambio si el puntero se encuentra coincidiendo con el fin de archivo, se genera un nuevo registro y el tamaño del archivo se expande una componente más. Ahora bien, ¿qué sucederá si se ubica el puntero al archivo mucho más allá de la marca de fin de archivo, digamos 5 posiciones más y se intenta grabar?. Se generan todos esos registros, solamente el registro que se graba tendrá valores conocidos, pero los registros intermedios contendrán basura, ya que no sabemos qué valores habrá allí, también en estos casos se expande el tamaño del archivo. Por lo tanto ubicar el puntero más allá del tamaño del archivo y grabar luego no generará ningún error en tiempo de ejecución. Pero, ¿qué sucederá si ubicamos el puntero al archivo antes de la primer componente, es decir, antes de la ubicación cero?, intentar grabar producirá un error en tiempo de ejecución.

Ejemplo:

write(Alumnos, rAlumnos); rAlumno es la variable de tipo compatible con cada componente del tipo de archivo binario, no se podrá grabar solamente una parte de dicha componente, es decir hacer write(Alumnos, rAlumnos.NroLeg) está mal.
En un archivo de texto writeln luego de grabar salta al comienzo de la próxima línea.
La impresora es un archivo de texto al cual podremos enviar informacón, el formato es write(NL, exp) o writeln(NL, exp). En el primer caso imprime el resultado de la expresión y permanece en la misma línea, en cambio en el segundo caso luego de imprimir avanza a la próxima línea.

Ejemplos:

write(Impresora, a,cad,’Mensaje: ‘,titulo,3.24:8:2);
write(lst,’Como estás ‘,Nom); en donde lst es una variable de tipo text definida en la unidad Printer, al cual debemos indicar en nuestro programa en la sección uses.
writeln(Impresora,’El total es: ‘,totVen:8:2);

Resumiendo: hacer read o write cuando el puntero está en una posición menor a cero está mal y generará un error en tiempo de ejecución; por otro lado si el puntero al archivo se encuentra más allá del tamaño del archivo, hacer read está mal, pero hacer write no es error.

close(NL): Cierra el archivo indicado en su argumento. Esta operación deberá realizarse cuando ya no debamos operar más con el archivo. Con los archivos de texto esta acción es muy importante ya que si no cerráramos el archivo perderíamos parte de la información debido a que si el buffer no se llenó, lo que quedó allí no sería enviado al disco. En cambio si cerramos el archivo, close antes de cerrarlo verificaría si hay algo pendiente de enviar desde el buffer, si es así se forzaría primero a enviar lo que hay allí al disco y luego se cerrará el archivo. En un archivo binario al no trabajar con el buffer esta situación no existe, no obstante, es aconsejable cerrar igualmente el archivo.
La impresora como archivo de texto debe ser cerrada, pero no si usamos la variable lst de la unidad printer, ya que la unidad se encarga de cerrarla.

Ejemplo:

close(Alumnos);
close(Impresora);

eof(NL): Es una función que retorna un valor de verdadero si el puntero está en fin de archivo, lo mismo si se encuentra en una posición menor a cero; caso contrario retorna falso. Esta función es común emplearla cuando leemos secuencialmente en un archivo, como condición en la cabecera de un ciclo indefinido, negando el valor retornado.

Ejemplo:

while not eof(Alumnos) do begin
read(Alumnos, rAlumno);
...
end;

filesize(NL): Función que retorna un valor longint que indica el tamaño del archivo en cantidad de registros.

Ejemplos:

writeln(fileSize(Alumnos);

for i:= 1 to fileSize(Alumnos) do begin
read(Alumnos, rAlumno);
...
end;

filepos(NL): Función que retorna un valor longint que indica la posición en que se encuentra el puntero en el archivo indicado por NL.

Ejemplo:

writeln(filePos(Alumnos));

seek(NL, dir): Ubica al puntero del archivo indicado por NL, en la dirección indicada por dir. El segundo parámetro puede ser una expresión. Se podrá ubicar el puntero dentro o fuera del tamaño del archivo, sin generar ningún error, inclusive antes de la posición cero.

Ejemplo:

seek(Alumnos, 3);
seek(Alumnos, fileSize(Alumnos)); la ubicación nueva coincide con eof.
seek(Alumnos, filepos(Alumnos));
seek(Alumnos, fileSize(Alumnos) – 1); la ubicación nueva coincide con el último
registro existente en el archivo.

truncate(NL): Sentencia que trunca o corta el archivo a partir en donde se encuentre el puntero al archivo. Actualiza el tamaño del archivo.
Si tomamos un archivo que contiene 15 registros y cambiamos el puntero al archivo a la ubicación 7, seek(Alumnos, 7); y luego hacemos truncate(Alumnos); se eliminarán todos los registros localizados desde la ubicación 7 hasta la ubicación 14 inclusives, es decir, ahora el tamaño del archivo se comprimió a 7 registros, desde la posición cero hasta la posición seis.

rename(NL, NVONF): Permite renombrar el archivo indicado por NL con otro nuevo nombre físico, la actualización se realiza en el directorio del disco.
Ejemplo:

rename(Alumnos, ‘Student.Dat’);

erase(NL): Elimina o borra el archivo indicado por NL, del directorio en el disco.

Ejemplo:

erase(Alumnos);

Archivo binario con 12 registros con direcciones [0; 11]

Si el puntero al archivo está ubicado en la marca de eof, realizar una operación de lectura producirá un error en tiempo de ejecución y se aborta el programa, lo mismo ocurrirá si está más allá de la marca de eof, pero grabar esta bién y se expande el tamaño del archivo una componente más y la marca se reubica después del registro grabado, coincidiendo con el puntero al archivo.
Si el puntero al archivo está ubicado en una dirección más alejada digamos 15 y se graba un nuevo registro, también se graban los registros 12 a 14 pero su contenido será desconocido.
Si el puntero al archivo está ubicado en una dirección menor a 0 realizar una operación de lectura o escritura producirá un error en tiempo de ejecución y se aborta el programa.
La función eof(f) retornará verdadero si el puntero al archivo se encuentra fuera de los límites del archivo, esto es, si está más allá de la marca eof o si se movió el puntero al archivo a una dirección menor a 0.

[1] IRD significa: Izquierda, Raíz, Derecha. RID significa: Raíz, Izquierda, Derecha. IDR significa: Izquierda, Derecha, raíz.

Anterior: Lenguaje Turbo Pascal

Siguiente: Archivos II

Arriba

Lenguaje Turbo Pascal

2008-03-28T20:41:00.000-07:00

Abajo

CLASE 7: Lenguaje Turbo Pascal.

Estructura de un programa en Turbo Pascal

El lenguaje Pascal fue creado en la década del 70 por Niklaus Wirth de Zurich, partiendo de otros lenguajes previamente desarrollados, como el Algol y el Fortran. El Pascal fue desarrollado como un lenguaje de propósito general, orientado hacia fines pedagógicos de nivel universitario y para los estudiantes en la carrera de Sistemas. Desde sus origenes fue concebido como un lenguaje con las herramientas necesarias para facilitar la programación estructurada, ya que reúne las estructuras de control de programa de: la sentencia compuesta –concatenación, bloque-, la estructura condicional –selección- y la cíclica –repetición, iteración-. Permite la programación modular, ya que, otorga la posibilidad de crear módulos –procedimientos y funciones-, logrando dividir un problema en partes menos complejas, partiendo de lo general a lo particular, a su vez, cada una de estas partes puede volver a dividirse, esta tarea se conoce como refinamiento sucesivo. También es un lenguaje fuertemente tipado, es decir, ante la menor incompatibilidad de tipos generará un error. Es un lenguaje procedural –imperativo, orientado a órdenes-. Existen ciertas diferencias entre el Pascal standard con el Turbo Pascal, este último incorpora notables diferencias para beneficio al programador, por lo tanto, de aquí en adelante al hablar del Pascal estaremos refiriéndonos al Turbo Pascal de Borland, versión 5 en adelante.
Entre las ventajas adicionales que encontramos están las unidades, herramientas para la programación orientada a objetos, gráficos, etc..

Los lenguajes de programación se clasifican en:

Lenguaje máquina: escritos a nivel de bits, hace que sea una tarea bastante tediosa al programador aunque directamente reconocible por la computadora –cpu-.
Lenguajes de bajo nivel: –ensambladores-: En lugar de escribir las ordenes impartidas a la máquina con ceros y unos, se utiliza un lenguaje simbólico, que establece una relación 1 a 1, por lo tanto es extraordinariamente rápida su ejecución, la desventaja es que estos lenguajes están muy comprometidos con la máquina en donde deban ser ejecutados, por lo tanto no son transportables prácticamente a otros equipos, esto hace entonces que cada hardware diferente cuente con un código especialmente escrito para cada equipo. Los lenguajes de bajo nivel, las instrucciones se escriben en códigos alfabéticos conocidos como mnemotécnicos, p.e.:

Cód. Código
Máq. Mnemotécnico
0010 ADD
0001 LOAD
0100 STG

Luego de escribir un programa en lenguaje assembler, se necesita de un programa ensamblador que lo traduzca a código máquina.

Lenguajes de medio nivel: Son lenguajes que se encuentran en un paso intermedio entre los lenguajes de bajo nivel y los lenguajes de alto nivel. Los lenguajes de bajo nivel se encuentran más cerca de la máquina que del programador, en cambio los lenguajes de alto nivel son más cercanos al programador que a la máquina. Los lenguajes de nivel medio por lo tanto están en un punto intermedio entre la máquina y el programador. El lenguaje C es considerado como un lenguaje de nivel medio, ya que posibilita escribir el código de diferentes maneras, el que se elija hará que esté más cerca de la máquina o del programador o inclusive en un punto medio, entre estos dos, p.e.: c = c + 1 o c += 1 o c++, son distintas maneras de hacer lo mismo, aunque el código máquina que genere no sea el mismo, esto determinará que algunas de estar órdenes al traducirse a código máquina sea más óptima que otras, es decir, se ejecutrá más rápidamente.
Lenguajes de alto nivel: Aquí encontramos muchos de los lenguajes de programación, p.e.: Pascal, Basic, Cobol, Fortran, Algol, Ada, Modula, etc. Esta categoría de lenguajes hace que se encuentren más cercanos al programador que de la máquina. Esto significa que al alejarse más de la máquina requerirá de mayor tiempo de ejecución, pero serán más fáciles de escribir por utilizar palabras similares al lenguaje natural. Los programas escritos en un lenguaje de alto nivel son transportables, es decir, se pueden ejecutar en distintas máquinas, ya que no son tan dependientes del hardware. El código escrito debe ser traducido al lenguaje de máquina y para llevar a cabo esta tarea se utilizan los compiladores o bien los intérpretes.

Etapas para la generación de código máquina

Edición del programa, utilizando la consola –teclado, pantalla-, a través de un editor de texto o que genere código ASCII puro, una vez finalizado se graba en disco con un nombre elegido por el programador y de una extensión que dependerá del lenguaje que hayamos seleccionado para escribir nuestro programa, p.e.: Pascal .Pas, Basic .Bas, C .c, Cobol .Cob o .Cbl, dBase o Clipper o Fox .prg, etc.. Este programa recibe el nombre de programa fuente y es muy importante conservarlo, debido a que en caso de necesitar realizar modificaciones, se realizará con el código fuente.
Compilar el programa fuente, -etapa anterior-, utilizando el compilador correspondiente al lenguaje empleado, por lo tanto, el compilador tiene una entrada que es el lenguaje fuente, p.e.:

Tp MiProg Tp, Compilador Turbo Pascal de Borland
Tc MiProg Tc, Compilador Turbo C de Borland
Cobol MiProg Cobol, Compilador Cobol.

El archivo generado recibe el nombre de programa objeto y tiene como extensión .obj, -object-. Este programa contiene la traducción del programa fuente, es decir, su código es el de máquina, pero aún no podrá ser ejecutado debido a que habrá que enlazarle las librerías a que hace referencia.
Vincular el programa objeto –resultado de la etapa de compilación-, utilizando la aplicación que contiene las librerías que requiera el programa objeto, generalmente con el nombre de Link o similar, p.e.:

Link MiProg
Blink MiProg
Tlink MiProg

Generalmente podrán incorporarse cuantos módulos .obj necesitemos para general un solo programa que ahora sí contendrán los códigos de las librerías que requería el .obj. El resultado del enlzador es un programa ejecutable cuya extención es .exe, p.e.: MiProg.exe, y es este programa autosuficiente de ser ejecutado.

Un programa en T.Pascal consta de las siguientes partes:

Una cabecera, precedida por una palabra reservada y un identificador, a saber:

Program IdProg;

IdProg tiene como propósito identificar con un nombre apropiado el sentido del programa, es decir, cuál es el proceso que lleva a cabo.

Un área de definiciones y declaraciones de objetos diversos, cada una representada por medio de una palabra reservada, que establece una sección, en el cuál existe una cierta libertad para el orden, salvo que obligatoriamente debamos escribir alguna sección antes de otra, por motivos de que un identificador antes de poder utilizarlo debe estar previamente definido. Las secciones son las siguientes:

uses
{lista de Id.de unidades}
const
{lista de Id. constantes}
type
{lista de tipos}
procedure
{Módulo procedimiento}
function
{Módulo función}
var {Ubicadas en el Segmento de Datos}
{lista de variables globales}

y un bloque principal, encerrado entre las palabras reservadas:

begin
sentencia1;
sentencia2;
.
sentencian
end.

Una palabra reservada en T.Pascal cumple un propósito específico, por lo tanto nunca debe ser utilizada para que cumpla otro rol. Las palabras que aparecen en negrita en el esquema anterior son palabras reservadas.
Un identificador es una palabra creada por el usuario y sirve para definir nombres de unidades, constantes con nombres, tipos, campos de registros, nombres de procedimientos, funciones y variables.Un identificador jamás puede ser una palabra reservada, por lo dicho en el apartado anterior.

En la sección uses definimos las unidades que se van a incorporar a nuestro programa. Una unidad es un conjunto de objetos previamente compilados y cuyo código se agrega al código de nuestro programa, solo el programa principal y sus módulos desarrollados deberán ser compilados. Una unidad compilada tiene extensión .TPU, mientras que el archivo de código fuente tiene la misma extensión que el programa .Pas. Los objetos que componen una unidad son los mismos objetos vistos en el esquema previo, vale decir, otras unidades, constantes con nombre, tipos, procedimientos, funciones y variables.

Unidades predefinidas

El lenguaje T.Pascal proporciona al usuario de unidades las cuales están almacenadas en el archivo TURBO.TPL algunas de las cuales son:

CRT, que reúne un conjunto de objetos para la facilidad del teclado y pantalla, entre estos objetos tenemos los siguientes identificadores de procedimiento o funciones:

gotoxy(x,y) que sirve para ubicar al cursor en las coordenadas x,y siendo (1,1) el ángulo superior izquierdo; (1,80) el ángulo superior derecho; (1,25) el ángulo inferior izquierdo y (80,25) el ángulo inferior derecho.

delay(n) realiza una espera de n milisegundos.

clrscr limpia la pantalla y ubica al cursor en el ángulo superior izquierdo, es decir en las coordenadas (1,1).

clreol limpia una linea pero desde la columna en donde se encuentre el cursor –puntero de la pantalla- hasta el final de la línea, y dejando al cursor posicionado en la fila y columna en que se encontraba previo a limpiar la línea.

keypressed función que realiza una espera hasta que se oprima una tecla, es necesario encerrarla dentro de una estructura cíclica, ya que retorna un valor de tipo boolean.

textcolor(n) cambia el color del carácter, n es un valor entre 0 y 15.

textbackground(n) cambia el color del fondo del cracter, n es un valor entre 0 y 7.

readkey función que lee desde el buffer del teclado un valor, si el buffer está vacío espera a que se presione una tecla, no es necesario terminar con la tecla ENTER.

window(x1,y1,x2,y2) crea una ventana, todo aquello que se emita será enviado a esta ventana, la ventana máxima es window(1,1,80,25).

sound(n) emite un sonido, por el speaker, n indica un valor de frecuencia.

nosound hace que deje de emitirse sonido, se utiliza para deterner a sound.

En lugar de utilizar valores entre 0 y 15 para indicar el color se podrán utilizar las constantes con nombres definidas en esta unidad, p.e.: blue, red, green, white, yellow, black, lightred, etc..

PRINTER brinda una variable lst de tipo archivo text que permite enviar la salida hacia la impresora, además da facilidades para su manejo ya que no es necesario ni abrir ni cerrar ese dispositivo, debido a que lo gestiona la unidad.

DOS otorga un conjunto de objetos de servicios al sistema operativo D.O.S., entre estos objetos se encuentran los procedimientos:
getdate(aa,mm,dd,ds) que obtiene la fecha del sistema, cada parámetro es de tipo word y ds indica el día de la semana, 0 para domingo, 1 para lunes, ..., 6 para sábado.
gettime(hh,mm,ss,cs) que obtiene la hora del sistema, cada parámetro es de tipo word y cs indica centésimas de segundo.

SYSTEM esta unidad siempre estará disponible en nuestros programas y jamás deberá anunciarse en la sección uses, si se hiciera se colgaría el programa. Aquí se encuentran muchos de los objetos que utilizamos en un programa, p.e.: las funciones numéricas, las funciones de cadenas, las sentencias de asignación externas de entrada y salida, es decir, los procedimientos read, readln, write, writeln que veremos más adelante, como todas las sentencias y funciones para manejo de archivos y asignación de memoria.

Unidades definidas por el usuario

T.Pascal también permite que el usuario desarrolle sus propias unidades; para hacerlo debemos conocer como es su estructura. Una unidad se compone de las siguientes partes:

Unit IdUnidad;
interface {Parte pública o visible a otras unidades o programas
que utilicen esta unidad}
uses
const
type
procedure {solo la cabecera}
function {solo la cabecera}
var

implementation {Parte privada}

uses
const
type
procedure {se desarrolla completamente}
{los procedimientos que no aparecen en la sección de interface no serán reconocidos por los programas que enlacen la unidad, solo serán reconocidos por la unidad, es decir son locales y solo serán reconocidos por otras unidades si están definidas dentro de su ámbito}
function {se desarrolla completamente}
{las funciones que no aparecen en la sección de interface no serán reconocidos por los programas que enlacen la unidad, solo serán reconocidos por la unidad, es decir son locales y solo serán reconocidos por otras unidades si están definidas dentro de su ámbito}

var

begin
{Inicializar la unidad}
sentencias
end.

El nombre que identifica a la unidad debe ser el mismo nombre que demos al archivo. El archivo fuente tiene extensión .Pas y el archivo compilado tiene extensión .Tpu, es decir, Unidad Turbo Pascal. Las unidades se compilan en forma independiente de los programas, por lo tanto, cuando un programa requiere los servicios de una unidad solo se la menciona en la sección uses, enlazando su código al programa.
Las unidades son llamadas también librerías, y los objetos que incluimos deben ser de un tema específico. Por último diremos que las unidades son módulos que acentúan la programación modular y permiten la construcción de grandes programas.

En la sección const definimos constantes con nombres y es de uso global en el programa. En vez de utilizar valores constantes en nuestro programa, en ciertas situaciones es conveniente utilizar este tipo de objetos, que por diversas razones lo hace más legible y dinámico a la hora de modificar el programa, p.e. en vez de utilizar la constante 21 del IVA, podríamos definir una constante con nombre denominada IVA y hacerla igual al valor 21, luego en los distintos puntos del programa en donde dicho valor podría aparecer, pondríamos este identificador. Si a futuro debemos realizar un cambio de valor solo iremos al único lugar en donde podemos modificarlo. Por conveniencia utilizamos nombres escrito todo en mayúscula a efectos de darnos cuenta en el momento de leer un listado fuente de que esos identificadores son objetos constantes y no variables. El único lugar en donde podemos cambiar el valor de una constante con nombre es en la sección const. La sintaxis es:

const
IdConst = expresión;

Ejemplos:

const
IVA = 21;
MIN = 12;
MAX = MIN * 2 –1;
VAL_ABS = abs(-MAX);
COC = MAX div MIN;
RES = MAX mod MIN;
CAD = ‘esto es una cadena de caracteres’;
LONG = length(cad);
C = #67;
VERDADERO = true;
ENT = trunc(23.74);
CODASCCI = ord(‘A’);

En la sección type definimos nuevos tipos de datos y es de uso global en el programa. La sintaxis es:

type
IdTipo = tipo;

IdTipo es un identificador válido.
tipo es un identificador o tipo simple o tipo estructurado o tipo string o tipo pointer.

El lenguaje Pascal es fuertemente tipado -strongly typed-, esto quiere decir que todas las variables deben estar previamente definidas correspondiendo a un tipo de dato al que pertenecen. Otra clase de lenguajes que verifican el tipo de variables según el valor que se le asigne por primera vez se denominan auto tipados –self typed- mientras que otros lenguajes podrían permitir que una variable tome valores de distinto tipo durante la ejecución del programa, en este caso se denomina dinámicamente tipados –dinamically typed-.
Definir a una variable como perteneciente a un tipo de dato, circunscribe al conjunto de valores que puede tener y las operaciones que pueden realizarse.

Los tipos en Pascal se clasifican en:

Tipos simples
Ordinales –predefinidos-
Integer
ShortInt
LongInt
Byte
Word
Char
Boolean
Ordinales -definidos por el usuario-
Enumerado
Intervalo
Reales
Real
Single
double
extended
comp
Tipos String –cadena de caracteres-
String
String[n]
Tipos estructurados
Record
File
Set
Array
Tipos punteros
Pointer
^IdTipoBase
Tipos Procedurales
Procedure...
Function...

Ejemplos:

type
int = integer;
str20 = string[20];
Fecha = record
aa : word;
dd,
mm : byte
end;
RegAlu = record
NroLeg : longint;
ApeNom,
Domic,
Local : str20;
FecNac : Fecha;
EstCiv : char
end; Meses = 1..12;
MesesStr = (Enero, Febrero, Marzo, Abril, Mayo, Junio, Julio, Agosto, Septiembre,
Octubre, Noviembre, Diciembre);
PriSem = Enero..Junio;
SegSem = Julio..Diciembre;

Meses es de tipo [1; 12]. MesesStr es de tipo por enumeración siendo los nombres de los meses constantes y únicos, es decir, no puede volver a definirse para otro tipo, los valores ordinales son Enero = 0, Febrero = 1, ... PriSem es de tipo [Enero; Junio].
Sobre los tipos ordinales se pueden aplicar las funciones : ord, pred y succ. p.e.: ord(Marzo) = 2, Succ(Mayo) = Junio, Pred(Octubre) = Septiembre, ord(false) = 0.

Las variables son objetos a los que se les pueden asignar valores del mismo tipo en que han sido definidas. La sintaxis es:

var
Lista-IdVar : tipo;

Lista_IdVar es una lista de identificadores válidos separados por comas.

Aquellas variables definidas fuera del ámbito de un módulo son variables globales. Estas variables son estáticas, debido a que el espacio que ocupen en la memoria estará definido en tiempo de compilación y no se libera hasta que finalice la ejecución del programa. Las variables globales se localizan en el segmento de datos, que es una región de memoria hasta un máximo de 64Kbytes, en caso de necesitar más espacio, se puede recurrir a un diseño modular, esto hace que aquellas variables que sean propias del módulo ocupen lugar en otra region de memoria que es el segmento del stack o pila, las variables definidas dentro del ámbito de un módulo se denominan variables locales y existen mientras el control de ejecución del programa esté cedido al módulo, vale decir estas variables como así también los parámetros, se crean cuando se llama o invoca al módulo y son eliminadas cuando se regresa el control al punto desde donde se invocó. Por otro lado si aún fuera necesario incrementar el espacio para variables se podrá utilizar otra región de memoria al área del heap o montículo, en donde el límite es el resto de la memoria disponible. Pero a diferencia de las variables globales, estas variables ubicadas en el heap se denominan variables dinámicas y se crean o eliminan en tiempo de ejecución, por medio de los procedimientos definidos por Pascal new y dispose respectivamente. Para poder acceder a estas localizaciones es necesario recurrir a las variables de tipo puntero, es decir, variables que contienen una dirección de memoria.

Ejemplos:

var
a, b, c : real;
i, j : integer;
cad20 : str20; {str20 es un identificador que debió definirse en la sección type}
car : char;
rAlumno : RegAlu {RegAlu debe estar definido previamente en la sección type}
existe : boolean;
NroLeg : longint;
cant, kg : word;

Los procedimientos son módulos que deben ser invocados para que su código pueda ser ejecutado, ya que, si no se lo invocan están como en un estado de hibernación. La comunicación entre la llamada y el módulo se logra por medio de los parámetros. En el punto de la llamada se denominan parámetros actuales, mientras que en la cabecera del módulo se denominan parámetros formales. Un procedimiento está estructurado en las siguientes partes:
Una cabecera que incluye:
La palabra reservada procedure
El identificador de procedimiento
Una lista de parámetros, que podrán ser pasados por valor o por referencia; en este último caso deberá estar precedido con la palabra reservada var.
Un área de definiciones y declaraciones de objetos locales.
Un cuerpo encerradas entre las palabras reservadas begin y end.
procedure IdProc(lista de parámetros);
var {Locales}

begin
sentencia; ...
end;
lista de parámetros es: Identificador, ... : tipo o var Identificador, ... : tipo

Si el parámetro no está precedido por la palabra reservada var, entonces el parámetro es pasado por valor, esto es, con el valor pasado se hace una copia en otra región de memoria y cualquier cambio que se hiciere, en realidad no afectará al parámetro actual, por estar trabajando con la copia, y no con el valor original. Este tipo de pasaje de parámetros es utilizado cuando el valor se conoce antes de invocar al módulo y deseamos pasar el valor al módulo para que realice algún proceso. Los parámetros pasados por valor son parámetros de entrada y sirve para inicializar al parámetro formal. El objeto que ocupa la misma posición, el parámetro actual, puede ser una expresión, es decir, puede ser una constante, una variable o una expresión propiamente dicha, p.e.:

Si el parámetro está precedido por la palabra reservada var, entonces el parámetro es pasado por referencia, esto es, se pasa la dirección del objeto, por lo tanto, este objeto, del parámetro actual, solo debe ser una variable. El parámetro formal recibe la dirección, y al momento en que se le asigne un valor dentro del módulo al parámetro formal, en realidad se lo está asignando al parámetro actual, a través del parámetro formal. Imaginemos que este parámetro formal es una catapulta que envía lo que recibe a un único punto, al punto al que apunta, es decir en donde está ubicada la variable –el parámetro actual-, cuya dirección es la que recibió el parámetro formal. Este tipo de pasaje de parámetros es utilizado cuando conocemos el valor dentro del módulo y queremos dárselo al bloque que lo llamó a través de su parámetro actual o bien conociendo previamente su valor, dentro del módulo invocado quizás sufra alguna modificación y queremos informarlo al bloque que invocó al módulo, por medio de su parámetro actual. Este tipo de parámetros pasados por referencia son parámetros de salida o bien de entrada-salida.

Las funciones son módulos que deben ser invocados para que su código pueda ser ejecutado, ya que, si no se invocan están como en un estado de hibernación. La comunicación entre la llamada y el módulo se logra por medio de los parámetros. En el punto de la llamada se denominan parámetros actuales, mientras que en la cabecera del módulo se denominan parámetros formales.

Una función está estructurada en las siguientes partes:

Una cabecera que incluye:
La palabra reservada function
El identificador de la función.
Una lista de parámetros, que podrán ser pasados por valor, es lo más habitual o por referencia; en este último caso deberá estar precedido con la palabra reservada var.
El tipo de dato simple que retornará la función.
Un área de definiciones y declaraciones de objetos locales.
Un cuerpo encerradas entre las palabras reservadas begin y end, el cual deberá tener al menos una sentencia de asignación y que asigne al nombre de la función el resultado de una expresión que deberá coincidir con el tipo en que fue definida en su cabecera.

function IdFunc(lista de parámetros) : tipo;
var {Locales}

begin
sentencia; ...
IdFunc <-- expresión end;

lista de parámetros es: Identificador, ... : tipo o var Identificador, ... : tipo

Si el parámetro no está precedido por la palabra reservada var, entonces el parámetro es pasado por valor, esto es, con el valor pasado se hace una copia en otra región de memoria y cualquier cambio que se hiciere, en realidad no afectará al parámetro actual, por estar trabajando con la copia, y no con el valor original. Este tipo de pasaje de parámetros es utilizado cuando el valor se conoce antes de invocar al módulo y deseamos pasar el valor al módulo para que realice algún proceso. Los parámetros pasados por valor son parámetros de entrada y sirve para inicializar al parámetro formal. El objeto que ocupa la misma posición, el parámetro actual, puede ser una expresión, es decir, puede ser una constante, una variable o una expresión propiamente dicha.

Si el parámetro está precedido por la palabra reservada var, entonces el parámetro es pasado por referencia, esto es, se pasa la dirección del objeto, por lo tanto, este objeto, del parámetro actual, solo debe ser una variable. El parámetro formal recibe la dirección, y al momento en que se le asigne un valor dentro del módulo al parámetro formal, en realidad se lo está asignando al parámetro actual, a través del parámetro formal. Imaginemos que este parámetro formal es una catapulta que envía lo que recibe a un único punto, al punto al que apunta, es decir en donde está ubicada la variable –el parámetro actual-, cuya dirección es la que recibió el parámetro formal. Este tipo de pasaje de parámetros es utilizado cuando conocemos el valor dentro del módulo y queremos dárselo al bloque que lo llamó a través de su parámetro actual o bien conociendo previamente su valor, dentro del módulo invocado quizás sufra alguna modificación y queremos informarlo al bloque que invocó al módulo, por medio de su parámetro actual. Este tipo de parámetros pasados por referencia son parámetros de salida o bien de entrada-salida.

La sentencia de asignación

Presenta el siguiente formato:
variable := expresión

Bloque del diagrama de flujo
variable <-- expresión

Permite asignar valores a las variables. El lado izquierdo del símbolo := es el objeto que recibe el valor, y debe ser solamente una variable. El lado derecho del mismo símbolo indicado anteriormente, es una expresión y una vez calculado su valor es asignado a la variable que está del lado izquierdo, el cual debe coincidir su tipo con el que ha sido definida la variable, pues en caso de que no coincida, se dará un mensaje de error. La excepción está cuando la variable es de tipo real y la expresión genere un resultado de tipo entero.

Ejemplos:

a := 3;
letra := ‘A’;
mes := Enero;
mesStr := ‘Enero’;
mesPos := ord(Enero);
c := 2; x := 30;
EsMayor := (x > y) and (‘A’ > ‘@’);
c := c + 5;
ApeNom := rAlumno.ApeNom;
existe := false;
precio := 281.94;
y := k + sqrt(sqr(a) + sin(x * pi / 180));

La asignación externa de entrada

Presenta el siguiente formato:

var, ...read(var,...)
readln(var,...)

Bloque del diagrama de flujo

Espera a que se ingrese un valor, siendo el dispositivo por defecto el teclado, por lo tanto, una vez tipeado el valor y luego de oprimir la tecla ENTER, el valor es asignado a la variable que aparece como parámetro del procedimiento read o readln, luego de esto la ejecución continúa su rumbo. Debe existir una correspondencia de tipos entre el valor ingresado y la definición del parámetro en el procedimiento read o readln, ya que si no se corresponden sus tipos ocacionará en un error de compilación. Si bien se aceptan escribir más de una variable, es conveniente escribir una sola y usar readln, para evitar ciertos fenómenos no deseados. Las cadenas y caracteres se ingresan sin encerrarlas entre apóstrofos.

Ejemplos:

readln(NroLeg);
readln(rAlumno.ApeNom);
readln(rAlumno.FecNac.dd);

La asignación externa de salida

Presenta el siguiente formato:
exp, ...
write(exp, ...)
writeln(exp, ...)

Bloque del diagrama de flujo

Espera a que se emita el valor, siendo el dispositivo por defecto la pantalla, por lo tanto, una vez que se haya emitido luego de esto la ejecución continúa su rumbo. Si la exp es una constante entonces el valor emitido es la propia constante, si exp es una variable entonces se emite su contenido y por último si exp es una expresión propiamente dicha entonces el resultado de evaluar la expresión es lo que se emite. Se puede dar formato a la salida de los valores enteros, escribiendo; writeln(valEnt:m) o write(valEnt:m), en donde m indica la longitud a reservar, p.e.: writeln(mes:2,’-‘,aa:4) en cambio con valores reales la forma es, writeln(valReal:m:n), en donde m indica el espacio a reservar y n la cantidad de dígitos decimales que se van a emitir, la longitud m incluye el punto decimal, p.e. writeln(‘$ ‘,imp:8:2), después de emitir el signo $ seguido de un espacio reserva 8 lugares para emitir el valor, compuesto por 5 dígitos enteros un punto decimal y dos dígitos decimales, si el número tuviera menos dígitos enteros entonces rellena con blancos a izquierda de la parte entera del número y con dígitos ceros a derecha en la parte decimal del número. En cambio, si el número necesita de más espacio igual se emite, pero ya no podrá quedar alineado con respecto a los valores emitidos en esa misma posición, es decir, quedarán corridos o desalineados. También se pueden emitir las cadenas con el siguiente formato, write(cad:m) o writeln(cad:m), si la cadena tiene menos caracteres que m, entonces primero se emiten espacios en blanco y después la cadena, por lo tanto, la alineación se efectúa a derecha. Para realizar un tabulado horizontal, se realiza de esta forma, write(‘ ‘:m), emitiendo m espacios en blanco, p.e. si queremos emitir una cadena y a continuación otro valor pero a partir de una misma posición , hacemos, write(Descrip,’ ‘:22-length(cad),precio:8:2).

Ejemplos:

write( ‘Apellido y Nombre: ‘,ApeNom);
writeln(‘Pre.unit.: ‘,PreUni:8:2,’ Cantidad: ‘,cant:5,’ Total: ‘,cant*PreUni:10:2);
writeln(‘[a; b] = [‘,a,’; ‘,b,’]’);

Estructuras de Control de programas

La sentencia compuesta BEGIN END

La sentencia compuesta establece que sus componentes que son sentencias, se ejecuten en el orden en que han sido escritas. Estas sentencias son consideradas como si fueran una sola sentencia; este concepto es vital para aquellos casos en que el ámbito de una estructura de control es una sola sentencia. Las palabras reservadas begin y end encierran las sentencias dentro de la sentencia compuesta y van separadas por punto y coma, antes de un end no es obligatorio su uso, si se escribe entonces la sentencia a ejecutar será la sentencia vacía. La sintaxis es:

begin {Bloque}
x := 5;
ObtDatos(rAlumno);
writeln(‘Localidad: ‘,rAlumno.Local);
writeln(‘x: ‘,x:4)
end.

Sentencias condicionales

Las sentencias condicionales son las que posibilitan una ruptura en la secuencia de ejecución de las sentencias, posibilitando cambiar de rumbo, es decir, poder seleccionar que acciones ejecutar si se cumple o no una condición. A continuación se presentan las variantes de este tipo de sentencias condicionales:

La sentencia condicional simple IF

Es la sentencia más habitualmente empleada para realizar bifurcaciones o ramificaciones, ya que, con este tipo de sentencia condicional permite efectuar la más variada forma de uso para estos casos. La sintaxis es:

La expresión debe generar un resultado de tipo boolean. Si la expresión produce un resultado verdadero –true-, entonces se ejecuta la sentencia que sigue a then. Si la expresión produce un resultado de falso –false-, entonces se ejecuta la sentencia que sigue a else. Si la parte else no está presente entonces nada se ejecuta.
Si una sentencia condicional if no tiene la parte else decimos que es una selección simple incompleta y si está presente es una selección simple completa. Un else se corresponde con el último if abierto, este concepto es muy importante debido a que en los casos de if’s anidados, podemos tener una situación de un if completo y dentro de este un if incompleto, ¿a que if le corresponde, entonces el único else?. Evidentemente al if interno, por lo tanto nuestra lógica estaría mal representada. La solución a estos casos obliga a usar un bloque de concatenación, encerrando al if interno, por lo cual la partícula else ahora se referirá al if externo, como era de esperar en nuestra lógica.

La sentencia condicional múltiple CASE

Una opción a la sentencia condicional simple es la sentencia condicional múltiple. Esta sentencia permite bifurcar por más ramas o caminos, pero presenta ciertas limitaciones con respecto a la condicional simple, ya que, la expresión debe generar un valor de tipo ordinal, por lo tanto, las expresiones reales y de cadena no pueden ser empleadas para las sentencias condicionales múltiples. La sintaxis es:

La sentencia case consiste en una expresión –selector- su resultado debe ser de tipo ordinal, y una lista de sentencias, cada una de las cuales está precedida por una o más constantes, del mismo tipo de la expresión, denominadas constantes case, o precedida con la palabra reservada else.
El valor ordinal del selector debe estar limitado a [-32768; 32767] y los tipos string, longint y word son inválidos para usarlos como selector.
La sentencia case después de evaluar el resultado de la expresión compara por igual con los valores constantes case en el orden en que han sido escritas, ejecutando la sentencia correspondiente a ese caso si existió una igualdad. En caso contrario y si está presente la partícula else se ejecutará la sentencia que le sigue, sino nada se ejecutará.
Este tipo de sentencia condicional es apta cuando se quiera evaluar una serie de valores ordinales; en lugar de emplear la sentencia condicional simple en forma anidada. Debido a esto, se hace más limpia la codificación a efectos de poder interpretar la lógica de manera más clara. No obstante, debemos tener en cuenta que este tipo de sentencia condicional no puede ser aplicada en todos los casos, es decir, es de aplicación limitada a los tipos ordinales.

Ejemplos:

Sentencias repetitivas

Las sentencias repetitivas establecen que ciertas sentencias serán ejecutadas repetidamente. Los ciclos son tan importantes en un proceso computacional que prácticamente no existen procesos que no incluya algún ciclo. Situaciones como escribir 10, 100, 1000 o mas veces un conjunto de sentencias haría improbable la programación, más aún, ¿cuántas veces escribir esas sentencias, si la cantidad de veces a realizarse estaría establecida por alguna condición?. Imposible de no existir los ciclos. A continuación se verán diversas variantes que podemos encontrarnos con este tipo de estructuras de control. Será el buen criterio del programador seleccionar una de estas variantes ante una situación particular.
En todo tipo de ciclos tendremos por lo general sentencias previas al inicio del ciclo, en este punto decimos preparar la situación antes. Entre las acciones más habituales tenemos; emitir títulos y/o datos, inicializar variables. Dentro del ámbito del ciclo denominamos procesar las acciones ubicadas en este segundo punto y por último, al salir del alcance del ciclo tenemos el terminar, que incluye ciertas acciones como ser, emitir resultados, cálculos de promedios, porcentajes, etc..

Preparar
Repetir
Procesar
FinRepetir
Terminar

La sentencia indefinida, pre-condición, 0-X, mientras WHILE

La sentencia indefinida establece que la sentencia o bloque de sentencias se ejecutarán si la condiciones pre-establecida en la cabecera de esta estructura es verdadera y en caso de que se haga falsa se abandonará la repetición. La sintaxis es:

La expresión que controla la repetición debe ser de tipo boolean. Ésta es evaluada antes que la sentencia contenida sea ejecutada. La sentencia contenida es ejecutada repetidamente mientras la expresión sea verdadera. Si la expresión fuera falsa al inicio entonces nada se ejecuta. Por lo tanto, este tipo de ciclo es un ciclo en la cual la sentencia contenida puede no ejecutarse o bien ser ejecutada x veces, de ahí que también se lo denomine ciclo 0-x. La expresión puede estar controlada por un acumulador, un valor centinela, una señal, una condición de fin de archivo como se verá más adelante, o por condiciones múltiples. Este tipo de estructura se basta por sí misma, esto quiere decir que no depende de la existencia de otras estructuras repetitivas. Aunque como se verá más adelante en ciertas condiciones particulares otra variante cíclica será más óptima para ciertos casos.
Debemos tener sumo cuidado con esta estructura cuando se haya ingresado al ciclo y poder establecer con alguna acción que modifique el resultado de la expresión, a que en algún momento se invierta produciendo un resultado de falso para así poder abandonar el ciclo. El ámbito es de una sola sentencia, más, requiere el uso de un bloque o sentencia compuesta –concatenación-.
En general existirá un conocer primer valor en la instancia de preparar; dentro del ciclo, procesar el valor y como última acción, dentro del ciclo, conocer próximo valor.

Preparar
Emitir títulos
Inicializar variables
Conocer primer valor
while expresión do begin
Procesar valor
Conocer próximo valor
end
Terminar
Cálculos finales
Emitir resultados finales del procesar

Ejemplos:

La sentencia exacta, pre-condición, para FOR

La sentencia for hace que la sentencia contenida sea ejecutada repetidamente una cantidad exacta de veces. La sintaxis es:

En el punto de entrada o cabecera se evalúa el valor inicial y final. Cuando una sentencia for, usa la cláusula to, si el valor inicial es mayor al valor final, la sentencia dentro del ámbito del ciclo no se ejecuta. La variable de control se inicializa con el valor inicial, luego que haya ejecutado la sentencia contenida y de haber determinado que su valor es menor al valor final, la variable de control se incrementa en uno por cada repetición, en cambio, si el valor de la variable de control se hizo igual al valor final, se abandona el ciclo. La cantidad de veces que se repite el ciclo está dado por la siguiente expresión:

CantRepAsc = valFin – valIni + 1.

Cuando una sentencia for usa la cláusula downto, si el valor inicial es menor al valor final, la sentencia dentro del ámbito del ciclo no se ejecuta. La variable de control se inicializa con el valor inicial, luego que haya ejecutado la sentencia contenida y de haber determinado que su valor es mayor al valor final, la variable de control se decrementa en uno por cada repetición, en cambio, si el valor de la variable de control se hizo igual al valor final, se abandona el ciclo. La cantidad de veces que se repite el ciclo está dado por la siguiente expresión:

CantRepDesc = valIni – valFin + 1.

La variable de control, como así también, el valor inicial y el valor final deben ser del mismo tipo ordinal.
El valor de la variable de control no debe ser modificada por el programador, pero sí puede ser usada para otro propósito.
Un ciclo for es más óptimo que un ciclo while. No obstante el ciclo for solo podrá se utilizado cuando se sabe de antemano la cantidad de veces en que se debe de ejecutar la sentencia contenida en su ámbito de alcance.

for i:= 1 to 5 do
writeln(i);

for i:= 5 downto 1 do
writeln(i);

write(‘Ingrese un valor inicial: ‘);
readln(vi);
write(‘Ingrese un valor final: ‘);
readln(vf);
for i:= vi to vf do begin
write(‘Ingrese nombre: ‘);
readln(Nom);
writeln(‘¿Cómo estás?, ‘,Nom)
end;

La sentencia indefinida, post-condición, 1-X, hasta REPEAT UNTIL

La sentencia repeat until contiene una expresión que controla la ejecución repetida de una secuencia de sentencias dentro de la sentencia repeat until. La sintaxis es:

La sentencia debe producir un resultado de tipo boolean. Las sentencias entre los símbolos repeat y until son ejecutadas secuencialmente hasta que el resultado de la expresión se torne verdadera. Las sentencias contenidas son ejecutadas al menos una vez, debido a que la expresión es evaluada después de la ejecución de cada secuencia.
Debemos tener sumo cuidado con esta estructura cuando se haya ingresado al ciclo y poder establecer con alguna acción que, modifique el resultado de la expresión, a que en algún momento se invierta produciendo un resultado de verdadero para así poder abandonar el ciclo. El ámbito queda establecido entre los símbolos repeat until, por lo tanto no es necesario el uso de un bloque para contener varias sentencias.
Este tipo de ciclo debe ser utilizado con mesura, solo en aquellos casos en que al menos una vez deben ejecutarse las acciones contenidas en el ciclo, como p.e., en la creación de menú, validación de datos, determinar si un conjunto de datos está ordenado, entre ciertos otros casos.

Ejemplos:

Anterior: Cadenas y Registros

Siguiente: Archivos I

Arriba

Estructura de dato: Registro. Tratamiento de cadenas

2008-03-28T18:46:00.000-07:00

Abajo

CLASE 6: Estructura de dato: Registro. Tratamiento de cadenas.

Estructuras de datos

El tipo registro

El tipo registro es una estructura de datos cuyas componentes se denominan campos, los cuales entre ellos pueden ser de diferentes tipos, por lo tanto, el tipo registro es una estructura heterogénea. Podemos referirnos a todo el conjunto de datos bajo un solo nombre, esto es, la variable de tipo registro, además podemos referirnos a solo una componente, usando la siguiente notación: NombreRegistro.NombreCampo, en donde: NombreRegistro es una variable de tipo registro y NombreCampo es una de las componentes del registro. El tipo registro es una estructura de datos estática, debido a que el compilador asignará una cantidad de byte en la memoria, del tamaño de la longitud del registro, esto es la sumatoria de las longitudes de cada componente. Para definir un tipo registro se utiliza la palabra reservada record. Los campos del registro se definen dentro de su ámbito, en la sección type, por lo cual, los nombres de los campos serán de uso global, es decir, en cualquier lugar del programa, siempre nos referiremos a un campo con los mismos nombres definidos en la sección type. No así con respecto al nombre del registro que podremos dar distintos nombres según en el lugar del programa en que nos encontremos.

La asignación entre registros es válida siempre y cuando sean del mismo tipo, si regA y regB son de tipo Reg, con campos cmp1, cmp2, ..., cmpn, entonces:

regB <-- regA, es válida, y es lo mismo que hacer: regB.cmp1 <-- regA.cmp1; regB.cmp2 <-- regA.cmp2; ...; regB.cmpn <-- regA.cmpn.

Cada campo de un tipo registro podrá ser de tipo simple o bien de tipo estructurado como es el tipo registro, en estos casos, los subcampos se definen bajo otro apartado record y la notación será, NomReg.NomCmp.NomSubCmp. El caso típico es un campo fecha y los subcampos dia, mes y año.

Ejemplo: rAlumno.FecNac.aa, en donde: rAlumno es una variable de tipo RegAlu, FecNac es un campo de tipo Fecha y aa es un subcampo de tipo word. A continuación se presenta una vista gráfica de lo que podría ser un registro de una transacción o novedad de una venta de un vendedor:

Tamaño del registro = 16 bytes.

Pasaje de parámetros de tipo registro

Las variables de tipo registro pueden ser pasadas como parámetros a los módulos por valor o por referencia, tanto el registro completo como una de sus componentes simples o estructuradas. A continuación se lista un programa que muestra el uso del tipo registro:

Program EjemploRegistro;
Uses
Crt;

Type
Str20 = string[20];
Fecha = record
aa : word;
mm,
dd : byte
end;
RegAlu = record
NroLeg : longint;
ApeNom,
Domic,
Local : str20;
FecNac : Fecha;
EstCiv : char;
Trabaja : boolean;
NroDoc : longint
end;

procedure ProcAlum(var rAlu : RegAlu);
begin
writeln(rAlu.NroLeg);
writeln(‘Ing. Apellido y nombre: ‘);
readln(rAlu.ApeNom)
end;

procedure EmiteAlum(ApeN : str20);
begin
writeln(‘Apellido y Nombre: ‘,ApeN);
delay(2000)
end;

var
rAlumno,
rAlumno2 : RegAlu;

begin
rAlumno.NroLeg := 123456;
writeln(rAlumno.NroLeg);
rAlumno.FecNac.mm := 5;
rAlumno2 := rAlumno;
if rAlumno.NroLeg = 123456 then
ProcAlum(rAlumno) {Pasa todo el registro}
Else
EmiteAlum(rAlumno.ApeNom) {Pasa solo el campo ApeNom}
end.

Tratamiento de cadenas de caracteres

Una cadena es una disposición o conjunto de caracteres o símbolos tomados de un alfabeto, que en el caso de las PC, ese alfabeto es el ASCII. Una computadora debe ser capaz no solo de procesar valores numéricos, sino también de procesar datos no numéricos, es en esta categoría en donde entran las cadenas.
El tratamiento de cadenas es bastante habitual, más allá de lo que podemos creer, p.e. al escribir un programa fuente en algún lenguaje de computadora, estamos utilizando cadenas, que posteriormente al compilarlo tomará esas cadenas para analizar si son palabras válidas del lenguaje empleado. Por otro lado, un programa debe poder procesar frases o mensajes, como ser:
‘Ingrese su nombre’, ‘¿Cómo está Ud. ‘ + Nom + ‘?’, entre otras situaciones que se verán a continuación.
La cadena vacía es la cadena con longitud lógica = 0, y se la representa con dos apóstrofos contiguos, p.e.: cad1 <-- ‘’ Un objeto variable se lo declara de tipo cadena por medio de la palabra reservada string que presenta dos formatos de uso: string o string[n], en el primer caso declara una variable con una longitud física de 256 bytes lo que permite almacenar hasta 255 caracteres y en el segundo caso declara una variable con una longitud física de n + 1 bytes lo que permite almacenar hasta n caracteres. El byte adicional está reservado para alamacenar el atributo de la longitud lógica de la cadena. Para el tratamiento de cadenas existen tres operaciones básicas, a saber.

Longitud de la cadena
Concatenación de cadenas
Sub-cadenas

Longitud de la cadena

Toda cadena tiene una longitud finita de caracteres, determinar cuál es la cantidad de caracteres que posee una cadena, es conocer su longitud lógica, por lo tanto la entrada es una cadena y su salida es un valor entero, que indica la cantidad de caracteres que contiene en un momento determinado del proceso, ese valor estará entre cero y el máximo permitido en su declaración. La longitud lógica de una cadena es dinámica debido a que podrá cambiar en tiempo de ejecución. Por ejemplo, si cad1 <-- ‘super’, para determinar la longitud lógica hacemos longitud(cad1), que responderá con un valor entero de 5.

Concatenación de cadenas

Es la operación que permite unir dos o más cadenas en una sola. La nueva cadena contendrá cada una de las cadenas en el orden en que han sido unidas y su longitud lógica será igual a la suma de c/u. de las longitudes lógicas de esas cadenas. Así p.e. si cad1 <-- ‘super’ y cad2 <-- ‘man’, cad <-- concatenar(cad1,cad2) = cad1 + cad2 = ‘superman’ cuya longitud lógica es de 8. La operación de concatenación generalmente, no es conmutativa, vale decir que, cad1 + cad2 <> cad2 + cad1, en cambio, si realizamos la siguiente operación cad1 + ‘’ = ‘’ + cad1, notamos que genera la misma cadena resultado, o este otro ejemplo: ‘aa’ + ‘aaaaa’ = ‘aaaaa’ + ‘aa’, produce la misma cadena resultado.
Si el resultado de concatenar cadenas resulta una cadena con longitud mayor a lo esperado, en estos casos se trunca o corta la cadena hasta la longitud máxima aceptada, p.e. si cad está definida de tipo str7, realizar cad <-- ‘superman’, truncará en ‘superma’.

Sub-cadena

Es la operación que permite obtener una parte de una cadena, sin modificar la cadena original, en realidad se hace una copia. Así p.e., podríamos desarmar la operación de la concatenación. Para ello debemos saber que esta operación requerirá de las siguientes entradas: la cadena, el punto de inicio y la cantidad de caracteres a obtener, contando a partir del punto de inicio y obtendremos como resultado una cadena. Si queremos desarmar el contenido de cad del ejemplo anterior en sus dos partes, procederíamos de la siguiente manera:

cadUno <-- subCadena(cad,1,longitud(cad1)) y
cadDos <-- subCadena(cad,longitud(cad1) + 1,longitud(cad2))

Nota: Las palabras longitud, concatenar y subCadena han sido seleccionadas del lenguaje castellano a efectos de dar claridad a los conceptos indicados anteriormente.

Una cadena puede ser tratada de dos formas:

Completa, p.e.: cad
Individual –por sus componentes, es decir, por sus caracteres o símbolos-, siendo la notación cad[i], en donde el subíndice indica la componente i, cuyo valor debe estar en el intervalo [0; n], si i = 0 entonces hace referencia a la longitud lógica de la cadena.

Para las operaciones de cadena tratadas en forma completa cualquier cambio que se produzca en la longitud lógica es modificada automáticamente, en cambio, cuando es tratada en forma individual y se produzca una modificación en su longitud es necesario que lo realice el programador, forzando el cambio en la componente cero con el nuevo valor de longitud lógica.
Representación gráfica de una variable cadena en memoria, dado el siguiente tipo de dato y la declaración de variable de ese tipo de dato:

type
str20 = string[20];

var
cad : str20;
longitud física –estática, no cambia, definida en tiempo de compilación-

byte de longitud lógica -dinámica, su valor puede cambiar en tiempo de ejecución-.

Si bien el máximo valor es 255, en realidad no debe ser mayor al valor de la longitud física previamente definido, y no menor que cero, es decir, chr(0) <= cad[0] <= chr(n). El valor que se establezca no ha de ser numérico, sino, ha de ser de tipo caracter. A continuación se presentan distintos valores que contendrá la variable cad definida de tipo cadena de 20 -string[20]-.

Los 3 caracteres de signo de pregunta simbolizan el caracter que se encuentre en esas componentes.

Una cadena puede ser comparada con otra, utilizando los distintos operadores de relación (>, <, =, <>, >=, <=). Para que una cadena sea igual a otra se deben comparar todos sus caracteres correspondientes, esta tarea la realiza directamente el lenguaje Turbo Pascal. Al igual que los números reales una cadena es no ordinal. Pero, ¿será ordinal si la tratamos individualmente?. Si asignamos a una variable destino una cantidad de símbolos mayor al que puede contener, los caracteres que sobrepasen el límite superior se truncarán, es decir, se pierden todos aquellos caracteres que sobrepasen la cantidad máxima soportada por la variable destino, esto vale cuando la tratamos en forma completa, no así cuando la tratamos en forma individual y si sobrepasamos el límite superior, entonces en estos casos estaremos invadiendo una posición de memoria desconocida, produciendo efectos catastróficos, los cuales podrían llegar a ser, que determinadas variables hayan modificado su valor, aparecer caracteres imprevistos en la pantalla, colgarse el programa, entre otros.

Funciones y Procedimientos para el tratamiento de cadenas de caracteres

Chr(x): Retorna el caracter correspondiente al código ASCII x enviado.

Ej. car <--char(65), asigna el caracter ‘A’.

Ord(car): Retorna el código ASCII correspondiente al caracter enviado.

Ej. x <-- ord(‘A’), asigna el valor 65. Es la función inversa de chr(x). Otra forma de obtener la longitud lógica de una cadena es aplicando esta función de la siguiente manera, x <-- ord(cad[0]). Asigna a x un valor entre 0 y 255, el que se encuentre en esa posición.

UpCase(car): Retorna el carácter convertido a mayúscula, si car es alfabético minúscula, sino el mismo caracter. car <-- UpCase(‘a’), asigna ‘A’. car <-- UpCase(‘B’), asigna ‘B’. car <-- upcase(‘+’), asigna ‘+’.

Length(cad): Retorna la longitud lógica de la cadena cad enviada. El valor retornado estará entre 0 y 255 como máximo. Length(cad) = ord(cad[0].

Pos(subCad,cad): Retorna cero si la subcadena subCad no se encontró en la cadena cad, sino retorna un valor > 0 indicando que en esa posición se encontro a partir de ahí la subcadena en la cadena.
Ej.: x <--pos(‘ma’,’mi mama me ama’), asigna 4 a x. x <-- (‘abc’,’xyzabrscbaqrbcmds’), asigna cero a x.

Copy(cad,i,x): Retorna una cadena armada a partir de la cadena cad desde la posición i, con x caracteres contando a partir de la posición i.
Ej.: cad1 ß copy(‘superman’,3,3), asigna ‘per’ a cad1.

Concat(cad1,cad2,...): Retorna una cadena, resultado de unir cada una de las cadenas enviadas en el orden dado. Otra forma de lograr el mismo propósito es utilizando el operador de concatenación ‘+’.
Ej.: cad <-- concat(‘super’,’man’). cad <-- ‘super’ + ‘man’.

SizeOf(objeto): Retorna un valor entero que indica el tamaño físico del objeto enviado que puede ser un tipo o una variable.
Ej.: x <-- sizeof(integer), asigna dos a x. x <-- sizeof(real), asigna 6 a x. x <-- sizeof(cad), asigna 21 a x si cad se definió como string[20]. x <-- sizeof(str20), asigna 21 a x si str20 se definió como string[20].

Succ(exprOrd): Retorna el sucesor de exprOrd que debe ser de tipo ordinal. Salvo el último elemento que no tiene sucesor, en tal caso sería error averiguarlo, todos los demás elementos tienen sucesor. El primer elemento de una lista tiene valor ordinal cero, salvo con los enteros negativos que tendrán valores ordinales negativos.
Ej.: x <-- succ(4), asigna 5 a x. X <-- succ(succ(10)), asigna 12 a x.

Pred(exprOrd): Retorna el predecesor de exprOrd que debe ser de tipo ordinal. Salvo el primer elemento que no tiene predecesor, en tal caso sería error averiguarlo, todos los demás elementos tienen predecesor. El primer elemento de una lista tiene valor ordinal cero, salvo con los enteros negativos que tendrán valores ordinales negativos.
Ej.: x <-- pred(4), asigna 3 a x. X <-- pred(pred(9)), asigna 7 a x. Car <-- pred(‘C’), asigna ‘B’ a car.

Delete(cad,i,x): Procedimiento que elimina de la cadena cad los caracteres desde la posición i una cantidad x de caracteres contando a partir de la posición i, actualiza la longitud lógica de cad.
Ej.: cad <-- ‘superman’. delete(cad,3,3), cad contiene suman y su longitud lógica es 5, se eliminaron los caracteres ‘p’, ‘e’ y ‘r’.

Insert(subCad,cad,i): Procedimiento que inserta la subcadena subCad en la cadena cad a partir de la posición i, actualiza la longitud lógica de cad.
Ej.: insert(‘per’,cad,3), ahora cad volverá a contener ‘superman’ y su longitud lógica volverá a ser de 8.

Str(x,cad): Procedimiento que convierte un número x a una cadena, el resultado queda en cad.
Ej.: str(725,cad), asigna a cad la cadena ‘725’ y su longitud lógica pasa a ser de 3. str(3825.425:0:2,cad), asigna a cad la cadena ‘3825.425’, en cambio str(3825.425,cad), asigna a cad la cadena ‘3.8254250’ que no es lo que se pretendería hacer.

Val(cad,x,cod): Procedimiento que convierte una cadena cad a un valor numérico, guardando el resultado en x, si la conversión tuvo éxito, en ese caso a cod se asigna cero. Puede ocurrir que no tenga éxito la conversión, en este otro caso se detiene la conversión, en x se asigna cero y en cod se asigna un valor > 0, indicando que en esa posición ocurrió un error, debido a que el caracter encontrado no pudo ser convertido a un dígito o signo + o – o el punto decimal.
Ej.: cad <-- ‘5318’. Val(cad,x,cod), asigna el valor 5318 a x, y a cod el valor 0, en cambio si cad <-- ‘3a92’. Val(cad,x,cod), asigna 0 a x, y a cod el valor 2, ya que, en la posición 2 se encontró un caracter que no pudo ser convertido. Funciones de tratamiento de cadenas creadas por el usuario

Al igual que con las funciones numéricas en que el usuario puede crear sus propias funciones, sucede lo mismo con las cadenas de caracteres. A continuación se presentan algunas funciones de cadenas.

Función que retorna el carácter enviado convertido a minúscula si es alfabético mayúscula, sino el mismo carácter.

Función que retorna invertida una palabra enviada:

Una posible aplicación de la función InvPal sería comprobar si una palabra es palíndromo, es decir, capicúa, p.e.: capicua <-- pal = InvPal(pal), habiendo declarado a capicua de tipo boolean, contendrá false si la palabra pal no es capicúa, sino será true. Pero, ¿podría ocurrir que al invertir una cadena, palabra de un lenguaje, la nueva cadena creada sea una palabra que pertenezca a ese mismo lenguaje?. p.e.: palreves <-- invpal(‘lámina’), obviando el tilde, asigna ‘animal’, o esta otra, palreves <-- invpal(‘roma’), asigna ‘amor’. Función que dado un caracter car y un número n, retorna el carácter car repetido n veces, es decir, retorna una cadena de longitud n, en donde cada componente es el caracter car.

También podría realizarse la siguiente función que retorna espacios en blanco:

Una posible aplicación de la función space o replicate podría ser rellenar una variable de cadena con espacios a derecha, a partir de la longitud lógica + 1 hasta el final, p.e.: cad <-- ‘Algoritmos’. cad <-- cad + space(pred(sizeof(cad)) – length(cad)).

Anterior: Procedimientos

Siguiente: Lenguaje Turbo Pascal

Arriba

Módulos. Procedimientos

2008-03-27T17:29:00.000-07:00

Abajo

CLASE 5: Módulos. Procedimientos.

Procedimientos

Un procedimiento es un módulo que presenta las siguientes partes:

Una cabecera
Un cuerpo

La cabecera presenta las siguientes partes:

El nombre del procedimiento
Una lista de parámetros, que podría estar vacía

El cuerpo del procedimiento es un bloque, dentro del cual se escriben las sentencias. Un procedimiento lo podemos ver como una caja negra –no nos interesa saber su interior- o como una caja transparente –si nos interesa saber su interior-. Para que un procedimiento pueda ser ejecutado, se deberá llamarlo o invocarlo. Los parámetros formales –aquellos que se definen en la cabecera de la función, pueden ser pasados por valor, en estos casos, se trabaja con una copia del valor pasado desde la invocación, cualquier modificación que se realice en los parámetros formales, no repercute en los parámetros actuales –los indicados en el momento de la invocación- o pueden ser pasados por referencia, también llamados por dirección o como los denomina el Lenguaje Pascal parámetros variables, en estos casos, lo que se envía no es el valor en sí, sino la dirección del objeto, por lo tanto, los parámetros actuales enviados por referencia solo pueden ser objetos que sean variables. Dentro del módulo los parámetros formales enviados por referencia contienen la dirección del parámetro actual correspondiente, cualquier valor asignado al parámetro formal, en realidad está modificando al parámetro actual. Un procedimiento se lo invoca en forma directa, debido a que es una sentencia en sí mismo, como se vió bajo el apartado sentencias simples.
Un procedimiento puede necesitar trabajar con variables internas a su ámbito, en estos casos esas variables definidas dentro del procedimiento son denominadas variables locales. Fuera del procedimiento en que han sido definidas no existen, salvo en los casos en que el procedimiento invoque a un módulo definido dentro de su ámbito, -módulos anidados- allí serán reconocidas. La comunicación entre el módulo que invocó al procedimiento y el procedimiento invocado se establece por medio de los parámetros.

Estructura de un procedimiento: -definición-

Llamada o invocación a un procedimiento

Ejemplo:

NomProc(lst_par-Actuales)

Pasaje de parámetros:

Los parámetros a un procedimiento pueden ser pasados por:

Valor o contenido
Referencia o dirección.

El pasaje de parámetros por valor o contenido, significa que lo que se está pasando es el valor del objeto enviado que puede ser un valor constante, el contenido de una variable o el resultado de una expresión; el valor recibido por el parámetro formal realiza una copia de ese valor en un área de almacenamiento temporal el Stack o Pila, eliminándose en el momento de abandonar el módulo; cualquier cambio que se produzca sobre ese objeto, el cambio se lo está realizando en la copia, por lo tanto el parámetro actual jamás se verá afectado de esas modificaciones.
En cambio el pasaje de parámetros por referencia o dirección, también llamado parámetro variable, significa que lo que se está pasando es la dirección del objeto enviado, que sólo podrá ser una variable. El parámetro formal correspondiente recibe la dirección de ese objeto y, cualquier valor que se le asigne, en realidad se lo está asignando al parámetro actual correspondiente, por lo tanto, no se trabaja con una copia sino con el propio objeto. La forma de establecer si un parámetro formal debe ser por referencia es indicando antes de la lista de parámetros la palabra reservada var. Todos aquellos parámetros que deban ser pasados por valor, entonces no se debe anteponer esa palabra.

¿Cuándo pasar parámetros por valor o por referencia?

Usamos parámetros por valor cuando conocemos previamente el valor de esos parámetros y deseamos pasarlo al módulo para que realice algún tratamiento con esos datos; aún si se cambiara su valor dentro del módulo invocado, no afecta al parámetro actual. En cambio usamos parámetros por referencia cuando el dato se va a conocer en el módulo o sabiendo su valor debemos modificarlo y se requiere saberlo en el ámbito en que fue invocado Los parámetros actuales cuando son pasados por valor pueden ser valores constantes, variables o expresiones. En cambio los parámetros actuales cuando son pasados por referencia solo pueden ser objetos variables.

Ejemplos:
Bloque principal

1: a <-- 9

2: Proc1(a,3,sqrt(a)+2.4,b)

3: Emitir(a,b)

4: Proc1(w,x:integer; y:real; var z:longint)

5: h <-- x + y

6: w <-- w - 2

7: x <-- x + w

8: z <-- h * x + 3

9: Emitir(h,x,z)

2: Parámetros actuales: los 3 primeros son pasados por valor, por lo tanto pueden ser; variables, constantes, o expresiones, en cambio el 4to. parámetro es pasado por referencia, solo puede ser un objeto variable.

4: w, x, y son parámetros formales pasados por valor, mientras que z es un parámetro formal pasado por referencia.

5: h es una variable local ¿de qué tipo, entero o real?

Prueba de escritorio

Dirección Llamada

d:231 d:1528 valores enviados valores recibidos ...var.loc..... Emite

...a......b......................... w... x...y...... z..... ..h

...9.. 87. 9, 3, 5.4, d:1528...9... 3..5.4. d:1528... 8.4 ...8.4 10 87

..................................7...10............................ 9... 87

Procedimientos definidos por el usuario:

Como ya se vió en párrafos previos, un procedimiento está formado por una cabecera que contiene el nombre del procedimiento, eventualmente una lista de parámetros y el cuerpo en donde se indican las acciones a realizar. Siguiendo estos pasos el usuario podrá definir sus propios procedimientos.

Variables globales y variables locales:

Las variables globales se definen en tiempo de compilación, reservando el espacio en el segmento de datos -un bloque de memoria cuyo tamaño máximo es de 64K bytes- la cantidad de bytes que corresponda al tipo de esa variable y ese espacio estará reservado hasta la finalización del programa, por lo tanto, estas variables son estáticas.

Las variables locales se definen en tiempo de compilación dentro del ámbito de un módulo –procedimientos o funciones-, pero no se reserva espacio hasta el momento en que el módulo es invocado, en ese instante se crean esas variables y al abandonar el módulo son eliminadas de esa región de memoria temporal. Esa región de memoria es el segmento del Stack o Pila, cuyo tamaño máximo es de 64K bytes. El valor por defecto reservado por el lenguaje Turbo Pascal es de 16384 bytes, pero puede ser ampliado o disminuido por medio de la directiva al compilador de ámbito global escribiéndola dentro del código del programa {$M Stack Size, heapmin,heapmax} o por medio de los comandos de menú del IDE Option Compiler Memory Sizes. Stack Size debe ser un valor entre 1024 y 65536 bytes y que establece el tamaño del segmento del stack, heapmin debe ser un valor en el intervalo 0 655360 bytes y heapmax debe ser un valor en el intervalo heapmin y 655360 bytes y que establece el tamaño del área del heap o montículo, región de memoria en donde se crean o eliminan las variables dinámicas en tiempo de ejecución.

Variables dinámicas:

Las variables dinámicas se definen en tiempo de ejecución por medio del procedimiento new y son eliminadas por medio del procedimiento dispose. La región de memoria en donde son creadas/eliminadas es en el heap o montículo. Debido a que la cantidad de variables globales que podemos contar en un programa no puede superar el límite de 64Kbytes, bajo estas condiciones estamos en la obligación de utilizar el heap a efectos de poder incrementar el espacio para poder contar con más variables.

Código del programa:

El código del programa que incluye al bloque principal y todos los módulos definidos en el programa se ubican en el segmento de código cuyo tamaño máximo es de 64 Kbyte. Si se necesita un mayor tamaño estamos obligados a crear unidades, cada una de las cuales no puede superar el límite de 64 Kbytes. Estas unidades estarán referenciadas en el programa en la sección uses que incorporará el código ya compilado de la unidad a nuestro programa, logrando en consecuencia romper la barrera de los 64 Kbytes para el código del programa.

De esta manera hemos visto que la memoria total estará dividida en cuatro regiones:

Segmento de Datos –Máximo 64 Kbytes, si se requiere un mayor tamaño utilizar variables dinámicas, esto es en el área del heap-.

Segmento de Código –Máximo 64 Kbytes, para ampliar el tamaño utilizar unidades c/u. con un máximo de 64 Kbytes-.

Segmento del Stack o Pila –Máximo 64 Kbytes-.

Área del heap o Montículo – resto de la memoria disponible-

Memoria convencional bajo el D.O.S. de 640Kbytes.

El siguiente cuadro muestra los objetos variables globales y los objetos variables locales o parámetros formales en el segmento del Stack –Pila- en el instante de la invocación o llamada al módulo y de su retorno. Observar sus contenidos según los casos. Si el número está precedido por d: entonces indica que es una dirección de memoria. Si el parámetro formal contiene un número precedido por d: entonces en esos casos, el parámetro ha sido pasado por referencia.

* Los parámetros o variables locales sólo existen cuando se invoca al módulo.
--- Indica que las variables globales o locales o los parámetros correspondientes de la columna no existen.

Anterior: Funciones

Siguiente: Cadenas y Registros.

Arriba

Módulos. Funciones: Primitivas y definidas por el usuario.

2008-03-26T20:50:00.000-07:00

Abajo

CLASE 4: Módulos. Funciones: Primitivas y definidas por el usuario

Módulos: Funciones.

En la programación modular, los programas se dividen en módulos. Un módulo es una unidad lógica de código e independiente de otros módulos, en el cual es posible analizar, codificar y probar por separado. Cada programa tiene un módulo o bloque principal que actúa como coordinador o controlador, el cual deriva el control a otros módulos. A su vez un módulo –sub-módulo- puede ceder el control temporalmente a otro módulo, el cual una vez finalizado deberá devolver el control al módulo que lo invocó. Ya que, los módulos son independientes unos de otros, una consecuencia de esto sería poder dividir el trabajo a distintos programadores a efectos de acelerar los tiempos. Además a un módulo se lo podrá modificar, sin alterar a otros módulos. Existen dos formatos de módulos, a saber:

Funciones
Procedimientos

Funciones:

Una función es un módulo que presenta las siguientes partes:

Una cabecera

Un cuerpo

La cabecera presenta las siguientes partes:

El nombre de la función

Una lista de parámetros, que podría estar vacía

El tipo de valor -simple- que devolverá la función

El cuerpo de la función es un bloque, dentro del cual se escriben las sentencias. Deberá existir alguna sentencia que asigne al nombre de la función el resultado de una expresión que debe ser de igual tipo que el valor devuelto por la función. Al finalizar la función, el último valor asignado, será el valor que retorne. Una función la podemos ver como una caja negra –no nos interesa saber su interior- o como una caja transparente –si nos interesa saber su interior-. Para que una función pueda ser ejecutada, se deberá llamarla o invocarla. Generalmente los parámetros formales –aquellos que se definen en la cabecera de la función, son pasados por valor, en estos casos, se trabaja con una copia del valor pasado desde la invocación, cualquier modificación que se realice en los parámetros formales, no altera a los parámetros actuales –los indicados en el momento de la invocación-. Una función se la invoca en forma indirecta, es decir, como perteneciente a una sentencia, como p.e., la asignación interna, o como formando parte de una condición, etc..
Una función puede necesitar trabajar con variables internas a su ámbito, en estos casos esas variables definidas dentro de la función son denominadas variables locales. Fuera de la función en que han sido definidas no existen, salvo en los caos en que la función invoque a un módulo definido dentro de su ámbito, allí serán reconocidas. La comunicación entre el módulo que invocó a la función y la función invocada se establece por medio de los parámetros. Si bien una función puede devolver valores por medio de sus parámetros, por el momento no se emplearán.

Estructura de una función: -definición

Llamada o invocación a una función

Ejemplo:

Var <-- NomFunc(lst_par_actuales)

Observación: Los parámetros en la invocación también suelen llamarse argumentos. En estos casos los parámetros en la cabecera de los módulos se los puede indicar como parámetros a secas.

Funciones primitivas numéricas:

A continuación se verán las funciones numéricas predefinidas por el lenguaje Pascal, para nosotros serán cajas negras, debido a que solo sabremos el nombre de la función, los parámetros a pasar, de qué tipo han de ser c/u. de ellos y en que orden deben aparecer el tipo de valor retornado por la función y que tarea realiza la función, pero no sabremos nada acerca de cómo lo realiza.

Abs(x):tipo_x; Retorna el valor absoluto de x, en donde x es cualquier valor de tipo numérico. El valor absoluto de x es x, si x >= 0 o es, –x si x menor a 0, por lo tanto el valor retornado es siempre positivo.

Sqrt(x:real):real; Retorna la raíz cuadrada de x, en donde, x es >= 0, el tipo de resultado es real.

Sqr(x):tipo_x; Retorna el cuadrado de x, es decir, x * x. El tipo de resultado es del mismo tipo que el parámetro x.

Sin(x:real):real; Retorna el seno de x. X expresa un ángulo en radianes. Para convertir grados a radianes, si x está expresado en grados, utilizar:

radianes <-- x * PI / 180

Cos(x:real):real; Retorna el coseno de x. X expresa un ángulo en radianes. Para convertir grados a radianes, si x está expresado en grados, utilizar:

radianes <-- x * PI / 180

ArcTan(x:real):real; Retorna el arco tangente o tg-1 de x. El resultado es la medida del ángulo expresado en radianes. Para convertir de radianes a grados, utilizar:

grados <-- arctan(x) * 180 / PI

Ln(x:real):real; Retorna el logaritmo natural de x, con x > 0. Para obtener el logaritmo de otra base, utilizar:

log10 <-- ln(x) / ln(10);

log4 <-- ln(x) / ln(4)

es decir, se divide el ln(x) sobre el ln de la base a pasar.

Exp(x:real):real; Retorna el exponencial o antilogaritmo o ln-1 de x. Exp(x) = e**x. Exp(1) = e. Para convertir la base e a otra base, utilizar: expo ß exp(x * ln(b)), es decir, multiplicar el valor de x por el ln de la base b, a pasar, y a este resultado aplicar la función exponencial.

Int(x:real):real; Retorna la parte entera de x, es decir, x redondeado hacia cero; el resultado es de tipo real, con la parte decimal cero.

Trunc(x:real):longint; Retorna la parte entera de x, es decir, x redondeado hacia cero, pero a diferencia de int, el tipo de resultado es de tipo longint. Ocurrirá un error si el resultado no está dentro del intervalo de un longint.

Round(x:real):longint; Retorna la parte entera de x redondeado al entero más cercano, el tipo de resultado es de tipo longint. Ocurrirá un error si el resultado no está dentro del intervalo de un longint.
round(x) = trunc(x+0.5) si x >= 0 y
round(x) = trunc(x-0.5) si x menor a 0

round (3.29 = 3

round(5.7) = 6

round(-451.3) = -451

round(-2.7) = -3

Frac(x:real):real; Retorna la parte decimal o fraccionaria de x, esto es:

frac(x) = x – int(x). Frac(23.79) = 0.79. frac(-12.43) = -0.43.

Odd(x:longint):boolean; Retorna true si x es impar o false si x es par.

Pi:real; Retorna el número irracional π = 3.1415926535897932385

Random:real;

Random(x:longint):longint: Retorna un número al azar.
Random sin argumento genera un número al azar –en realidad pseudoaleatorio- en el intervalo semicerrado [0; 1).
Random con argumento genera un número al azar en el intervalo [0; x – 1].
Random(6) + 1, generará un valor en el intervalo [1; 6]
Random(b – a + 1) + a, con a <= b, generará un valor en el intervalo [a; b]

Randomize –Procedimiento-: Los valores generados por random son pseudoaleatorios, debido a que, en distintas ejecuciones se generarán las mismas secuencias de valores. Por esa razón si queremos generar valores aleatorios para que en distintas ejecuciones se generen distintas secuencias de valores, debemos utilizar randomize al comienzo del programa; esto prepara al algoritmo de generación de números aleatorios para que la semilla, -así se denomina al punto inicial para la generación de los valores aleatorios- quede preparada con un valor de arranque, que será distinto en cada nueva ejecución del programa.

Funciones definidas por el usuario

Como se vió en párrafos previos, una función está formada por una cabecera que contiene el nombre de la función, eventualmente una lista de parámetros y el tipo de valor devuelto y el cuerpo en donde se indican las acciones a realizar, en donde, al menos una de estas acciones se debe asignar al nombre de la función el resultado de una expresión del mismo tipo definido en la cabecera. Siguiendo estos pasos el usuario podrá definir sus propias funciones. A continuación se desarrollan algunas de estas funciones, de tratamiento numérico.

Aplicación:

Dados dos valores enteros a y b, encontrar la fracción irreducible de a / b.

Anterior: Sentencias

Siguiente: Procedimientos

Arriba

Sentencias: Simples y Estructuradas

2008-03-26T12:11:00.000-07:00

Abajo

CLASE 3: Sentencias: Simples y Estructuradas.

Sentencias:

Las sentencias son acciones algorítmicas que pueden ser ejecutadas. Hay dos tipos principales de sentencias:

Sentencias simples

Sentencias estructuradas

Sentencias simples:

Una sentencia simple es una sentencia que no contiene a ninguna otra sentencia.

Sentencia de asignación:

Asignación interna: Es utilizada para almacenar valores en variables.

Referencia a variable representa una variable e Identificador de función el nombre de una función y expresión representa una constante o una variable o una expresión propiamente dicha. La flecha representa la asignación.
Se evalúa la expresión y el resultado es asignado a la variable o al identificador de la función ubicada en el miembro izquierdo de la asignación. Debe existir una correspondencia de tipos entre, el resultado de la expresión, y el tipo definido para la variable, caso contrario se generará un error de incompatibilidad de tipos. La expresión podrá estar formada por, una constante, una variable o una expresión propiamente dicha, en cambio en el miembro izquierdo de la asignación solo podrá especificarse un objeto variable o el nombre de la función dentro de su propio bloque. Cualquier valor previo que tuviera la variable en la parte izquierda de la asignación es reemplazado por el nuevo valor asignado, por lo tanto, la asignación es destructiva. Cualquier variable situada en la parte derecha de la asignación deberá tener un valor previamente asignado, debido a que deberá leerse su contenido.

Ejemplos:

a <-- 4; a toma el valor constante entero 4

b <-- a; b toma el valor de a

b <-- b + 3 b toma el valor de b + 3

ApeNom <-- ‘Perez Juan’ ApeNom toma el valor constante de cadena

x <-- sqrt(25) ¿de qué tipo definiría a x?

Car <-- ‘h’

Cociente <-- b div a

Resto <-- b mod a

existe <-- true existe y negativo son de tipo boolean.

Negativo <-- x MENOR 0

Sentencias de Procedimientos:

Una sentencia de procedimiento establece la activación del procedimiento indicado. Si la declaración del procedimiento correspondiente contiene una lista de parámetros formales, -los parámetros listados en la definición- entonces la sentencia de procedimiento debe tener una lista de parámetros actuales, -en la llamada a la sentencia-. Los parámetros actuales son pasados a los parámetros formales como parte de la llamada o invocación.

Asignación externa de entrada:

Var deberá ser una variable. El valor asignado a la variable indicada en el bloque se lee desde un dispositivo periférico, siendo el teclado el dispositivo por defecto. El dato a conocer puede ser leído desde otro dispositivo como ser un archivo en disco. En cualquier caso la ejecución del proceso entra en espera, a efecto de que pueda leerse el dato solicitado. Si la entrada es ingresada por teclado, luego de tipear el valor se deberá presionar la tecla ENTER tras lo cual se reanuda la ejecución del proceso con la próxima acción que continúa en la secuencia. Deberá existir coincidencia de tipos entre el valor leído y el tipo de la variable. Una cadena de caracteres o un carácter deberá ser ingresado sin apóstrofos. Si el ingreso es desde un archivo también existe una espera, solo que en estos casos dicha espera es menor, ya que el ingreso del dato se realiza electrónicamente y no requiere de la intervención manual del usuario. Los puntos suspensivos indican que se podrá escribir más de una variable separadas por comas. La ventaja de la asignación externa de entrada con respecto a la asignación interna, es que en distintas ejecuciones del programa podemos ingresar diferentes valores sin modificar el código.
Asignación externa de salida:

Exp puede ser una constante, una variable o bien una expresión propiamente dicha. El resultado de la expresión es enviado al dispositivo periférico que corresponda, por defecto la pantalla, otros dispositivos pueden ser archivos en disco, la impresora. Al igual que la asignación externa de entrada, también existe una espera, a efectos de dar tiempo a que se envíen los resultados, una vez que esto suceda, la ejecución del proceso continúa su marcha con la próxima acción de la secuencia. Se podrá enviar un valor constante, el contenido de una variable o bien el resultado de una expresión propiamente dicha. Los diferentes objetos van separados por comas. Si la salida va destinada a la pantalla, impresora o disco; el término empleado es emitir-mostrar, listar y grabar respectivamente.

Ejemplos de sentencias de procedimientos:

Llamada o invocación para que se ejecute

Imprimir
InterCambio(a, b)
Encontrar(Lista, Nombre, posic)

Estructuras de control de programas

Sentencias estructuradas
Las sentencias estructuradas son construcciones compuestas por otras sentencias que son ejecutadas en secuencia, condicionalmente o repetidamente.

Sentencia compuesta o de concatenación

La sentencia compuesta está constituida por un bloque, el cual es considerado como una unidad lógica de información. Esta estructura de control de programa es muy importante conocer, ya que, guarda una relación muy extrecha con las otras dos estructuras de control de programa: la selección y la repetición, debido a que el alcance de acción es de una sola setnencia, por lo cual si queremos que la lógica de un proceso incluya más de una acción dentro del alcance de la selección y/o la repetición, debemos encerrar estas acciones dentro de un bloque, es decir, la sentencia compuesta o de concatenación.

Sentencia condicional

Selección simple:

Luego de ejecutar la acción alfa, en el punto de entrada se evalúa la condición, si el resultado es verdadero, se ejecuta la acción indicada por la acción beta –rama izquierda- caso contrario, se ejecuta la acción gamma –rama derecha- en ambos casos luego en el punto de salida se ejecuta la acción delta. Si la acción gamma no está presente –se representa por una línea en diagonal- en ese caso, nada se ejecuta, nos encontramos con una selección simple incompleta, de lo contrario sera una selección simple completa.
Las acciones alfa y delta siempre se ejecutan por encontrarse fuera del alcance o ámbito de la estructura de control de programa. En cambio la acción beta solo se realizará si la condición resulta verdadera y gamma no se realizará. Por otro lado, solo se ejecutará la acción gamma si la condición resulta falsa en cuyo caso la acción beta no se realizará.

Ejemplo 1: Asumiendo que condición resulta verdadera entonces las acciones que se ejecutan son: alfa, beta y delta.

Ejemplo 2: Asumiendo que condición resulta falsa y gamma es vacía, entonces las acciones que se ejecutan son: alfa y delta.

Ejemplo 3: Asumiendo que condición resulta falsa y gamma no es vacía, entonces las acciones que se ejecutan son: alfa, gamma y delta.

Con este tipo de estructura es posible realizar cualquier grado de complejidad de alternativas o decisiones o selecciones.
Es válido armar alternativas encadenadas o alternativas dentro de alternativas –en estos casos se denominan selecciones anidadas-.

Ejemplo de selecciones anidadas y en secuencia:

Selección múltiple:

Luego de ejecutar la acción alfa en el punto de entrada se evalúa la expresión ordinal, el resultado es comparado por igual con cada uno de los valores constantes de izquierda a derecha, en cuanto ocurra la primera igualdad se ingresa por la rama correspondiente y se ejecuta la acción beta indicada por esa rama, en caso contrario, se ejecuta la acción gamma, en caso de estar presente. En todos los casos en el punto de salida se ejecuta la acción delta.
Esta estructura de control de programa está limitada a ciertos procesos, debido a que la expresión debe ser de tipo ordinal. Los valores constantes también deben ser del mismo tipo ordinal que el de la expresión.
Cada una de las Ctei puede adoptar la siguiente forma: Cte1,1,Cte1,2,Cte1,3..Cte1,4,...

Repetición pre-condición

Repetición 0-X, Mientras o Indefinido:

Luego de ejecutarse la acción alfa en el punto de entrada se evalúa la condición, si el resultado es verdadero se ingresa al ciclo y ejecuta la acción beta, luego en el punto de salida se vuelve otra vez a la cabecera para ser evaluada nuevamente la condición, en caso que resulte falsa se abandona el ciclo por el punto de salida y a continuación se ejecuta la acción delta. Puede ocurrir que en el punto de entrada la condición resulte falsa, en ese caso la acción beta jamás será ejecutada. Hay que asegurar que si se ingresa al ciclo lograr que la condición en algún momento se haga falsa, para poder abandonar la estructura cíclica. La condición podrá estar controlada por un contador, un sumador, un valor centinela, un valor boolean, una situación de fin de archivo, una condición compuesta, entre otras. Con este tipo de ciclo se pueden llevar a cabo cualquier complejidad de situaciones que requieran el uso de una estructura cíclica. Es válido construir estructuras cíclicas anidadas o en secuencia.
Repetición Exacta o Para ascendente:

Luego de ejecutarse la acción alfa, en el punto de entrada, se realizan por la propia estructura de control, las siguientes acciones; si el resultado de la expr.ini. es menor o igual al resultado de la expr.fin. entonces el resultado de la expr.ini. es asignado a var –variable de control, es una variable contadora del ciclo- y se ingresa al ciclo, ejecutándose la acción beta. En el punto de salida, se llevan a cabo las siguientes acciones, -también propias de la estructura de control- si la variable de control var es menor al resultado de la expr.fin., entonces var toma el valor ordinal sucesor del que contiene y se vuelve a ejecutar la acción beta. Se abandona el ciclo una vez que var haya alcanzado al valor de la expr.fin. ejecutándose la acción delta. Por otro lado, estando en el punto de entrada si el valor de la expr.ini. fuera mayor al valor de la expr.fin. directamente se busca el punto de salida y se ejecuta la acción delta. El tipo de var, la expr.ini. y la expr.fin. deben ser todas del mismo tipo ordinal.
Este tipo de ciclo es de uso limitado, ya que solo sirve para valores de tipo ordinal. De todas maneras en ciertos casos es más aconsejable su uso cuando se conozca de antemano, la cantidad de veces que deba ser ejecutado. Una de las ventajas es que no se debe llevar la cuenta del contador, ya que lo gestiona la propia estructura de control.
La cantidad de veces que se repetirán las acciones dentro del ciclo, queda establecida de la siguiente manera:

Cant.Rep.Desc. <-- valor expr.ini. – valor expr.fin. + 1

Repetición Exacta o Para descendente:

Luego de ejecutarse la acción alfa, en el punto de entrada, se realizan por la propia estructura de control, las siguientes acciones; si el resultado de la expr.ini. es mayor o igual al resultado de la expr.fin. entonces el resultado de la expr.ini. es asignado a var –variable de control, es una variable contadora del ciclo- y se ingresa al ciclo, ejecutándose la acción beta. En el punto de salida, se llevan a cabo las siguientes acciones, -también propias de la estructura de control- si la variable de control var es mayor al resultado de la expr.fin., entonces var toma el valor ordinal predecesor del que contiene y se vuelve a ejecutar la acción beta. Se abandona el ciclo una vez que var haya alcanzado al valor de la expr.fin. ejecutándose la acción delta. Por otro lado, estando en el punto de entrada si el valor de la expr.ini. fuera menor al valor de la expr.fin. directamente se busca el punto de salida y se ejecuta la acción delta. El tipo de var, la expr.ini. y la expr.fin. deben ser todas del mismo tipo ordinal.
Este tipo de ciclo es de uso limitado, ya que solo sirve para valores de tipo ordinal. De todas maneras en ciertos casos es más aconsejable su uso cuando se conozca de antemano, la cantidad de veces que deba ser ejecutado. Una de las ventajas es que no se debe llevar la cuenta del contador, ya que lo gestiona la propia estructura de control.
La cantidad de veces que se repetirán las acciones dentro del ciclo, queda establecida de la siguiente manera:

Cant.Rep.Desc. <-- valor expr.ini. – valor expr.fin. + 1

Repetición post-condición:

Repetición 1-X o Hasta:

Luego de ejecutar la acción alfa, en el punto de entrada se ingresa a la estructura cíclica, ejecutándose la acción beta, luego en el pié de la estructura se evalúa la condición, si el resultado es falso, permanece en el ciclo, volviéndose a ejecutar la acción beta, hasta que la condición cambie de estado, es decir, cuando su resultado se haga verdadero, abandona el ciclo y en el punto de salida se ejecute la acción delta. La condición podrá ser lo más compleja que se desee. Este tipo de ciclo requiere un uso específico ya que la acción beta se podrá ejecutar al menos una vez, por eso a este ciclo también se lo denomina ciclo 1-x. Existen casos puntuales para su uso, a saber, creación de menú de opciones, validación de datos, ordenamiento de burbuja optimizado, y otros casos especiales.

Luego de haber conocido cada una de la estructuras de control de programa, es de esperar que el alumno utilice la mejor herramienta para llevar a cabo el algoritmo. No siempre la forma en que el alumno ve la situación será la mejor de ellas, un cierto grado de experiencia va a afianzar más el criterio a adoptar en cada situación que se presente.
Cuando determinamos que hay que utilizar una estructura repetitiva, luego nos planteamos cuál de ellas es la más adecuada, hay casos por ejemplo que aparentemente en un primer momento creemos que es un ciclo exacto, entonces no dudamos y utilizamos el ciclo exacto, pero luego vemos que en realidad no estamos obligados a alcanzar la cantidad total de repeticiones debido a que existe una segunda condición que nos hará abandonar el ciclo antes de haber alcanzo el final máximo, ahora nos damos cuenta que el ciclo apropiado es un ciclo indefinido con dos condiciones, mientras no hayamos encontrado un valor que estamos buscando y mientras no hayamos alcanzado la cantidad de repeticiones máximas, si el valor no aparece.
En toda estructura de control condicional y repetitiva existen distintos momentos, un momento previo al punto de entrada, un momento durante entre los puntos de entrada y salida y un momento después del punto de salida. Si la estructura es repetitiva indefinida el momento previo es el de preparar acciones previas, inicializar variables, conocer primer dato; el momento durante es el de procesar los datos y conocer próximo dato y el momento después es el de terminar, emitir, cálculos a totales mayores, promedios, porcentajes, grabar, etc.. En cambio en una estructura repetitiva exacta, en el momento previo inicializamos variables pero no conocemos primer dato, sino que en el momento durante, primero conocemos dato y luego procesamos, y en el momento después realizamos las acciones de terminar. Cualquier variable que aparezca en la condición de un ciclo deberá tener un valor previamente asignado en un momento anterior.
Lo mismo puede suceder con las alternativas simples y múltiples para determinar cuál será la estructura condicional más conveniente bajo ciertas circunstancias.
¿Serán ciclos en secuencia, o anidados?. ¿Serán condiciones en secuencia o anidadas?. ¿Serán ciclos dentro de decisiones o decisiones dentro de ciclos?. ¿Las selecciones tendrán acciones por cada una de las ramas o solo en una de ellas?. Estas son tan solo algunas de las preguntas que nos debemos formular al momento de resolver un problema computacional.
Como vemos la forma de combinar estas pocas estructuras de control de programa es lo que nos da una gran diversidad de variantes, el esqueleto que formará nuestro algoritmo. No obstante, la forma esquelética de nuestros algoritmos se determinará en base a otro tipo de estructuras, las estructuras de datos, este será entonces nuestro primer paso, a partir de allí, pensaremos como han de ser las estructuras de control de programa. Finalmente decimos que las estructuras de control de programa esta determinada por las estructuras de datos.

Anterior: Metodología II

Siguiente: Funciones

Arriba

Una Metodología de Resolución de Problemas II

2008-03-25T15:07:00.000-07:00

Abajo

CLASE 2: Una Metodología de resolución de problemas II.

2. Diseñar una ESTRATEGIA:

Es elaborar un plan de acción global. Una planificación en la cual se establece qué debe hacerse. Es identificar las acciones relevantes. Es ver el bosque antes que el propio árbol. Es mirar de arriba hacia abajo, es decir, de lo general a lo particular. El bosque representa lo general, mientras que el árbol representa lo particular, los detalles. Por lo tanto, “en el nivel de estrategia se deben establecer las acciones más importantes del proceso”, sin entrar en los detalles para no vernos abrumados por ellos, ya que podemos perder el rumbo, desorientarnos y hacer fracasar nuestro objetivo a resolver. La metodología que va de lo general a lo particular se conoce como diseño descendente o TOP – DOWN.
La estrategia será pues un conjunto de acciones relevantes interrelacionadas, dispuestas en un orden lógico, que tendrá como meta alcanzar un objetivo.
El concepto de Sistema es algo complejo de entender. Lo que hacemos para poder asimilarlo es, dividirlo en problemas menores, más fácil de comprender; si aún algunas de estas partes fuera complejo, volvemos a dividir nuevamente, hasta alcanzar un punto en el cual ya no es necesario seguir dividiendo, debido a su evidencia. La solución del Sistema queda definido cuando c/u. de estas partes brinden la solución esperada y queden establecidas las interrelaciones, conectadas por medio de interfases, que posibilitan la comunicación entre ellas.
Divide y vencerás es el axioma de la estrategia.
Si tomamos como Sistema un Automóvil, vemos que este es bastante difícil de comprender. Pues bien, nuestra tarea consiste entonces en dividirlo en subsistemas, los cuales podrían ser: Eléctrico, Mecánico, Frenos, Dirección, Chasis entre otros. Notamos que el Sistema Eléctrico, para nosotros es aún complejo, por lo cual decidimos volver a dividir en los siguientes subsistemas: Batería, Alternador, Bujías, Luces y Cableado. Aún podemos continuar con la Batería en: Bornes,, Nivel del Líquido, etc..

Sistema AUTOMÓVIL
S. ELÉCTRICO
S. BATERÍA
BORNES
NIVEL DEL LÍQUIDO
S. ALTERNADOR
S. BUJÍAS
S. LUCES Y CABLEADO
S. MECÁNICO
S. FRENOS
S. DIRECCIÓN
S. CHASIS-CARROCERÍA

El concepto de caja negra, representa para los científicos una abstracción de detalles, conoce su interfase, sabe lo que realiza, pero no le interesa como lo hace; es este un concepto, muy importante, ya que ayuda a simplificar notablemente la idea de algún tema; lo opuesto es el de caja transparente, en este caso está representando el poder ver como funcionan las cosas por dentro, los detalles de su mecanismo de acción. Al simple automovilista que solo le interesa manejar su vehículo, ve a este en cada una de sus partes como una caja negra, mientras que el mecánico necesita verlo como una caja transparente. Un televisor es también una caja negra, para el simple usuario que requiere ver un programa televisivo, él sabe qué finalidad cumple dicho aparato, también sabe que requiere de entradas y salidas, digamos alimentación eléctrica, la señal desde la antena o cable o satélite y las salidas del aparato de, imagen y sonido. Por otro lado el técnico en TV verá a ese aparato como a una caja transparente, debido a que requiere poder entender todo su mecanismo interno de funcionamiento para darle solución en caso de algún problema técnico que se presente.

3. Refinar la estrategia: El ALGORITMO y su prueba :

Algoritmo: Es una secuencia de acciones dadas en un orden lógico que conociendo ciertos datos debemos obtener ciertos resultados esperados. Ciertas acciones deberán ir antes que otras, y en determinados casos ciertas acciones podrán ir antes o después de otras indistintamente. La palabra deriva del nombre del matemático y astrónomo árabe Alkhôwarîzmi[1] del siglo IX.

Todo algoritmo debe ser:

Preciso, se debe indicar el orden de ejecución en cada paso.
Definido, cada vez que se lo realice, se deben obtener los mismos resultados.
Finito, tiene un número determinado de acciones, debe terminar.

Las 2 herramientas más comúnmente empleadas para diseñar algoritmos son:

Pseudocódigo: utiliza palabras en castellano para indicar las acciones a realizar.
Diagramas de estructuras: utiliza una representación gráfica, denominados símbolos o bloques que indican las acciones a realizar.

El diseño del algoritmo se basa en dos etapas una de análisis y otra de diseño. En la etapa de análisis se determina qué debe realizar, mientras que en la etapa de diseño se determina cómo lo debe hacer. La realización de un problema complejo se lleva a cabo dividiendo el problema original en sub-problemas de menor complejidad, continuando con estas divisiones hasta alcanzar un nivel en el cual ya no es necesario seguir avanzando. Este método se conoce como diseño descendente o modular. El proceso de explotar el problema en etapas y expresar cada paso en forma más detallada se denomina refinamiento sucesivo.
Todo programa bien diseñado consta de un bloque principal –es el módulo de nivel más alto- y es el que llama a otros módulos –de nivel más bajo- los cuales pueden llamar a otros módulos. Los algoritmos diseñados de esta forma se dice que tienen un diseño modular. Cada módulo puede ser realizado, probado, depurado en forma independiente del resto.

Programación estructurada:

La programación estructurada significa escribir un programa de acuerdo a las siguientes reglas:

El algoritmo tiene un diseño modular.
Los módulos son diseñados de modo descendente.
Cada módulo se codifica utilizando las tres estructuras de control básicas:
Concatenación
Selección
Repetición

Además la programación estructurada es el conjunto de técnicas que han evolucionado desde los primeros trabajos de Edsgar Dijkstra y que incorporan:

Recursos abstractos.
Diseño descendente.
Estructuras básicas.

El teorema de la programación estructurada establecido en mayo de 1966 por Böhm y Jacopini, demostró que un programa propio puede ser escrito utilizando solamente tres tipos de estructuras de control: la Concatenación, la Selección y la Repetición.

Un programa se define como propio si cumple las siguientes características:

Posee un solo punto de entrada y uno de salida.
Existen caminos desde la entrada hasta la salida que se pueden seguir y que pasan por todas las partes del programa.
Todas las acciones son ejecutables y no existen ciclos o iteraciones infinitas.

Terminologías:

Palabras reservadas: Es un conjunto restringido de palabras creadas por el lenguaje y que son utilizadas por él para cumplir una tarea específica. El programador debe conocer estos nombres y evitar así utilizarlos para otro propósito.

Identificador: Son palabras creadas por el programador para poder identificar a diferentes objetos empleados en un algoritmo, como ser constantes con nombres, nombres de variables, de módulos, de programa, de campos, de unidades, de tipos; el cual debe seguir ciertas reglas, a saber:

Debe comenzar con una letra o subrayado, a continuación podrá seguir con letras y/o dígitos y/o subrayado –guión bajo-.
No hay diferencias entre mayúsculas y minúsculas.
Se reconocen los primeros 63 caracteres. Los restantes no serán reconocidos.

Además el nombre de un identificador debe ser significativo, es decir, representar su contenido, para hacer más claro el entendimiento al leer un algoritmo. El nombre que se elija no debe ser demasiado largo ni muy compacto, sino un punto de equilibrio, p.e.: para asignar el nombre de identificador a una variable que va a contener los nombres de personas, ellos podrían ser: apellidoyNombre, an, apenom, apeNom, Ape_Nom, ApeNom2, APENOM. En el 1ro. notamos que es muy largo, el 2do. es muy compacto, los restantes es una medida equilibrada. De éstos vemos que fueron escritos de diversas formas, en los casos de apenom, apeNom y APENOM hacen referencia a una misma variable –asumiendo que han sido definidas en el mismo bloque, el compilador en estos casos responderá con un mensaje de Identificador duplicado-, debido a que no hay diferencias entre mayúsculas de minúsculas, pero no sucede lo mismo con Ape_Nom o ApeNom2.

Constantes: Es un valor que no cambia a lo largo de un algoritmo.

Ejemplos:

Constantes enteras: 293, -12, 0, 15981, 3
Constantes reales de punto fijo: 24.92, -2438.7321, 3.0, -4.2, 0.00004.
Constantes reales de punto flotante –notación científica-: 1E6, -3.827E-7.
Constantes booleanas o lógicas: false, true.
Constantes carácter: ‘A’, ‘3’, ‘+’, ‘ ‘.
Constantes de cadena: ‘esto es una cadena de caracteres’, ‘3+2’, ‘’.

Variables: Contiene un valor que podrá ser modificado a lo largo de un algoritmo. Debe tener un nombre y ser definida perteneciente a un tipo de datos. Al hacer esto estamos indicando qué valores podrá contener, enteros con o sin signo, reales, booleanos, carácter, cadenas de caracteres –string-, entre otros. Cada variable ocupa un lugar de almacenamiento en la memoria interna de la computadora y de acuerdo al tipo de dato en que ha sido declarada será la cantidad de bytes que reserve.

Expresiones: Están formadas por operandos y operadores. Los operandos pueden ser constantes, variables o funciones. Los operadores pueden ser:

Aritméticos: Suma +, Resta -, Multiplicación *, División real /, Cociente entero div y Resto de división entera mod, siendo además div y mod palabras reservadas y requiere que sus operandos sean de tipo entero. Las prioridades de estos operadores son:

suma y resta como operadores unarios,
multiplicación, división, div y mod
suma y la resta como operadores binarios.

Para alterar las operaciones de acuerdo a esta prioridad se utilizan paréntesis que poseen la mayor prioridad. A igualdad de prioridades se evalúan las operaciones de izquierda a derecha. El resultado final de una expresión aritmética es un número. El símbolo + también es utilizado para realizar las operaciones entre cadenas de caracteres y es la operación de concatenación y para operaciones entre conjuntos, es la operación de la Unión.

Ejemplos:

2 + 3 * 5 = 17
(2 + 3) * 5 = 25.

Relacionales o comparativos: Son los siguientes: Igual =, Mayor >, Menor <, Distinto <>, Mayor o igual >=, Menor o igual <=, Pertenencia in. Todos ellos están en el mismo nivel de prioridad. Son de menor jerarquía que los operadores aritméticos. El resultado final de la expresión es un valor lógico de verdad o falsedad.

Ejemplos:

3 > x es verdad si el valor de x es menor o igual a 3;
x² – 2 <= 2 * z, es falso si el resultado de la expresión aritmética del miembro izquierdo es mayor al resultado de la expresión aritmética del miembro derecho de la expresión relacional.

Booleanos o lógicos: Son los siguientes: and ^, or v, xor v, not ~, todas ellas palabras reservadas. Las prioridades son: 1ro. Not, 2do. And, 3ro. Or , Xor. El resultado de evaluar una expresión boolean es un valor de verdad o falsedad. Se deben encerrar las expresiones relacionales entre paréntesis cuando haya operadores booleanos, debido a las prioridades, ya que el not está al mismo nivel que los operadores unarios, el and al mismo nivel que los aritméticos de la multiplicación, división, cociente entero y resto entero; y el or y xor al mismo nivel que los operadores binarios de suma y resta.

Ejemplos:

(3 / x + 1 > h – 2) ^ (a + b < 2 =" sqrt(x)"> t * g)

Inicializar: Es asignar un valor inicial a una variable por primera vez.

Acumuladores: Los acumuladores pueden ser, contadores y sumadores.

Contador: Es una variable que está en ambos miembros de una asignación interna, a la que se le suma un valor constante. Es necesario haber inicializado en un momento previo a esta variable, ya que va a ser leído su contenido.

Ejemplos:

c <-- 0;

c <-- c + 1

Sumador: Es una variable que está en ambos miembros de una asignación interna a la que se le suma un valor variable. Es necesario haber inicializado en un momento previo a esta variable, ya que va a ser leído su contenido.

Ejemplos:

c,s <-- 0;

c <-- c + 1;

s <-- s + c;

c <-- c + 1,

s <-- s + c

Señales: Son variables utilizadas para que nos indiquen si sucedió o no un determinado evento, al cual hemos establecido ciertos valores convenidos para indicar tal o cual situación. Si solo adoptan 2 valores posibles, entonces el tipo de dato más apropiado es el boolean.

Ejemplo:

Luego de ingresar una lista de valores se solicita informar si se ingresó algún valor negativo. Se procede de la siguiente manera: antes de ingresar algún valor se inicializa una variable, digamos negativo <-- false, luego se ingresan de a uno por vez los valores y por c/u. de ellos se averigua si es MENOR 0, si es así entonces se cambia el valor de negativo <-- true, por último al finalizar el ingreso de todos los valores se determina, si negativo es verdadero, se emite 'hubo algún valor negativo ingresado' o caso contrario este otro cartel 'no se ingresó ningún valor negativo'.

Auxiliar: Son variables que nos auxilian en determinados procesos, el caso más típico quizás sea el de intercambiar 2 valores.

Ejemplo:

Se quieren intercambiar los valores de las variables a y b, realizamos entonces las siguientes acciones: a <-- 4; b <-- 7; aux <-- a; a <-- b, b <-- aux; luego de esto, en la variable a quedó el valor 7 y en la variable b quedó el valor 4.

Máximos y Mínimos: Son variables que utilizamos para guardar el valor de un máximo o mínimo de una lista de valores. Procedemos de la siguiente manera: si el problema es de máximo inicializamos con un valor ficticio que esté por fuera de los posibles valores reales a ingresar en el proceso y que esté por debajo de esos valores reales, de tal manera que aseguremos que al ingresar el primer valor real sea reemplazado por éste, luego los próximos valores que se vayan conociendo podrán reemplazar o no al valor guardado en ese instante en la variable que hemos elegido como máximo, realizando una pregunta si el valor actual ingresado es mayor al valor guardado en la variable máximo. Al terminar el proceso estamos en condiciones de emitir o de realizar cualquier otra acción necesaria con dicha variable. Tratándose de un problema de mínimo presenta características similares, pero inicializando con un valor mayor que cualquier valor real que se ingrese en el proceso y preguntando durante el momento en que se vayan conociendo c/u. de los valores reales si es menor que el valor guardado en la variable elegida para contener el mínimo en el momento actual. Otro método a elegir podría asignarse a la variable máximo o mínimo el primer valor real ingresado, luego se procede de la manera indicada anteriormente, con los restantes datos.

Ejemplo:

Se ingresan edades de personas, informar la persona con mayor edad. Inicializar MayEdad <-- 0, luego por cada edad conocida se pregunta Edad > MayEdad por verdad se modifica MayEdad <-- Edad, caso contrario no hacemos nada. Al finalizar el ingreso de todas las edades, informamos que la persona de mayor edad tiene MayEdad años.

Ejemplo:

Temperaturas registradas en alguna región geográfica.

Promedios y Porcentajes: Son cálculos que debemos realizar en el proceso.

Ejemplo:

Se pide los promedios de notas en un examen de Algoritmos, en el cual se saben la cantidad de alumnos y las notas alcanzadas por c/u. de ellos. Se requiere uso de un sumador, el cual vaya sumando las notas de cada alumno, al finalizar de ingresar todas las notas, se obtiene el promedio asignando a Prom <-- SumNotas / N, en donde SumNotas es la suma de todas las notas y N la cantidad de alumnos.

Ejemplo:

Se solicita obtener los porcentajes de alumnos aprobados y de alumnos reprobados en el mismo examen. Necesitamos un contador de alumnos que aprueban. Este contador se inicializa en cero, luego tras conocer c/u. de las notas de cada alumno y de comparar si es mayor o igual a 4 se sumará uno en dicho contador. Finalmente, al término de todas las notas, se calculan los porcentajes, de la siguiente forma: PorcApr <-- CantApr / N x 100; PorcRepr <-- (N – CantApr) / N x 100.

[1] Escribió un tratado sobre manipulación de números y ecuaciones titulado Kitab al-jabr w’almugabala.

Anterior: Metodología I

Siguiente: Sentencias

Arriba