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

x := 0;

i := 0;

{ Invariante I: ( x = ( ∑j: 0 ≤ j < i : f [j] ) ) ∧ (0 ≤ i ≤ N), función de cota creciente: i }

do i < N → x := x +f[i]; i := i+1 od

{ x = (∑j: 0 ≤ j < N : f [j] ) }

]

Veamos un nuevo problema donde utilizamos arreglos.

Problema: Dado un arreglo A de enteros con dominio [0,N), N ≥ 0, deseamos calcular el

segmento A[p..q) de A cuya suma de sus elementos sea máxima entre todos los segmentos

de A.

Una especificación formal de este problema es:

[ const N: entero;

const A: arreglo [0..N) de entero; {N ≥ 0}

var suma: entero;

{ verdad }

maxsegsum

{ suma = (max p,q: 0 ≤ p ≤ q ≤ N : (∑ j: p ≤ j < q : A[j])) }

]

Para simplificar la notación, definimos, para 0 ≤ p ≤ q ≤ N:

S(p,q): (∑ j: p ≤ j < q : A[j])

Una estrategia para resolver este problema es la siguiente:

Supongamos que N > 0 y hemos resuelto el mismo problema pero para el segmento de

A[0..N-1), es decir, conocemos (max p,q: 0 ≤ p ≤ q

...