Subconjunto ordenado de array

El siguiente ejemplo pide ingresar una lista de números positivos y guardarlos en un array, para luego leerlos y copiar a otro array de forma ordenada sólo aquellos que son múltiplos de 5.

Un ejemplo de ejecución:

¿Qué cambiarías en el programa para que extraiga los múltiplos de otro número?

¿Qué cambiarías para que el orden sea ascendente?

¿Qué otras variaciones añadirías al programa?

#include <iostream>

int main(int argc, char** argv) {

int fin = 0;

int numero;

int listaNumeros[20];

int totalNumeros = 0;

int listaOrdenada[20];

int totalOrdenada = 0;

//lectura por teclado de un conjunto de números positivos, como máximo 20 números

while(!fin && totalNumeros<20){

printf("ingrese un numero:");

scanf("%d", &numero);

if(numero > 0) {

listaNumeros[totalNumeros] = numero;

totalNumeros++;

}else{

fin++;

}

}

//imprimir la lista

for(int i = 0; i<totalNumeros; i++) printf("%d ", listaNumeros[i]);

//seleccionar los múltiplos de 5 ordenados descendente

for(int i = 0; i<totalNumeros; i++){

if( (listaNumeros[i]%5) == 0 ){

int encuentra = 0;

int indice; //indice que recorre la lista ordenada para encontrar la posición donde insertar

int multiploInsertar = listaNumeros[i];//número a insertar en la lista ordenada

indice = totalOrdenada - 1;

//recorremos la lista ordenada de forma descendente y vamos desplazando hasta qu encontramos la posición correcta

while(!encuentra && indice >= 0){

//comparo el número a ubicar con el elemento en la ListaOrdenada en la posición índice

if(multiploInsertar > listaOrdenada[indice]){

//como es mayor muevo el valor de lista ordenada al siguiente índice

listaOrdenada[indice + 1 ] = listaOrdenada[indice];

}

else{

listaOrdenada[indice+1] = multiploInsertar;

totalOrdenada++;

encuentra = 1;

}

indice--;

}

if(!encuentra) {//en el caso que recorra todo el arrayOrdenado y sea mayor a todos, se coloca en el primer elemento

listaOrdenada[0] = multiploInsertar;

totalOrdenada++;

}

}

}

//imprimir la lista

printf("\nNumero de multiplos encontrados %d\n", totalOrdenada);

for(int i = 0; i<totalOrdenada; i++) printf("%d ", listaOrdenada[i]);

return 0;

}

Ordenamiento de una lista simplemente enlazada

El ordenamiento de una lista simplemente enlazada es similar al ordenamiento de vectores con la gran diferencia de que en una lista simplemente enlazada no disponemos del concepto del “índice” que nos ayuda a acceder directamente a un elemento de la lista, en este caso para acceder a un elemento debemos recorrer desde el inicio hasta hallar el elemento que nos interese.

Un algoritmo sencillo es el del Intercambio, consiste en lo siguiente:

1. Situar un puntero al inicio de la lista que nos irá indicando a medida que vayamos ordenando, cuánto de la lista ya está ordenada, es la variable más importante del algoritmo porque nos servirá para saber que hemos acabado de ordenar la lista.

Elemento * elemBase = elemInicio;

while(elemBase != NULL)

{

//en este proceso vamos ordenando la lista a partir del nodo elemBase hasta el final

elemBase = elemBase->next;

}

2. En el caso que el ordenamiento sea de menor a mayor, necesitamos encontrar el menor de los elementos a partir del elemento base hasta el final de la lista.

En el caso del ordenamiento de Vectores obteníamos la posición, en este caso obtendremos un puntero al menor elemento.

Elemento* buscarMenor(Elemento* ptrInicial)

Esta función tendría que utilizarse en cada iteración

Elemento * elemBase = elemInicio;

Elemento* elemMenor; //puntero que nos sirve para apuntar al menor elemento encontrado

while(elemBase != NULL)

{

elemMenor = buscarMenor(elemBase);

elemBase = elemBase->next;

}

3. Intercambiar el elemento menor con el elemento que se encuentra apuntando el puntero base. Para hacer este intercambio es necesario que el elemento anterior al elemento base apunte al elemento menor, para eso necesitamos un puntero que apunte al anterior del elemento base.

Como es una lista simplemente enlazada, no podemos retroceder para hallar al puntero anterior al puntero base, por tanto, crearemos una función que nos sirva para ubicarnos en el elemento anterior que queramos. Esta función es necesaria para luego poder hacer el intercambio de nodos.

Elemento * getElemAnterior(Elemento* elemInicio, Elemento* elem);

Utilizaremos esta función para obtener el elemento anterior al base y al menor y de esta forma poder realizar el intercambio

Elemento * elemAnteBase = NULL;//puntero que apunta al anterior de elemento base

Elemento * elemBase = elemInicio;

Elemento* elemAnteMenor; //puntero que apunta al anterior del elemento menor

Elemento* elemMenor; //puntero que nos sirve para apuntar al menor elemento encontrado

while(elemBase != NULL)

{

elemMenor = buscarMenor(elemBase);

elemAnteBase = getElemAnterior(elemInicio, elemBase);

elemAnteMenor = getElemAnterior(elemInicio, elemMenor);

elemBase = elemBase->next;

}

Teniendo el puntero anterior al base ya podemos hacer el intercambio:

void intercambio(Elemento* elemAnteBase, Elemento* elemBase,

Elemento* elemAnteMenor, Elemento* elemMenor);

Incorporamos el intercambio en cada iteración y asignamos el nodo menor como el nuevo elemento base:

Elemento * elemAnteBase = NULL;//puntero que apunta al anterior de elemento base

Elemento * elemBase = elemInicio;

Elemento* elemAnteMenor; //puntero que apunta al anterior del elemento menor

Elemento* elemMenor; //puntero que nos sirve para apuntar al menor elemento encontrado

while(elemBase != NULL)

{

elemMenor = buscarMenor(elemBase);

elemAnteBase = getElemAnterior(elemInicio, elemBase);

elemAnteMenor = getElemAnterior(elemInicio, elemMenor);

intercambio(elemAnteBase, elemBase, elemAnteMenor, elemMenor);

elemBase = elemMenor;

elemBase = elemBase->next;

}

4. Finalmente desarrollamos las funciones:

Elemento* buscarMenor(Elemento* ptrInicial)

{

Elemento* elemMenor = ptrInicial;

Elemento* ptr = ptrInicial;//puntero que sirve para recorrer la lista

int menorValor = elemMenor.valor;//inicializamos el primer valor menor

//recorremos toda la lista y dejamos el puntero elemMenor en el de menor valor

while(ptr!=NULL)

{

if(ptr.valor < menorValor)

{

elemMenor = ptr;

menorValor = ptr.valor;

}

ptr = ptr->next;

}

return elemMenor;

}

void intercambio(Elemento* elemAnteBase, Elemento* elemBase,

Elemento* elemAnteMenor, Elemento* elemMenor)

{

Elemento* aux = elemBase->next; //nos sirve para hacer el intercambio sin perder punteros

elemBase->next = elemMenor->next;

elemMenor->next = aux;

elemAnteBase->next = elemMenor;

elemAnteMenor->next = elemBase;

}

Elemento * getElemAnterior(Elemento* elemInicio, Elemento* elem)

{

Elemento*anterior = NULL;

Elemento*ptr = elemInicio;

int finBusqueda = 0;

while(ptr!=NULL && ptr->next!=NULL && !finBusqueda)

{

if(ptr->next.valor == elem.valor)

{

finBusqueda = 1;

}

anterior = ptr;

ptr = ptr->next;

}

return anterior;

}

Lectura de fichero de texto

En este post veremos los pasos para realizar la lectura de un fichero de texto, para esto es necesario saber que es similar a escuchar música en un vinilo, se deben realizar  pasos:

1- Poner el disco y la aguja al inicio del disco.
2- Escuchar la música.
3- Levantar la aguja cuando ya no se quiera escuchar o esperar a que termine de reproducirlo todo.

La aguja en el disco viene a representar un puntero de tipo FILE* que se prepara al inicio del fichero, avanza con cada caracter que lee y finalmente debemos cerrarlo.

Fichero que leeremos:

Primer Paso: Abrir Fichero
FILE* abrirFichero () {
      FILE* fptr = NULL; //puntero que abre al inicio del fichero y sirve para recorrerlo
      fptr = fopen ("fichero_prueba.txt", "rt"); //apertura de fichero con permiso de lectura
      return fptr;
}

Invocación de la función abrirFichero:
FILE* ptrFichero; //declaramos una variable de tipo puntero
ptrFichero = abrirFichero (); //invocamos a la función y guardamos el resultado en la variable puntero

Segundo Paso: Leer Fichero
Esta función leerá el fichero hasta el final

void leerFichero(FILE* fptr )
{
  char palabra1 [BUFSIZ];
  char palabra2 [BUFSIZ];
  int numero;
  //La función eof = End Of File devuelve true cuando el puntero llega al final del fichero
  while(!feof(fptr))
  {
      //leemos palabra a palabra (se sabe previamente el formato del fichero)
      //sabemos que leemos 2 palabras y un número por registro
      //cada iteración del while leerá un registro
      fscanf (fptr, "%s", palabra1);
      fscanf (fptr, "%s", palabra2);
      fscanf (fptr, "%i",&numero);
      //imprimimos por pantalla lo que hemos leído
      printf("palabra 1: %s, palabra 2: %s, numero: %i \n", palabra1, palabra2, numero);
   }
}

Invocación de la función leerFichero:
Sólo puede realizarse si el fichero se llego a abrir (ptrFichero != NULL)
FILE* ptrFichero;
ptrFichero = abrirFichero ();
if(ptrFichero != NULL)
{
  leerFichero(ptrFichero);
}

Tercer Paso: Cerrar Fichero
void cerrarFichero (FILE* fptr) {
     fclose(fptr);
}

Invocación de la función leerFichero:
Sólo puede realizarse si el fichero se llego a abrir (ptrFichero != NULL)
FILE* ptrFichero;
ptrFichero = abrirFichero ();
if(ptrFichero != NULL)
{
  leerFichero(ptrFichero);
  cerrarFichero(ptrFichero);
}

El resultado de la ejecución es el siguiente:

El mejor algoritmo

Este post está dedicado a una persona que quiero mucho y que a pesar que cambió la informática por la economía, aún tiene un bichito informático dentro que se pregunta: ¿cómo saber si un algoritmo es mejor que otro? 

La respuesta es el clásico "depende":

- Depende de los datos, en algunos casos a medida que se evalúan más datos el algoritmo se va degradando, porque la función del rendimiento es exponencial por ejemplo.

- Depende de la arquitectura, en algunos casos el procesador está preparado para soportar operaciones más complejas en menor número de instrucciones.

- Depende del objetivo, en algunos casos se puede hacer un algoritmo muy complejo y casi ininteligible, con lo que a otro programador le costaría mucho entenderlo como para probarlo o modificarlo, se debe tener siempre en consideración que además de apoyarnos en buenos comentarios en el código y nombres de variables que ayuden a la comprensión, el código en sí, si es para uso masivo y cualquiera puede modificarlo no debería ser tan complejo, sin embargo si es un código cerrado, se puede elevar la complejidad.

Existen más variables que hacen que un algoritmo sea mejor o peor que otro, pero en este post quería centrarme estrictamente en la función de rendimiento que nos puede ayudar a hacer comparaciones entre diferentes soluciones.

Para entender mejor esto del rendimiento, trataremos el cálculo del factorial de un número:

Problema: Calcular el Factorial de N, donde N es un numero Natural >= 1
Supuestos:
1) Cada instrucción tarda una unidad de tiempo T
2) No consideraremos el tiempo en que se reserva memoria en la función recursiva

Propuesta 1 de Factorial
Función FactorialIterativa(N)
  F = N; --> T
  //la variable i va desde N-1 hasta 1 y es la que se va multiplicando
  i = N - 1; --> T 
  Mientras (i > 1) --> La comparación se realiza N-1 veces: T * (N-1)
    F = F * i; --> La comparación se realiza N-2 veces: T * (N-2)
    i = i - 1; --> La comparación se realiza N-2 veces: T * (N-2)
  Fin_Para
  Return F; --> T 
Fin_Función
Tiempo Total = T + T + T * (N-1) + T * (N-2) + T * (N-2) + T = (3N - 2) T

Propuesta 2 de Factorial

Funcion FactorialRecursiva (N)

  Si N = 1 --> Cada vez que se llama a la recursiva se hace la comparación, por tanto se hace N veces. N * T

    Return N --> Esta se hace sólo una vez, la última. T

  Caso Contrario

    Return N * FactorialRecursiva(N-1) --> Se ejecuta N - 1 veces. (N - 1) * T

  Fin_Si

Fin_Funcion

Tiempo Total = N * T + T + (N-1) * T = 2N * T

Con estas funciones de rendimiento, podríamos decir que para los supuestos considerados y para N > 2, la propuesta 2 tiene mejor rendimiento que la propuesta 1.

Con esto logramos tener una herramienta simple para comparar algoritmos, siempre bajo supuestos. 

Sería muy difícil contemplar todas las variables que intervienen, pero podemos aproximarnos y nos puede servir para optar por algún algoritmo u otro. 

Juego: Tres en raya

Esta vez repasaremos matrices, funciones, condicionales e iteraciones, todo esto aplicado en el clásico juego del tres en raya, las reglas del juego son muy conocidas, sólo haré unos cuantos razonamientos previos antes de empezar a programar:

Sobre los turnos

Sabemos que son 2 jugadores que juegan por turnos hasta que alguno gana o el tablero se llena sin ganador (situación de empate).

Vemos que debe existir una iteración que finalice cuando el juego termina:

var fin_juego = false;

var turno = 0; //los jugadores son 0 y 1

while(!fin_juego)

{

//se hace la jugada

//si se gana en este turno fin_juego = true;

//si el tablero se llena sin ganador fin_juego = true;

turno = (turno + 1) % 2; //esto es para cambiar el turno de 0 a 1 y de 1 a 0

}

Sabemos que es un tablero de 9 casillas (3 filas y 3 columnas). En principio todas las casillas están vacías y en cada turno se va llenando alguna de las casillas con la jugada hecha en el turno.

Si todas las casillas están llenas y no hay ganador, entonces es un empate.

Para controlar que el juego termine en empate creamos un condicional en cada iteración que controle si se llenó el tablero o no.

var fin_juego = false;

var turno = 0; //los jugadores son 0 y 1

var casillas_vacias = 9;

while(!fin_juego)

{

//se hace la jugada

casillas_vacias = casillas_vacias - 1; //al hacer la jugada disminuye en 1 las casillas vacías

//si se gana en este turno fin_juego = true;

//si el tablero se llena sin ganador fin_juego = true;

if(!fin_juego && casillas_vacias == 0) fin_juego = true;

turno = (turno + 1) % 2; //esto es para cambiar el turno de 0 a 1 y de 1 a 0

}

Sobre la jugada

El jugador debe seleccionar la casilla que quiere marcar, para esto utilizaremos las filas y las columnas de la matriz que representa al tablero.

var boolean fin_juego = false;

var int turno = 0; //los jugadores son 0 y 1

var int casillas_vacias = 9;

var char tablero [3][3];//matriz de 3 x 3 que representa al tablero

var int fila_jugada;

var int columna_jugada;

var char ficha='0'; //será 'X' cuando el turno sea 1

while(!fin_juego)

{

//se hace la jugada

fila_jugada = leer(); //lee de consola la fila (de 0 a 2) que selecciona el jugador en ese turno

columna_jugada = leer(); //lee de consola la columna (de 0 a 2) que selecciona el jugador en ese turno

if(turno == 0) ficha = '0'; //escoge ficha

else ficha = 'X';

tablero[fila_jugada][columna_jugada] = ficha;

casillas_vacias = casillas_vacias - 1; //al hacer la jugada disminuye en 1 las casillas vacías

//si se gana en este turno fin_juego = true;

//si el tablero se llena sin ganador fin_juego = true;

if(!fin_juego && casillas_vacias == 0) fin_juego = true;

turno = (turno + 1) % 2; //esto es para cambiar el turno de 0 a 1 y de 1 a 0

}

Sobre el control de la jugada ganadora

Cuando se coloca la ficha se hace control en vertical, horizontal y diagonales a ver si es una jugada ganadora.

Para el control horizontal, todas las fichas de la fila_jugada deben ser iguales, por tanto haremos una validación iterando las columnas.

Para el control vertical, todas las fichas de la columna_jugada deben ser iguales, por tanto haremos una validación iterando las filas.

Para el control diagonal, no es necesario realizarlo siempre, sólo cuando la jugada esté en alguna diagonal. Y sólo si está en el medio del tablero la comprobación debe ser de la doble diagonal.

Comprobar diagonal 1

fila_jugada: 0 y columna_jugada:0,

fila_jugada: 2 y columna_jugada:2

Comprobar diagonal 2

fila_jugada: 2 y columna_jugada:0,

fila_jugada: 0 y columna_jugada:2

Comprobar ambas diagonales.

fila_jugada: 1 y columna_jugada:1

Como esta lógica es un poco larga, la encapsularemos en una función y la utilizaremos en cada jugada para comprobar si la jugada es ganadora:

Entrada: ¿Qué necesito?

Tablero, fila_jugada, columna_jugada

Salida: ¿Qué quiero?

Booleano que indique si es una jugada ganadora o no

Función: ¿Cómo lo hago?

Comprobando la Horizontal, Vertical y cuando toque las diagonales.

Boolean esGanador(tablero, fila_jugada, columna_jugada)

{

Boolean jugada_ganadora = false;

//validación horizontal 

if(Tablero[fila_jugada][0] == Tablero[fila_jugada][1] &&

Tablero[fila_jugada][0] == Tablero[fila_jugada][2])

{

return true; //jugada ganadora en la horizontal, termina la ejecución

}

//validación vertical 

if(Tablero[0][columna_jugada] == Tablero[1][columna_jugada] &&

Tablero[0][columna_jugada] == Tablero[2][columna_jugada])

{

return true; //jugada ganadora en la vertical, termina la ejecución

}

//verifica la diagonal 1 (sólo si es necesario)

if( (fila_jugada == 0 && columna_jugada == 0) || (fila_jugada == 2 && columna_jugada == 2))

{

if(Tablero[0][0] == Tablero[1][1] &&

Tablero[0][0] == Tablero[2][2])

{

return true; //jugada ganadora en la diagonal 1, termina la ejecución

}

}

//verifica la diagonal 2 (sólo si es necesario)

if( (fila_jugada == 0 && columna_jugada == 2) || (fila_jugada == 2 && columna_jugada == 0))

{

if(Tablero[0][2] == Tablero[1][1] &&

Tablero[0][2] == Tablero[2][0])

{

return true; //jugada ganadora en la diagonal 2, termina la ejecución

}

}

//verifica la doble diagonal(sólo si es necesario)

if( fila_jugada == 1 && columna_jugada == 1)

{

if((Tablero[0][2] == Tablero[1][1] &&

Tablero[0][2] == Tablero[2][0]) ||

(Tablero[0][0] == Tablero[1][1] &&

Tablero[0][0] == Tablero[2][2]))

{

return true; //jugada ganadora en alguna de las diagonales, termina la ejecución

}

}

return jugada_ganadora; //sólo llega a esta línea de código cuando no es jugada ganadora

}

Incorporamos la llamada a la función en el programa principal

var boolean fin_juego = false;

var int turno = 0; //los jugadores son 0 y 1

var int casillas_vacias = 9;

var char tablero [3][3];//matriz de 3 x 3 que representa al tablero

var int fila_jugada;

var int columna_jugada;

var char ficha='0'; //será 'X' cuando el turno sea 1

while(!fin_juego)

{

//se hace la jugada

fila_jugada = leer(); //lee de consola la fila (de 0 a 2) que selecciona el jugador en ese turno

columna_jugada = leer(); //lee de consola la columna (de 0 a 2) que selecciona el jugador en ese turno

if(turno == 0) ficha = '0'; //escoge ficha

else ficha = 'X';

tablero[fila_jugada][columna_jugada] = ficha;

casillas_vacias = casillas_vacias - 1; //al hacer la jugada disminuye en 1 las casillas vacías

//si se gana en este turno fin_juego = true;

fin_juego = esGanador(tablero, fila_jugada, columna_jugada);

//si el tablero se llena sin ganador fin_juego = true;

if(!fin_juego && casillas_vacias == 0) fin_juego = true;

turno = (turno + 1) % 2; //esto es para cambiar el turno de 0 a 1 y de 1 a 0

}

Con esto tendríamos lo básico para el tres en raya, pero ¿qué pasaría si el jugador pusiera la ficha en un lugar ocupado? ¿qué pasaría si inicialmente el tablero está ocupado?¿No vendría bien agregar una impresión del tablero para que jugador sepa en cada jugada cuáles son sus opciones de juego?

¿Cómo modificaríais el programa para agregar estas funcionalidades?

Enlaces

Tres en raya (wikipedia)

Instancia de un objeto

A veces nos resulta complicado controlar que todos los atributos de todas las clases queden bien instanciados, para tener todo esto mejor controlado lo mejor es tener un diagrama de clases para saber qué clases deben instanciar a qué otras.

A continuación os mostraré lo que puede ocurrir si no tenemos bien controladas todas las instancias.

Tenemos una clase llamada Persona:

using System.IO;
using System;
public class Persona{   

  string nombre;   
  int edad;   
  char sexo;      
  public Persona()   
  {      nombre = "";      
         edad = 0;      
         sexo = ' ';   
  }   
  public Persona(string pNombre, int pEdad, char pSexo)   
  {       nombre = pNombre;
         edad = pEdad;
         sexo = pSexo;   
  }      
  public void imprimir()   
  {      Console.WriteLine("Persona-Nombre: "+nombre);
         Console.WriteLine("Persona-Edad: "+edad);
         Console.WriteLine("Persona-Sexo: "+ sexo);
  }
}

Y tenemos una clase llamada Cliente que incluye a un objeto de tipo Persona, en este caso es Cliente el que debe instanciar al objeto de tipo Persona

using System.IO;

using System;

public class Cliente

{

    int codigo;

    Persona persona;

    

    public Cliente()

    {

        codigo = 0;

        persona = new Persona();//es en el constructor del cliente que instanciamos al objeto de tipo Persona

    }

    public void imprimir()

    {

        Console.WriteLine("Cliente-Codigo: "+codigo);

        persona.imprimir();

    }

}

Si ejecutamos este código:

using System.IO;

using System;

class Program

{

    static void Main()

    {

        Cliente cliente = new Cliente();

        cliente.imprimir();

    }

}

El resultado de la ejecución es la siguiente:

Cliente-Codigo: 0                                                                                                                                                                  

Persona-Nombre:                                                                                                                                                                    

Persona-Edad: 0                                                                                                                                                                    

Persona-Sexo: 

Ahora os mostraré lo que pasaría en el caso que en el constructor de cliente NO se instancie el objeto persona, comentaremos la linea

public Cliente()

    {

        codigo = 0;

        //persona = new Persona();//es en el constructor del cliente que instanciamos al objeto de tipo Persona

    }

El compilador no nos avisará, porque no es un error sintáctico, pero el error vendrá en la ejecución:

Cliente-Codigo: 0                                                                                                                                                                  

                                                                                                                                                                                   

Unhandled Exception:                                                                                                                                                               

System.NullReferenceException: Object reference not set to an instance of an object                                                                                                

  at Cliente.imprimir () [0x00000] in <filename unknown>:0                                                                                                                         

  at Program.Main () [0x00000] in <filename unknown>:0                                                                                                                             

[ERROR] FATAL UNHANDLED EXCEPTION: System.NullReferenceException: Object reference not set to an instance of an object                                                             

  at Cliente.imprimir () [0x00000] in <filename unknown>:0                                                                                                                         

  at Program.Main () [0x00000] in <filename unknown>:0   

Vemos que Cliente-codigo si que lo ha impreso correctamente, pero a partir de allí la impresión del objeto persona dio error por NULLReference, esto es porque no está instanciado el objeto.

Ahora que hemos visto la importancia de tener controladas las instancias os mostraré como instanciar con valores al objeto persona a partir de la clase Cliente.

Vimos que la clase Persona tiene el constructor:

   public Persona(string pNombre, int pEdad, char pSexo)

   {

       nombre = pNombre;

       edad = pEdad;

       sexo = pSexo;

   }

Agregamos ahora un nuevo constructor a la clase Cliente que utilice este constructor de la clase Persona:

    public Cliente(int pCodigo, string pNombre, int pEdad, char pSexo)

    {

        codigo = pCodigo;

        persona = new Persona(pNombre, pEdad, pSexo);

    }

Y desde el Main le pasamos todos los valores utilizando este nuevo constructor de la clase Cliente:

    static void Main()

    {

        Cliente cliente = new Cliente(1, "Juan", 30, 'H');

        cliente.imprimir();

    }

Y finalmente vemos la ejecución:

Cliente-Codigo: 1                                                                                                                                                                  

Persona-Nombre: Juan                                                                                                                                                               

Persona-Edad: 30                                                                                                                                                                   

Persona-Sexo: H   

Push en una Pila

Cuando nos explican el concepto de Pilas lo principal es que: "el primero que entra es el primero que sale":

con esto parece que tenemos toda la teoría aprendida, el problema viene cuando intentamos implementarlo y no sabemos por dónde empezar.

Por lo general cuando se explica este tema se hace en C++ y utilizando estructuras, por tanto antes de continuar esta explicación os recomiendo leer previamente el post relacionado a estructuras

Vemos en la imagen que cada elemento de la pila está formado por un círculo con un valor y una flecha que lo une con el siguiente círculo, con estos dos elementos formaremos un elemento de la Pila, de esta forma:

struct ElemPila{
  int valor; //esto representa el valor que está dentro del círculo
  struct ElemPila * siguienteElem; //esto representa la flecha, observar que es un puntero
};

Hasta aquí tenemos definida la estructura, pero aún no la estamos utilizando, ahora veremos como desde el programa utilizamos esta esta estructura para agregar los elementos: 1, 2 y 3:

int main()
{
  / /Creamos el primer elemento, con valor 1 y la flecha que apunta al siguiente elemento apunta a NULL
   struct ElemPila* elem1 = new ElemPila; //reserva memoria para el contenido de la estructura
   elem1->valor = 1; //inicializa el valor de la estructura
   elem1->siguienteElem = NULL; //inicializa el valor hacia donde apunta el siguiente
   
   struct ElemPila* elem2 = new ElemPila;
   elem2->valor = 2;
   elem2->siguienteElem = NULL;
   
   struct ElemPila* elem3 = new ElemPila;
   elem3->valor = 3;
   elem3->siguienteElem = NULL;
      
   return 0;
}

Al ejecutar este programa lo que logramos es tener 3 elementos independientes, así:

Como paso siguiente modificaremos el programa para introducir el puntero que será cabeza de la pila e introduciremos sólo el primer elemento a la pila:

int main()
{
   struct ElemPila* elem1 = new ElemPila;
   elem1->valor = 1;
   elem1->siguienteElem = NULL;
   
   struct ElemPila* elem2 = new ElemPila;
   elem2->valor = 2;
   elem2->siguienteElem = NULL;
   
   struct ElemPila* elem3 = new ElemPila;
   elem3->valor = 3;
   elem3->siguienteElem = NULL;
   
   struct ElemPila* cabezaPila; //creamos el puntero
   cabezaPila = elem1; //hacemos que apunte al primer elemento
   
   return 0;
}

Para incluir el segundo elemento en la pila, lo que tenemos que hacer es que el segundo elemento apunte al primero (elem1) y la cabeza de pila apunte al segundo:

int main()

{

   struct ElemPila* elem1 = new ElemPila;

   elem1->valor = 1;

   elem1->siguienteElem = NULL;

   struct ElemPila* elem2 = new ElemPila;

   elem2->valor = 2;

   elem2->siguienteElem = NULL;

   struct ElemPila* elem3 = new ElemPila;

   elem3->valor = 3;

   elem3->siguienteElem = NULL;

   struct ElemPila* cabezaPila;

   cabezaPila = elem1;

   elem2-> siguienteElem = cabezaPila;

   cabezaPila = elem2;

   return 0;

}

Finalmente incluimos el tercer elemento, siguiendo los mismo pasos que el anterior, que es hacer que el siguiente de elemento 3 apunte al elemento 2 y la cabeza de la pila apunte a elemento 3:

int main()

{

   struct ElemPila* elem1 = new ElemPila;

   elem1->valor = 1;

   elem1->siguienteElem = NULL;

 

   struct ElemPila* elem2 = new ElemPila;

   elem2->valor = 2;

   elem2->siguienteElem = NULL;

 

   struct ElemPila* elem3 = new ElemPila;

   elem3->valor = 3;

   elem3->siguienteElem = NULL;

 

   struct ElemPila* cabezaPila;

   cabezaPila = elem1;

 

   elem2->siguienteElem = cabezaPila;

   cabezaPila = elem2;

 

   elem3->siguienteElem = cabezaPila;

   cabezaPila = elem3;

 

   return 0;

}

Si observamos atentamente el código y las imágenes veremos que las variables elem1 y elem2 se quedan apuntando a elementos de la pila que en teoría no se deberían acceder directamente (el acceso es sólo con la cabeza de pila), por tanto podríamos deducir que con una sola variable de tipo ElemenPila sería suficiente. De la misma forma podemos observar en el código que el mecanismo para agregar un elemento es el mismo, por lo tanto podríamos utilizar una función para reutilizar el código. todo esto de esta forma:

#include <iostream>

struct ElemPila{

  int valor;

  struct ElemPila * siguienteElem;

};

using namespace std;

//incluimos una función de impresión para comprobar el orden en que se han guardado

void imprimir(struct ElemPila* cabezaPila)

{

    struct ElemPila* auxiliar = cabezaPila;

    while(auxiliar != NULL)

    {

      cout << auxiliar->valor << " - ";

      auxiliar = auxiliar -> siguienteElem;

    }

    cout << "=====================\n";

}

//función que realiza el push de forma genérica para cualquier elemento

struct ElemPila* push(int pValor, struct ElemPila* elem, struct ElemPila* cabezaPila)

{

   elem = new ElemPila;    

   elem->valor = pValor;

   elem->siguienteElem = NULL;

   elem->siguienteElem = cabezaPila;

   cabezaPila = elem;

   return cabezaPila;

}

int main()

{

   struct ElemPila* cabezaPila = NULL;

   struct ElemPila* elem = NULL;

   cabezaPila = push(1, elem, cabezaPila);   

   imprimir(cabezaPila);

       

   cabezaPila = push(2, elem, cabezaPila);   

   imprimir(cabezaPila);

   

   cabezaPila = push(3, elem, cabezaPila);   

   imprimir(cabezaPila);

   

   return 0;

}

Executing the program....

1 - =====================
2 - 1 - =====================
3 - 2 - 1 - =====================