jueves, 4 de septiembre de 2008

ESTRUCTURA SECUENCIAL

Explicamos las estructuras secuenciales, cómo se representan en pseudocódigo y algunos ejemplos prácticos de las mismas.


La estructura secuencial es aquella en la que una acción (instrucción) sigue a otra en secuencia. Las tareas se suceden de tal modo que la salida de una es la entrada de la siguiente y así sucesivamente hasta el fin del proceso.

En Pseudocódigo una Estructura Secuencial se representa de la siguiente forma:



Observe el siguiente problema de tipo cotidiano y sus respectivos algoritmos representados en Pseudocódigo y en diagramas de flujos:

• Tengo un teléfono y necesito llamar a alguien pero no sé como hacerlo.


El anterior ejemplo es un sencillo algoritmo de un problema cotidiano dado como muestra de una estructura secuencial. Ahora veremos los componentes que pertenecen a ella:

Asignación

La asignación consiste, en el paso de valores o resultados a una zona de la memoria. Dicha zona será reconocida con el nombre de la variable que recibe el valor. La asignación se puede clasificar de la siguiente forma:

  • Simples: Consiste en pasar un valor constante a una variable (a 15)
  • Contador: Consiste en usarla como un verificador del numero de veces que se realiza un proceso (a a + 1)
  • Acumulador: Consiste en usarla como un sumador en un proceso (a a + b)
  • De trabajo: Donde puede recibir el resultado de una operación matemática que involucre muchas variables (a c + b*2/4).
En general el formato a utilizar es el siguiente:

<>

El símbolo debe leerse “asigne”.

Escritura o salida de datos

Consiste en mandar por un dispositivo de salida (p.ej. monitor o impresora) un resultado o mensaje. Esta instrucción presenta en pantalla el mensaje escrito entre comillas o el contenido de la variable. Este proceso se representa así como sigue:


Lectura o entrada de datos

La lectura o entrada de datos consiste en recibir desde un dispositivo de entrada (p.ej. el teclado) un valor o dato. Este dato va a ser almacenado en la variable que aparece a continuación de la instrucción. Esta operación se representa así:


DECLARACION DE VARIABLES Y CONSTANTES

La declaración de variables es un proceso que consiste en listar al principio del algoritmo todas las variables que se usarán, además de colocar el nombre de la variable se debe decir qué tipo de variable es.

Contador: ENTERO
Edad, I: ENTERO
Direccion : CADENA_DE_CARACTERES
Salario_Basico : REAL
Opcion : CARACTER

En la anterior declaración de variables Contador, Edad e I son declaradas de tipo entero; Salario_Basico es una variable de tipo real, Opcion es de tipo carácter y la variable Direccion está declarada como una variable alfanumérica de cadena de caracteres.

En el momento de declarar constantes debe indicarse que lo es y colocarse su respectivo valor.

CONSTANTE Pi 3.14159
CONSTANTE Msg “Presione una tecla y continue”
CONSTANTE ALTURA 40

Cuando se trabaja con algoritmos por lo general no se acostumbra a declarar las variables ni tampoco constantes debido a razones de simplicidad, es decir, no es camisa de fuerza declarar las variables. Sin embargo en este curso lo haremos para todos los algoritmos que realicemos, con esto logramos hacerlos más entendibles y organizados y de paso permite acostumbrarnos a declararlas ya que la mayoría de los lenguajes de programación (entre ellos el C++) requieren que necesariamente se declaren las variables que se van a usar en los programas.

Veamos algunos ejemplos donde se aplique todo lo que hemos visto hasta el momento sobre algoritmos:

Ejemplo 1: Escriba un algoritmo que pregunte por dos números y muestre como resultado la suma de estos. Use Pseudocódigo y diagrama de flujos.


Ejemplo 2: Escriba un algoritmo que permita conocer el área de un triángulo a partir de la base y la altura. Exprese el algoritmo usando Pseudocódigo y diagrama de flujos.

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

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:




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

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

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

  4. Á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:




  1. Una cabecera precedida por la palabra reservada Unit, el identificador IdUnidad debe tener el mismo nombre que el archivo en disco de la unidad.

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

  3. Una parte de implementación precedida por la palabra reservada implementation que tiene carácter privado, es decir los objetos aquí definidos y que no fueron indicados en la parte de interface no podrán ser accedidos desde un ámbito externo a la unidad, solo podrá acceder la unidad para un requerimiento de uso local necesario para el desarrollo del proceso interno a la misma. En el caso de los módulos, funciones y procedimientos, además de establecer la cabecera de los mismos, se desarrollan en forma completa el conjunto de las sentencia que deban de realizarse para la actividad del módulo como así tambien los objetos propios y locales del módulo.

Una última parte de inicialización de la unidad encerrada entre las palabras reservadas begin y end. Por ejemplo, inicializar las variables definidas en la unidad, ejecutar algunas sentencias o invocaciones a los módulos definidos en la unidad.
Una vez que la unidad ha sido probada con éxito se procede a realizar la compilación por única vez, a menos que en el futuro debamos efectuar algún cambio. El programa que haga uso de la unidad, solo deberá enlazarla a su propio código, el único que deberá compilarse. Las ventajas de usar unidades es que permiten la construcción de grandes programas, dividen las tareas en problemas menores, son más fáciles de corregir, se pueden clasificar de acuerdo a su temática y formar librerías para ser empleadas por diferentes programas.
A continuación se presenta la estructura de una unidad:

   1:Unit IdUnidad;      { Encabezado o cabecera de la unidad }

2:interface { Parte pública }

3: uses { Objetos públicos }

4: const
5: type
6: procedure
7: function
8: var
9:
10:implementation { Parte privada }
11: uses { Objetos privados }
12: const
13: type
14: procedure
15: function
16: var
17:
18:begin { Inicialización de la unidad }
19: sentencias(s)
20:end.

21:




Direccionamiento de memoria bajo el D.O.S.


El D.O.S. –Sistema Operativo en Disco- puede direccionar hasta 1Mbyte de memoria, esto es 220 = 1.048.576 bytes. El Turbo Pascal fue desarrollado para correr bajo el DOS y bajo la familia de procesadores 8088 y 8086. El esquema de la memoria permite direccionar hasta 1Mbyte a pesar de que el cableado de la circuitería interna de los registros sean de 16 bits. Para poder acceder a las direcciones de 20 bits debe utilizar un método de direccionamiento que encaje en el formato de 16 bits.
Direccionamiento segmentado
El espacio de memoria está dividio en segmentos, cada uno de los cuales tiene 64Kbytes de memoria. Para poder acceder a cada posición dentro de un segmento se utiliza un desplazamiento. Debido a que el desplazamiento se mide siempre en relación al segmento, este método se conoce como direccionamiento relativo.
La combinación de un segmento y un desplazamiento forma una dirección segmentada que puede hacer referencia a un byte del espacio de memoria de un total de 1Mega byte. Una dirección segmentada de 32 bits es convertida por el procesador en una dirección de 20 bits utilizando la dirección del segmento como un párrafo adicionando la dirección del desplazamiento. En realidad se desplaza la dirección del segmento 4 bits hacia la izquierda y se le suma el valor del desplazamiento, dando como resultado una dirección de 20 bits.
El siguiente ejemplo ilustra lo dicho anteriormente, si tomamos 1234H como una dirección de segmento y 4321H como una dirección de desplazamiento, la notación empleada para indicar una dirección segmentada sería 1234H:4321H. El número de la parte izquierda de los 2 puntos indica el segmento y el número de la parte derecha de los 2 puntos indica el desplazamiento. La letra H indica que el número está expresado en el sistema de numeración en base hexadecimal. Para calcular la dirección real en memoria se procede a realizar las siguientes operaciones:
12340H se agrega un cero por el extremo derecho a la dirección del segmento
+ 4321H se suma la dirección del desplazamiento relativo
16661H es la dirección real en memoria

Cualquier dirección de memoria puede ser establecida con diferentes combinaciones de direcciones segmentadas, por ejemplo la dirección real de memoria 16661H puede ser establecida no solo como 1234:4321, sino también como 1666:0001, 1665:0011, 1664:0021 y así sucesivamente.
A continuación se presenta otro ejemplo utilizando notación binaria

Ejemplo:





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 cercanosNEAR- son punteros que solamente pueden apuntar a su propio segmento, utilizan solo la parte de desplazamiento para poder acceder dentro de los 64Kbytes o 65536 posiciones de memoria dentro del segmento. Por lo tanto 2 bytes serán necesarios, es decir, con 16 bits o 216 para poder direccionar a cada byte de un segmento.


Punteros lejanos:

Los punteros lejanosFAR- 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:



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

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

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

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

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

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



  1. Genéricos

  2. 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 programaconcatenació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.

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, Anxm, 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, Anxm = Anxn 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 / 21, n / 22, n / 23

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

Si tomamos un conjunto de 50000 elementos, la cantidad máxima de comparaciones estará en el orden de log2 n = log2 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 (N2) 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)


}


}


}