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

// define a estrutura do no
struct _no {
  char nome[40];
  char telefone[15];
  struct _no *proximo;
};
typedef struct _no No;

// define um ponteiro para o no raiz
No *Raiz=NULL;

void Insere(char *nome, char *telefone) {
  No *Atual;
  No *Anterior;
  No *Inserido;

  // verifica se o nó raiz é nulo. Se for, cria nó raiz com os dados fornecidos
  if (Raiz==NULL) {
    Raiz = (No *)malloc(sizeof(No));
    strcpy (Raiz->nome,nome);
    strcpy (Raiz->telefone,telefone);
    Raiz->proximo = NULL;
  }
  else {  // se já houver raiz

    // percorre a lista encadeada, comecando da raiz. Inicialmente, não
    // há nó anterior
    Anterior = NULL;
    Atual = Raiz;
    while (Atual!=NULL) {
      if (strcmp(Atual->nome,nome)>=0) break; // se o nó atual é
                                              // lexicograficamente superior,
					      // pára
      else {
	Anterior = Atual;
	Atual = Atual->proximo;
      }
    }

    if (Atual != NULL) // só faz a comparação abaixo se existe o nó Atual
      if (strcmp(Atual->nome,nome)==0) {
          printf ("Nome já existente!\n");
 	  return;
    }
    
    // aloca memória para o novo nó
    Inserido = (No *)malloc(sizeof(No));
    
    // coloca o nó na lista encadeada, mudando o ponteiro para o próximo no
    // do nó anterior
    if (Atual != Raiz)
        Anterior->proximo = Inserido;
    else // se atual é nó raiz, atualiza raiz
	Raiz = Inserido;
    
    // coloca dados no nó Inserido
    strcpy (Inserido->nome,nome);
    strcpy (Inserido->telefone,telefone);

    // indica que o próximo nó do nó inserido é o nó apontado por Atual
    Inserido->proximo = Atual;
  }
}

void Busca(char *nome) {
  No *Atual;
 
  // percorre a lista encadeada desde a raiz
  Atual = Raiz;
  while (Atual!=NULL) {
    // verifica se já encontrei ou já passei do nome procurado
    if (strcmp(Atual->nome,nome)>=0)  break;
    else    // se ainda não passou
      Atual = Atual->proximo;
  }
 
  // verifica se o nó atual é mesmo o nó procurado
  if (Atual != NULL)
    if (strcmp(Atual->nome,nome)==0) {
      printf ("Telefone: %s\n",Atual->telefone);
      return;
  }
  
  // se não achou, avisa
  printf ("Nao achei!\n");
}

void Lista() {
  No *Atual;

  printf ("\n");
  Atual = Raiz;
  while (Atual!=NULL) {
    printf ("Nome: %s\n",Atual->nome);
    printf ("Telefone: %s\n\n",Atual->telefone);
    Atual = Atual->proximo;
  }
}

void Deleta(char *nome) {
  No *Atual;
  No *Anterior=NULL;
  char *nomeatual;

  // primeiro, percorre a lista encadeada desde a raiz
  Atual = Raiz;
  while (Atual!=NULL) {
    // verifica se já encontrei ou já passei do nome procurado
    if (strcmp(Atual->nome,nome)>=0) break;
    else  {  // se ainda não passou
      Anterior = Atual;
      Atual = Atual->proximo;
    }
  }
 
  // verifica se o nó atual é mesmo o nó procurado
  if (Atual != NULL)
    if (strcmp(Atual->nome,nome)==0) {  // se for, deleta
      // faz com que o anterior veja o subsequente ao atual como proximo
      if (Atual != Raiz)
	  Anterior->proximo = Atual->proximo;
      else  // se o no atual e a raiz, tenho que atualizar a raiz para ser
	    // o proximo no
	  Raiz = Atual->proximo;
      free(Atual);
      printf ("Nome deletado!\n\n");
      return;
  }

  printf("Nao achei!\n");
}


main () {
int opcao;
char nome[40];
char telefone[15];


do {
  printf("\nLista de telefones:\n\n");
  printf("1 - Buscar por nome\n");
  printf("2 - Listar em ordem alfabetica\n");
  printf("3 - Inserir\n");
  printf("4 - Deletar\n");
  printf("0 - Sair\n\n");
  printf("Opcao: ");
  scanf("%d",&opcao);

  if (opcao == 1 || opcao == 3 || opcao == 4) {
    printf("\nDigite nome: ");
    scanf("%s",nome);
  }

  switch (opcao) {
    case 1: Busca(nome); break;
    case 2: Lista(); break;
    case 3: printf ("Digite telefone: ");
	    scanf ("%s",telefone);
	    Insere(nome,telefone);
	    break;
    case 4: Deleta(nome);
  }
} while (opcao != 0);
	 
}