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

typedef struct cel {
  int valor;
  struct cel *prox;
} celula;

celula *insere(celula *inicio, int n);

void LiberaLista(celula *inicio);
void LiberaListaR(celula *inicio);
void imprime(celula *inicio);
celula *busca(celula *inicio, int n);
celula *buscaR(celula *inicio, int n);
celula *Remove(celula *inicio, int n); /* remove e' funcao do stdio.h */

int main()
{
  celula *inicio, *p;
  int n;

  inicio = NULL; /* lista vazia */
  
  /* Le inteiros ate um 0 ser digitado */
  printf("Digite um inteiro (0 para terminar): ");
  scanf("%d", &n);
  while (n != 0) {
    inicio = insere(inicio, n);
    if (inicio == NULL) {
      printf("Sem memória\n");
      return 1;
    }
    printf("Digite um inteiro (0 para terminar): ");
    scanf("%d", &n);
  }
    
  imprime(inicio);

  /* Busca inteiros ate um 0 ser digitado */
  printf("Digite numero a ser procurado (0 para terminar): ");
  scanf("%d", &n);
  while (n != 0) {
    p = busca(inicio, n);
    if (p != NULL)
      printf("Inteiro %d encontrado\n", n);
    else
      printf("Inteiro %d nao encontrado\n", n);
    printf("Digite numero a ser procurado (0 para terminar): ");
    scanf("%d", &n);
  }

 /* Remove inteiros ate um 0 ser digitado */
  printf("Digite numero a ser removido (0 para terminar): ");
  scanf("%d", &n);
  while (n != 0) {
    inicio = Remove(inicio, n);
    imprime(inicio);
    printf("Digite numero a ser removido (0 para terminar): ");
    scanf("%d", &n);
  }

  LiberaLista(inicio);

  return 0;
}

/* Insere celula com valor n no inicio da lista 
   devolve endereco do início da nova lista ou NULL se nao foi
   possivel fazer a insercao 
*/

celula *insere(celula *inicio, int n)
{
  celula *nova;

   nova = malloc(sizeof(celula)); /* |nova| -> |_?_|_?_| */

  if (nova == NULL)
    return NULL;

  nova->valor = n;
  nova->prox = inicio;

  return nova;
}

/* Libera memoria alocada para lista */
void LiberaLista(celula *inicio)
{
  celula *ant;

  while (inicio != NULL) {
    ant = inicio;
    inicio = inicio->prox;
    free(ant);
  }
}

/* Libera memoria alocada para lista */
void LiberaListaR(celula *inicio)
{
  celula *ant;

  if (inicio != NULL) {
    ant = inicio;
    inicio = inicio->prox;
    free(ant);
    LiberaListaR(inicio);
  }
}

/* Imprime valores armazenados na lista */
void imprime(celula *inicio)
{
  printf("Valores na lista: ");
  while (inicio != NULL) {
    printf("%d ", inicio->valor);
    inicio = inicio->prox;
  }
  printf("\n");
}

/* Devolve endereco de celula com valor n 
   ou NULL caso esse valor nao apareca na lista
*/
celula *busca(celula *inicio, int n)
{
  while (inicio != NULL) {
    if (inicio->valor == n)
      return inicio;
    inicio = inicio->prox;
  }
  return NULL;
}

/* Devolve endereco de celula com valor n 
   ou NULL caso esse valor nao apareca na lista
*/
celula *buscaR(celula *inicio, int n)
{
  if (inicio == NULL || inicio->valor == n)
    return inicio;
  return busca(inicio->prox,n);
}

/* Remove, se existir, celula com valor n
   Devolve lista sem a celula, com valor possivelmente alterado
*/
celula *Remove(celula *inicio, int n)
{
  celula *corrente, *ant;

  /*                 ant -\  corrente -\
   |inicio| -> |_30_|-| -> |_40_|-| -> |_20_|-| -> |_10_|_/_|
  */

  corrente = inicio;
  ant = NULL;

  while (corrente != NULL && corrente->valor != n) {
    ant = corrente;
    corrente = corrente->prox;
  }

  if (corrente == NULL) /* n nao foi encontrado */
    return inicio;

  if (ant == NULL) /* n esta no inicio */
    inicio = inicio->prox;
  else
    ant->prox = corrente->prox;

  free(corrente);
  return inicio;
}