/************************************************************** 

   #Programa#: #prova1AB.c#							
   #Autor#: #Gustavo Sverzut Barbieri#
   #RA#: #008849#
   #Data#: #28/09/2001#
   #Professor#: #João Meidanis#
   #Descrição#: #1o. Prova de MC202 para Turmas A e B#
   #Uso#: #prova1AB < arq.tes > arq.res#
   #Parâmetros#:
     #entrada#: 
       #arq.tes#: #Arquivo de teste.#     
     #saída#:
       #arq.res#: #Arquivo com os resultados do teste.#
**************************************************************/
#include "prova1AB.h"
#include <malloc.h>

/* (2,5) Questão 1: Insere elemento com o valor dado no 
   final da lista (após o último). */
void InsereFinal(Lista **l, int valor){ 
  Lista *noh;
  Lista *tmp;

  if (l != NULL) {
    noh = (Lista *) calloc(1,sizeof(Lista));
    
    noh->valor = valor;
    noh->prox  = NULL;
    tmp = *l;
    
    /* Vai ateh o ultimo noh */
    if (tmp == NULL) /* Vazia */
      *l = noh;
    else {
      while (tmp->prox != NULL)
	tmp = tmp->prox;
      tmp->prox = noh; 
    }
  }
  return;
}

/* (2,5) Questão 2: Usa recursão para calcular a soma dos quadrados dos
   valores armazenados na lista e  retorna o resultado da soma. */
int  SomaQuadrados(Lista *l){ 
  int soma=0;
  if (l != NULL) {
    soma = SomaQuadrados(l->prox);
    soma += l->valor*l->valor;
  }
  return soma;
}


  /* (2,5) Questão 3: Remove o elemento que vem  imediatamente depois 
     do primeiro elemento com o valor dado. Não faz nada, caso o valor
     não exista na lista ou seja o último. */
void RemoveDepois(Lista *l, int valor){
  Lista *tmp;
  Lista *tmp2;

  if (l != NULL) {
  /* Procurar pelo elemento com valor='valor' */
  tmp = l;
  while ( (tmp != NULL) && (tmp->valor != valor))
    tmp = tmp->prox;

  if (tmp != NULL) /* Achou valor */
    if (tmp->prox != NULL) {/* Nao eh o ultimo elemento */
      tmp2 = tmp->prox; /* Guarda apontador a ser liberado */
      tmp->prox = tmp->prox->prox; /* liga ao proximo noh */
      free(tmp2);
    }
  }
  return;
}

 /* (2,5) Questão 4: Coloca os elementos da lista em ordem crescente de
    valores usando ordenação por inserção  e sem o uso de memória adicional 
    do tipo vetor ou outra lista. 
    Dica: troque apenas os valores, nao os apontadores. */
void OrdenaInsercao(Lista *l) {
  Lista *m, *n, *tmp, *o;

  if (l != NULL) {
    m = l;
    n = m->prox;
    while (n != NULL) {
      o = m;
      if (m->valor > n->valor) { 
	tmp = m;
	m = n;
	n = tmp;
	tmp = m->prox;
	m->prox = n;
	n->prox = tmp;
      }
      while (o->prox->valor > n->valor) {
	tmp = o->prox;
	o->prox = n;
	n = tmp;
	tmp = m->prox;
	m->prox = n;
	n->prox = tmp;
      }
      if (n != NULL)
	n = n->prox;
      if (o != NULL)
	o = o->prox;
    }
  }
  return;
}

/* Funções dadas */

void ImprimeLista(Lista *l)
{

  while(l != NULL) {
    fprintf(stdout,"%d ",l->valor);
    l = l->prox;
  }
  fprintf(stdout,"\n");
  
}

void DestroiLista(Lista **l) {
  Lista *m,*n;
  
  m = *l;
  while (m != NULL) {
    n = m->prox;
    free(m);
    m = n;
  }
  *l = NULL;
}


int main(int argc, char **argv) {
  
  Lista *l=NULL; 
  int valor;
  char acao[10]; /* Acao a ser tomada conforme indicado na entrada */

  /* ------------------------------------------------------------

                  VÁLIDO APENAS PARA LINUX

     Declarações para verificação do uso da memória dinâmica.  A
     variável 'lixo' está sendo usada apenas para contornar um
     problema do funcionamento das funções da biblioteca 'malloc': a
     memória por ela apontada é desalocada logo a seguir!
     ------------------------------------------------------------ */
  
  void *lixo = malloc(1);                   /* truque: variável auxiliar */
  
  struct mallinfo info;   
  int MemDinInicial, MemDinFinal;
 
  free(lixo);                              /* truque */
  info = mallinfo();
  MemDinInicial = info.uordblks;
  
  /* ------------------------------------------------------- */


  /* Executa o teste */

  fscanf(stdin,"%s",acao);
  while(strcmp(acao,"t")!=0) { 
    switch(*acao) {
    case 'i': /* Insere elemento com valor dado no final da lista */
      fscanf(stdin,"%d",&valor);
      InsereFinal(&l,valor);
      ImprimeLista(l);
      break;

    case 's': /* Soma quadrado dos valores armazenados usando recursão
                 e retorna resultado. */
      valor=SomaQuadrados(l);
      fprintf(stdout,"%d\n",valor);
      break;

    case 'r': /* Remove elemento imediatamente depois do elemento com o
                 valor dado. */
      fscanf(stdin,"%d",&valor);
      RemoveDepois(l,valor);
      ImprimeLista(l);
      break;

    case 'o': /* Coloca valores em ordem crescente. */
      OrdenaInsercao(l);
      ImprimeLista(l);
      break;

    default:
      fprintf(stderr,"Ação %s inválida\n",acao);
      exit(-1);
    }
    fscanf(stdin,"%s",acao);
  }

  DestroiLista(&l);

  /* ------------------------------------------------------------
     Verificação do uso da memória dinâmica.
     ------------------------------------------------------------ */

  info = mallinfo();
  MemDinFinal = info.uordblks;
  if (MemDinInicial!=MemDinFinal)
    printf("\n\nMemória dinâmica não foi totalmente liberada (%d, %d)\n",
                      MemDinInicial,MemDinFinal);

  /* ------------------------------------------------------------ */

  printf("\n\nFim da execução.\n\n");
  
  return 0;

} /* testpilha */







/* author: Gustavo Sverzut Barbieri (http://www.gustavobarbieri.com.br) */