Tipo arreglo

Arreglos

En este capítulo definimos el tipo arreglo. La mayoría de los lenguajes de programación

(JAVA, C, PASCAL, etc.) poseen el tipo arreglo. Como veremos, los arreglos permiten

implementar, representar y manipular de una manera muy conveniente al tipo abstracto de

dato secuencia, en particular permiten implementar de manera sencilla los cambios de

valores que pueda tener una variable tipo secuencia.

6.1. Definición del tipo arreglo

Un conjunto finito de enteros consecutivos se denomina un segmento. Por ejemplo {0, 1,

2} es un segmento y lo denotamos por [0..3). En general, dados dos enteros p, q con p ≤ q,

el segmento de los enteros i que satisfacen p ≤ i < q, lo denotamos por [p..q). Note que p =

q implica que el segmento [p..q) es el conjunto vacío. También note que el número de

elementos del segmento [p..q) es q-p. Note además que [2..1) no es un segmento.

Un arreglo es una función parcial de los enteros en cualquiera de los tipos básicos ya vistos

(entero, real, carácter, booleano) o el mismo tipo arreglo, y cuyo dominio es un segmento

[p..q), para p, q dados. Note que si p=0 entonces el arreglo no es más que una secuencia.

Por lo que usaremos la misma notación de secuencias para denotar la aplicación de la

función en un elemento del segmento, por ejemplo si b es un arreglo con dominio [0..3)

entonces b es una secuencia de tres elementos y b[2] representa la imagen de 2 según b, es

decir, el último elemento de la secuencia. Decimos que b[0] es el primer elemento del

arreglo b, b[1] es el segundo elemento del arreglo b, etc. Un arreglo con dominio [p..p)

diremos que es un arreglo sin elementos, es vacío.

Si b es un arreglo con dominio [0..2) y rango los números enteros, y cuyos elementos tienen

los valores b[0]=-4, b[1]=-5, entonces el valor del arreglo lo denotamos por b = <-4, -5>.

Decimos que el tipo arreglo es un tipo estructurado, lo cual significa que los valores del

tipo vienen definidos por una estructura sobre valores de otros tipos (en este caso una

función de enteros a otro conjunto).

Tradicionalmente los arreglos han sido vistos como un conjunto de variables indexadas e

independientes que comparten un mismo nombre: el arreglo b con dominio [0..3)

corresponde a las variables b[0], b[1] y b[2] (ver figura 1). Sin embargo, ver a los arreglos

como funciones nos ayudará a manejar la formalidad cuando demostremos correctitud de

programas.

En nuestro pseudolenguaje declararemos un arreglo b de la forma siguiente:

arreglo [p..q) de <tipo>

donde <tipo> puede ser cualquier tipo de nuestro pseudolenguaje, inclusive el tipo arreglo

mismo. Tanto p como q representan expresiones de tipo entero cuyos valores satisfacen p ≤

q.114

Ejemplo de declaraciones de arreglos:

1) var b: arreglo [0..N) de entero; (con N ≥ 0)

2) var f: arreglo [2..3) de entero;

3) var a: arreglo [1..6) de booleano;

En la figura 7 vemos la representación gráfica de un arreglo, donde cada casilla

corresponde a una localidad de memoria, es decir, b[i] es una variable.

Figura 7

Si b es un arreglo con dominio [p..q) y p ≤ i ≤ j ≤ q, denotamos por b[i..j) los elementos del

arreglo b correspondientes a los índices en el segmento [i..j) y decimos que es el segmento

de b entre i y j. Note que, por ejemplo, b[p,p) (la secuencia vacía) es un segmento de b.

El tipo de los elementos de un arreglo puede ser un arreglo:

b: arreglo [p1..q1) de arreglo [p2..q2) de <tipo>;

Para abreviar la notación colocamos:

b: arreglo [p1..q1)×[p2..q2) de <tipo>;

Decimos que b es un arreglo de dimensión 2 de elementos de tipo <tipo>. Note también que

b es un arreglo de dimensión 1 de elementos de tipo “arreglo [p2..q2) de <tipo>”. Y vemos

que b será una función del producto cartesiano [p1..q1)×[p2..q2) en el conjunto de valores

de <tipo>. Vemos que b[i], p1 ≤ i < q1, es un arreglo cuyos elementos son de tipo arreglo

[p2..q2) de <tipo>. Y b[i][j] será el elemento j del arreglo b[i]

Por ejemplo si b es un arreglo con dominio [0..2)×[1..4) en los enteros, y b=<<-4, -5, 2>,

<5, 0, -3>>, entonces b[0][2] = -5.

Ejemplo de uso de arreglos:

El problema ya visto “sumar los elementos de una secuencia de enteros de largo N” puede

ser implementado con el tipo arreglo, obteniéndose el programa siguiente:

[ const N: entero;

const f: arreglo [0..N) de entero;

var x,i: entero;

{ N ≥ 0 }

2 -3

b[2]

6

b[0] b[1]

b:115

...