Arreglos

Introducción

Un arreglo, array en inglés, es un grupo consecutivo de localidades de memoria que tienen el mismo nombre y el mismo tipo. Para referirnos a una localidad o elemento particular de un arreglo, especificamos el nombre del arreglo y la posición del elemento dentro de éste encerrándola entre corchetes ([]). En C, el primer elemento de cualquier arreglo es el elemento cero; por lo tanto, el primer elemento del arreglo está en la posición 0, el segundo en la posición 1, ..., el i-ésimo elemento esta en la posición i-1.

Los arreglos ocupan espacio de memoria. El programador especifica el tipo de cada elemento y el número de elementos requerido por cada arreglo, de modo que el compilador reserve la memoria necesaria. Para declarar un arreglo, se utiliza la declaración

tipo nombre_del_arreglo[tamaño];

Los arreglos pueden tener múltiples dimensiones. Podemos usar un arreglo de dos dimensiones para representar: una matriz, una tabla, un tablero, etc. Un arreglo de múltiples dimensiones se declara de la siguiente forma

tipo nombre_del arreglo[tamaño1][tamaño2]...[tamañoN];

Es una buena práctica de programación declarar el tamaño del arreglo como una constante, en lugar de indicar el tamaño directamente en la declaración. Otra buena práctica de programación es reservar un poco más de espacio, del máximo esperado durante la ejecución del programa, esto nos puede evitar problemas de violación de segmento.

Por ejemplo si queremos usar un arreglo que almace 100 números flotantes, se utiliza la declaración

#define SIZE 100 // usar una constante para definir el tamaño
float nums[SIZE+10]; // hacer el arreglo un poco más grande del máximo esperado

Para acceder a un elemento dentro del arreglo, se utiliza la declaración

nums[2] = 5.0; // Asigna 5.0 al 3er elemento del arreglo
val = nums[2]; // Asigna el contenido del 3er elemento a la variable val

Ventajas y desventajas de usar arreglos:

  • Si conocemos la posición dentro del arreglo del elemento que queremos consultar, la consulta toma un tiempo constante.
  • Pueden ser usados para implementar otras estructuras de datos sofisticadas como pilas, colas, tablas hash.
  • Su tamaño es fijo, por lo que si no se conoce de antemano el número máximo de elemento a almacenar pueden ocurrir problemas si el espacio reservado es menor del necesario.
  • Insertar elementos de manera ordenada es muy lento.
  • Buscar un elemento en un arreglo desordenado es muy lento.

STL, vector

En C++, la clase STL nos proporciona una clase vector que es un arreglo de tamaño variable, es decir, el tamaño del vector se va ajustando de acuerdo a nuestras necesidades durante la ejecución.

Para usarla es necesario incluir la libreria vector.

#include < vector >

Para declarar una variable de tipo vector, podemos usar alguna de las siguientes tres formas:

// vector < tipo > variable;
vector < int > v; // Crea un vector vacío
vector < int > v(n); // Crea un vector con n elementos
vector < int > v(n, t); // Crea un vector con n copias de t

Los métodos que podemos usar se muestran en la siguiente tabla, en ellos se supondrá que se ha declarado lo siguiente:

vector < int > v;
vector < int >::iterator it;

En C++, la clase STL nos proporciona un vector de tamaño variable, es decir, el tamaño del vector se va ajustando a nuestras necesidades en tiempo de ejecución. La forma de declararlo es la siguiente

vector < int > v; // declaracion de un vector de enteros

Las funciones para trabajar con ella son las siguientes

v.clear(); // elimina todos los elementos del vector
v.size(); // regresa el número de elementos almacenados en el vector
v.push_back(x); // inserta x al final del vector
v.pop_back(); // elimina el último elemento del vector
v[i] // regresa el elemento que se encuentra en la i-ésima posición

Ejemplo

#include <cstdio>
#include <vector>

using namespace std;

main()
{
  // vector <tipo, en este caso, entero> nombre_del_vector;
  vector <int> v;

  // insertamos tres elementos
  v.push_back(2); v.push_back(1); v.push_back(3);

  // podemos acceder a los elementos usando su indice
  for (int i=0; i<v.size(); i++)
    printf("%d ", v[i]);
  printf("\n");

  // o por medio de un iterador
  vector <int>::iterator it;

  for (it = v.begin(); it != v.end(); it++)
    printf("%d ", *it);
  printf("\n");

  // eliminamos el ultimo elemento insertado en el vector
  v.pop_back();

  // eliminamos todos los elementos contenidos en el vector
  v.clear();
}
 

Problemas relacionados en la UVA

482 - Permutation Arrays
10703 - Free spots
541 - Error Correction
101 - The Blocks Problem
105 - The Skyline Problem
10189 - Minesweeper
227 - Puzzle
232 - Crossword Answers
161 - Traffic Lights
10038 - Jolly Jumpers