Unidad II: Estructura de Datos

Arreglos
 Estructuras de datos

• Los arreglos son un tipo de estructura de datos.

• Una estructura de datos es una colección de datos
que se caracteriza por su organización y las
operaciones que se definen en ella.
• Las estructuras de datos son muy importantes en
los sistemas de computadora. Los tipos de datos
más frecuentes utilizados en los diferentes
lenguajes de programación son:
Tipos de datos
 Estructuras de datos

Las estructuras de datos estáticas son

aquellas en las que el tamaño ocupado en
memoria se define antes de que el
programa se ejecute y no puede
modificarse durante la ejecución del
programa.
 Arreglos

Un arreglo (matriz o vector) es un conjunto finito y

ordenado de elementos homogéneos. La
propiedad ordenados significa que el elemento
primero, segundo, tercero,…, n-ésimo de un
arreglo puede ser identificado. Los elementos
de un arreglo son homogéneos, es decir, del
mismo tipo de datos (todos, de tipo cadena o
enteros, o reales, etc.).
 Arreglos unidimensionales:
vectores
• El tipo más simple de arreglo es el arreglo unidimensional o vector.
Un vector de una dimensión denominado NOTAS que consta de n
elementos se puede representar así:

• El subíndice o índice de un elemento [1,2,3,…,i,…,n] designa su

posición en la ordenación del vector.
• Solo el vector global tiene nombre (NOTAS). Los elementos del
vector se referencian por su subíndice o índice, es decir, su
posición relativa en el vector.
 Arreglos unidimensionales:
vectores
Notación algorítmica para declarar vectores:

tipo de variable nombre del arreglo [cantidad de elementos];

Ejemplos:

int numeros [10];

Se están declarando un vector o arreglo de 10 elementos de tipo entero

char nombres [15];

Se están declarando un vector o arreglo de 15 elementos de tipo caracter

 Arreglos unidimensionales:
Operaciones con Vectores
Las operaciones que se pueden realizar con vectores
durante el proceso de resolución de un problema
usando la programación son:
• Recorrido (acceso secuencial)
• Lectura/escritura
• Asignación
• Actualización (añadir, borrar insertar)
• Ordenación
• Búsqueda
1. Recorrido (acceso secuencial)

• Se puede acceder a cada elemento de un vector

para introducir datos (leer) en él o bien para
visualizar su contenido (escribir).
• A la operación de efectuar una acción general
sobre todos los elementos de un vector se le
denomina recorrido del vector.
1. Recorrido (acceso secuencial)

• Estas operaciones se realizan utilizando

estructuras repetitivas, cuyas variables de
control (por ejemplo i) se utilizan como
subíndices del vector (por ejemplo S[i]).
• El incremento del contador del bucle producirá
el tratamiento sucesivo de los elementos del
vector.
 1. Recorrido (acceso secuencial)

Normalmente se utiliza la estructura de repetición para, ya

que se conoce de antemano la cantidad de veces que se
desea repetir el bucle:

para i  1 hasta n hacer

escribir(‘Introduzca el elemento ‘ ,i, ‘del vector F: ’)
leer(F[i])
fin_para
1. Recorrido (acceso secuencial)

• También se pueden utilizar las estructuras de repetición

mientras y repetir:
i1
mientras i <= 20 hacer
escribir(‘Introduzca el elemento ‘ ,i, ‘del
vector F: ’)
leer(F[i])
ii+1
fin_mientras
1. Recorrido (acceso secuencial)

i1
repetir
escribir(‘Introduzca el elemento ‘ ,i, ‘del vector F:
’)
leer(F[i])
ii+1
hasta_que i > 20
2. Lectura/escritura

La lectura/escritura de datos en arreglos

normalmente se realiza con estructuras
repetitivas (usando un recorrido secuencial).
Las instrucciones simples de lectura/escritura se
representarán como:
• leer(A[5]) lectura del elemento 5 del vector A
• escribir(A[8]) escribir el elemento 8 del vector A
2. Lectura/escritura
Generalmente se desea leer o escribir el vector
completo, para lo cual se debe hacer un
recorrido del vector:

para i1 hasta n hacer

escribir(‘Introduzca el elemento ‘ ,i, ‘del
vector F: ’)
leer(F[i])
fin_para
2. Lectura/escritura

Para escribir el vector nombres:

para i1 hasta n hacer

escribir(nombres[i])
fin_para
3. Asignación

La asignación de valores a un elemento del vector

se realizará con la instrucción de asignación:
• A[29]  5 asigna el valor 5 al elemento 29 del
vector A
• Suma  A[1] + A[3]
• A[3]  A[3] + 10.8
• A[1]  A[4] + A[5]
4. Actualización

La operación de actualización de un vector

consta a su vez de tres operaciones más
elementales:
• Añadir elementos
• Insertar elementos
• Borrar elementos
4. Actualización
Añadir elementos: es la operación de
agregar un nuevo elemento al final del
vector. La única condición necesaria para
esta operación consistirá en la
comprobación de espacio de memoria
suficiente para el nuevo elemento, dicho
de otra manera, que el vector no contenga
todos los elementos con que fue definido.
4. Actualización

Ejemplo: se tiene un vector de edades definido para 7

elementos, pero ya tiene almacenado 5 elementos
EDADES(1), EDADES(2), EDADES(3), EDADES(4) y
EDADES(5). Se podrán añadir dos elementos más al
final del vector con una simple operación de asignación:
• EDADES(6)  23
• EDADES(7)  20
(Si conoce los espacio del vector que están libres.)
5. Métodos de ordenamiento y
búsqueda en vectores
 Ordenación (clasificación)

• Es la operación de organizar un conjunto de

datos en algún orden o secuencia específica, tal
como creciente o decreciente para datos
numéricos o alfabéticamente para datos de tipo
carácter o cadena de caracteres.
• Operaciones típicas de ordenación son: lista de
números, archivos de clientes de banco,
nombres en una agenda telefónica.
 Ordenación (clasificación)

• En síntesis, la ordenación significa poner

objetos en orden ascendente o
descendente. El propósito final de la
clasificación es facilitar la manipulación de
datos en un vector.
 Ordenación (clasificación)

Los métodos directos son los que se

realizan en el espacio ocupado por el
arreglo. Los que vamos a estudiar son:
• Método de intercambio o burbuja.
• Ordenación por Inserción
• Ordenación por Selección
 Método de intercambio o de
burbuja

Se basa en el principio de comparar pares

de elementos adyacentes e
intercambiarlos entre sí hasta que estén
todos ordenados.
 Método de intercambio o de
burbuja
El elemento cuyo valor es mayor sube posición a
posición hacia el final de la lista, al igual que las
burbujas de aire en un depósito.
Tras realizar un recorrido completo por todo el
vector, el elemento mencionado habrá subido
en la lista y ocupará la última posición.
En el segundo recorrido, el segundo elemento
llegará a la penúltima posición, y así
sucesivamente.
 Método de intercambio o de
burbuja
Los pasos a dar son:
1. Comparar A[1] y A[2], si están en orden, se mantienen
como están, en caso contrario se intercambian entre si.
2. A continuación se comparan los elementos 2 y 3, de
nuevo se intercambian si es necesario.
3. El proceso continúa hasta que cada elemento del
vector ha sido comparado con sus elementos
adyacentes y se han realizado los intercambios
necesarios.
 Método de intercambio o de
burbuja
La acción de intercambiar entre sí los valores de dos
elementos A[i], A[i+1] es una acción compuesta que
contiene las siguientes acciones, utilizando una variable
auxiliar:
2
A[i] A[i+1]

1 3
AUX
 Método de intercambio o de
burbuja

En pseudocódigo:
AUX  A[i]
A[i]  A[i+1]
A[i+1]  AUX
 Método de intercambio o de
burbuja
Suponga que se quiere ordenar de forma
ascendente el vector:
/*Ordenamiento Burbuja */
#include <iostream>
using namespace std;
#define TAM 9
int main() Método de
{
int a[TAM] = { 9, 8, 0, 2, 5, 1, 3, 2, 9};
int i, pasada, aux;
intercambio o
cout << "Datos en el orden inicial:"<< endl;
for(i=0;i<=TAM-1;i++) de burbuja
cout <<a[i] << endl;
for(pasada=1;pasada<=TAM-1;pasada++) /*pasadas*/
for (i=0;i<=TAM-2;i++)
if (a[i]>a[i+1]) /*comparación */
{
/*intercambio*/
aux=a[i];
a[i] = a[i+1];
a[i+1] = aux;
}
cout<< "Datos ordenados en sentido ascendente:" << endl;
for (i=0;i<=TAM-1;i++ )
cout << a[i] << endl;
return 0;
}
 Métodos de Búsqueda
• La recuperación de información, como ya se ha
comentado, es una de las aplicaciones más
importantes de las computadoras.
• La búsqueda se refiere a la operación de
encontrar la posición de un elemento entre un
conjunto de elementos dados: lista, tabla o
fichero.
• Existen diferentes algoritmos de búsqueda. El
algoritmo elegido depende de la forma en que
se encuentren organizados los datos.
 Métodos de Búsqueda
La operación de búsqueda de un elemento
N en un conjunto de elementos consiste
en:
1. Determinar si N pertenece al conjunto y,
en ese caso, indicar su posición en él.
2. Determinar si N no pertenece al
conjunto.
 Métodos de Búsqueda

Los métodos más usuales de búsqueda

son:
• Búsqueda secuencial o lineal.
• Búsqueda binaria.
Búsqueda secuencial o lineal

El método más sencillo de buscar un elemento en

un vector es explorar secuencialmente el vector
(recorrer el vector), desde el primer elemento
hasta el último. Si se encuentra el elemento
buscado visualizar un mensaje similar a
‘Elemento encontrado en la posición x’, en caso
contrario visualizar un mensaje similar a
‘Elemento no existe en el vector’.
Búsqueda secuencial o lineal
• En otras palabras, la búsqueda secuencial
compara cada elemento del vector con el valor
deseado, hasta que se encuentra o termina de
recorrer el vector completo.
• La búsqueda secuencial no requiere ningún
registro por parte del vector por consiguiente no
requiere que el vector esté ordenado.
Búsqueda secuencial o lineal

Este método tiene el inconveniente del consumo

excesivo de tiempo en la localización del
elemento buscado. Cuando el elemento
buscado no se encuentra en el vector, se
verifican o comprueban sus n elementos. Por
esto no es el método más adecuado para
vectores con un gran número de elementos.
#include <iostream>
using namespace std;
#define TAM 10
int main()
{
int a[TAM], temp, i, j, num, c, posicion;
for (c = 0; c < TAM; c++) //llenar el arreglo con números
{
Búsqueda
cout <<"Dime un valor : " << endl;

}
cin >> a[c]; secuencial o
cout << "Numero a buscar? "<<endl;
cin >>num; lineal
for (i=0; i< TAM; i++)
if (a[i] == num)
{
temp =1;
posicion= i;
}
else temp = 0;
if (temp==1)
cout << "Valor encontrado en la posicion:" << posicion << endl;
else if (temp == 0) cout << "No existe" <<endl;
cout << "El arreglo era:" << endl;
for (i=0; i< TAM; i++)
cout << a[i] <<endl;
return 0;
}
 Búsqueda binaria
Presupone una ordenación previa de los
elementos del vector.
Este método se basa en la división
sucesiva del vector en dos partes, y seguir
dividiendo cada mitad hasta encontrar el
elemento buscado.
 Búsqueda binaria
Utiliza un método de divide y vencerás para localizar el
valor deseado.
Con este método se examina primero el elemento central
del vector, si este es el elemento buscado, entonces la
búsqueda ha terminado.
En caso contrario se determina si el elemento buscado
está en la primera o segunda mitad de la lista, y a
continuación se repite este proceso, utilizando el
elemento central de esa sublista.
 Búsqueda binaria

Es un método eficiente siempre que el

vector esté ordenado.
En la práctica esto suele suceder, pero no
siempre es así. Por esta razón la
búsqueda binaria exige una ordenación
previa del vector.
Arreglos de varias dimensiones

Existen grupos de datos que se representan mejor

en forma de tabla o matriz con dos o más
subíndices. Ejemplos típicos de tablas o
matrices son:
• Distancias entre ciudades
• Horarios
• Informes de ventas periódicas
Arreglos de varias dimensiones

Se pueden definir a las tablas o matrices como

arreglos multidimensionales, cuyos elementos
se pueden referenciar por dos, tres o más
subíndices. Los arreglos de varias dimensiones
se dividen en dos grandes grupos:
• Arreglos bidimensionales: tablas o matrices.
• Arreglos multidimensionales.
Arreglos bidimensionales: matrices

Un arreglo bidimensional se puede considerar

como un vector de vectores.
Es un conjunto de elementos, todos del mismo
tipo, en el cual el orden de los componentes es
significativo y en el que se necesitan especificar
dos subíndices para poder identificar cada
elemento del arreglo.
 Arreglos bidimensionales: matrices
Matriz A:

Fila 1

Fila 2 30

Fila 3

Fila 4

Fila 5 150

Columna 1 Columna 2 Columna 6

 Arreglos bidimensionales: matrices
A[2,5]
Matriz A:

30
Subíndice i
para las filas

150
Subíndice j
A[5,2] para las columnas
Arreglos multimensionales
Un arreglo se puede definir de tres, cuatro y hasta
n dimensiones.
Se manejan los mismos conceptos para los
subíndices que en los vectores o matrices.
Cada elemento del arreglo se puede identificar
usando la cantidad de subíndices necesarios,
por ejemplo en un arreglo de n dimensiones se
escribirá: A[I1, I2, I3, …, In]
Arreglos multimensionales

Ejemplo: Un arreglo de tres dimensiones puede

ser uno que contenga los datos relativos al
número de estudiantes de una universidad de
acuerdo a los siguientes criterios:
– año (primero a quinto)
– sexo (femenino/masculino)
– facultad (cinco facultades diferentes)
Arreglos multimensionales

Curso

Facultad

Sexo