Estructuras I Práctica 3

///EJERCICIO 1

#include <stdio.h>
#include <stdlib.h>
#define MAX_PILA 50

typedef struct _Pila {
    int datos[MAX_PILA];
    int ultimo;
} *Pila;


Pila pila_new(){
    Pila nueva = (Pila) malloc (sizeof(struct _Pila));
    nueva -> ultimo = 0;
    return nueva;
}

int pila_is_empty (Pila puntero){
    return (puntero->ultimo == 0)? 1 : 0;
}

///No dice qué hacer en caso que la lista sea vacía.
int pila_top (Pila puntero){
    return puntero->datos[puntero->ultimo-1];
}

void pila_push (Pila puntero, int dato){
    if (puntero -> ultimo != MAX_PILA -1)
        puntero -> datos[(puntero->ultimo)++] = dato;
}

void pila_pop (Pila puntero){
    if (puntero -> ultimo != 0)
        puntero->ultimo--;
}

void pila_print (Pila puntero){
    for(int i=0; i < puntero -> ultimo ; i++)
        printf("%d  ", puntero -> datos[i]);

    printf("\n");
}



int main(){
    Pila puntero = pila_new();
    pila_is_empty(puntero)? printf("La pila inicia vacia\n") : printf("Esto no deberia pasar\n");

    pila_push(puntero, 1);
    pila_push(puntero, 2);
    pila_push(puntero, 3);
    pila_push(puntero, 4);
    pila_push(puntero, 5);
    pila_is_empty(puntero)? printf("No deberia pasar\n") : printf("Despues de agregar, deja de estarlo\n");


    pila_print(puntero);
    printf("Tope: %d \n", pila_top(puntero));
    pila_pop(puntero);
    printf("Tope: %d \n", pila_top(puntero));
    pila_print(puntero);
    return 0;
}





///EJERCICIO 2

#include <stdio.h>
#include <stdlib.h>
#define PILA_INICIAL 50

typedef struct _Pila {
    int* datos;
    int ultimo;
    int maximo;
} *Pila;


Pila pila_new(){
    Pila nueva = (Pila) malloc (sizeof(struct _Pila));
    nueva -> datos = (int *) malloc (sizeof(int) * PILA_INICIAL);
    nueva -> ultimo = 0;
    nueva -> maximo = PILA_INICIAL;
    return nueva;
}

int pila_is_empty (Pila puntero){
    return (puntero->ultimo == 0)? 1 : 0;
}

///No dice qué hacer en caso que la lista sea vacía.
int pila_top (Pila puntero){
    return puntero->datos[puntero->ultimo-1];
}

void pila_push (Pila puntero, int dato){
    if (puntero -> ultimo == puntero -> maximo -1){
        puntero -> maximo += PILA_INICIAL;
        puntero -> datos = (int *) realloc (puntero -> datos, sizeof(int) * puntero-> maximo);
    }
        puntero -> datos[(puntero->ultimo)++] = dato;
}

void pila_pop (Pila puntero){
    if (puntero -> ultimo != 0)
        puntero->ultimo--;
}

void pila_print (Pila puntero){
    for(int i=0; i < puntero -> ultimo ; i++)
        printf("%d  ", puntero -> datos[i]);

    printf("\n");
}



int main(){
    Pila puntero = pila_new();
    for(int i=0; i<101; i++)
        pila_push(puntero, 50 - i);
    pila_print(puntero);
    return 0;
}





///EJERCICIO 3

#include <stdio.h>
#include <stdlib.h>

typedef struct _SNodo {
  int dato;
  struct _SNodo *sig;
} SNodo;

typedef SNodo *SList;
typedef SList Pila;


Pila pila_new() {
  return NULL;
}

int pila_is_empty(Pila pila) {
  return pila == NULL;
}

int pila_top (Pila pila){
    return pila -> dato;
}

Pila pila_push(Pila pila, int dato) {
  Pila nuevoNodo = malloc(sizeof(SNodo));
  nuevoNodo -> dato = dato;
  nuevoNodo -> sig = pila;
  return nuevoNodo;
}

Pila pila_pop(Pila pila){
    if(pila != NULL){
        Pila aEliminar = pila;
        pila = pila -> sig;
        free(aEliminar);
    }
    return pila;
}

void pila_print (Pila pila){
    for(; pila != NULL; pila = pila -> sig)
        printf("%d  ", pila -> dato);
    printf("\n");
}

void pila_free (Pila pila){
    for(Pila aux = pila; pila != NULL; pila = aux){
        aux = pila->sig;
        free(pila);
    }
}


int main(){
    Pila puntero = pila_new();
    pila_is_empty(puntero)? printf("La pila inicia vacia\n") : printf("Esto no deberia pasar\n");

    puntero = pila_push(puntero, 1);
    puntero = pila_push(puntero, 2);
    puntero = pila_push(puntero, 3);
    puntero = pila_push(puntero, 4);
    puntero = pila_push(puntero, 5);
    pila_is_empty(puntero)? printf("No deberia pasar\n") : printf("Despues de agregar, deja de estarlo\n");


    pila_print(puntero);
    printf("Tope: %d \n", pila_top(puntero));
    puntero = pila_pop(puntero);
    printf("Tope: %d \n", pila_top(puntero));
    pila_print(puntero);


    pila_free(puntero);
    return 0;
}





///EJERCICIO 4

#include <stdio.h>
#include <stdlib.h>

typedef struct _SNodo {
  int dato;
  struct _SNodo *sig;
} SNodo;

typedef SNodo *SList;
typedef SList Pila;


Pila pila_new() {
  return NULL;
}

int pila_top (Pila pila){
    return pila -> dato;
}

Pila pila_push(Pila pila, int dato) {
  Pila nuevoNodo = malloc(sizeof(SNodo));
  nuevoNodo -> dato = dato;
  nuevoNodo -> sig = pila;
  return nuevoNodo;
}

Pila pila_pop(Pila pila){
    if(pila != NULL){
        Pila aEliminar = pila;
        pila = pila -> sig;
        free(aEliminar);
    }
    return pila;
}

void pila_print (Pila pila){
    for(; pila != NULL; pila = pila -> sig)
        printf("%d  ", pila -> dato);
    printf("\n");
}

SList slist_reverse (SList lista){
    Pila pila = pila_new();

    for(SList aux = lista; aux != NULL; aux = aux -> sig)
        pila = pila_push(pila, aux->dato);

    for(SList aux = lista; aux != NULL; aux = aux -> sig){
        aux -> dato = pila_top(pila);
        pila = pila_pop(pila);
    }
    return lista;
}


int main(){
    Pila puntero = pila_new();

    puntero = pila_push(puntero, 1);
    puntero = pila_push(puntero, 2);
    puntero = pila_push(puntero, 3);
    puntero = pila_push(puntero, 4);
    puntero = pila_push(puntero, 5);
    pila_print(puntero);
    printf("Al reves es fea, cambiemos eso... \n");
    puntero = slist_reverse (puntero);
    pila_print(puntero);
    return 0;
}





///EJERCICIO 5

#include <stdio.h>
#include <stdlib.h>
#define MAX_COLA 50


typedef struct _Cola {
int datos[MAX_COLA];
int primero, ultimo;
} *Cola;

Cola cola_new(){
    Cola puntero = (Cola) malloc (sizeof (struct _Cola));
    puntero -> primero = puntero -> ultimo = 0;
    return puntero;
}

int cola_is_empty (Cola cola){
    return (cola->primero == cola->ultimo)? 1 : 0 ;
}

int cola_front (Cola cola){
    return cola->datos[cola->primero];
}

void cola_enqueue (Cola cola, int dato){
    if(cola -> ultimo != -1){
        cola -> datos [cola -> ultimo] = dato;
        if(cola -> ultimo == MAX_COLA - 1)
            cola -> ultimo = 0;
        else
            cola -> ultimo ++;

        if (cola -> ultimo == cola ->primero)
            cola -> ultimo = -1;
    }
}

void cola_dequeue (Cola cola){
    if (cola -> primero != cola -> ultimo){
        cola -> primero ++;
        if (cola -> ultimo == -1)
            cola -> ultimo = cola -> primero - 1;
    if (cola -> primero == MAX_COLA) cola -> primero = 0;
    }
}

void cola_print(Cola cola){
    if(cola -> ultimo == -1){
        for(int i = cola -> primero, j = 0; j < MAX_COLA ; i++, j++){
            printf("%d   ", cola->datos[i]);
            if(i == MAX_COLA - 1)
                i = -1;
    }
        printf("\n");
    }
    else{
    for(int i = cola -> primero; i != cola -> ultimo; i++){
        printf("%d   ", cola->datos[i]);
        if(i == MAX_COLA - 1)
            i = -1;
    }
    printf("\n");


    }
}




int main(){
    Cola cola = cola_new();
    for (int i = 0; i < MAX_COLA; i++)
        cola_enqueue(cola, i);
    cola_print(cola);


    for (int i = 0; i < MAX_COLA / 2 ; i++)
        cola_dequeue(cola);
    cola_print(cola);


    for(int i = 0; i < MAX_COLA; i++)
        cola_enqueue(cola, i);
    cola_print(cola);

    return 0;
}




///EJERCICIO 6

#include <stdio.h>
#include <stdlib.h>

typedef struct _Cola {
    int dato;
    struct _Cola *anterior, *siguiente;
} *Cola;

Cola cola_new(){
    return NULL;
}

int cola_is_empty (Cola cola){
    return (cola == NULL)? 1 : 0;
}

int cola_front (Cola cola){
    return cola -> dato;
}

Cola cola_enqueue (Cola cola, int dato){
    Cola nuevoNodo = (Cola) malloc (sizeof(struct _Cola));
    nuevoNodo -> dato = dato;

    if (cola == NULL){
        nuevoNodo -> siguiente = nuevoNodo -> anterior = nuevoNodo;
        return nuevoNodo;
    }

    nuevoNodo -> siguiente = cola;
    nuevoNodo -> anterior = cola -> anterior;
    cola -> anterior -> siguiente = nuevoNodo;
    cola -> anterior = nuevoNodo;
    return cola;
}

Cola cola_dequeue (Cola cola){
    if(cola == NULL)
        return NULL;

    if (cola -> siguiente == cola){
        free(cola);
        return NULL;
    }

    cola -> siguiente -> anterior = cola -> anterior;
    cola -> anterior -> siguiente = cola -> siguiente;

    Cola aux = cola -> siguiente;
    free(cola);
    return aux;
}

void cola_print (Cola cola){
    if (cola != NULL){
        printf("%d  ", cola -> dato);
        for(Cola aux = cola -> siguiente; aux != cola; aux = aux ->siguiente)
            printf("%d  ", aux -> dato);
    }

    printf("\n");
}


int main(){
    Cola cola = cola_new();
    cola = cola_enqueue(cola, 1);
    cola = cola_dequeue(cola);
    cola = cola_dequeue(cola);
    (cola_is_empty(cola) == 1)? printf("La cola queda vacia\n") : printf("No deberia pasar\n");
    printf("Esta linea no deberia mostrar nada: ");cola_print(cola);

    for(int i=0; i<10; i++)
        cola = cola_enqueue(cola, i);

    printf("Esta si: ");
    cola_print(cola);

    return 0;
}




///EJERCICIOS 7 Y 10

#include <stdio.h>
#include <stdlib.h>
#define MAX_HEAP 128

typedef struct _BHeap {
    int datos[MAX_HEAP];
    int nelems;
} *BHeap;
 ///datos[0] no existe, escribo desde datos[1].


BHeap bheap_new(){
    BHeap nuevo = (BHeap) malloc (sizeof(struct _BHeap));
    nuevo -> nelems = 0;
    return nuevo;
}

int bheap_is_empty (BHeap heap){
    return (heap -> nelems == 0)? 1 : 0;
}

///No especifica que ocurre si es vacio, supongo que no lo va a ser.
int bheap_min (BHeap heap){
    return heap -> datos[1];
}

void bheap_pop_min (BHeap heap){
    int aux;
    if(! bheap_is_empty(heap) ){
        heap -> datos [1] = heap -> datos [heap -> nelems];
        heap -> nelems --;
        for(int index = 1; index <= heap -> nelems;){
          if(index * 2 + 1 <= heap -> nelems){
            if(heap -> datos[index * 2] <= heap -> datos [index * 2 + 1]){
                aux = heap -> datos [index];
                heap -> datos [index] = heap -> datos[index * 2];
                heap -> datos[index * 2] = aux;
                index *= 2;
              }
            else{
                aux = heap -> datos [index];
                heap -> datos [index] = heap -> datos[index * 2 + 1];
                heap -> datos[index * 2 + 1] = aux;
                index = index * 2 + 1;
              }
            }
          else if(index * 2 <= heap -> nelems && heap -> datos [index * 2] < heap -> datos [index]){
                aux = heap -> datos [index];
                heap -> datos [index] = heap -> datos[index * 2];
                heap -> datos[index * 2] = aux;
                index *= 2;
            }
          else index *= 2;
        }
      }
}

void bheap_insert (BHeap heap, int dato){
    if(heap -> nelems != MAX_HEAP - 1){
        int aux;
        heap -> nelems ++;
        heap -> datos [heap -> nelems] = dato;
        for (int index = heap -> nelems; index > 1; index /= 2){
          if(heap -> datos[index] < heap -> datos[index/2]){
            aux = heap -> datos [index/2];
            heap -> datos [index/2] = heap -> datos [index];
            heap -> datos [index] = aux;
            }
          }
      }
}

void bheap_print (BHeap heap){
  int potencia = 2;
  for(int i = 1; i <= heap -> nelems; i++){
      printf("%d  ", heap -> datos [i]);
      if( (i+1) == potencia){
        printf("\n");
        potencia *= 2;
        }
    }
  printf("\n\n");
}


void bheap_free (BHeap heap){
  free(heap);
}


BHeap bheap_merge (BHeap heap1, BHeap heap2){
    if ( heap1 -> nelems + heap2 -> nelems < MAX_HEAP){
        for (int i = 1; i <= heap2 -> nelems; i++)
            bheap_insert(heap1, heap2->datos[i]);
    }

    return heap1;
}


int main(){
    BHeap pepe = bheap_new(), pepe2 = bheap_new();
    for(int i = 0; i < 20; i++)
      bheap_insert (pepe, 20 - i);
    bheap_print(pepe);

    for(int i = 0; i < 10; i++)
      bheap_pop_min (pepe);
    bheap_print(pepe);

    for(int i = 0; i < 20; i++)
      bheap_insert (pepe2, 100 - 10 * i);

    pepe = bheap_merge(pepe, pepe2);
    bheap_print(pepe);


    bheap_free(pepe);
    bheap_free(pepe2);
    return 0;
}

///EJERCICIO 8

#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 31

///Array circular.
/*
typedef struct arrayCirc{
    int inicio, fin;
    int array[MAX_SIZE];
}*PCola;

void swapp(int* a, int* b){
    int aux = *a;
    *a = *b;
    *b = aux;
}

PCola pcola_crear(){
    PCola nuevo = (PCola) malloc(sizeof(struct arrayCirc));
    nuevo -> inicio = nuevo -> fin = 0;
}

int pcola_esta_vacia(PCola cola){
    return (cola -> inicio == cola -> fin)? 1 : 0;
}

int pcola_minimo(PCola cola){
    return cola -> array[cola -> inicio];
}

void pcola_eliminar_minimo(PCola cola){
    if (!pcola_esta_vacia(cola)){
        cola -> inicio ++;
        if (cola -> inicio == MAX_SIZE)
            cola -> inicio = 0;
    }
}

void pcola_insertar(PCola cola, int dato){
    if (cola -> inicio == (cola -> fin + 1) % MAX_SIZE )
        return;

    int i;
    for(i = cola -> inicio; i != cola->fin && dato > cola -> array[i]; i++)
        if (i == MAX_SIZE - 1) i = -1;

    cola -> fin = (cola -> fin + 1) % MAX_SIZE;
    for(int j = cola -> fin; j != i; j--){
        if(j == 0){
            swapp(&(cola -> array[MAX_SIZE-1]) , &(cola -> array[j]) );
            j = MAX_SIZE;
        }
        swapp(&(cola -> array[j-1]) , &(cola -> array[j]) );
    }
    cola -> array [i] = dato;
}


void pcola_mostrar(PCola cola){
    for(int i = cola -> inicio; i != cola -> fin; i++){
        printf("%d   ", cola -> array[i]);
        if(i == MAX_SIZE - 1) i = -1;
    }
}
*/


///Lista enlazada.
/*typedef struct Nodo{
    int dato;
    struct Nodo* siguiente;
}*PCola;


PCola pcola_crear(){
    return NULL;
}

int pcola_esta_vacia(PCola cola){
    return (cola == NULL)? 1 : 0;
}

int pcola_minimo(PCola cola){
    return cola ->dato;
}

PCola pcola_eliminar_minimo(PCola cola){
    if(cola != NULL){
        PCola aux = cola;
        cola = cola -> siguiente;
        free(aux);
        return cola;
    }
}

PCola pcola_insertar(PCola cola, int dato){
    PCola nuevoNodo = (PCola) malloc (sizeof(struct Nodo));
    nuevoNodo -> dato = dato;
    nuevoNodo -> siguiente = NULL;

    if(cola == NULL)
        return nuevoNodo;

    if (nuevoNodo -> dato <= cola -> dato){
        nuevoNodo -> siguiente = cola;
        return nuevoNodo;
    }

    PCola auxiliar;
    for(auxiliar = cola; auxiliar -> siguiente != NULL && auxiliar -> siguiente -> dato < nuevoNodo -> dato; auxiliar = auxiliar -> siguiente );

    nuevoNodo -> siguiente = auxiliar -> siguiente;
    auxiliar -> siguiente = nuevoNodo;
    return cola;
}


void pcola_mostrar(PCola cola){
    for(;cola != NULL; cola = cola -> siguiente)
        printf("%d   ", cola -> dato);
}
*/


///Heap.
/*
typedef struct heap{
    int cantElementos;
    int array[MAX_SIZE];
}*PCola;


void swapp(int* a, int* b){
    int aux = *a;
    *a = *b;
    *b = aux;
}

PCola pcola_crear(){
    PCola nuevaCola = (PCola) malloc (sizeof(struct heap));
    nuevaCola -> cantElementos = 0;
    return nuevaCola;
}

int pcola_esta_vacia(PCola cola){
    return (cola -> cantElementos == 0)? 1 : 0;
}

int pcola_minimo(PCola cola){
    return cola -> array[0];
}

void pcola_eliminar_minimo(PCola cola){
    if(cola -> cantElementos != 0){
        cola -> array[0] = cola -> array[cola -> cantElementos - 1];
        cola -> cantElementos --;
        for(int i = 0; i * 2 + 1 <= MAX_SIZE - 1 ;){
            if(i * 2 + 2 <= MAX_SIZE - 1){
                if(cola -> array[i*2 + 1] < cola -> array[i*2 + 2]){
                    if(cola -> array[i*2 + 1] < cola -> array[i]){
                        swapp( &(cola -> array[i*2 + 1]), &(cola -> array[i]) );
                        i = i*2 + 1;
                    }
                    else break;
                }
                else{
                    if(cola -> array[i*2 + 2] < cola -> array[i]){
                        swapp( &(cola -> array[i*2 + 2]), &(cola -> array[i]) );
                        i = i*2 + 2;
                    }
                    else break;
                }
            }
            else{
                if(cola ->array[i*2 + 1] < cola -> array[i]){
                    swapp( &(cola -> array[i*2 + 1]), &(cola -> array[i]) );
                    i = i*2 + 1;
                }
                else break;
            }
        }
    }
}



void pcola_insertar(PCola cola, int dato){
    if(cola -> cantElementos != MAX_SIZE){
        cola -> array[cola -> cantElementos] = dato;
        cola -> cantElementos++;

        for(int i = cola -> cantElementos - 1; i > 0; i = (i-1)/2){
            if(cola -> array[(i-1)/2] > cola -> array[i])
                swapp( &(cola -> array[(i-1)/2]), &(cola -> array[i]) );
            else break;
        }
    }
}

void pcola_mostrar(PCola cola){
    for(int i = 0; i < cola -> cantElementos; i++)
        printf("%d   ", cola ->array[i]);
}

*/

int main(){
    PCola cola = pcola_crear();

    printf("Cola vacia: ");
    pcola_mostrar(cola);

    for(int i = 0; i < 50; i++)
        pcola_insertar(cola, 50-i);

    printf("\n\nCola: ");
    pcola_mostrar(cola);

    for(int i = 0; i < 50; i++)
        pcola_eliminar_minimo(cola);

    printf("\n\nCola: ");
    pcola_mostrar(cola);

    return 0;
}



///EJERCICIO 9

#include <stdio.h>
#include <stdlib.h>

void swap (int array[], int pos1, int pos2){
  int aux = array[pos1];
  array[pos1] = array[pos2];
  array[pos2] = aux;
  }

///Versión 1.
void heapify (int array[], size_t largo){
    for(int nuevo = 0; nuevo < largo; nuevo++){
      for(int i = nuevo; i > 0 ; i = (i-1)/2){
        if(array[i] < array[(i-1)/2])
          swap (array, i, (i-1)/2);
        else break;
      }
    }
}

void array_bheap_print (int array[], size_t largo){
  int limite = 0;
  for(int i = 0; i < largo; i++){
      printf("%d  ", array[i]);
      if( i == limite){
        printf("\n");
        limite = limite * 2 + 2;
        }
    }
  printf("\n\n");
}

int check_heap (int array[], size_t largo){
  for(int i=0; i < largo; i++){
    if(i * 2 + 2 < largo &&(array[i] > array[i * 2 + 1] || array[i] > array[i * 2 + 2]))
      return 0;
    }
  return 1;
}


int main(){
  int array[50];
  for (int i=0; i<50; i++)
    array[i] = 100 - 2*i;
  array_bheap_print(array, 50);
  if (! check_heap(array, 50)) printf ("Eso no es un heap\n\n\n");


  heapify(array, 50);
  array_bheap_print(array, 50);
  if(check_heap(array, 50)) printf("Si, eso es un heap\n\n\n");
  return 0;
}