Estructuras de Datos Abstracta: Array

Estructura de Datos Abstracta: Array

Vamos a implementar desde cero la funcionalidad de arrays de forma abstracta. Es decir, la manera en que se almacenan los datos, al igual de las operaciones que realizamos sobre ellos.

Representacion de datos

Esta estructura de datos abstracta va a tener como datos:

1. El espacio del array (espacio de memoria)
2. El tamano (numero maximo de elementos)
3. La longitud (numero de elementos actuales)

Operaciones

Y va a tener las siguientes operaciones:

1. Agregar (x): Agrega el elemento x a el array.
2. Insertar (indice, x): Agrega el elemento x en la posicion indice del array.
3. Eliminar (indice): Elimina el elemento en la posicion indice del array.
4. Buscar (x): Busca el elemento x del array.
5. Obtener (indice): Obtiene el elemento del array en indice.
6. Establecer (indice, x): Establece el elemento x en indice.
7. Max () / Min (): Obtiene el maximo y el minimo elemento del array.
8. Invertir (): Invierte el orden del array.
9. Desplazar (): Desplaza los elementos del array.
10. Rotar (): Rota el array.

Creacion del Array

Primero, vamos a definir la estructura para el array con los datos anteriormente mencionados:

struct array {
  int *elementos; /* el array */
  int tamano; /* maximo elementos */
  int longitud; /* elementos actuales */
};

Inicializando el Array

Ahora vamos a escribir una funcion para crear un array utilizando nuestra estructura.

void
array_crear (int tamano, struct array *arr)
{
  if (!arr)
    return;

  arr->longitud = 0;
  arr->tamano = tamano;
  arr->elementos = malloc (sizeof (int) * arr->tamano);
}

Liberando el Array

Y tambien escribiremos una para liberar el espacio creado para un array.

void
array_free (struct array *arr)
{
  if (!arr || !arr->elementos)
    return;

  free (arr->elementos);
  arr->longitud = 0;
  arr->tamano = 0;
}

Mostrar los Elementos de un Array

Podemos mostrar todos los elementos de un array por medio de un for loop.

Implementacion

void
array_mostrar (struct array arr)
{
  if (!arr.elementos || arr.longitud == 0)
    return;

  for (int i = 0; i < arr.longitud; i++)
    printf ("arr[%d]: %d\n", i, arr.elementos[i]);
}

Agregando Elementos en un Array

Para agregar un elemento al final del array, tenemos que insertar el elemento x en elementos[longitud], e incrementar por uno el valor de longitud.

Implementacion

Podemos hacerlo de la siguiente manera:

void
array_agregar (int x, struct array *arr)
{
  if (!arr || !arr->elementos || arr->longitud >= arr->tamano)
    return;

  arr->elementos[arr->longitud++] = x;
}

Y su complejidad de tiempo es \(O(1)\).

Insertando Elementos en un Array

Para insertar un elemento x en indice dentro de nuestro array, primero necesitamos liberar un espacio (dado el caso que este ocupado), e insertar el elemento.

Para liberar un elemento, tenemos que mover los elementos de indice a longitud para asi tener un espacio libre. Una vez con el espacio libre, ya podremos insertar x.

Implementacion

Podemos hacerlo de la siguiente manera:

void
array_insertar (int indice, int x, struct array *arr)
{
  if (!arr || !arr->elementos || indice < 0 || indice >= arr->tamano)
    return;

  /* mover los elementos */
  if (indice < arr->longitud)
    for (int i = arr->longitud; i > indice; i--)
      arr->elementos[i] = arr->elementos[i - 1];

  /* insertar el elemento */
  arr->elementos[indice] = x;
  arr->longitud++;
}

La complejidad de tiempo depende de la cantidad de elementos que tengamos que mover. Si queremos insertar un elemento en longitud no tendriamos que mover ningun elemento, pero si queremos insertar un elemento en el indice 0 tendriamos que mover todos los elementos.

Teniendo en cuenta que desconocemos la cantidad de elementos que tendremos que mover, decimos que la complejidad de tiempo es: minimo \(O(1)\) y maximo \(O(n)\).

Eliminando un Elemento de un Array

Para eliminar un elemento de un Array, vamos a devolver una copia de este, vamos a liberar el indice, vamos a mover los elementos > indice un espacio hacia atras, y vamos a reducir la longitud.

Para mover los elementos, vamos a iterar desde indice hasta longitud - 1 y copiar los valores de elementos[i + 1] a elementos[i].

Implementacion

int
array_eliminar (int indice, struct array *arr)
{
  if (!arr || !arr->elementos || indice < 0 || indice >= arr->longitud)
    return -1;

  int x = arr->elementos[indice];

  for (int i = indice; i < arr->longitud - 1; i++)
    arr->elementos[i] = arr->elementos[i + 1];
  arr->longitud--;

  return x;
}

De nuevo, tiene una complejidad de tiempo minima de \(O (1)\), y maxima de \(O (n)\).

Busqueda en un Array

Al momento de buscar un elemento de un array, podemos utilizar dos tipos de busqueda: busqueda linear y busqueda binaria.

Es importante tener en cuenta que para realizar operaciones de busqueda, no pueden haber elementos duplicados en un array, si hay elementos duplicados unicamente tendremos una copia del elemento.

Busqueda Linear

La busqueda linear, es cuando tenemos una llave (elemento por el que estamos buscando), y recorremos el array entero, por cada uno de sus elementos hasta encontrar una ocurrencia.

Si no se encuentra una ocurrencia, decimos que la busqueda no fue exitosa y se debe devolver un valor para reconocer que no hubieron ocurrencias.

• Implementacion

  int
  array_busqueda_linear (int llave, struct array arr)
  {
    if (!arr.elementos)
      return -1;
  
    for (int i = 0; i < arr.longitud; i++)
      {
        if (arr.elementos[i] == llave)
          return i;
      }
  
    return -1;
  }
  

• Complejidad de Tiempo

  La complejidad de tiempo de este metodo de busqueda es: minimo \(O(1)\) y maximo \(O(n)\). Para una busqueda que no fue exitosa, la complejdiad de tiempo siempre sera \(O(n)\) (porque necesita ir por todos los elementos del array.)

• Mejorando la Busqueda Linear

  Algo que podemos hacer, para mejorar el tiempo promedio de una busqueda linear, es que podemos mover elementos que hayan sido buscados antes un espacio hacia atras (mas cercanos a 0), por si vuelven a ser buscados en el futuro, disminuir asi la cantidad de comparaciones necesarias.

  Este metodo se llama transposicion.

• Implementacion

  void
  intercambiar (int *a, int *b)
  {
    if (!a || !b)
      return;
  
    int temp = *a;
    *a = *b;
    *b = temp;
  }
  
  int
  array_busqueda_linear_tpos (int llave, struct array *arr)
  {
    if (!arr || !arr->elementos)
      return -1;
  
    for (int i = 0; i < arr->longitud; i++)
      {
        if (arr->elementos[i] == llave)
          {
            /* transposicion */
            if (i != 0)
              intercambiar (&arr->elementos[i], &arr->elementos[i - 1]);
            return i;
          }
      }
  
    return -1;
  }
  

Busqueda Binaria ATTACH

Para hacer una busqueda binaria, los elementos del array deben estar organizados. Por ejemplo:

Como funciona la busqueda binaria, es que va a buscar por una llave en la mitad de una lista de elementos organizados, diviendola en la mitad.

• Ejemplo ATTACH

  Supongamos que nuestra llave es 6 (presente en el indice 2).

  Para realizar una busqueda binaria necesitamos tres variables: baja, alta y media. El valor de media es \([\frac{\text{baja} + \text{alta}}{2}]\), y siempre vamos a redondear al valor hacia abajo, es decir, si tenemos 2.1 usaremos el 2.

  Como funciona es que nuestra variable “baja” va a apuntar al inicio de la lista, “alta” al final y media a \([\frac{\text{baja} + \text{alta}}{2}]\):

  

  Y vamos a revisar si en nuestra media tenemos nuestra llave 6. En este caso, \(10 \ne 6, 6 < 10\). Como 6 es menor a 10, vamos a asignarle a alta el valor de media - 1, y no vamos a mover baja:

  

  Ahora miramos, es \(6 > 4\)? Si, 6 es mayor que 4, por lo que asignamos el valor de baja a media + 1 y volvemos a calcular media:

  

  Quedando con baja y media en 2, y ahora comparamos \(6 = 6\)? Si, hemos encontrado el valor que estabamos buscando.

• Busqueda No Exitosa

  Sabemos que una busqueda no es exitosa cuando \(\text{baja} > \text{alta}\), eso significa que el valor que estamos buscando no esta presente en la lista. Siempre baja debe estar a la izquierda de alta.

• Implementacion

  La implementacion para la busqueda binaria de forma iterativa es la siguiente:

  int
  array_busqueda_bin (int llave, struct array *arr)
  {
    if (!arr || !arr->elementos)
      return -1;
  
    int baja = 0, alta = arr->longitud-1, media = 0;
    while (baja <= alta)
      {
        media = (baja + alta) / 2;
        if (llave == arr->elementos[media])
          return media;
  
        if (llave < arr->elementos[media])
          alta = media - 1;
        else
          baja = media + 1;
      }
  
    return -1;
  }
  

  La complejidad de tiempo de la busqueda binaria es: minimo \(O(1)\) (si estamos buscando por el elemento en el indice media) o \(O(\log n)\) para los demas.

• Implementacion Recursiva

  La busqueda binaria tambien la podemos implementar de forma recursiva:

  int
  array_busqueda_bin_rec (int baja, int alta, int llave, int *elementos)
  {
    if (!elementos || baja > alta)
      return -1;
  
    int media = (baja + alta) / 2;
    if (llave == elementos[media])
      return media;
  
    if (llave < elementos[media])
      return array_busqueda_bin_rec (baja, media - 1, llave, elementos);
    else
      return array_busqueda_bin_rec (media + 1, alta, llave, elementos);
  
    return -1;
  }
  

  Como podemos ver, esta funcion es una funcion recursiva de cola, porque lo ultimo que hace es llamarse a si misma y no tiene que realizar ninguna otra operacion. Como mencionado anteriormente, las funciones recursivas de cola es mejor utilizar la version iterativa (con bucles), ya que su cumplejidad de espacio sera \(O(1)\).

Obtiendo un Elemento de un Array

Obtener un elemento en un indice especificado es una operacion bastante sencilla. Unicamente tenemos que verificar que el indice sea valido, y de serlo, obtener el elemento en esa posicion.

Implementacion

int
array_obtener (int indice, struct array arr)
{
  if (!arr.elementos || indice < 0 || indice >= arr.longitud)
    return -1;

  return arr.elementos[indice];
}

Como solo hay 2 pasos, la complejidad de tiempo es constante \(O(1)\).

Escribir un Elemento de un Array

Escribir o reescribir un elemento en un indice en especifico, solo debemos verificar que el indice sea valido y de serlo, escribir el valor de ese elemento.

Implementacion

void
array_set (int indice, int x, struct array *arr)
{
  if (!arr || !arr->elementos || indice < 0 || indice >= arr->longitud)
    return;

  arr->elementos[indice]= x;
}

Obteniendo el Elemento Maximo de un Array

Para encontrar el maximo elemento de un array que no este organizado (si ya esta organizado, el maximo va a ser o el primer o el ultimo elemento) tenemos que recorrer todos sus elementos.

Como funciona, es que se tendria una variable max cuyo valor inicial sera el de elementos[0], y se iterara por todos los elementos de la lista, si `elementos[i]

maxreescribiremos el valor demaxaelementos[i]`.

Implementacion

int
array_max (struct array arr)
{
  if (!arr.elementos)
    return -1;

  int max = arr.elementos[0];
  for (int i = 1; i < arr.longitud; i++)
    if (arr.elementos[i] > max)
      max = arr.elementos[i];

  return max;
}

Como recorrimos todos los elementos una vez, su complejidad de tiempo es \(O(n)\).

Obteniendo el Elemento Minimo de un Array

Para obtener el elemento minimo de un array, haremos lo mismo que hicimos con el maximo, pero estariamos haciendo una comparacion menor que, en lugar de mayor que.

Implementacion

int
array_min (struct array arr)
{
  if (!arr.elementos)
    return -1;

  int min = arr.elementos[0];
  for (int i = 1; i < arr.longitud; i++)
    if (arr.elementos[i] < min)
      min = arr.elementos[i];

  return min;
}

Invertir un Array

Para invertir un array tenemos dos metodos:

1. Utilizando un Array Auxiliar
2. Intercambiar los elementos del final con los del inicio del Array.

Utilizando un Array Auxiliar

Lo que haremos sera crear un array adicional, y vamos a copiar los elementos del primer array en orden inverso en el segundo, y los copiamos en el array original.

• Implementacion

  • Array Auxiliar

    void
    array_invertir1 (struct array *arr)
    {
      if (!arr || !arr->elementos)
        return;
    
      int b[arr->longitud] = { 0 };
      for (int i = arr->longitud - 1, j = 0; i >= 0; i--, j++)
        b[j] = arr->elementos[i];
    
      for (int i = 0; i > arr->longitud; i++)
        arr->elementos[i] = b[i];
    }
    

• Complejidad de Tiempo

  Para este metodo estamos copiando los elementos del array A al array B, eso tiene una complejidad de tiempo \(O(n)\), y para copiarlos de vuelta tiene una complejidad de \(O(n)\), entonces la complejidad total seria \(O(2n)\) y como el exponente mas grande es \(1\), decimos que la complejidad de tiempo es \(O(n)\).

Intercambiar Elementos

Para este metodo tendremos dos variables: i y j, i apuntara al inicio del array, j al final del array, y se intercambiaran los elementos A[i] con A[j].

• Implementacion

  void
  array_invertir2 (struct array *arr)
  {
    if (!arr || !arr->elementos)
      return;
  
    for (int i = 0, j = arr->longitud - 1; i < j; i++, j--)
      intercambiar (&arr->elementos[i], &arr->elementos[j]);
  }
  

• Complejidad de Tiempo

  Como vamos a estar realizando operaciones por cada elemento del array, decimos que la complejidad de tiempo es \(O(n)\).

Desplazamiento de un Array

Desplazar un Array es mover todos los elementos ya sea una posicion adicional a la derecha, o una posicion menos a la izquierda.

Implementacion

void
array_desplazar (struct array *arr)
{
  if (!arr || !arr->elementos)
    return;

  for (int i = 0; i < arr->longitud - 1; i++)
    arr->elementos[i] = arr->elementos[i + 1];
}

Complejidad de Tiempo

Como vamos a estar moviendo todos los elementos, exactamente una vez, decimos que la complejidad de tiempo es \(O(n)\).

Rotacion de un Array

La rotacion de un Array es similar a la del desplazamiento, la unica diferencia es que los elementos de los extremos (ya sea el primero o el ultimo) no se pierden, sino que son movidos al otro extremo.

Implementacion

void
array_rotar (struct array *arr)
{
  if (!arr || !arr->elementos)
    return;

  int primero = arr->elementos[0];
  for (int i = 0; i < arr->longitud - 1; i++)
    arr->elementos[i]= arr->elementos[i + 1];

  arr->elementos[arr->longitud - 1] = primero;
}

Complejidad de Tiempo

Como vamos a estar moviendo todos los elementos, exactamente una vez, decimos que la complejidad de tiempo es \(O(n)\).