Pagina para Basadxs

Estructuras de Datos

Estructuras de Datos

Introduccion

Podemos pensar en un programa como una serie de instrucciones que realizan acciones sobre datos. Sin datos, no tendriamos programas.

Estructuras de Datos

Una estructura de datos se puede definir como una coleccion de elementos sobre la que se realizan operaciones y se utiliza eficientemente.

Basicamente, es como se organizan datos en memoria (RAM).

Stack vs Heap

La memoria esta dividida por bytes, cada byte tiene una direccion y se almacenan de manera lineal.

La memoria esta dividida en tres secciones: la seccion code, el heap, y el stack.

La seccion code es donde estan almacenadas las instrucciones del programa.

Stack

En el siguiente programa:

int
main (void)
{
  int a = 0;
  float b = 0;

  return 0;
}

Esas dos variables seran almacenadas en el stack.

En el stack se va a crear un “activation record” o “stack frame” para cada funcion (una division del stack, donde unicamente las variables definidas dentro de el seran visibles.)

El tamano de memoria que se necesita para almacenar una variable se decide durante la compilacion del programa, por eso se llama gestion de memoria estatica.

Heap

La memoria en el heap puede ser gestionada de forma dinamica (puede ser creada, destruida, incrementada o disminuida).

A diferencia del stack, esta no se crea ni se destruye automaticamente.

Si no liberamos memoria que pusimos en el heap vamos a tener memory leaks (fugas de memoria.)

Para manejar el heap, utilizamos pointers.

Por ejemplo, si queremos un espacio en memoria para almacenar 5 enteros:

int *enteros = malloc (5 * sizeof (int));

Y manualmente tenemos que liberarla cuando no sea necesaria:

free (enteros);

Estructuras de Datos Fisicas vs Logicas

Las estructuras de datos se pueden categorizar como estructuras de datos fisicas y estructuras de datos logicas.

Estructuras de Datos Fisicas

Las estructuras de datos fisicas definen como la memoria esta organizada. Por ejemplo arrays y linked lists.

En los arrays la memoria es continua, el proximo elemento esta justo despues del anterior.

Estructuras de Datos Logicas

Las estructuras de datos logicas son formas organizadas de almacenar y manipular datos en memoria para su uso eficiente, independientemente de como se almacenen fisicamente.

Ejemplos de estructuras de datos logicas:

1. Stack
2. Queues
3. Trees
4. Graphs
5. Hash Tables

Los stacks y queues son estructuras de datos lineales, los trees y graphs son no-lineales, y las hash tables son estructuras de datos tabulares.

Complejidad de Espacio y de Tiempo

Complejidad de Tiempo

La complejidad de tiempo, es una manera de medir que tanto tiempo le toma a una maquina realizar una tarea.

Por ejemplo, si tenemos un array de \(n\) elementos (5, 10, 20, 100, 10000, etc), si queremos pasar por cada uno de estos elementos y nos preguntamos que tanto tiempo tomara hacerlo? Decimos que su complejidad de tiempo es \(n\). Es decir, si tenemos una lista, y estamos recorriendo sus elementos una sola vez, su complejidad de tiempo es \(O(n)\).

Si tenemos una lista, de \(n\) elementos y tenemos que recorrer esos elementos 2 veces, ahora su complejidad de tiempo es \(O(n^2)\).

Si tenemos que iterar sobre una lista \(\frac{n}{2}\) veces, su complejidad de tiempo seria \(O(\log n)\).

• Ejemplo 1

  Cual es la complejidad de tiempo de este bucle:

  for (int i = 0; i < n; i++)
    {
      /* operaciones aqui */
    }
  

  • Solucion

    \(O(n)\) porque apenas interamos \(n\) cantidad de veces.

• Ejemplo 2

  Cual es la complejidad de tiempo de este bucle:

  for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < n; j++)
        {
          /* operaciones aqui */
        }
    }
  

  • Solucion

    \(O(n^2)\) porque tenemos que iterar por todos los elementos dos veces.

• Ejemplo 3

  Cual es la complejidad de tiempo de esta funcion.

  for (int i = 0; i < n; j++)
    {
      for (int j = i + 1; j < n; j++)
        {
          /* operaciones aqui */
        }
    }
  

  • Solucion

    \(O(n^2)\) tambien, aunque en el segundo bucle \(j = i + 1\) estamos pasando \(n\) cantidad de veces, en dos veces.

• Ejemplo 4

  Cual es la complejidad de tiempo de esta funcion:

  int i = n;
  while (i > 1)
    {
      /* operaciones aqui */
  
      i = i / 2;
    }
  

  • Solucion

    \(O(\log n)\) porque estamos pasando \(\frac{n}{2}\) cantidad de veces.

Complejidad de Espacio

Cuando queremos saber cuanto espacio es consume en memoria durante la ejecucion de un programa, a eso le llamamos la complejidad de espacio.

Es importante saber que no estamos calculando el espacio en bytes, unicamente queremos saber en que depende el espacio que se utilice.

Si en un array hay \(n\) elementos, su complejidad de espacio es \(O(n)\).

Ejemplos con codigo

• Ejemplo 1

  int
  suma (int num[], int n)
  {
    int total = 0;
    for (int i = 0; i < n; i++)
      {
        total += num[n];
      }
    return total;
  }
  

  • Solucion

    Complejidad de tiempo: \(O(n)\)

• Ejemplo 2

  void
  suma (int **a, int **b, int **out, int n)
  {
    for (int i = 0; i < n; i++)
      {
        for (int j = 0; j < n; j++)
          {
            out[i][j] = a[i][j] + b[i][j];
          }
      }
  }
  

  • Solucion

    Complejidad de tiempo: \(O(n^2)\)

• Ejemplo 3

  void
  swap (int *x, int *y)
  {
    int temp = *x;
    *x = *y;
    *y = temp;
  }
  

  • Solucion

    Complejidad de tiempo: \(O(1)\). Es constante, unicamente se realizan 2 asignaciones siempre.

• Ejemplo 4

  Cual es la complejidad de tiempo de func1?

  void
  func2 ()
  {
    for (int i = 0; i < n; i++)
      {
        /* operaciones aqui */
      }
  }
  
  void
  func1 ()
  {
    func2();
  }
  

  • Solucion

    La complejidad de tiempo de func1 es \(O(n)\). Aunque apenas tengamos una sola instruccion, eso no lo hace \(O(1)\), porque esa instruccion es llamar a una funcion cuya complejidad de tiempo es \(O(n)\).

Recursion

Como Funciona la Recursion

Como Funcionan las Llamadas a una Funcion

Si tenemos un programa como el siguiente:

void
fun1 (int n)
{
  /* instruccion */
  /* instruccion */
  /* instruccion */
}

int
main (void)
{
  /* instruccion */
  /* instruccion */
  fun1 (x);
  /* instruccion */
  /* instruccion */
}

Cuando se ejecuta main, se van a ejecutar las instrucciones en orden (una despues de la otra), cuando llegue a la llamada de fun1, se van a ejecutar sus tres instrucciones, y el control del programa va a volver a main donde se van a ejecutar las dos instrucciones restantes (a menos que haya alguna otra operacion en esa linea, ya que se realizaria antes de pasar a la siguiente.)

A lo que se refiere con otra operacion, es por ejemplo si tenemos:

int a = fun1 (x) * 2;

La multiplicacion se va a realizar, una vez la ejecucion de fun1 haya terminado.

Recursion

Una funcion recursiva, es una funcion que se llama a si misma:

void
fun1 (/* parametros */)
{
  if (/* condicion base */)
    {
      fun1 (parametro);
    }
}

Algo importante sobre la recursion, es que siempre debe haber una condicion base que termine las llamadas recursivas, o se llamaria a si misma de forma infinita. Por eso, debe haber una condicion que haga que pare las llamadas recursivas.

Recursion tiene dos fases:

1. Calling phase: cuando la funcion se llama a si misma.
2. Returning phase: Cuando los resultados son pasados hacia arriba.

• Ejemplo 1

  void
  imprimir (int n)
  {
    if (n < 0)
      return;
  
    printf ("%d ", n);
    imprimir (n - 1);
  }
  

• Trazo 1 ATTACH

  

  Por eso tenemos como salida (3, 2, 1, 0).

• Ejemplo 2

  void
  imprimir2 (int n)
  {
    if (n < 0)
      return;
  
    imprimir2 (n - 1);
    printf ("%d ", n);
  }
  

• Trazo 2 ATTACH

  

  Por eso su salida es ahora (0, 1, 2, 3). Las impresiones se estan haciendo una vez terminen las llamadas recursivas, es decir, la ultima llamada va a ser la primera impresion.

Complejidad de Espacio: Recursion

La complejidad de espacio de la recursion es \(O(n)\), ya que por cada llamada se esta creando un record de activacion en el stack \(n + 1\) veces (mas la llamada donde no se cumple la condicion base.)

Complejidad de Tiempo: Recursion

La complejidad de tiempo de la recursion es \(O(n)\) ya que las unidades de tiempo que tomara finalizar una llamada recursiva, depende del numero de veces \(n\) que tenga que ser llamada.

Variables Globales y Estaticas en Recursion

Como las variables globales y estaticas estan almacenadas en una seccion especial de .code, no se creara por cada llamada recursiva, sino que su valor se mantendra.

Ejemplo

int
func (int n)
{
  static int x = 0;
  if (n <= 0)
    return 0;

  x++;
  return func (n - 1) + x;
}

Trazo ATTACH

Tail Recursion (Recursividad de Cola)

Una funcion con Recursividad de Cola, es aquella que se llama a si misma, y este llamado es la ultima instruccion de la funcion. Por ejemplo:

void
func (int n)
{
  if (n <= 0)
    return;

  printf ("%d ", n);
  func (n - 1);
}

Si la llamada recursiva fuese de la siguiente forma, no seria recursiva de cola:

func (n - 1) + n;

Porque aun tiene pendiente agregar n al resultado de la llamada recursiva.

Recursividad de Cola vs Bucles

Todas las funciones recursivas pueden ser escritas con bucles, y vice-versa. Convertir las funciones con recursividad de cola a bucles es mas facil:

void
fun_rec (int n)
{
  if (n <= 0)
    return;

  printf ("%d ", n);
  fun_rec (n - 1);
}

void
fun_buc (int n)
{
  while (n > 0)
    {
      printf ("%d ", n);
      n--;
    }
}

La complejidad de tiempo de ambas es de \(O(n)\).

La complejidad de espacio de la funcion recursiva es \(O(n)\) y la complejidad de espacio de la funcion con bucle es \(O(1)\).

Por eso, si se va a escribir una funcion con recursividad de cola, es mejor reescribirla como un bucle debido a la complejidad de espacio. Incluso, algunos compiladores detectan estas funciones, y las convierten a bucles como optimizacion.

Head Recursion (Recursion de Cabeza)

Cuando una funcion se llama a si misma, como primera instruccion de la funcion, decimos que es recursiva de cabeza:

void
func (int n)
{
  if (n <= 0)
    return;

  func (n - 1);
  printf ("%d ", n);
}

Si se debe realizar alguna operacion antes de la llamada recursiva, entonces no es una funcion con recursividad de cabeza. Dado este caso, la funcion seria unicamente recursiva, no se le daria ningun nombre especial.

Recursividad de Cabeza vs Bucles

Convertir una funcion de recursividad de cabeza a bucles es mas complicado que las funciones recursivas de cola. Si queremos que la salida del programa con bucles sea la misma a la del ultimo ejemplo recursivo (1, 2, 3), tendriamos la siguiente funcion:

void
func_rec (int n)
{
  if (n <= 0)
    return;

  func_rec (n - 1);
  printf ("%d ", n);
}

void
func_buc (int n)
{
  int i = 1;
  while (i <= n)
    {
      printf ("%d ", i);
      i++;
    }
}

Tree Recursion (Recursion de Arbol)

En la recursion tenemos dos posibilidades de hacer una llamada recursiva: de forma lineal, o por la recursion de arbol.

Recursion Lineal

Llamamos recursion lineal, a la funcion que se llama a si misma una unica vez:

void
fun (int n)
{
  if (n <= 0)
    return;

  /* instruccion */
  /* instruccion */
  fun (n - 1);
  /* instruccion */
}

Recursion de Arbol

Llamamos recursion de arbol, a la funcion que se llama a si misma mas de una vez:

void
fun (int n)
{
  if (n <= 0)
    return;

  /* instruccion */
  /* instruccion */
  fun (n - 1);
  /* instruccion */
  fun (n - 1);
  /* instruccion */
  /* instruccion */
}

Ahi la funcion fun esta siendo llamada en 2 ocasiones.

• Ejemplo

  void
  fun (int n)
  {
    if (n <= 0)
      return;
  
    printf ("%d ", n);
    fun (n - 1);
    fun (n - 1);
  }
  

• Trazo ATTACH

  

• Complejidad

  La complejidad de tiempo es \(O(2^n)\) y la complejidad de espacio es \(O(n)\).

Recursion Indirecta ATTACH

En la recursion indirecta, supongamos que tenemos 3 funciones: A, B y C:

En este ejemplo, A llama a B, B llama a C y C llama de nuevo a A.

Por ejemplo:

void A(int n);

void
B (int n)
{
  if (/* cond */)
    return;

  A (n - 1);
}

void
A (int n)
{
  if (/* cond */)
    return;

  B (n - 1);
}

Ejemplo

void fun2 (int n);

void
fun1 (int n)
{
  if (n <= 0)
    return;

  printf ("%d ", n);
  fun2 (n - 1);
}

void
fun2 (int n)
{
  if (n <= 1)
    return;

  printf ("%d ", n);
  fun1 (n / 2);
}

Trazo ATTACH

Recursion Anidada

En la recursion anidada, una llamada recursiva va a tomar otra llamada recursiva como parametro. Por ejemplo:

int
func (int n)
{
  if (/* condicion */)
    return;

  /* instruccion */
  /* instruccion */
  func (func (n - 1));
}

Ejemplo

int
func (int n)
{
  if (n > 100)
    return n - 10;
  return func (func (n + 11));
}

Trazo ATTACH

Ejemplos de Recursion

Suma de \(N\) Numeros Naturales Usando Recursion

Lo que queremos encontrar es \(1 + 2 + 3 + \cdots + n\).

Nosotros podemos definir esa funcion como:

\(\text{sum}(n) = 1 + 2 + 3 + \cdots + (n - 1) + n\)

Y recursivamente la podemos definir como:

\(\text{sum}(n) = \text{sum}(n - 1) + n\)

Y mas a fondo la podemos definir como:

\begin{equation} \text{sum}(n) = \begin{cases} 0 &\quad n = 0 \\ \text{sum}(n - 1) + n &\quad n > 0 \\ \end{cases} \end{equation}

• Funcion en C

  Desde que tengamos una definicion recursiva, facilmente podemos escribirlo en cualquier lenguaje que soporte recursion:

  int
  suma (int n)
  {
    if (n == 0)
      return 0;
    return suma (n - 1) + n;
  }
  

  Esta funcion tiene una complejidad de tiempo y de espacio \(O(n)\).

  Aunque para lograr lo mismo podemos utilizar la formula con complejidad de espacio y de tiempo \(O(1)\):

  \(\frac{n (n + 1)}{2}}\)

  Por lo que no es necesario utilizar la funcion recursiva.

  Tambien se puede hacer con un bucle con complejidad de tiempo \(O(n)\) y de espacio \(O(1)\):

  int
  suma (int n)
  {
    int s = 0;
    for (int i = 1; i <= n; i++)
      s += i;
    return s;
  }
  

• Trazo ATTACH

  

Factorial Usando Recursion

Un factorial (denotado por “!”) es definido como:

\(n! = 1 \times 2 \times 3 \times \cdots \times (n - 1) \times n\)

Entonces el factorial de 5:

\(5! = 1 \times 2 \times 3 \times 4 \times 5 = 120\)

Es importante tener en cuenta que \(0! = 1, 1! = 1\). Entonces, podemos definir esta funcion recursivamente como:

\begin{equation} \text{fact}(n) = \begin{cases} 1 &\quad n = 0\\ \text{fact}(n - 1) \times n &\quad n>0 \end{cases} \end{equation}

• Funcion en C

  La funcion que definimos anteriormente, la podemos escribir en codigo como:

  int
  fact (int n)
  {
    if (n == 0)
      return 1;
    return fact(n - 1) * n;
  }
  

  Escribir funciones recursivas es bastante sencillo una vez hayamos definido una formula.

  Similar a la suma de \(N\) numeros naturales, esta tiene una complejidad de tiempo y de espacio \(O(n)\) y puede ser escrita de forma iterativa para tener una complejidad de tiempo \(O(n)\) y de espacio \(O(1)\):

  int
  fact (int n)
  {
    int fac = 1;
    for (int i = 1; i <= n; i++)
      {
        fac *= i;
      }
    return fac;
  }
  

Funcion Exponencial \(m^n\) Usando Recursion

Nosotros podemos definir la funcion exponencial como:

\(m^n = m \times m \times m \times m \times \cdots \times \text{n veces}\)

Y la podemos definir recursivamente como:

\begin{equation} \text{exp}(m, n) = \begin{cases} 1 &\quad n = 0 \\ \text{exp}(m, n - 1) \times m &\quad n > 0 \end{cases} \end{equation}

• Funcion en C

  La funcion anteriormente definida la podemos escribir en C como:

  int
  exp (int m, int n)
  {
    if (n == 0)
      return 1;
    return exp(m, n - 1) * m;
  }
  

• Optimizaciones

  Esta funcion, esta realizando muchas multiplicaciones cuando podria ser simplificada, por ejemplo:

  \(2^8 = (2^2)^4 = (2 \times 2)^4\)

  Ahi pasaremos de usar 8 multiplicaciones a hacer 4 multiplicaciones.

  \(2^9 = 2 \times (2 \times 2)^4\)

  Si la potencia es un numero par podemos dividirla entre dos, si es impar tenemos que realizar una multiplicacion de mas. La nueva funcion quedaria como:

  int
  exp (int m, int n)
  {
    if (n == 0)
      return 1;
  
    /* si el exponente es par */
    if (n % 2 == 0)
      return exp (m * m, n / 2);
  
    /* restamos 1 para que el expontente sea par */
    return m * exp (m * m, (n - 1) / 2);
  }
  

• Trazo ATTACH

  Con la funcion exp original, hacer exp (2, 9) nos tomaria 9 multiplicaciones.

  

  En este trazado nos toma 6 multiplicaciones, en lugar de las 9 que nos tomaria con la otra funcion.

Sucesion de Fibonacci

La serie de fibonacci es la siguiente:

\(\text{0 1 1 2 3 5 8 13}\cdots\)

Cada uno de los terminos es obtenido con la suma de los dos terminos anteriores. Por ejemplo: \(1 + 1 = 2\), \(2 + 3 = 5\), \(5 + 8 = 13\), etc.

Los terminos iniciales son 0 y 1, mientras que los demas terminos son obtenidos con la suma de los dos terminos anteriores.

Matematicamente lo podemos definir como:

\begin{equation} \text{fib}(n) = \begin{cases} 0 &\quad n =0 \\ 1 &\quad n = 1\\ \text{fib}(n - 2) + \text{fib}(n - 1) &\quad n > 1 \end{cases} \end{equation}

• Funcion en C

  Para obtener el \(n\) termino de la sucesion de fibonacci, podemos usar nuestra definicion recursiva:

  int
  fib (int n)
  {
    if (n <= 1)
      return n; /* n = 0 || n = 1 */
    return fib (n - 2) + fib (n - 1);
  }
  

  La complejidad de tiempo de esta funcion es \(O(2^n)\).

• Funcion Iterativa

  Si queremos escribir esa funcion de forma iterativa, lo podemos hacer de la siguiente manera:

  int
  fib (int n)
  {
    int t0 = 0, t1 = 1, sum = 0;        /* termino 0, termino 1, suma */
    if (n <= 1)
      return n; /* n == 0 devuelva 0, n == 1 devuelva 1 */
  
    for (int i = 2; i <= n; i++)
      {
        sum = t0 + t1;
        t0 = t1;
        t1 = sum;
      }
  
    return sum;
  }
  

  Esta funcion iterative tiene una complejidad de espacio \(O(1)\) y de tiempo \(O(n)\).

• Trazo ATTACH

  Para fib(5) tendriamos:

  

• Optimizacion ATTACH

  Si revisamos el trazo, la funcion \(\text{fib}(3)\) es llamada en 2 ocasiones, de igual forma, \(\text{fib}(2)\) es llamada en 3 ocasiones, y tambien \(\text{fib}(0)\), \(\text{fib}(1)\) se llaman varias veces.

  Una funcion recursiva que se llama a si misma varias veces, por los mismos valores se llama recursion excesiva. Esta implementacion de la sucesion de fibonacci es una recursion excesiva.

  Para evitar esto podemos utilizar un array global, que todos sus valores se inicialicen a \(-1\). Y por cada llamada se haria array[n] = fib(n).

  El trazo seria el siguiente:

  

  Asi pasamos de 15 llamadas a 6. Pasando de una complejidad de tiempo \(O(2^n)\) a \(O(n)\).

  Esta tecnica, la de almacenar valores ya conocidos en un arreglo se llama Memoizacion.

• Implementacion en C

  int F[10];
  
  int
  fib (int n)
  {
    if (n <= 1)
      {
        F[n] = n;
        return n;
      }
  
    if (F[n - 2] == -1)
      F[n - 2] = fib (n - 2);
  
    if (F[n - 1] == -1)
      F[n - 1] = fib (n - 1);
  
    return F[n - 2] + F[n - 1];
  }
  

  Notese que el array no esta inicializado a -1, ese es solo un ejemplo.

La Torre de Hanoi ATTACH

El problema de la torre de hanoi es el siguiente:

Fuente: www.mathsisfun.com

Hay una cantidad \(n\) de discos en una torre A (de tres torres: A, B y C). El problema, es que debemos mover todos los discos de la torre A a la torre C y tenemos 2 reglas para hacerlo:

1. Unicamente podemos mover un disco a la vez.
2. No puede haber un disco mas grande sobre uno mas pequeno.

Siguiendo esas reglas tenemos que mover los \(n\) discos de torrea A a torre C.

• Algoritmo recursivo

  • 1 Disco ATTACH

    Si tenemos un unico disco:

    

    Podemos unicamente mover ese disco de A a C:

    

    Entonces si tenemos:

    \(\text{TOH}(1, A, B, C) = \text{Mover disco de A a C usando B}\)

    El orden de esa funcion es “Torre de Hanoi, usando 1 disco, movemos de la torre A a la torre C, usando la torre B”.

    El primer parametro son el numero de discos, el segundo es la torre inicial, el cuarto es la torre final, y el tercero es la torre intermedia.

  • 2 Discos ATTACH

    Si ahora tenemos dos discos:

    

    Podemos mover el disco mas pequeno a B:

    

    Movemos el disco de la torre A a la torre C:

    

    Y por ultimo movemos el disco de la torre B a la torre C.

    Tendriamos una funcion de 3 pasos:

    \(\text{TOH}(2, A, B, C):\)

    1. \(\text{TOH}(1, A, C, B)\): Movemos un disco de la torre A a la torre B, usando la torre C.
    2. Movemos un disco de la torre A a la torre C, usando la torre B (el mismo paso que hicimos al mover un solo disco.)
    3. \(\text{TOH} (1, B, A, C)\): Movemos un disco de la torre B a la torre C, usando la torre A.

  • 3 Discos

    Si tenemos \(\text{TOH}(3, A, B, C)\) podemos utilizar el paso anterior, para mover dos discos de A a B, mover el disco de A a C, y los dos discos restantes de B a C:

    \(\text{TOH}(3, A, B, C)\)

    1. \(\text{TOH}(2, A, C, B)\): movemos dos discos usando los 3 pasos anteriores.
    2. Movemos un disco de A a C
    3. \(\text{TOH}(2, B, A, C)\): movemos dos discos usando los 3 pasos anteriores.

  • Procedimiento

    Con el procedimiento de los 3 discos nos podemos hacer una idea para N cantidad de discos:

    \(\text{TOH}(n, A, B, C)\):

    1. \(\text{TOH}(n - 1, A, C, B)\)
    2. Mover un disco de A a C
    3. \(\text{TOH}(n - 1, B, A, C)\)

  • Funcion en C

    Este problema lo podemos escribir en C de la siguiente manera:

    void
    TOH (int n, int A, int B, int C)
    {
      if (n <= 0)
        return;
    
      TOH (n - 1, A, C, B);
      printf ("Mover de %d a %d usando %d\n", A, C, B);
      TOH (n - 1, B, A, C);
    }
    

  • Trazo ATTACH

    

    Segun ese trazo, los pasos son:

    1. Disco de 1 a 3
    2. Disco de 1 a 2
    3. Disco de 3 a 2
    4. Disco de 1 a 3
    5. Disco de 2 a 1
    6. Disco de 2 a 3
    7. Disco de 1 a 3

    En total, hizo 15 llamadas (hay 8 llamadas que no se realizaron porque \(n \le 0\)) para 3 discos.

    La complejidad de tiempo de esta funcion es \(O(2^n)\).

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)\).

Linked List ATTACH

Una linked list es una coleccion de nodos, donde cada uno de estos nodos contiene algun tipo de informacion, y un pointer hacia el siguiente nodo. La podemos definir graficamente de la siguiente manera:

Al primer nodo le llamamos head (cabeza), y al ultimo, el que no apunta a ningun otro nodose llama tail (cola).

Las linked lists son definidas en el heap.

Linked List vs Array

A diferencia de los array, la memoria en un linked list no es contigua, es decir, un elemento no esta proximo al anterior, sino que cada una esta en su propia direccion de memoria, y se mantiene la continuidad de la lista por medio de enlaces (pointers).

Definiendo la Estructura

Necesitamos definir dos estructuras: la de los nodos, y la de la lista en general.

Nodo

La estructura del nodo, va a tener dos elementos: un entero que va a ser el que almacene los datos, y un pointer al proximo nodo.

struct nodo
{
  int dato;
  struct nodo *next;
};

La estructura del nodo hace referencia a si misma para el pointer de next.

Y podemos usar esa estructura de la siguiente manera:

struct nodo *a = calloc(1, sizeof(*a));
c->dato = 10;

struct nodo *b = calloc(1, sizeof(*b));
b->dato = 20;
c->next = b;

Asi estamos creando una lista con dos nodos: a y b, y el proximo elemento de a es b.

Mostrando la Linked List ATTACH

Supongamos que tenemos la linked list:

a->dato = 8;
a->next = b;

b->dato = 10;
b->bext = c;

c->dato = 12;
c->next = d;

d->dato = 14;
d->next = e;

e->dato = 16;
e->next = NULL;

Primero, necesitamos recorrer la linked list. Una forma en que podemos hacer esto es la siguiente:

struct node *actual = a;
while (actual)
  {
    /* realizar operaciones */
    actual = actual->next;
  }

Como no sabemos exactamente cuantos nodos hay, usamos un while loop.

Ahora, para imprimir la linked list, unicamente tenemos que recorrerla e imprimir actual->dato:

void
linked_list_imprimir (struct nodo *primero)
{
  if (!primero)
    return;

  struct nodo *n = primero;
  while (n)
    {
      printf ("%d\n", n->dato);
      n = n->next;
    }
}

Mostrando una Linked List de Forma Recursiva

La manera en que podemos implementar la misma funcion de mostrar una linked list, pero de forma recursiva es la siguiente: vamos a tener una funcion que acepta un struct nodo *, y la primera instruccion que ejecuta es la de revisar que nodo != NULL, y dado el caso que esta sea cierta, se imprime el contenido nodo->dato y llamamos mostrar_recursiva(nodo->next):

void
linked_list_mostrar_recursiva (struct nodo *nodo)
{
  if (!nodo)
    return;

  printf ("%d\n", nodo->dato);
  mostrar_recursiva (nodo->next);
}

Tanto con la implementacion recursiva como con la iterativa la complejidad de tiempo de ambas es de \(O(n)\), ya que el numero de repeticiones depende del numero de elementos. Por eso, es que siempre que una operacion traverse una lista de elementos, su complejidad de tiempo va a ser \(O(n)\).

Como ya sabemos, la complejidad de espacio de las funciones recursivas cuando se traversa una lista es \(O(n)\), por lo que la complejidad de espacio de la funcion recursiva es \(O(n)\) y el tamano del estack sera \(n + 1\).

Contando los Nodos de una Linked List

Para esto vamos a necesitar traversar la linked list hasta llegar al ultimo elemento, y agregar 1 a la cantidad de nodos que hemos contado:

int
linked_list_contar (struct nodo *nodo)
{
  if (!nodo)
    return;

  int cantidad = 0;
  struct nodo *actual = nodo;
  while (actual)
    {
      cantidad++;
      actual = actual->next;
    }

  return cantidad;
}

Como por esta funcion estamos pasando por cada uno de los nodos de la linked list, decimos que la complejidad de tiempo es \(O(n)\), y la complejidad de espacio es \(O(1)\) ya que aunque tengamos 300 elementos, tendremos las mismas tres variables: cantidad, actual y nodo.

Esta funcion la podemos implementar de forma recursiva de la siguiente manera:

int
linked_list_contar_recursiva (struct nodo *nodo)
{
  if (!nodo)
    return 0;
  return linked_list_contar_recursiva (nodo->next) + 1;
}

Buscando en una Linked List

Nosotros no podemos hacer una busqueda binaria en una linked list, ya que no hay manera directa de ir a la mitad de ella, siempre tenemos que traversar desde el primer nodo, que toma \(O(n)\) de tiempo. Como no podemos llegar a la mitad de una linked list con una complejidad de tiempo constante, la busqueda binaria no queda bien con las Linked Lists.

Una funcion sencilla para buscar seria la siguiente:

struct nodo *
linked_list_buscar1 (int valor, struct nodo *nodo)
{
  if (!nodo)
    return NULL;

  struct nodo *actual = nodo;
  while (actual)
    {
      if (actual->dato == valor)
        return actual;

      actual = nodo->next;
    }

  return NULL;
}

Y la misma funcion de forma recursiva seria:

struct nodo *
linked_list_buscar_recursiva (int valor, struct nodo *nodo)
{
  if (!nodo)
    return NULL;

  if (nodo->dato == valor)
    return nodo;
  return linked_list_buscar_recursiva (valor, nodo->next);
}

Mejorando la Busqueda

Como ya lo vimos con los Arrays, podemos mejorar la busqueda para que la proxima vez que se busque se haga en menos tiempo utilizando:

1. Transposicion (mover un elemento a posicion - 1)
2. Move to head (hacerlo el primer elemento)

Para hacer el move to head necesitamos modificar 3 nodos:

• El primero de la linked list.
• El nodo que estaremos moviendo.
• Y el nodo anterior al que estamos moviendo, ya que debe apuntar a otro nodo.

Para hacerlo, en lugar de tener un solo pointer actual sino que tambien vamos a tener uno anterior que va a apuntar al nodo anterior a actual:

struct nodo *
linked_list_buscar2 (int valor, struct nodo **nodo)
{
  if (!nodo)
    return NULL;

  struct nodo *actual = *nodo;
  struct nodo *anterior = NULL;

  while (actual)
    {
      if (actual->dato == valor)
        {
          anterior->next = actual->next;
          actual->next = *nodo;
          *nodo = actual;
        }

      anterior = actual;
      actual = actual->next;
    }

  return NULL;
}

Insertando en una Linked List

Para insertar en una linked list tenemos dos posibilidades:

1. Insertar antes del primer nodo (volviendolo el head.)
2. Insertar en una posicion indicada.

Dado el caso que fuera la primer situacion, que vamos a volver el nuevo nodo el head, tendriamos que seguir los siguientes pasos:

1. Se crea un nuevo nodo con el valor especificado como dato.
2. Este nuevo nuevo nodo->next debe ser la direccion del primer nodo.
3. Modificamos la direccion del primer nodo haciendola el nuevo nodo.

Como siempre van a ser los mismos tres pasos en esta situacion, decimos que la complejidad de tiempo para insertar un nodo en la primer posicion es de \(O(0)\).

Si, en cambio, quisieramos agregar un nodo en una posicion x necesitaremos:

1. Crear un nuevo nodo con el valor especificado como dato.
2. Tomamos un pointer p que se va a desplazar por posicion - 1 veces (ya que tomamos el cero como volverlo el head de la linked list.)
3. El nodo->next del nuevo nodo, debe apuntar al siguiente nodo de la posicion indicada.
4. El nodo anterior a la posicion indicada debe apuntar como next al nuevo nodo.

La complejidad de tiempo de esta situacion es \(O(n)\), con una complejidad de tiempo minima de \(O(1)\).

Implementacion

Lo anteriormente descrito puede implementarse como:

void
linked_list_insertar (int pos, int valor, struct nodo **primero)
{
  if (!primero)
    return;

  struct nodo *nuevo = NULL, *p = *primero;
  if (pos == 0)
    {
      nuevo = calloc (1, sizeof (*nuevo));
      nuevo->dato = valor;
      nuevo->next = p;
      *primero = nuevo;

      return;
    }

  for (int i = 0; i < pos - 1 && p; i++)
    p = p->next;

  if (!p)
    return;

  nuevo = calloc (1, sizeof (*nuevo));
  nuevo->dato = x;
  nuevo->next = p->next;
  p->next = nuevo;
}

Insertando en una Linked List Ordenada

Para insertar un elemento de forma ordenada en una linked list que ya esta ordenada, tomariamos un pointer p, pasamos por cada uno de los elementos para ver si p->dato < valor. Si esa condicion no se cumple, quiere decir que este nuevo nodo debe ir en el nodo anterior a p:

void
linked_list_insertar_ordenada (int valor, struct nodo **primero)
{
  struct nodo *actual = *primero, *anterior = NULL;

  struct nodo *nuevo = calloc (1, sizeof (*nuevo));
  nuevo->dato = valor;
  nuevo->next = NULL;

  if (!primero)
    {
      *primero = nuevo;
      return;
    }

  while (actual && actual->dato < x)
    {
      anterior = actual;
      actual = actual->next;
    }

  if (actual == *primero)
    {
      nuevo->next = *primero;
      *primero = nuevo;
      return;
    }

  nuevo->next = anterior->next;
  anterior->next = nuevo;
}

La complejidad de tiempo de esta funcion es: minimo \(O(1)\) y en promedio \(O(n)\).

Eliminando de una Linked List

Al momento de eliminar tenemos que tomar en cuenta dos posibles escenarios:

1. Cuando vamos a eliminar el primer nodo.
2. Cuando vamos a eliminar un nodo en una ubicacion especifica.

Cuando vamos a eliminar el primer nodo, necesitaremos mover el pointer del primer nodo, al siguiente nodo. IMPORTANTE: al hacer esto aunque el nodo queda inutilizable porque ya no podra ser accedido en la linked list, sigue existiendo en el heap, por lo que es muy importante liberar ese espacio en memoria.

Para eliminar el primer nodo necesitaremos otro pointer p que apunta al primer nodo, haremos que el primer nodo apunte a primero->next y liberamos p. La complejidad de tiempo de este caso es de \(O(1)\).

Para eliminar de una posicion, unicamente tenemos que traversar la linked list hasta esa posicion, hacemos que (posicion - 1)->next = posicion->next y liberamos la memoria del nodo en posicion. La complejidad de tiempo de este caso es de minimo \(O(1)\) y maximo \(O(n)\).

Implementacion

int
linked_list_eliminar (int pos, struct nodo **primero)
{
  if (!primero)
    return -1;

  struct nodo *actual = *primero, *anterior = NULL;
  int x = 0;
  if (pos == 1)
    {
      x = *primero->dato;
      actual = *primero;
      *primero = *primero->next;
      free (actual);

      return x;
    }

  for (int i = 0; i < pos - 1 && actual; i++)
    {
      anterior = actual;
      actual = actual->next;
    }

  if (!actual)
    return -1;

  anterior->next = actual->next;
  x = actual->dato;
  free (actual);

  return x;
}

Checar si una Linked List esta Ordenada

Para revisar si una linked list esta ordenada o no (en orden ascendiente, el menor primero) vamos a necesitar dos pointers: uno para el nodo actual, y otro para el nodo anterior. Utilizando estos dos pointers, por cada nodo vamos a revisar si actual->dato > ~anterior->dato si esa condicion se cumple hasta llegar al final de lista, significa que la lista esta ordenada.

_Bool
linked_list_esta_ordenada (struct nodo *primero)
{
  if (!primero || !primmero->next)
    return 0;

  struct nodo *anterior = primero;
  struct nodo *actual = primero->next;
  while (actual)
    {
      if (actual->dato < anterior->dato)
        return 0;

      anterior = actual;
      actual = actual->next;
    }

  return 1;
}

La complejidad de tiempo minima es \(O(1)\) y la complejidad de tiempo maxima es \(O(n)\).

Remover Duplicados de una Linked List Ordenada

Para remover duplicados de una Linked List ordenada, vamos a necesitar dos pointers actual y anterior y vamos a estar revisando si si el dato de ambos nodos es igual. Dado el caso que lo sea vamos a poner el next de anterior a actual->next, vamos a hacerle free a actual y hacer actual = anterior->next:

void
linked_list_remover_duplicados (struct nodo *primero)
{
  if (!primero)
    return;

  struct nodo *actual = primero;
  struct nodo *anterior = NULL;

  while (actual)
    {
      if (actual->dato == anterior->Dato)
        {
          anterior->next = actual->next;
          free (actual);
          actual = anterior->next;
          continue;
        }

      anterior = actual;
      actual = actual->next;
    }
}

Invirtiendo Linked List

Para invertir una linked list podemos hacerlo de dos maneras:

1. Invirtiendo los elementos.
2. Invirtiendo los enlaces.

Invirtiendo los Elementos

Invertir los elementos, es hacer que ultimo->dato = primero->dato y asi suscesivamente, estaremos cambiando el valor de dato.

Una de las maneras en que podemos implementar esta manera, es creando un array de la misma longitud que elementos en la linked list, e iterar la lista e ir agregando nodo->dato a este array. Al lllegar al final de la lista, iteramos de nuevo desde el inicio, y le asignaremos el valor a los nodos de forma decresciente como valores en el array:

void
linked_list_invertir1 (struct nodo *primero)
{
  if (!primero)
    return;

  int *array = calloc(array_list_contar (primero), sizeof (int));
  if (!array)
    return;

  struct nodo *actual = primero;
  int i = 0;
  while (actual)
    {
      array[i++] = actual->dato;
      actual = actual->next;
    }

  actual = primero;
  i--;

  while (actual)
    {
      actual->dato = array[i--];
      actual = actual->next;
    }
}

La complejidad de tiempo es \(O(n)\).

Invirtiendo los Enlaces ATTACH

Al invertir los enlaces, no se estaria cambiando el valor de dato sino que la direccion del ultimo nodo seria la del primero, la del penultimo la del segundo, y asi suscesivamente.

Para revertir los enlaces de una llinked list vamos a necesitar 3 pointers: p, q y r. Vamos a revertir la linked list cambiando 3 nodos a la vez, y estos se van a estar siguiendo, uno despues del otro:

Haciendolo de esa manera.

Despues, vamos a hacer que el nodo q->next = r.

En el primer paso q->next va a ser puesto como NULL:

Quedando asi en el segundo paso:

Y asi suscesivamente:

void
linked_list_invertir2 (struct nodo **primero)
{
  if (!primero)
    return;

  struct nodo *p = *primero;
  struct nodo *q = NULL;
  struct nodo *r = NULL;

  while (p)
    {
      r = q;
      q = p;
      p = p->next;

      q->next = r;
    }

  *primero = q;
}

Siguiendo esos pasos la linked list queda invertida:

Generalmente se prefiere invertir los enlaces antes que el contenido de los nodos, porque no sabemos cual sera el contenido de estos, aunque en estos ejemplos sean enteros, pueden ser estructuras enteras, o clases en C++.

Invirtiendo de Forma Recursiva

Para implementar esta funcion de forma recursiva, vamos a necesitar dos pointers: p y q, y q va a ser el anterior a p para asi poder hacer la inversion (que se hara en return time).

void
linked_list_invertir_recursiva(struct nodo *q, struct nodo **p)
{
  if (*p)
    {
      linked_list_invertir_recursiva (*p, &(*p)->next);
      (*p)->next = q;
    }
  else
    {
      *p = q;
    }
}

Concatenando 2 Linked Lists

Concatenar 2 linked lists significa unirlas. Para hacerlo, unicamente tenemos que traversar la linked list hasta el final, y el ultimo nodo next va a apuntar al primer nodo de la segunda linked list:

void
linked_list_concatenar (struct nodo *a, struct nodo *b)
{
  if (!a || !b)
    return;

  struct nodo *p = a;
  while (p)
    p = p->next;
  p->next = b;
}

La complejidad de tiempo es \(O(n)\).

Uniendo 2 Linked Lists

Ahora, vamos a unir 2 linked lists ordenadas para que hagan una sola linked list ordenada.

Para hacer esto vamos a usar 2 pointers, y vamos a estar comparando cada uno de los nodos para ver cual es el mayor, y vamos a estar cambiando los next con la ayuda de estos dos pointers:

struct nodo *
linked_list_unir_ordenada (struct nodo *a, struct nodo *b)
{
  if (!a || !b)
    return NULL;

  /* paso 1: inicializar los pointers */
  struct nodo *ultimo = NULL;
  struct nodo *lista = NULL;

  /* hacer la primer comparacion */
  if (a->dato > b->dato)
    {
      lista = ultimo = a;
      a = a->next;
      ultimo->next = NULL;
    }
  else
    {
      lista = ultimo = b;
      b = b->next;
      ultimo->next = NULL;
    }

  /* comparar cada uno de los elementos */
  while (a && b)
    {
      if (a->dato < b->dato)
        {
          ultimo->next = a;
          ultimo = a;
          a = a->next;
          ultimo->next = NULL;
        }
      else
        {
          ultimo->next = b;
          ultimo = b;
          b = b->next;
          ultimo->next = NULL;
        }
    }

  /* si quedan elementos en una de las linked lists, agregarlos al ultimo
   * nodo */
  if (a)
    ultimo->next = a;
  else if (b)
    ultimo->next = b;

  return lista;
}

Revisar si una Linked List tiene Bucles

Un bucle en una linked list, es cuando el ultimo elemento next apunta a otro elemento dentro de la linked list (no tiene que ser el primero), haciendo que esta no sea linear.

Para revisar si una linked list tiene un bucle, podemos utilizar dos pointers p y q. Vamos a travesar la linked list y p se va a mover un nodo a la vez, y q se va a mover dos nodos a la vez, dado el caso que llegase a haber un bucle, en algun punto estos dos pointers van a ser el mismo nodo:

_Bool
linked_list_bucle (struct nodo *n)
{
  if (!n)
    return 0;

  struct nodo *p, *q;
  p = q = n;

  do {
    p = p->next;
    q = q->next;
    q = q ? q->next : NULL;
  } while (p && q && p != q);

  if (p == q)
    return 1;
  return 0;
}

Linked List Circular ATTACH

Una linked list circular es cuando el ultimo elemento de la linked list, apunta al primer elemento de la lista.

En estas listas no llamamos ningun elemento primero o ultimo, sino que usamos los terminos head y tail

Si en una linked list circular hay un solo elemento, este debe apuntar a si mismo.

Podemos tener dos representaciones de una linked list circular:

Imprimiendo una Linked List Circular

Para imprimir una linked list circular vamos a traversar todos los elementos, tal como hicimos con la linked list linear, solo que ahora la condicion para salir del bucle es revisar que p no sea igual a head:

void
linked_list_circular_imprimir (struct nodo *n)
{
  if (!n)
    return;

  struct nodo *p = n;
  do {
    printf ("%d\n", p->dato);
    p = p->next;
  } while (p != n);
}

Para implementar esta misma funcion de forma recursiva vamos a necesitar una variable que llamaremos flag y la utilizaremos en la condicion recursiva.

void
linked_list_circular_imprimir_recursiva (struct nodo *n, struct nodo *head)
{
  static int flag = 0;
  if (n != head || flag == 0)
    {
      flag = 1;
      printf ("%d\n", n->dato);
      linked_list_circular_imprimir_recursiva (n->next, head);
    }
  flag = 0;
}

Esta nos va a servir para poder hacer llamada recursiva la primera vez que p = head, pero evitar que se repita la segunda vez que esta condicion se cumple.

Creando una Linked List Circular a partir de un Array

Para crear una linked list circular a partir de un array podemos hacer una funcion similar a la siguiente:

struct nodo *
linked_list_circular_crear (int *a, int n)
{
  if (!a)
    return NULL;

  struct nodo *head = NULL, *t = NULL, *last = NULL;
  head = calloc (1, sizeof (*head));
  head->data = a[0];
  head->next = head;
  last = head;

  for (int i = 1; i < n; i++)
    {
      t = calloc (1, sizeof (*t));
      t->data = a[i];
      t->next = last->next;
      last->next = t;
      last = t;
    }
}

Asi, el primer nodo que agreguemos despues de crear head su next va a estar apuntando a head y gracias a last todos los nodos que se vayan agregando tambien van a tener el next de head si son el ultimo nodo.

Insertando en una Linked List Circular

Para insertar en una linked list circular, tendremos en cuenta dos situaciones:

1. Insertar antes de head.
2. Insertar en una posicion dada.

Insertar antes de head: para insertar un nodo antes de head, necesitaremos crear un nuevo nodo, poner su next que sea head y traversar la lista hasta llegar al ultimo nodo (sabremos que hemos llegado cuando nodo->next = head) y hacer que el next del ultimo nodo sea el nuevo nodo que hemos creado.

Insertar en una posicion dada: para insertar en una posicion n (empezando a contar desde 1, ya que la posicion 0 sera para hacerlo el head) lo que haremos sera iterar n-1 veces en la linked list para obtener un pointer al nodo anterior, y hacer que el nuevo nodo next sea nodo_anterior->next y que el next del nodo anterior sea el nuevo nodo.

Esta situacion toma \(O(1)\) complejidad de tiempo minima, y \(O(n)\) complejidad de tiempo maxima.

struct nodo *
linked_list_circular_insertar (int dato, int pos, struct nodo *l)
{
  if (!l || pos < 0)
    return NULL;

  struct nodo *n = calloc (1, sizeof (*n));
  n->dato = dato;

  if (pos == 0)
    {
      n->next = l;

      struct nodo *p = l;
      while (p->next != l)
        p = p->next;

      p->next = t;
      /* opcional: cambiar head, aunque no es necesario */

      return n;
    }

  struct nodo *p = l;
  for (i = 0; i < pos - 1 && p; i++)
    p = p->next;

  n->next = p->next;
  p->next = n;

  return n;
}

Eliminando un Nodo de una Linked List Circular

Para eliminar un nodo de una linked list circular debemos tomar en cuenta dos situaciones:

1. Si vamos a eliminar el head.
2. Si vamos a eliminar un nodo de una posicion dada.

Eliminar head: para eliminar head vamos a necesitar un pointer p que apunte al ultimo elemento de la lista, vamos a hacer que su next sea head->next, y eliminamos head.

Eliminar un nodo en una posicion dada: para eliminar un nodo de una posicion x vamos a necesitar dos pointers: uno que apunte al nodo posicion - 2 y otro que apunte al nodo posicion - 1, los vamos a llamar p y q respectivamente. Una vez tengamos estos dos pointers, vamos a asignar p->next = q->next y ahora si podemos eliminar el nodo q.

int
linked_list_circular_eliminar (int pos, struct nodo **head)
{
  if (!head || pos < 0)
    return -1;

  if (pos == 1)
    {
      struct nodo *p = *head;
      while (p->next != *head)
        p = p->next;

      int x = *(head)->data;
      if (p == *head)
        {
          free (*(head));
          *head = NULL;

          return x;
        }

      p->next = *(head)->next;
      free (*(head));
      *head = p->next;

      return x;
    }

  struct nodo *p = *head;
  for (int i = 0; i < pos - 2 && p; i++)
    p = p->next;

  struct nodo *q = p->next;
  p->next = q->next;
  int x = q->data;
  free (q);

  return x;
}

Linked List Doble

Una Linked List Simple los nodos van a tener un pointer al siguiente nodo, en una linked list doble tambien van a tener un pointer al nodo anterior:

struct nodo_doble
{
  int dato;
  struct nodo_doble *prev;
  struct nodo_doble *next;
};

Podemos definir una funcion para crear una linked list doble a partir de un array de la siguiente manera:

struct nodo_doble *
linked_list_doble_crear (int *a, int n)
{
  if (!a)
    return NULL;

  struct nodo_doble *lista = NULL;
  struct nodo_doble *t = NULL, *ultimo = NULL;

  lista = calloc (1, sizeof (*lista));
  lista->dato = a[0];
  lista->prev=lista->next=NULL;
  ultimo = lista;

  for (int i = 1; i < n; i++)
    {
      t = calloc (1, sizeof (*t));
      t->dato = a[i];
      t->next = ultimo->next;
      t->prev = ultimo;
      ultimo->next = t;
      ultimo = t;
    }
}

Y para mostrar una linked list, lo haremos de la misma forma en que lo hicimos con una linked list simple:

void
linked_list_doble_imprimir (struct nodo_doble *n)
{
  if (!n)
    return;

  while (n)
    {
      printf ("%d\n", n->dato);
      n = n->next;
    }
}

De igual forma, para obtener la longitud seria exactamente lo mismo:

int
linked_list_doble_longitud (struct nodo_doble *n)
{
  if (!n)
    return -1;

  int l = 0;

  while (n)
    {
      l++;
      n = n->next;
    }

  return l;
}

Insertando en una Linked List Doble

Para insertar un elemento en una linked list doble tenemos dos escenarios:

1. Vamos a insertar antes del primer nodo.
2. Vamos a insertar en una posicion dada.

Antes del primer nodo: Para insertar un nuevo nodo antes del primer nodo, necesitaremos crear un nuevo nodo, modificar el prev del primer nodo, y el next del nodo creado. La complejidad de tiempo de este escenario es \(O(1)\).

En una posicion dada: Para insertar un nuevo nodo en una posicion dada, necesitaremos crear un nuevo nodo, traversar la linked list hasta pos - 1, y poner modificar los enlaces para que el prev del nuevo nodo sea pos - 1 el next sea p->next y modificar el prev de p->next para que sea el nuevo nodo.

struct nodo_doble *
linked_list_doble_insertar (int dato, int pos, struct nodo_doble **l)
{
  if (!l || pos < 0)
    return NULL;

  struct nodo_doble *t = calloc (1, sizeof (*t));
  t->dato = dato;

  struct nodo_doble *p = *l;

  if (pos == 0)
    {
      p->prev = t;
      t->next = p;
      *l = t;

      return t;
    }

  for (int i = 1; i < pos - 1 && p; i++)
    p = p->next;

  t->next = p->next;
  t->prev = p;
  if (p->next)
    p->next->prev = t;
  p->next = t;

  return t;
}

Eliminando un Nodo en una Linked List Doble

Como cuando eliminamos de una llinked list simple, hay dos situaciones que debemos manejar:

1. Eliminar el primer nodo.
2. Eliminar de un indice dado.

Eliminar el primer nodo: Lo primero que debemos hacer es obtener un pointer del primer elemento de la lista p, mover el pointer del primer elemento a p->next y dado el caso de que p->next != NULL, pondremos head->prev = NULL, obtendremos el valor de p y liberamos la memoria.

Eliminar en una posicion dada: para eliminar un nodo en un indice dado, traversaremos la lista hasta llegar a pos y modificamos los nodos prev y next (si existe.)

int
linked_list_doble_eliminar (int pos, struct nodo_doble **head)
{
  if (!head || pos < 0)
    return -1;

  struct nodo_doble *p = *head;
  if (pos == 1)
    {
      *head = *head->next;
      int x = p->data;
      free (p);

      if (*head)
        *(head)->prev = NULL;

      return x;
    }

  for (int i = 0; i < pos - 1 && p; i++)
    p = p->next;

  p->prev->next = p->next;
  if (p->next)
    p->next->prev = p->prev;

  int x = p->data;
  free (p);

  return x;
}

Invertir una Linked List Doble

Para invertir una linked list, vamos a estar intercambiando los pointers prev y next de los nodos, y cambiar el valor de head:

void
linked_list_doble_invertir (struct nodo_doble **head)
{
  if (!head)
    return;

  struct nodo_doble *p = *head;
  struct nodo_doble *temp = NULL;
  while (p)
    {
      temp = p->next;
      p->next = p->prev;
      p->prev = temp;
      p = p->prev;

      if (!p->next)
        *(head) = p;
    }
}

Linked List Ciircular Doble

Las operaciones con una linked list circular doble es la misma que las de una linked list circular simple, unicamente tendremos que tener en cuenta los enlaces prev.

Para obtener el ultimo nodo de una linked list circular doble, solo debemos hacer head->prev.

Stacks

El stack es una estructura de datos LIFO (last in, first out), queriendo decir que el ultimo elemento que fue agregado, sera el primero en ser accedido.

Para implementar un stack como estructura de datos abstracta vamos a necesitar una estructura con:

1. Espacio para almacenar los elementos.
2. Pointer al top (ultimo elemento agregado) del stack.

Las operaciones que se implementaran son:

• push: insertar un nuevo elemento.
• pop: eliminar un elemento del stack.
• peek: ver un elemento en un indice especificado.
• stack_top: ver cual es el elemento top del stack.
• is_empty: dice si el stack esta vacio.
• is_full: dice si el stack esta lleno.

Podemos utilizar tanto arrays como linked lists para implementar un stack.

Implementacion Usando un Array

Para implementar un stack usando arrays vamos a usar la siguiente estructura:

struct stack
{
  int size;
  int top; // indice top
  int *s;
};

Podemos crear un stack con una funcion similar a la siguiente:

struct stack
stack_create (int size)
{
  struct stack s = { 0 };
  s.size = s;
  s.s = calloc (1, sizeof (int));
  s.top = -1;
  return s;
}

Y dos de las operaciones mencionadas is_empty y is_full pueden ser implementadas de la siguiente manera:

_Bool
stack_is_empty (struct stack *s)
{
  if (!s || s->top != -1)
      return 0;
  return 1;
}

_Bool
stack_is_full (struct stack *s)
{
  if (!s || s->top !=  (s->size - 1))
    return 0;
  return 1;
}

Podemos implementar push vamos a insertar un elemento en s.top + 1 y debemos revisar que no este lleno tampoco al momento de insertar:

void
stack_push (int x, struct stack *s)
{
  if (!s || s->top ==  (s->size - 1))
    return;

  s->top++;
  s->s[s->top] = x;
}

Para pop, vamos a obtener el ultimo valor del stack, vamos a modificar el valor de top a top - 1 y vamos a devolver el valor eliminado. Esto se debe ejecutar, siempre y cuando top != -1.

int
stack_pop (struct stack *s)
{
  if (!s || s->top == -1)
    return -1;

  return s->s[s->top--];
}

La complejidad de tiempo para estas dos operaciones es \(O(1)\).

Para peek y obtener un valor de una posicion especificada, podemos convertir la posicion del stack a un indice del array haciendo: top - pos + 1:

int
stack_peek (int pos, struct stack *s)
{
  if (!s)
    return -1;

  int i = s->top - pos + 1;
  if (i < 0)
    return -1;
  return s->s[i];
}

Y por ultimo stack_top:

int
stack_top (struct stack *s)
{
  if (!s || s->top == -1)
    return -1;
  return s->s[s->top];
}

La complejidad de tiempo de todas las operaciones del stack tiene una complejidad de tiempo \(O(1)\).

Stacks Usando Linked Lists

En una implementacion de stack en una linked list, para evitar que la complejidad de tiempo de operaciones simples como la de push o pop tengan una complejidad de tiempo \(O(n)\) sino que sea \(O(1)\) se van a realizar estas operaciones en la parte izquierda de la lista, es decir, siempre sera con el primer elemento.

Para push y pop ya lo vimos antes, es hacer la operacion antes del primer nodo.

Cuando top == NULL, es decir, la lista no tenga nodos, decimos que el stack esta vacio.

Y como aqui podemos crear tantos nodos como nos permitan los recursos, la condicion para saber si un stack esta lleno, es si no podemos crear nuevos nodos, es decir, ya no haya memoria en el heap:

struct nodo
{
  int dato;
  struct nodo *next;
};

void
stack_push (int x, struct nodo **s)
{
  struct nodo *t = calloc (1, sizeof (*t));
  if (!t)
    return; // el stack esta lleno

  t->dato = x;
  t->next = *s;
  *s = t;
}

int
stack_pop (struct nodo **s)
{
  if (!s)
    return -1; // el stack esta vacio

  struct nodo *p = *s;
  *s = p->next;
  int x = p->dato;
  free (p);

  return x;
}

int
stack_peek (int pos, struct nodo *s)
{
  if (!s)
    return -1;

  struct node *p = s;
  for (int i = 0; i < pos - 1 && p; i++)
    p = p->next;

  if (!p)
    return -1;
  return p->dato;
}

int
stack_top (struct nodo *s)
{
  if (!s)
    return -1;
  return s->dato;
}

_Bool
stack_is_empty (struct nodo *s)
{
  return s ? 0 : 1;
}

_Bool
stack_is_full ()
{
  struct nodo *n = calloc (1, sizeof (*n));

  if (!n)
    return 1;

  free (n);
  return 0;
}

Parenthesis Matching

Una de las aplicaciones del stack es la de emparejar parentesis. Por ejemplo, tenemos una expresion: ((a + b) * (c - d)) y tenemos que revisar si los parentesis estan balanceados o no.

Como va a funcionar, es que vamos a comparar cada uno de los caracteres de la expresion si es un ( dado el caso que si lo sea, se va a pushear ese caracter al stack. Cuando el caracter actual sea un ) vamos a eliminar un elemento del stack.

Al llegar al final de la expresion vamos a revisar que el stack este vacio y que no intentemos eliminar un elemento cuando no hayan, si estas condiciones se cumplen, quiere decir que los parentesis estan balanceados.

_Bool
esta_balanceado (const char *exp)
{
  if (!exp)
    return 0;

  struct stack s = stack_create (strlen (exp));


  for (int i = 0; exp[i] != '\0'; i++)
    {
      if (exp[i] == '(')
        stack_push ((int)exp[i], &s);
      else if (exp[i] == ')')
        {
          if (stack_is_empty (&s))
            {
              stack_destroy (&s);
              return 0;
            }

          stack_pop (&s);
        }
    }

  _Bool empty = stack_is_empty (&s);

  stack_destroy (&s);
  return empty;
}

Convertir de Infijos a Sufijos ATTACH

Nosotros podemos representar de 3 formas diferentes una expresion matematica:

1. Infijo: Operando - Operador - Operando (a + b)
2. Prefijo: Operador - Operando - Operando (+ a b)
3. Sufijo: Operando - Operando - Operador (a b +)

Para estas conversiones, lo primero que haremos sera agregarles parentesis a la expresion basados en la siguiente (muy basica) tabla de precedencia:

Por ejemplo, si tenemos la expresion: a + b * c, en base a esa precedencia quedaria de la siguiente forma (a + (b * c)).

Si convertimos la expresion con parentesis en prefijos quedaria + a * b c, y en sufijos a b c * +.

Como va a funcionar la conversion usando stacks es que vamos a tener dos variables: un stack y un string que seria la expresion final. Escanearemos caracter por caracter la expresion con los infijos y cada operando lo vamos a agregar a la expresion que estamos generando, y por cada operador vamos a pushearlo al stack, si el elemento top del stack tiene menos o igual precedencia lo agregaremos a la expresion que estamos generando.

Al finalizar la expresion, vamos a agregar cualquier otro operador que tengamos en el stack a la expresion generada.

Por ejemplo, con la expresion: a + b * c - d / e:

Terminando con la expresion abc*+de/-

Podemos hacerlo de la misma manera si tomamos los operandos como los elementos de mayor precedencia.

La implementacion en C seria la siguiente:

_Bool
es_operando (char c)
{
  if (c == '+' || c == '-' || c == '*' || c == '/')
    return 0;
  return 1;
}

int
precedencia (char c)
{
  if (c == '+' || c == '-')
    return 1;
  else if (c == '*' || c == '/')
    return 2;
  return 0;
}

char *
convertir (char *infijo)
{
  if (!infijo)
    return NULL;

  size_t size = strlen (infijo);

  struct stack s = stack_create (size);
  char *sufijo = calloc (size, sizeof (char));

  int i = 0;
  int j = 0;
  while (infijo[i] != '\0')
    {
      if (es_operando (infijo[i]))
        {
          sufijo[j++] = infijo[i++]; // los operandos se agregan directamente.
          continue;
        }

      if (precedencia (infijo[i]) > precedencia (stack_top (&s)))
        stack_push (&s, infijo[i++]);
      else
        sufijo[j++] = stack_pop (&s);
    }

  while (!stack_is_empty (&s))
    sufijo[j++] = stack_pop (&s);
  sufijo[j] = '\0';

  stack_destroy (&s);
  return sufijo;
}

Ya teniendo la expresion en su forma de sufijo, podemos evaluarla pusheando todos los operandos al stack, y por cada operador que se encuentre se realiza la operacion con los operandos disponibles en el stack.

Por ejemplo, si tenemos 15 8 + 4 -, primero se pushearia 15, despues 8, como el proximo caracter es un operador se hace la operacion de suma entre 15 y 8, quedando 23 como unico elemento en el stack, se pushea 4, y como el proximo es un operador se efectua la resta quedando con 19.