CAPITULO 5
TIPOS ESTRUCTURADOS DE DATOS
La escritura de un programa no sólo implica la formulación de un algoritmo adecuado; también debe sustentarse en una estructura de datos apropiada a la solución que se tiene en mente. Un algoritmo se define como una secuencia finita de instrucciones, cada una de las cuales tiene un significado claro y puede realizarse con una cantidad finita de esfuerzo en una longitud finita de tiempo. Matemáticamente, una estructura de datos es una función que a cada elemento de un conjunto determinado le asocia una nupla ordenada de elementos de otros conjuntos. Teniéndose además una colección de operaciones definidas sobre dicho modelo. Por ejemplo al conjunto de empleados de una fábrica podemos asociarle una estructura de datos con información como: Nombre del empleado, sueldo devengado, cargo, años de servicio, etc. En la medida en que un programa conjuge estos dos elementos Algoritmos y Estructuras de datos - de una manera coherente se obtendrán mejores resultados.
El lenguaje Pascal brinda la posibilidad de definir diversas estructuras de datos de acuerdo a las necesidades propias del usuario, empleando para ello los tipos estándar ya mencionados. Las declaraciones de tipos se hacen justo antes de la declaración de variables en un programa o subprograma; los siguientes son los tipos de estructuras de datos que son viables de definir.
TIPOS ENUMERADOS
Un tipo enumerado es una secuencia ordenada de identificadores, donde cada identificador se interpreta como dato individual. Estos datos individuales, tomados colectivamente, se asocian a un nombre que sirve para identificar el tipo. En la definición de un tipo enumerado se deben especificar sus elementos en el ORDEN en que se desean.
Ejemplo:
Type
Operacion = (suma, resta, mult, div);
Dia = (lun, mar, mie, jue, vie, sab, dom);
Una variable del tipo Dia puede asumir cualquiera de los 7 valores mencionados.
TIPOS SUB-RANGO.
Un tipo simple ordenado puede definirse como un subrango de otro previamente definido Un subconjunto de éste . No se permiten subrangos del tipo real.
Ejemplo:
Type
DiaHabil = lun .. vie;
Grados = 0 .. 360;
Mayúsculas = 'A' .. 'Z';
En este caso DiaHabil es un subrango de Dia. Grados es un subrango de los enteros. Las variables correspondientes a un tipo enumerado se pueden declarar directamente así:
Var
diatrabajo : DiaHabil;
angulo : Grados;
estas declaraciones son equivalentes a
Var
diatrabajo : lun .. vie;
angulo : 0 .. 360;
En Object Pascal un valor de tipo escalar puede convertirse a un valor de otro tipo escalar mediante su numero ordinal.
Por ejemplo, asumiendo las definiciones anteriores:
Integer (mar) = 1; { = Ord(mar) }
Dia (6) = dom;
Nótese que al primer elemento del rango o conjunto le corresponde el subíndice 0 (cero).
TIPO CADENA DE CARACTERES (STRING).
En Object Pascal una cadena de caracteres se considera como un ARREGLO o vector de caracteres. Es por ésto que mediante el subíndice adecuado se puede acceder a caracteres individuales en una cadena. Al declarar una variable de cadena como un tipo -o directamente en la declaración de variables- se puede indicar su longitud (número máximo de caracteres que puede contener) entre paréntesis cuadrados. Si esta longitud no se especifica, Object Pascal asume un máximo de 255 caracteres.
var
Nombre : String[25];
en este caso una variable de tipo nombre puede contener hasta 25 caracteres. Si:
Nombre := 'Blaise Pascal';
entonces
Nombre[8] = 'P'
Esta forma de acceder a los elementos individuales de una cadena es muy útil. Por ejemplo si se desean convertir las minúsculas de la variable Nombre a mayúsculas, bastaría con hacer:
for pos := 1 to length(Nombre) do
Nombre[pos] := UpCase(Nombre[pos]);
resultando
Nombre = 'BLAISE PASCAL'
TIPO ARREGLO (ARRAY).
El arreglo (array) es un tipo estructurado que consta de un número fijo de componentes que tienen asociado un identificador común a pesar de representar múltiples elementos. Cada componente de un arreglo se referencia mediante el nombre del arreglo seguido de un subíndice encerrado entre paréntesis cuadrados. Los elementos del arreglo pueden ser de cualquier clase, siempre y cuando todos pertenezcan al mismo tipo.
Declaración de arreglos.
La declaración o definición consta de la palabra ARRAY seguida por el tipo de índice encerrado entre paréntesis cuadrados [], la palabra OF y el tipo de los elementos. El tipo de índice puede ser un ordinal de tipo simple o un subrango. El arreglo puede ser de cualquier tipo, incluyendo tipos estructurados.
Suponiendo que un programa necesita una lista de cien elementos de tipo real, la declaración del arreglo se puede escribir así:
Var
lista : array [1..100] of real;
Otro modo de escribirlo sería:
type
indice = 1..100;
Var
lista : array [indice] of real;
Observe que los elementos del array son de tipo real, pero el índice es un subrango del tipo entero.
Arreglos multidimensionales.
Los arreglos vistos anteriormente pueden considerarse como un vector (una sola columna de datos). El arreglo multidimensional es una extensión de esta idea, donde un arreglo de dos dimensiones, por ejemplo, nos representa una tabla (matriz) de datos compuesta de filas y columnas con sus dos índices respectivos [ fila, columna].
La declaración de un arreglo multidimensional puede ir incluída en una declaración de variable, al igual que un arreglo unidimensional, especificando para cada dimensión un tipo de índice separado. En consecuencia una definición de arreglo puede ser escrita como:
var
nombre : array [indice1, indice2, .., indiceN] of tipo;
Muchas aplicaciones que utilizan arreglos multidimensionales requieren ciclos anidados, empleando un bucle para cada una de las dimensiones. El siguiente ejemplo ilustra cómo manipular dos matrices para obtener su producto.
El producto de una matriz A(m,n) por una matriz B(n,r) es igual a una matriz C(m,r); donde cada elemento C(i,j) se define como la sumatoria desde un k = 1 hasta k = n de A(i,k) * B(k,j) .
Note que este producto sólo está definido si el número de columnas de A (n) es igual al número de filas de B (n). Por ésto, el programa se limita a preguntar los índices m, n y j; asumiendo que n (preguntado como columnas de A ) es el número de filas de B.
program producto_de_matrices;
const
MAXFILAS = 20;
MAXCOLUM = 20;
type
matriz = array[1..MAXFILAS,1..MAXCOLUM] of integer;
var
matrizA,matrizB,matrizC : matriz;
Afilas,Acolumnas,Bcolumnas,
i,j,k : integer;
m,n : string;
procedure preguntar (pregunta : string; var respuesta :integer);
begin
Write(pregunta); Readln(respuesta)
end;
procedure LeerMatriz(numfilas,numcolum : byte;
var arreglo : matriz);
begin
for i := 1 to numfilas do
begin
Str(i:2,m);
for j := 1 to numcolum do
begin
Str(j:2,n);
preguntar('Elemento (' + m + ',' + n + '): '
,arreglo[i,j]);
end
end
end;
begin
preguntar('Filas de A : ',Afilas);
preguntar('Columnas de A : ',Acolumnas);
preguntar('Columnas de B : ',Bcolumnas);
Writeln('Entre la matriz A por filas');
LeerMatriz(Afilas,Acolumnas,matrizA);
Writeln('Entre la matriz B por filas');
LeerMatriz(Acolumnas,Bcolumnas,matrizB);
{ *** Hace cero la matriz matrizC *** }
for i := 1 to Afilas do
for j := 1 to Bcolumnas do
matrizC[i,j] := 0;
{ *** Realiza el producto *** }
for i := 1 to Afilas do
for j := 1 to Bcolumnas do
for k := 1 to Acolumnas do
matrizC[i,j] := matrizC[i,j] +
matrizA[i,k] * matrizB[k,j];
{ *** Despliega resultado *** }
for i := 1 to Afilas do
begin
for j := 1 to Bcolumnas do
Write(matrizC[i,j]:4);
Writeln
end
end.
Es necesario hacer cero la matriz matrizC antes de realizar su cálculo; de otra manera aparecerían errores en sucesivas ejecuciones del programa, ya que se estarían acumulando los resultados en los elementos de matrizC.
TIPO REGISTRO (RECORD).
Un registro es una estructura que consta de varios elementos constitutivos llamados campos. Los campos pueden ser de diferentes tipos, incluyendo escalares, arreglos, registros, etc.
Declaración de Registros.
La declaración de un registro se hace con la palabra record seguida de una lista de campos (con el tipo de cada uno), y termina con la palabra end, así:
Type
fecha = record
Dia : 1..31;
Mes : 1..12;
Año : 1900..2100;
end;
estudiante = record
Nombre : String[25];
Direccion : String[25];
Codigo : Word;
Semestre : 1..10;
Ingreso : Fecha;
end;
Una vez definido el registro se pueden declarar varias variables diferentes como registros de este tipo:
var
Curso : Array [1..30] of estudiante;
alumno : Estudiante;
Pueden también declararse registros como elementos individuales de otras estructuras (un registro que a su vez contiene otro: Estudiante contiene el registro Fecha; o el arreglo Curso cuyos elementos individuales son registros del tipo Estudiante).
El tipo de operación más sencilla en el procesamiento de registros es la asignación de un registro íntegro a otro. Esto requiere que ambos registros tengan la misma composición. Así con las anteriores declaraciones de registros podríamos tener un programa en que se hiciera la asignación:
Curso[10] := alumno;
Para acceder a los elementos individuales de un registro (ya que es más frecuente el procesamiento de campos individuales que el procesamiento de registros enteros), se debe construír un designador de campo; éste es la combinación del nombre de la variable de tipo registro, un punto y el nombre de un campo; el siguiente es un trozo de programa con referencias válidas a los campos de la variable Alumno del tipo Estudiante:
Write('Entre el nombre del estudiante');
ReadLn(Alumno.Nombre);
Write('Semestre :');
Readln(Alumno.Semestre);
if Alumno.Semestre = 1 then
begin
Alumno.Ingreso.Dia := 24;
Alumno.Ingreso.Mes := 7;
Alumno.Ingreso.Año := 1989;
end;
LA SENTENCIA WITH.
Si observamos las líneas anteriores, nos damos cuenta de que la referencia a registros se hace un poco complicada y monótona porque tenemos que repetir los nombres del registro cada vez que se hace referencia a un campo del mismo. En tales casos se ofrece la instrucción WITH, la cual permite omitir el nombre de los registros en los designadores de campo.
La instrucción WITH consta de la palabra with seguida por una lista de variables del tipo registro separadas por comas y terminada con la palabra DO (hacer). Enseguida deberán ir las instrucciones sobre las que actúa.
Entonces las últimas líneas del ejemplo anterior se pueden reescribir así:
if Alumno.Semestre = 1 then
With Alumno.Ingreso do
begin
Dia := 24;
Mes := 7;
Año := 1989;
end;
Todo el ejemplo anterior podría escribirse así:
With Alumno do
begin
Write('Entre el nombre del estudiante');
ReadLn(Nombre);
Write('Semestre :');
Readln(Semestre);
if Semestre = 1 then
With Ingreso do
begin
Dia := 5;
Mes := 4;
Año := 1986;
end
end;
Registros Variantes.
La sintaxis del tipo registro permite una parte variante, dando la posibilidad de que un campo del registro pueda variar a lo largo del programa entre algunos tipos predefinidos dependiendo del valor que se asigne a un campo particular dentro del registro (el campo de marca).
La forma general para la definición de un registro que contiene tanto una parte fija como una variante es:
TYPE NombreReg = RECORD
campo fijo 1;
campo fijo 2;
.
.
CASE identificador Campo de Marca : tipo OF
rotulo case 1 : (lista de campos variantes1);
rotulo case 2 : (lista de campos variantes2);
.
.
END
El campo de marca debe ir asociado con un dato de tipo ordinal previamente definido. Cada valor de este ordinal debe aparecer una vez como un rótulo case en las subsiguientes partes variantes de la definición de registro. La parte activa del registro consistirá entonces en aquellos campos que correspondan a cada rótulo case particular, según se asignen al identificador del campo de marca.
En cada registro sólo puede haber una parte variante y siempre debe seguir a la parte fija del registro.
Suponiendo que deseamos procesar información sobre las personas que visitan un museo, registrando diferentes datos acorde a si la persona es nacional o extranjera; podemos definir:
Type
Origen = (Nacional, Extranjero);
El siguiente registro contiene una parte variante que registra diversos datos según el valor que tome el campo de marca PROCEDENCIA de tipo ORIGEN. Si Procedencia = Nacional, se registrará el Departamento y Municipio; de lo contrario, se colocará el país de origen, la fecha de ingreso al país y la fecha en que deberá salir de él. La declaración del registro será como aparece enseguida:
Type
linea = string[30];
Visitante = record
Nombre: linea;
Visita: Fecha;
Case Procedencia : Origen of
Nacional :( Depart : linea;
Municipio: linea );
Extran :( Pais : linea;
Entrada : fecha;
Salida : fecha );
end;{ record }
TIPO CONJUNTO (SET)
En general, un conjunto es una colección ordenada de datos simples (todos del mismo tipo), llamados elementos.
Con el fin de utilizar el concepto de conjunto, primero se debe definir un tipo conjunto, con el que se podrán declarar variables de tipo conjunto, cuyos valores individuales sean elementos de este tipo de conjunto. De hecho, una variable conjunto puede representar cualquier número de elementos del conjunto, incluído ninguno. Esta característica nos ofrece una manera sencilla de determinar si una entidad o evento está dentro de una o más categorias predefinidas.
En Object Pascal, los elementos son datos de algún tipo previamente declarado. Ejemplos de Conjuntos son:
Los números enteros de 1 a 100.
Las letras del alfabeto = ['a'..'z','A'..'Z'].
Las vocales = [a,e,i,o,u].
B = [i,o,a,u,e].
Dos conjuntos son iguales sí y solo sí sus elementos son los mismos, sin importar el orden. El conjunto de las vocales y el conjunto B, del ejemplo anterior son iguales.
Declaración de conjuntos.
Se comienza asociando un grupo ordenado de datos de tipo simple con un tipo de dato (el tipo base). Se declara entonces el tipo conjunto en términos del tipo base usando las palabras reservadas SET OF .
Type
Carácter = Set of Char;
Colores = Set of (rojo, verde, azul, amarillo);
Operaciones con conjuntos.
Hay tres operaciones básicas con conjuntos (muy similares a las operaciones con números):
UNION (o suma) de dos conjuntos A y B (A+B): es el conjunto de los elementos de A más los elementos de B.
INTERSECCION es el conjunto de los elementos de A que también están en B.
DIFERENCIA (resta) de B con respecto a A (denotada A-B). Son los elementos de A que no están en B.
Operadores para conjuntos.
Operador Nombre
* Intersección
+ Unión
- Diferencia
= Igualdad
<> Desigualdad
>= "Contiene a"
<= "Contenido en"
IN Pertenencia
:= Asignación
Construcción de conjuntos.
En Object Pascal hay varias normas en cuanto a los elementos que forman parte del conjunto:
Deben ser escalares, excepto del tipo real.
Todos los miembros del conjunto deben ser del mismo tipo (llamado tipo base).
El número máximo de elementos de un conjunto es 256, descritos con los índices ordinales del 0 al 255.
Los elementos deben haber sido declarados previamente, y ser del mismo tipo que el conjunto.
Para construír un conjunto, se deben colocar los elementos que lo forman entre paréntesis cuadrados y separados por comas. También se pueden construír conjuntos realizando operaciones entre conjuntos previamente definidos. En este caso se debe asignar el resultado de la operación a una variable del tipo conjunto.
El siguiente ejemplo ilustra el uso de conjuntos; éste programa cuenta el número de vocales y consonantes en una línea de texto.
program cuenta;
type
letras = Set of char;
var
consonantes,vocales : letras;
cont,
cuentaconso,cuentavocal : integer;
linea : string;
begin
vocales := ['A','E','I','O','U','a','e','i','o','u'];
consonantes := ['A'..'Z','a'..'z'] - vocales;
cuentavocal := 0;
cuentaconso := 0;
Writeln('Entre la linea a analizar :');
Readln(linea);
for cont := 1 to length(linea) do
if linea[cont] in consonantes
then cuentaconso := cuentaconso + 1
else if linea[cont] in vocales
then cuentavocal := cuentavocal + 1;
Writeln('El número de vocales en la linea es : ',cuentavocal);
Writeln('El número de consonantes en la linea es : ',cuentaconso);
end.
CONSTANTES CON TIPO.
Son "identificadores" cuyo valor se asigna al inicio del programa aunque pueden modificarse durante la ejecución del mismo. Pueden considerarse como "variables inicializadas" porque su valor está definido desde el principio, mientras que el valor de una variable normal es indefinido hasta que se haga una operación de asignación. Aunque son diferentes de las variables, se usan exactamente igual que ellas.
Su uso es muy importante por ejemplo, cuando se necesita un valor que debe repetirse muchas veces dentro del programa.
Una constante se puede definir de cualquier tipo escalar, de acuerdo con la siguiente sintaxis:
CONST Identificador : Tipo = valor;
TIPOS DE CONSTANTES NO ESTRUCTURADAS.
Son constantes definidas como cualquier tipo escalar, así:
Const
NUM_CARROS : Integer = 1267;
INTERES : Real = 0.3;
TITULO : String [7] = 'Circular';
TIPOS DE CONSTANTES ESTRUCTURADAS.
Son arreglos, registros o conjuntos constantes, cuyos elementos son de un tipo predefinido, y que se usan por ejemplo, para inicializar tablas. El componente de un arreglo constante puede ser de cualquier tipo diferente a archivos o apuntadores.
Arreglos simples:
Type
Status = 1..3;
Actual = Array[status] of string [7];
Const
ESTADO : Actual = ('Activo','Pasivo','Espera');
El ejemplo define el arreglo constante Estado, cuyos elementos son del tipo Actual (cadenas de hasta 7 caracteres), y equivale a:
ESTADO [1] = 'Activo'
ESTADO [2] = 'Pasivo'
ESTADO [3] = 'Espera'
En el uso de arreglos constantes de caracteres, las dos declaraciones siguientes son equivalentes y válidas:
const
DIGITOS: array [0..9] of char = ('0','1','2','3','4','5','6','7','8','9');
DIGITOS: array [0..9] of char = '0123456789';
Arreglos multidimensionales constantes.
Los arreglos multidimensionales constantes se definen encerrando las constantes de cada dimensión entre paréntesis, separadas por comas.
Ejemplo:
Type
coordenadas3D = (x,y,z);
VerticesCubo = array [1..8,coordenadas3D] of integer;
Const
CAJA : VerticesCubo = ((0,0,0), { Vertice 1 }
(1,0,0),
(1,1,0),
(1,1,1),
(1,0,1),
(0,0,1),
(0,1,1),
(0,1,0)); { Vertice 8 }
El ejemplo define el arreglo multidimensional (2 dimensiones) constante Caja; al cual se asignan las coordenadas de cada vértice para una caja de lado 1. Los valores de las coordenadas x, y, z en los vertices 1 y 7 equivalen a asignar los siguientes valores a los correspondientes elementos del arreglo:
CAJA[1,x] := 0; CAJA[7,x] := 0;
CAJA[1,y] := 0; CAJA[7,y] := 1;
CAJA[1,z] := 0; CAJA[7,z] := 1;
Registros constantes.
La definición de un registro constante se hace con el identificador de la constante, dos puntos (:), el tipo del registro (previamente definido), el signo igual (=) y los valores constantes expresados como una lista de los campos constantes (precedidos del identificador de campo y dos puntos) separados por punto y coma (;) y encerrados entre paréntesis.
Ejemplo:
Type
Point = record
X,Y,Z: integer;
end;
Const
ORIGEN : Point = (X:0; Y:0; Z:0);
PLANO : array[1..3] of point = ((X:41; Y:12; Z:-8),
(X:10; Y:-5; Z:45),
(X:93; Y:10; Z:16));
Los campos constantes deben especificarse en el mismo orden en que aparecen en la definición del tipo registro.
Conjuntos Constantes.
Un conjunto constante se define como uno o más elementos pertenecientes a un conjunto, separados por comas, y encerrados entre paréntesis cuadrados. Un rango se expresa mediante dos constantes separadas por dos puntos suspensivos, por ejemplo: [1..5] define los enteros entre 1 y 5.
Ejemplo:
Type
Mayúsculas = set of 'A'..'Z';
minúsculas = set of 'a'..'z';
Const
MAYUS : Mayúsculas = ['A'..'Z'];
MIN_VOC : minúsculas = ['a','e','i','o','u'];
MAY_VOC : Mayúsculas = ['A','E','I','O','U'];
CON_MIN : minúsculas = ['b'..'d','f','g','h','j'..'n','p'..'z'];