Desenvolva um programa que implemente uma Tabela Hash com tratamento de colisões do tipo lista. O elemento a ser armazenado será uma agenda telefônica com nome (item chave) e telefone. A agenda deve apresentar funções na forma de menu.

TabTelHash.cpp

/* Desenvolva um programa que implemente uma Tabela Hash com tratamento de colisões do tipo lista. O elemento a ser armazenado será uma agenda telefônica com nome (item chave) e telefone. A agenda deve apresentar funções na forma de menu. O No deve ser implementado da seguinte forma:
struct NO {
   char nome[1000]; 
   char tel[13];
   NO *prox;
};
*/

// Criado por: profa. Divani Barbosa Gavinier
// Curriculo Lattes: http://lattes.cnpq.br/8503400830635447
// divanibarbosa@gmail.com

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
////////////////////////////////////////////////
struct NO {
   char nome[1000]; 
   char tel[13];
   NO *prox;
};
//////////////////////////////////////////////////
class ListaSE {
  private: NO *primeiro; 
           NO *ultimo; 

  public: ListaSE() { primeiro = ultimo = NULL; }  
  
  bool vazio() { return (primeiro==NULL);  }

  void insere_lista(char *n, char *t) {
     NO *lista = new NO; 
     strcpy(lista->nome,n);
     strcpy(lista->tel,t);
     lista->prox = primeiro;
     primeiro = lista; 
  }   
  
  bool pesquisa_lista(char *chave) {
    NO *atual = primeiro;
    while (atual != NULL) {  
      if( stricmp( atual->nome,chave) == 0) return true;
      atual = atual->prox;
    }
    return false;
  }

  void imprime_lista() {
    NO *atual = primeiro;
    while (atual != NULL) {   
      cout << atual->nome << " " << atual->tel << " -> ";
      atual = atual->prox;
    }
  } 

  void apaga_lista(char *valor) {  
    NO *atual, *anterior;
    atual = anterior = primeiro;
    while (atual != NULL) { 
      if ( stricmp(atual->nome,valor)==0 ) break;
      anterior = atual;
      atual = atual->prox;
    }
    if (atual == NULL) return;
    if (atual == primeiro) { primeiro = primeiro->prox;
                             anterior = NULL;
    }
    else if (atual == ultimo) { ultimo = anterior;
                                ultimo->prox = NULL;
         }
         else anterior->prox = atual->prox;
    delete atual; 
  }
  
  void imprimenumero(char *chave) {
    NO *atual = primeiro;
    while (atual != NULL) {  
      if( stricmp( atual->nome,chave) == 0) cout << atual->tel;
      atual = atual->prox;
    }
  }
  
};
//////////////////////////////////////////////////
class HashLista {
  private:	ListaSE *tab;
  			bool *ocupado;
  			int tam_max;
  
  public: HashLista(int n) {
    tab = new ListaSE[n];
    ocupado = new bool[n];
    tam_max = n;
    for(int i=0; i<n; i++) ocupado[i] = false;
  }  
  
  private: int funcaohash(char *chave) {
	  int h = chave[0];    
	  for(int i=0; i<strlen(chave); i++)
	     h = (h * 251 + chave[i]) % tam_max; 
	  return abs(h);
  }
  
  public: void insere(char *chave, char *t) {
    int pos = funcaohash(chave);
    if (tab[pos].pesquisa_lista(chave)) { 
         cout << " Nome " << chave << " duplicado (ja cadastrado)\n";
         return; 
    }
    tab[pos].insere_lista(chave,t); // insere item na lista
    if ( !ocupado[pos] ) ocupado[pos] = true;
  }
  
  void apaga(char *chave) {
    int pos = busca(chave);
    if (pos == -1) cout << "ATENCAO: Nome nao encontrado\n";
    else tab[pos].apaga_lista(chave);
  }

  void imprime() {
    for (int i=0; i<tam_max; i++) { 
       if ( ocupado[i] ) {
       		cout << "HASH[" << i << "] -> ";
       		tab[i].imprime_lista();
       		cout << " NULL\n";
	   }
    }
  }

  int busca(char *chave) {
    int pos = funcaohash(chave);
    if ( tab[pos].pesquisa_lista(chave) ) {
    	cout << "Numero ";
		tab[pos].imprimenumero(chave);
		cout << endl;
    	return pos;
	}
    return -1;
  }
  
}; 
////////////////////////////////////////////////
main() {
    HashLista tab(31);
    char nome[1000], tel[13];
    int opcao;
    cout << "\n*************************************************\n";
    cout << " AGENDA TELEFONICA Tabela HASH colisao Lista\n";
    cout << " REGISTRO DE AGENDA TELEFONICA (Nome e Telefone)\n";
    while(true) {
		cout << "*************************************************\n";   
		cout << "1. Armazenar um registro\n";
		cout << "2. Obter telefone\n";
		cout << "3. Remover registro\n"; 
		cout << "4. Listar todos os registros\n";
		cout << "5. Sair do programa\n";
		cout << "-> Informe a opcao desejada: ";
		cin >> opcao;
		if (opcao == 5) break;
		if (opcao == 1) {
			cout << "-> Informe nome: ";
			fflush(stdin);
			gets(nome);
			cout << "-> Informe o telefone: ";
			fflush(stdin);
			gets(tel);
			tab.insere(nome,tel);
		}	
		if (opcao == 2) {
			cout << "-> Informe nome que deseja buscar: ";
			fflush(stdin);
			gets(nome);
			if (tab.busca(nome) == -1) {
				cout << "ATENCAO: Nome nao encontrado\n";
			}			
		}
		if (opcao == 3) {
			cout << "-> Informe nome que deseja remover: ";
			fflush(stdin);
			gets(nome);
			tab.apaga(nome);
		}
		if (opcao == 4) {
			tab.imprime();
		}
	}
}