Arreglos

6.

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 variabletipo 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 elnú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 mismanotació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 = . 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 estecaso 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 donde 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.

113

Ejemplo de declaraciones de arreglos: 1) var b: arreglo [0..N) de entero; (con N ≥ 0) 2) var f: arreglo [2..3) deentero; 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. b[0] b[1] b[2] b: 2 -3 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 quees 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 ; Para abreviar la notación colocamos: b: arreglo [p1..q1)×[p2..q2) de ; Decimos que b es un arreglo de dimensión 2 de elementos de tipo . Note también que b es un arreglo de dimensión 1 deelementos de tipo “arreglo [p2..q2) de ”. Y vemos que b será una función del producto cartesiano [p1..q1)×[p2..q2) en el conjunto de valores de . Vemos que b[i], p1 ≤ i < q1, es un arreglo cuyos elementos son de tipo arreglo [p2..q2) de . 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=, entonces b[0][2] = -5. Ejemplo de...