7/30/2019 Cap IV, ARREGLOS.pdf
1/54
FACULTAD DE INGENIERA
ESCUELA DE INGENIERA EN SISTEMAS YCOMPUTACIN
ESTRUCTURA DE DATOS
Ing. Pamela Vsquez Costales
7/30/2019 Cap IV, ARREGLOS.pdf
2/54
1. Estructuras fundamentales
1.1. Introduccin
Los datos a procesar por unacomputadora pueden clasificarse en:
Simples Estructurados
7/30/2019 Cap IV, ARREGLOS.pdf
3/54
Simples: usan una sola casilla, por lotanto una variable simple hacereferencia a un nico valor a la vez.
Dentro de este grupo de datos seencuentran: enteros, reales,caracteres, booleanos.
identificador
7/30/2019 Cap IV, ARREGLOS.pdf
4/54
Estructurados: se caracterizan porel hecho de que con un nombreidentificador de variable estructuradase hace referencia a un grupo de
casillas de memoria.
identificador
7/30/2019 Cap IV, ARREGLOS.pdf
5/54
1.2. ArreglosCon frecuencia se presentan problemas cuyasolucin no resulta fcil implementar a veceses imposible si se usan datos simples.
A continuacin se presenta un problema ydos posibles soluciones del mismo utilizandotipos simples de datos. El objetivo es ilustrar
lo complejo que resulta un algoritmo desolucin para ciertos problemas, sin usartipos estructurados de datos.
7/30/2019 Cap IV, ARREGLOS.pdf
6/54
Ejemplo1.1: se tienen calificaciones de
50 alumnos, se necesita saber cuantosalumnos tienen calificacin superior alpromedio del grupo
7/30/2019 Cap IV, ARREGLOS.pdf
7/54
7/30/2019 Cap IV, ARREGLOS.pdf
8/54
7/30/2019 Cap IV, ARREGLOS.pdf
9/54
Las dos soluciones son representativas de
los inconvenientes a los que se enfrenta altratar de resolver utilizando datos simples.En la primera el usuario debe ingresar dosveces el conjunto de datos lo que resultamolesto considerando que el nmero
puede ser mayor que 50 y es ineficiente.
En la segunda se manejan 50 variables dememoria, esta solucin presenta elinconveniente de que el manejo de lasvariables puede tomarse incontrolable, si elnmero de las mismas crececonsiderablemente.
7/30/2019 Cap IV, ARREGLOS.pdf
10/54
Ninguna solucin es prctica y eficiente.Es necesario un nuevo tipo de datos quepermita tratar estos problemas demanera ms adecuada. Los tipos de
datos estructurados que ayudan aresolver problemas como este son losARREGLOS.
7/30/2019 Cap IV, ARREGLOS.pdf
11/54
Un arreglo es una coleccin finita,
homognea y ordenada de elementos.
Finita, todo arreglo tiene un lmite: esdecir debe determinarse cul ser el
nmero mximo de elementos quepodrn formar parte del arreglo.
Homognea, todos los elementos de unarreglo son del mismo tipo (todosenteros, booleanos, etc., pero nunca unacombinacin de distintos tipos).
7/30/2019 Cap IV, ARREGLOS.pdf
12/54
Ordenada, se puede determinar cul es el
primer elemento, el segundo, y el ensimoelemento. Grficamente el arreglo serepresenta as:
Componente
Indice
7/30/2019 Cap IV, ARREGLOS.pdf
13/54
Si un arreglo tiene la caracterstica de que
puede almacenar N elementos del mismotipo, deber tener la facilidad de permitir elacceso a cada uno de ellos.
As se distinguen dos partes en los arreglos:
Componentes
ndices
7/30/2019 Cap IV, ARREGLOS.pdf
14/54
Los componentes hacen referencia a los
elementos que forman el arreglo: esdecir, los valores que se almacenan encada una de las casillas del mismo. Delejemplo las 50 calificaciones ser uncomponente de un arreglocalificaciones.
Los ndices especifican cuntos elementostendr el arreglo y adems de que modopodrn accesarse esos componentes. Losndices permiten hacer referencia a loscomponentes del arreglo en formaindividual. Es decir, distinguir entre los
elementos del mismo.
7/30/2019 Cap IV, ARREGLOS.pdf
15/54
Por tanto para hacer referencia a un
elemento de un arreglo se utiliza:
El nombre del arreglo
El ndice del elemento
7/30/2019 Cap IV, ARREGLOS.pdf
16/54
La figura muestra que el nombre del
arreglo es nico e identifica a todo elconjunto de datos almacenados en laestructura. Por su parte V1, V2, , Vnindican los valores almacenados en cada
una de las casillas del arreglo. Los ndices0,1, , n-1 referencian a cada una de lasceldas y por lo tanto permiten el acceso acada uno de los valores almacenados en
ellas.
7/30/2019 Cap IV, ARREGLOS.pdf
17/54
En C y C++ los ndices se enumeran a
partir del 0. Es decir, si se declara unarreglo de 20 elementos, las casillas seidentificarn con los nmeros del 0 al 19 yel arreglo tiene una capacidad para
almacenar 20 valores.
7/30/2019 Cap IV, ARREGLOS.pdf
18/54
1.2.1. Definicin de arreglos
Ident_arreglo = ARREGLO[lminf..lmsup] DE tipo
Con los valores lminf y lmsup se declarael tipo de los ndices as como el nmerode elementos que tendr el arreglo. Elnmero total de componentes NTC que
tendr el arreglo puede calcularse:
NTC = lmsup lminf + 1
7/30/2019 Cap IV, ARREGLOS.pdf
19/54
Con tipo se declara el tipo de datos para
todos los componentes del arreglo. El tipode los componentes no tiene que sernecesariamente el mismo de los ndices.
Observaciones: El tipo ndice puede ser cualquier tipo
ordinal: carcter, entero, etc. El tipo de los componentes puede ser
cualquier tipo: entero, real, cadena decaracteres, registro, arreglo, etc.
Se usan corchetes []para indicar el ndicede un arreglo que es un valor ordinal.
7/30/2019 Cap IV, ARREGLOS.pdf
20/54
Ejemplo 1.2: Sea V un arreglo de 50elementos enteros con ndices enteros. Su
representacin queda as:
V = ARREGLO[1..50] DE enteros
NTC = (50-1+1)=50
Cada componente del arreglo V ser unnmero entero y podr accesarse por mediode un ndice que ser un valor comprendidoentre 1 y 50.
V
1 2 3 50
7/30/2019 Cap IV, ARREGLOS.pdf
21/54
V[1] hace referencia al elemento de la posicin 1V[2] hace referencia al elemento de la posicin 2V[50] hace referencia al elemento de la posicin 50
7/30/2019 Cap IV, ARREGLOS.pdf
22/54
Ejemplo 1.3: Sea A un arreglo de 26elementos booleanos con ndices de tipo
caracter. Su representacin queda as:A = ARREGLO[a.. z] DE booleanos
NTC = (ord(z)-ord(a)+1)=122-97+1=26
Cada componente del arreglo A ser uno de los dosposibles valores lgicos (VERDADERO o FALSO) ypodr accesarse por medio de un ndice que ser unvalor comprendido entre los caracteres a y z.
A
a b c z
7/30/2019 Cap IV, ARREGLOS.pdf
23/54
A[a]hace referencia al elemento de la posicin a (1era)A[b]
hace referencia al elemento de la posicin b (2da)A[z]hace referencia al elemento de la posicin z
(27ma)
7/30/2019 Cap IV, ARREGLOS.pdf
24/54
Ejemplo 1.4: Sea CICLO un arreglo de 12
elementos reales con ndices de tipoescalar. Su representacin queda as:
CICLO = ARREGLO[meses] DE reales
NTC = (ord(dic)-ord(ene)+1=12
Cada componente del arreglo CICLO ser unnmero real y podr accesarse por medio de unndice que ser un valor comprendido entre ene
y dic.
7/30/2019 Cap IV, ARREGLOS.pdf
25/54
CICLO[ene]hace referencia al elemento de la posicin ene (1era)CICLO[feb]
hace referencia al elemento de la posicin feb (2da)CICLO[dic]hace referencia al elemento de la posicin dic (12ma)
7/30/2019 Cap IV, ARREGLOS.pdf
26/54
1.2.2. La clase Arreglo
Tiene como atributos la coleccin deelementos que forman la estructura dedatos y el nmero de elementos y comomtodos el conjunto de operaciones queson aplicables a un arreglo.
7/30/2019 Cap IV, ARREGLOS.pdf
27/54
Plantilla de la clase Arreglo:
7/30/2019 Cap IV, ARREGLOS.pdf
28/54
En la seccin privada de la clases se define el
arreglo mediante la instruccin:T Datos[MAX];
Que significa que tiene una coleccin deelementos, llamada Datos, que tiene unacapacidad mxima de MAX (constantepreviamente definida) elementos y que todos loselementos son del tipo T. T se instanciar con eltipo de dato usado al declarar un objeto del tipo
Arreglo. Adems se define el atributo Tam querepresenta el nmero actual de elementos quetiene el arreglo. Para declarar el objeto se utilizala siguiente sintaxis:
Arreglo ObjArreglo;
7/30/2019 Cap IV, ARREGLOS.pdf
29/54
1.2.3. Mtodos de acceso y modificacin a
arreglos
Las operaciones ms importantes son:Lectura
Escritura Eliminacin Insercin Bsqueda Ordenacin
7/30/2019 Cap IV, ARREGLOS.pdf
30/54
1.2.3.1. Lectura de arreglos
Consiste en darle valores a los componentesdel mismo mediantes el ingreso de datosdesde medios externos, como el teclado.
7/30/2019 Cap IV, ARREGLOS.pdf
31/54
Plantilla de un mtodo de lectura devalores de arreglo:
7/30/2019 Cap IV, ARREGLOS.pdf
32/54
En el mtodo presentado se leen los
primeros Tam (1 , en la seccin pblica dela clase se debe incluir la siguiente
declaracin:
Luego se debe escribir el mtodo delectura (con la sobrecarga del operador>>) correspondiente a los miembros delarreglo.
7/30/2019 Cap IV, ARREGLOS.pdf
33/54
7/30/2019 Cap IV, ARREGLOS.pdf
34/54
En ambas soluciones la lectura del tamao se
incluy junto a la lectura de los elementos delarreglo. Otra solucin es que el nmero actualde elementos se lea desde la aplicacin uno delos objetivos de PP es cdigo reutilizable.
Para declarar un arreglo que almacene 10nmeros enteros se usar:
Arreglo ObjArre(10);
7/30/2019 Cap IV, ARREGLOS.pdf
35/54
1.2.3.2. Escritura de arreglos
Consiste en imprimir el contenido de lascasillas. Plantilla de un mtodo que permiteel despliegue en pantalla de los valoresalmacenados en un arreglo:
7/30/2019 Cap IV, ARREGLOS.pdf
36/54
En el mtodo se despliega en pantalla el
contenido del los primeros Tam (1
7/30/2019 Cap IV, ARREGLOS.pdf
37/54
7/30/2019 Cap IV, ARREGLOS.pdf
38/54
1.2.3.3. Eliminacin en arreglos
Primero se debe localizar el elemento, luegose deben recorrer todos los elementos queestn a la derecha una posicin hacia laizquierda. Es decir, el elemento no se puedequitar fsicamente, solo se ignoralgicamente. Debe reducirse el nmeroactual de componentes. En esta operacin severifica, como errores posibles que el arregloest vaco y que valor a quitar no seencuentre en el arreglo.
7/30/2019 Cap IV, ARREGLOS.pdf
39/54
7/30/2019 Cap IV, ARREGLOS.pdf
40/54
7/30/2019 Cap IV, ARREGLOS.pdf
41/54
1.2.3.4. Operaciones en arreglos
desordenados
Son aquellos cuyos elementos no guardanningn orden, esta caracterstica influye enlas operaciones de bsqueda e insercin.
Bsqueda en arreglos:
Permite determinar si un cierto elemento fuealmacenado o no en el arreglo, el mtodoaplicable es la bsqueda secuencial.
7/30/2019 Cap IV, ARREGLOS.pdf
42/54
Bsqueda secuencial consiste en recorrer el
arreglo, elemento por elemento, comparandocada uno de ellos con el dato buscado. Sicoinciden, la bsqueda termina con xito.
Plantilla de un mtodo que lleva a cabola bsqueda secuencial de un dato, enun arreglo desordenado:
7/30/2019 Cap IV, ARREGLOS.pdf
43/54
7/30/2019 Cap IV, ARREGLOS.pdf
44/54
Insercin en arreglos
En el caso de los arreglos desordenados lainsercin de un nuevo elemento al arreglo sehace en la primera casilla disponible, quegeneralmente ser Tam, considerando que enC++ los ndices van de 0 a Tam-1.
Esta operacin implica verificar que hayaespacio en el arreglo, es decir queTam
7/30/2019 Cap IV, ARREGLOS.pdf
45/54
Esta ltima condicin puede omitirse
dependiendo de la aplicacin, por ejemplono aplica para el ejemplo de lascalificaciones.
Plantilla de un mtodo que lleva a cabo lainsercin de un nuevo elemento en elarreglo:
7/30/2019 Cap IV, ARREGLOS.pdf
46/54
7/30/2019 Cap IV, ARREGLOS.pdf
47/54
En el mtodo presentado, considerando
que el arreglo est desordenado, el nuevoelemento se inserta en la primera casilladisponible. Es decir, en la casilla nmeroTam. Despus de asignar el valor a dichacasilla, se incrementa Tam en uno.
En el programa 4.1 se presenta la
plantilla de la clase Arreglo con lasoperaciones asociados, considerando quelos elementos del arreglo estndesordenados.
7/30/2019 Cap IV, ARREGLOS.pdf
48/54
7/30/2019 Cap IV, ARREGLOS.pdf
49/54
7/30/2019 Cap IV, ARREGLOS.pdf
50/54
7/30/2019 Cap IV, ARREGLOS.pdf
51/54
En el programa 4.2 presenta un ejemplo
de aplicacin de la plantilla previamentedefinida. Crea un objeto de tipo Arreglo,que almacena las claves de un grupo dealumnos. Por medio de los mtodos sepodrn leer, imprimir, registrar nuevasclaves y eliminar algunas de las yaalmacenadas. Este es un caso de
aplicacin en el cual no se puede repetirinformacin al ingresar un nuevoelemento en en el arreglo.
7/30/2019 Cap IV, ARREGLOS.pdf
52/54
7/30/2019 Cap IV, ARREGLOS.pdf
53/54
7/30/2019 Cap IV, ARREGLOS.pdf
54/54