#include <stdio.h>
#include <stdlib.h>
#include<cstring>
#include<iostream>
using namespace std;
#define TAM_STR 10
#define TAM_TAB 10

int hash1(char []);
int hashN(char [],int);
void inserir(char* [],char []);
void remover(char*[],char[]);
int buscar(char* [], char[]);
void imprimir(char* []);


int hash1(char s[]){
	int i,sum = 0;
	for(;i<TAM_STR;i++){
		sum+=s[i];	
	}	
	return sum%TAM_TAB;
}
int hashN(char s[],int n){
	int sum = 0,hash2;
	int i = hash1(s);
	for(int j = 0;j<TAM_STR;j++){
		sum += s[j];          			
	}
	hash2 = (sum%(TAM_TAB -1))+1;
		
	return (i + n*hash2)%TAM_TAB;	
}		
void inserir(char* tab[],char* s){
	int n = 0;
	char * din= (char*)malloc(TAM_STR*sizeof(char));
	strcpy(din,s);
	int i = hash1(din);
	while(tab[i] != NULL){
		if (strcmp(tab[i],din) == 0){
			printf("Elemento j existente!"); 
			return;
		}
		if(n == TAM_TAB){
		printf("Tabela Cheia!\n");
		}
		n++;
		i = hashN(din,n);
	}
	tab[i] = din;
}	
int buscar(char* tab[],char s[]){
	int cont = 0;
	int i = hash1(s);
	char* din = (char*)malloc(TAM_STR*sizeof(char));
	strcpy(din,s);
	while(strcmp(tab[i],din)!= 0){
		if(cont == TAM_TAB){
			printf("Lista Percorrida, elemento no encontrado");	
			return -1;
		}	
		if(tab[i] == NULL){
			printf("Elemento no encontrado!");
			return -1;	
		}	
		cont++;	
		i = hashN(din,cont);
	}
	printf("Elemento %s encontrado na posicao %d\n",tab[i],i);	
	return i;
}	

void imprimir(char* tab[]){
	printf("(");
	for(int i =0;i<TAM_TAB;i++){
		if(tab[i] == NULL){
			printf(" ,");
			continue;			
		}	
		printf("%s, ",tab[i]); 	
	}
	printf(")\n");
}
void remover(char*tab[],char s[]){
	int cont = 0;
	char * din =(char*)malloc(TAM_STR*sizeof(char));
	strcpy(din,s);
	int i = buscar(tab,din);
	if (i == -1){
		printf("Elemento nao encontrado!");	
		return;
	}	
	else
	tab[i] =NULL;
	
}	
int main(){
	int in;
	char buffer[10];
	char* tab[TAM_TAB];
	for(int i =0;i<TAM_TAB;i++){
		tab[i] = NULL;	
	}	
	
	while(true){
		printf("Digite (1)Inserir (2)Remover (3)Buscar (4)Imprimir\n");
		cin>>in;
		switch(in){
			case 1:
			scanf("%s",buffer);
			inserir(tab,buffer);
			break;
			
			case 2:
			scanf("%s",buffer);
			remover(tab,buffer);
			break;
			
			case 3:
			scanf("%s",buffer);
			buscar(tab,buffer);
			break;
			
			case 4:
			imprimir(tab);
			break;
		}
	}	
		
		
}