Almacenamiento de Datos en Arreglos

MIGUEL . TOLEDO MARTNEZ

CONTENIDO DE LA LECCIN 18ALMACENAMIENTO DE DATOS EN ARREGLOS1. Introduccin 2. Estructura de un arreglo2.1. Elementos del arreglo 2.2. ndice del arreglo

3 35 5

3. Examen breve 34 4. Definicin de arreglos unidimensionales en C++4.1. Formato para un arreglo unidimensional 4.2. Ejemplo 18.1

76 55 6

5. Examen breve 35 6. El acceso a los arreglos6.1. Insercin de elementos en los arreglos unidimensionales6.1.1. Asignacin directa 6.1.1.1. Formato de asignacin directa (insercin de elementos en un arreglo) 6.1.2. Sugerencia de depuracin 6.1.3. Lectura de los elementos del arreglo 6.1.4. Insercin de elementos del arreglo con el uso de ciclos 6.1.4.1. Insercin dentro de un arreglo unidimensional con el uso de un ciclo for

76 666 6 7 7 8 8

7. Extraccin de elementos de los arreglos unidimensionales7.1. Asignacin directa7.1.1. 7.1.2. 7.1.3. 7.1.4. Formato de asignacin directa (extraccin de elementos del arreglo) Escritura de elementos del arreglo Extraccin de elementos del arreglo con el uso de ciclos Sugerencia de depuracin

999 10 10 11

8. Examen breve 36 9. Ejemplos 18.2, 18.3, 18.4, 18.5, 18.6, 18.7, 18.8, 18.9, 18.10, 18.11, 18.12, 18.13, 18.14,18.15, 18.16, 18.17.

76 12 2121

10. Paso de arreglos y elementos de arreglos a las funciones10.1. Ejemplos 18.18, 18.19, 18.20, 18.21, 18.22, 18.23, 18.24, 18.25

11. Examen breve 37 12. Ordenamiento de arreglos12.1. Ejemplos 18.26, 18.27, 18.28, 18.29, 18.30, 18.31, 18.32

76 3132

13. Bsqueda en arreglos: Bsqueda lineal y bsqueda binaria13.1. Ejemplos 18.33, 18.34, 18.35

4040

ARREGLOS, APUNTADORES Y ESTRUCTURAS LECCIN 18

18-1


14.

Solucin de problemas en accin: Bsqueda en un arreglo con iteracin(bsqueda secuencial) 14.1. Problema 14.2. Definicin del problema 14.3. Planeacin de la solucin 14.4. Codificacin del programa

4545 45 46 46

15. Solucin de problemas en accin: Como ordenar un arreglo con iteracin (ordenacin por insercin) 15.1. Problema 15.2. Definicin del problema 15.3. Planeacin de la solucin 15.4. Codificacin del problema

4747 47 48 50

16. Solucin de problemas en accin: Bsqueda en un arreglo con recursin(bsqueda binaria) 16.1. Problema 16.2. Definicin del problema 16.3. Planeacin de la solucin 16.4. Codificacin del problema

5151 51 52 55

17. Ejemplos 18.36, 18.37 18. Iniciacin de arreglos18.1. Iniciacin predeterminada de arreglos globales y estticos19. Examen breve 38 20. Arreglos que rebasan los 64 kbytes de memoria

56 6163

77 6565

20.1. Ejemplos 18.38 y 18.39

21. Lo que necesita saber 22. Preguntas y problemas22.1. Preguntas 22.2. Problemas 22.3. Problemas de recursividad

66 6868 70 75


18-2


LECCIN 18ALMACENAMIENTO DE DATOS EN ARREGLOSINTRODUCCIN Esta leccin tratar un tema muy importante en cualquier lenguaje de programacin: los arreglos. No es posible enfatizar sobremanera la importancia de los arreglos, pues ellos mismos dan origen a muchas aplicaciones. En muchas ocasiones, sus programas requerirn almacenar varios valores, tales como 50 calificaciones, 10 ttulos de libros, 1000 nombres de archivos, etc. Cuando sus programas necesitan almacenar varios valores, entonces define un arreglo, especificando su clase de datos, nombre y nmero de elementos que el arreglo almacenar.Un arreglo es una estructura de datos indexados que se utiliza para almacenar elementos de datos de la misma clase.

Los arreglos simplemente proporcionan un medio organizado para localizar y almacenar datos, as como el apartado postal en el correo de su oficina postal local proporciona un medio organizado de localizar y clasificar el correo. Por esto a un arreglo se le conoce como una estructura de datos que se usa para almacenar cualquier clase de datos, incluyendo enteros, flotantes, caracteres, arreglos, apuntadores, y registros (structs) Adems, los arreglos son tan verstiles que se pueden usar para implementar otras estructuras de datos, como pilas, colas, listas ligadas y rboles binarios, de hecho en algunos lenguajes corno FORTRAN, el arreglo es la nica estructura de datos disponible para el programador, porque, por medio del uso de arreglos es posible implementar la mayor parte de otras estructuras.Los objetivos de esta leccin son: Presentar la estructura de datos de arreglo. Declarar un arreglo dentro de su programa. Comprender cmo se declaran e inicializan los arreglos y de qu manera se hace referencia a los elementos de un arreglo. Aprender a pasar los arreglos a las funciones Aprender a utilizar los arreglos para almacenar, ordenar y hacer bsquedas en listas y tablas de valores. Discernir las tcnicas bsicas para el ordenamiento.

ESTRUCTURA DE UN ARREGLO Un arreglo es una estructura de datos. En otras palabras, un arreglo consta de elementos de datos organizados o estructurados en una forma particular. Esta estructura de datos proporciona un medio conveniente para almacenar grandes cantidades de datos en la memoria primaria o del usuario. Existen arreglos unidimensionales o listas y multidimensionales. En esta leccin revisaremos los arreglos unidimensionales; en la leccin 19 estudiaremos los arreglos multidimensionales.


18-3


Para obtener la idea de un arreglo, observe la ilustracin de la figura 18.1. En esta figura se puede ver una sola lnea de cajas de apartados postales como se encuentran en cualquier oficina de correos. Como se sabe, cada caja tiene un nmero de apartado postal (A. P.) En la figura 18.1, los nmeros del A. P. empiezan con cero y van hasta un nmero finito n. Cmo se localiza una determinada caja? Por medio del nmero de apartado postal, correcto? Sin embargo, el nmero del A. P. no tiene nada que ver con lo que contiene la caja. Simplemente se usa para localizar una caja determinada. Desde luego, el contenido es la correspondencia enviada a esta caja. La razn por la que el servicio postal usa el mtodo de apartado postal es que proporciona un mtodo conveniente y bien organizado para almacenar y tener acceso a la correspondencia de sus clientes. Un arreglo hace lo mismo en un programa de computadora; proporciona un mtodo conveniente y bien organizado para almacenar y tener acceso a los datos para usted, el programador. De modo que, cuntos apartados postales hay en la figura 18.1? Debido a que el primer nmero del apartado es 0 y el ltimo es n, habr n + 1 apartados. ...

...APARTADO POSTAL 0 APARTADO POSTAL 1 APARTADO POSTAL 2 APARTADO POSTAL 3 APARTADO POSTAL n

Figura 18.1.Un arreglo unidimensional o lista es como una fila de buzones de apartados en la oficina de correos.

Imagine que un arreglo unidimensional, como el que se muestra en la figura 18.2, es similar a una lnea de cajas de apartados postales. El arreglo unidimensional consiste en una sola fila de lugares de almacenamiento, cada una etiquetada con un nmero que se conoce con el nombre de ndice. Cada localizacin del ndice se utiliza para almacenar una clase de datos determinada. Los datos almacenados en una localizacin de ndice determinada se conoce como elemento del arreglo. De esta manera, un arreglo unidimensional es una lista secuencial de lugares de almacenamiento que contiene elementos de datos individuales que se localizan o accedan por medio de ndices.

Elemento 0 [0]

Elemento 1 [1]

Elemento 2 [2]

Elemento 3 [3]

Elemento n [n]

NDICES Figura 18.2 Un arreglo unidimensional, tambin llamado lista, es una lista secuencial de localizaciones de almacenamiento que contiene los elementos de datos que se localizan por medio de los ndices.

Los dos componentes principales de un arreglo son los elementos almacenados en el arreglo y los ndices que localizan los elementos almacenados. No se confunda con estos dos componentes del arreglo! Aunque los elementos del arreglo y los ndices se relacionan, son cantidades completamente separadas, al igual que el contenido de una caja de apartado postal es diferente de su nmero de apartado. Con esto presente, vamos a explorar los elementos e ndices del arreglo un poco ms a fondo.ARREGLOS, APUNTADORES Y ESTRUCTURAS LECCIN 18

18-4


ELEMENTOS DEL ARREGLO

Los elementos de un arreglo son los datos almacenados en ste y pueden ser de cualquier clase de datos que se hayan visto. De esta manera, un arreglo dado puede almacenar elementos enteros, elementos de punto flotante, caracteres, y elementos booleanos. Adems, de estos elementos de clase de datos estndar, un arreglo tambin es til para almacenar elementos de datos enumerados. De hecho, aun los elementos de un arreglo pueden ser otros arreglos. Sin embargo, existe una restriccin importante que se aplica a los elementos del arreglo: todos los elementos de un arreglo determinado debern ser de la misma clase de datos. Como se ver en breve, es necesario definir los arreglos en un programa C++. Parte de la definicin es especificar la clase de los elementos que el arreglo almacenar. Una vez que se ha definido un arreglo determinado para cierta clase de datos, slo los elementos de esa clase de datos se almacenarn en ese arreglo.NDICES DEL ARREGLO

Los ndices del arreglo localizan a los elementos del arreglo, en C++, el compilador en forma automtica asigna ndices enteros a la lista de elementos del arreglo empezando con el ndice 0. Por lo tanto, el primer elemento del arreglo en la figura 18.2 se localiza en el ndice 0, y el ltimo elemento se localiza en el ndice n. Los ndices empiezan con 0 y van a n, por tanto habr n + 1 elementos en el arreglo. Tambin, debido a que es un arreglo unidimensional, o lista, decimos que tiene una dimensin de 1 (n + 1) lo cual significa que hay un rengln de n + 1 elementos. La dimensin de un arreglo indica el tamao del arreglo, justo como la dimensin de una pieza de madera indica su tamao. EXAMEN BREVE 34 DEFINICIN DE ARREGLOS UNIDIMENSIONALES EN C++ En C++ todos los arreglos debern estar definidos. Para definir un arreglo, especifique 3 cosas:1. 2. 3. La clase de datos de los elementos del arreglo. El nombre del arreglo. El tamao del arreglo.

El formato general es como sigue:FORMATO PARA UN ARREGLO UNIDIMENSIONAL [];

Lo primero que se ve en la definicin es la clase de datos de los elementos del arreglo. La clase de datos del arreglo es seguida por el identificador del arreglo, su nombre, el cual es seguido por el nmero de elementos que almacena el arreglo dentro de los corchetes, [] La definicin termina con un punto y coma. Por ejemplo, la siguiente es una definicin de un arreglo de 10 caracteres cuyo nombre es caracteres.char caracteres [10];


18-5


Ejemplo 18.1Escriba las definiciones para los siguientes arreglos: a. b. c. d. Un arreglo llamado enteros que almacenar 10 enteros. Un arreglo llamado reales que almacenar 5 valores de punto flotante. Un arreglo llamado caracteres que almacenar 11 caracteres. Un arreglo llamado clase que almacenar calificaciones de 25 estudiantes. Suponga que las calificaciones A, B, C, D y R se definen en una clase de datos enumerados denominada calificaciones.

Qu ndice localiza el ltimo elemento en cada uno de los arreglos anteriores?

Solucina. b. c. d. e. int enteros[10]; float reales[5]; char caracteres[11]; enum calificaciones {R, D, C, B, A}; calificaciones clase[25]; El ndice que localiza el ltimo elemento en cada uno de los arreglos anteriores es uno menos que el tamao definido del arreglo. En cada una de las definiciones anteriores se menciona primero la clase de datos del elemento, seguida por el identificador del arreglo, despus el tamao del arreglo encerrado en corchetes. Cada una de las definiciones es muy obvia, excepto quiz la definicin del arreglo clase. En esta definicin, la clase de datos del arreglo es la clase de datos enumerada llamada calificaciones, que deber anunciarse antes de la definicin del arreglo. Por tanto, diremos que el arreglo clase puede almacenar elementos cuya clase de datos sean calificaciones. De esta manera, los elementos que se pueden almacenar en el arreglo clase se limitan a los elementos de la clase de datos enumerados de R, D, C, B y A. Observe que el compilador no los considera como caracteres, sino como elementos de una clase de datos enumerados llamada calificaciones.

EXAMEN BREVE 35 EL ACCESO A LOS ARREGLOS Tener acceso al arreglo significa insertar elementos dentro del arreglo para almacenar u obtener elementos almacenados desde el arreglo.INSERCIN DE ELEMENTOS EN LOS ARREGLOS UNIDIMENSIONALES

Hay bsicamente 3 formas principales de insertar elementos dentro de un arreglo: mediante un enunciado de asignacin directa, mediante lectura o usando ciclos.ASIGNACIN DIRECTA

El formato general para insertar un elemento, dentro un arreglo, con asignacin directa es como sigue:FORMATO DE ASIGNACIN DIRECTA (INSERCIN DE ELEMENTOS EN UN ARREGLO) [ndice del arreglo] = valor del elemento;


18-6


Con las siguientes definiciones de arreglos:char caracteres[6]; int enteros[3];

las asignaciones directas pueden ser como estas:caracteres [0] ='H'; caracteres [5] ='\0'; enteros [0] = 16; enteros [2] = -22;

En cada uno de estos ejemplos se coloca un elemento en la primera y en la ltima posicin de almacenamiento del arreglo respectivamente. El carcter 'H' se coloca en la primera posicin del arreglo caracteres y el terminador nulo se coloca en la ltima posicin de este arreglo. Recuerde que la primera posicin de este arreglo es siempre [0] y la ltima posicin del arreglo es siempre uno menos que el tamao del arreglo. El entero 16 se coloca en la primera posicin del arreglo enteros y el entero -22 se coloca en la ltima posicin de este arreglo. Observe que se menciona el nombre respectivo del arreglo, seguido por el ndice del arreglo dentro de corchetes. Entonces se usa un operador de asignacin (=) seguido por el elemento que se va a insertar. La clase de datos del elemento que se inserta deber ser la misma que aquella definida para los elementos del arreglo; de otra manera, se obtendrn resultados impredecibles cuando se trabaje con los elementos del arreglo.SUGERENCIA DE DEPURACINRecuerde que los ndices de un arreglo en C++ son valores enteros. Esto significa que cualquier ndice especificado se convierte en su equivalente entero. Por ejemplo, es posible especificar un ndice como un carcter como este: arreglo['A]; sin embargo, C++ trata esto como arreglo[65], porque, desde el cdigo ASCII, el equivalente entero del carcter A es 65. De la misma manera, se puede especificar un ndice usando un valor de punto flotante, como este: arreglo[1.414], sin embargo, C++ lo ve como arreglo[1], porque la parte entera de 1.414 es 1. Los elementos de datos enumerados tambin se pueden usar como ndices, porque el compilador iguala los elementos enumerados a enteros, de acuerdo con el orden listado en el enunciado de la clase de datos enumerados. Para evitar confusin y problemas potenciales, se sugiere utilizar siempre valores enteros en los ndices, a menos que la aplicacin especficamente indique otra cosa. LECTURA DE LOS ELEMENTOS DEL ARREGLO

Tambin es posible usar cualquiera de las funciones u objetos de entrada de C o C++ para insertar los elementos del arreglo desde un teclado, como sigue:cin > caracteres[1]; cin > enteros[0];

En este caso, el usuario deber escribir el valor del elemento del arreglo respectivo desde el teclado y oprimir la tecla ENTER para ejecutar cada enunciado. Deber escribir un carcter para el primer enunciado cin y un entero para el segundo cin. (Por qu?) El carcter escrito desde el teclado se almacenar en la segunda posicin (ndice[1]) del arreglo caracteres, mientras que el entero escrito desde el teclado se almacenar en la primera posicin (ndice[0]) del arreglo enteros.


18-7


INSERCIN ELEMENTOS DE ARREGLOS CON EL USO DE CICLOS

La desventaja obvia al usar asignaciones directas para insertar elementos de arreglos es que se requiere un enunciado de asignacin separado para llenar cada posicin del arreglo. Puede automatizar el proceso de insercin usando una estructura de ciclo. Aunque cualquiera de las tres estructuras de ciclo (while, do/while, for) se puede emplear, la estructura for es la ms comn. A continuacin est el formato general para el uso de un ciclo for:INSERCIN DENTRO DE UN ARREGLO UNIDIMENSIONAL CON EL USO DE UN CICLO for for(int indice = 0; indice < tamao del arreglo; ++indice)

Considere el siguiente programa://LLENADO DE UN ARREGLO CON UN CICLO for #include // Para cin y cout // DECLARA EL TAMAO DEL ARREGLO const int MAX = 10; void main(void) { int muestra[MAX]; // DEFINE UN ARREGLO ENTERO

cout

Documents

Almacenamiento de Datos en Arreglos