2013/2-AED-TAD Lista Arquivo .H

// TAD LISTA

// Tipos de dados
typedef int TipoChave;

struct T_Item{
  TipoChave Chave;
};

typedef struct T_Item TipoItem;

typedef struct T_Celula * TipoApontador;

struct T_Celula{
  TipoItem Item;
  TipoApontador Prox;
};

typedef struct T_Celula TipoCelula;

struct T_Lista{
  int Tamanho;
  int Capacidade;
  TipoApontador Primeiro, Ultimo;
};

typedef struct T_Lista TipoLista;

// Cabeçalho das operações

// inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item);
// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item);
// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item);
// verificar se estah cheia
int ListaCheia(TipoLista Lista);
// verificar se estah vazia
int ListaVazia(TipoLista Lista);
// criar uma nova lista
void CriarLista(TipoLista * Lista, int capacidade);
// obter o tamanho da lista
int TamanhoLista(TipoLista Lista);
// imprimir a lista
void ImprimirLista(TipoLista Lista);

// Implementação das operações

void CriarLista(TipoLista * Lista, int capacidade){
// 1) criar a celula cabeça
  Lista->Primeiro = (TipoApontador) malloc(
                             sizeof( TipoCelula));
// 2) atualizar os apontadores Prim. e Ult.
  Lista->Ultimo = Lista->Primeiro;
// 3) atualizar o tamanho (zero) e capacidade (parametro)
  Lista->Tamanho = 0;
  Lista->Capacidade = capacidade;
// 4) atualizar o apontador prox da celula cabeca
  Lista->Primeiro->Prox = NULL;
}

// inserir uma chave na lista
void InserirLista(TipoLista * Lista, TipoItem item)
{
  //1 ) verificar se LISTA estah cheia
  if (ListaCheia(*Lista) == 1){
    printf("ERRO: lista cheia!\n");return;
  }
  //2 ) criar nova celula a partir da ultima celula
  Lista->Ultimo->Prox = (TipoApontador)
      malloc(sizeof(TipoCelula));
  //3 ) inserir a chave na celula
  Lista->Ultimo->Prox->Item = item;
  //4 ) atualizar apontadores (prim e ult.)
  Lista->Ultimo = Lista->Ultimo->Prox;
  Lista->Ultimo->Prox = NULL;
  //5 ) atualizar tamanho
  Lista->Tamanho++;
}

// retirar uma chave da lista
void RetirarLista(TipoLista * Lista, TipoItem * item)
{
  TipoApontador aux, q;
  //1) verificar se LISTA estah vazia
  if(ListaVazia(*Lista) == 1){
    printf("ERRO: lista vazia");return;
  }
  //2) guardar a celula anterior (aux)
  aux = Lista->Primeiro;
  //3) guardar a celula a ser removida (q)
  q = aux->Prox;
  //4) atualizar a celula anterior
  aux->Prox = q->Prox;
  //5) obter o item removido
  *item = q->Item;
  //6) liberar o espaco de memoria de q
  free(q);
  //7) decrementar tamanho
  Lista->Tamanho--;
}

// pesquisar por uma chave na lista
int PesquisarLista(TipoLista Lista, TipoItem item)
{
  TipoApontador aux;
  int i = -1;
  //1) verificar se LISTA estah vazia
  if (ListaVazia(Lista) == 1){
    printf("ERRO: lista vazia!\n");return;
  }
  //2) inicializar o apontador aux
  aux = Lista.Primeiro;
  //3) enquanto houver celula apos aux
  while (aux->Prox != NULL &&
     aux->Prox->Item.Chave != item.Chave){
  //3.1) se a chave que estiver na celula apos aux
  //     for igual a chave procurada
  //3.2) atualizar aux
    aux = aux->Prox;
    i++;
  }
  if (aux->Prox !=NULL){
    // achei
    printf("Elemento encontrado!\n");
  } else {
    // nao achei
    printf("Elemento NAO encontrado!\n");
  }
  return i;
}

// verificar se estah cheia
int ListaCheia(TipoLista Lista){
  if (Lista.Tamanho == Lista.Capacidade)
  {  return 1; // lista cheia
  } else {
    return 0;  //lista nao cheia
  }
}
// verificar se estah vazia
int ListaVazia(TipoLista Lista)
{
  if (Lista.Primeiro == Lista.Ultimo)
  { return 1; // lista vazia
  } else {
    return 0; // lista nao vazia
  }
}
// obter o tamanho da lista
int TamanhoLista(TipoLista Lista){
  return Lista.Tamanho;
}
// imprimir a lista
void ImprimirLista(TipoLista Lista)
{
  TipoApontador aux;
 
  printf("TAD Lista [%d/%d]\n",
     Lista.Tamanho, Lista.Capacidade);
  //1) verificar se LISTA estah vazia
  if (ListaVazia(Lista) == 1){
    printf("ERRO: lista vazia!\n");return;
  }
  //2) inicializar o apontador aux
  aux = Lista.Primeiro;
  //3) enquanto houver celula apos aux
  while (aux->Prox != NULL){
  //3.2) atualizar aux
    printf("%d -> ", aux->Prox->Item.Chave);
    aux = aux->Prox;
  }
  printf("\n\n");
}