Estruturas de Dados - Tabela Hash (implementação)

Olá caros alunos sejam bem-vindos hoje nós vamos falar sobre tabelas redes só que agora nós falaremos sobre a implementação de tabelas hash utilizando a linguagem ser mas não Brasil hoje nós vamos seguir este roteiro aqui eu vou dar uma breve explicação sobre a aplicação que utilizaremos hoje depois eu falarei sobre o tipo abstrato de dados queremos implementar depois eu darei alguns detalhes de implementação e depois eu falarei sobre algum uso dessa implementação que eu estou fazendo apenas inserção e remoção de elementos da estrutura de dados Hoje vamos falar sobre aplicação dessa estrutura em geral nós podemos utilizar as tabelas hash sempre que nós queremos armazenar uma coleção de dados e depois obter os registros de maneira eficiente se a função de resta por bem estruturada nós conseguiremos inserir e obter os valores em tempo com estantes fala sobre aplicação nós vamos supor que estamos em uma universidade e que queremos organizar os alunos em uma estrutura e posteriormente fazer as buscas pelo registro acadêmico o r a Ou seja a chave de busca que nós queremos é o r a é com essa chave que nós queremos as músicas em tempo constante vamos supor também que a única informação que nós queremos os alunos é o nome então dentro aqui dessa minha classe aluno a única informação além do HFA é o nome aqui nós temos alguns métodos construtores é o primeiro deles é um Construtor sem nenhum parâmetro esse Construtor sem nenhum parâmetro ele vai ser utilizado na locação dinâmica de memória tá todos os elementos eles vão ser alocados utilizando este Construtor aqui e eu vou também colocar um aluno aqui eu vou criar você era um Construtor para que o usuário ou a pessoa que vai utilizar essa casa possa configurar o r a e possa configurar o nome da maneira que bem entender além desses métodos eu tenho o Gates nome para obter o nome alcatra e huguette ef a para obter o r a a implementação desse método dessa classe vai ser feita como basicamente no Construtor fazer o da classe aluno a única coisa que eu preciso colocar é R A = -1 que vai significar para mim que aquela posição do vetor está vazia depois nome vai ser igual a uma stringhi significando o poder a qualquer qualquer coisa aqui porque eu poderia colocar qualquer coisa porque quem vai indicar que aquela posição do vetor está vazia é o r a = -1 tá vamos assumir que dentro dessa nossa escola todos os alunos Jessé E aí a maior do quiser então sei QRA = -1 em válido então eu sei que esse aluno aqui é esse registro de aluno é inválido então ele vai representar para mim uma posição vazia dentro de uma tabela é se é assim que eu vou interpretar e agora o outro construtor é um Construtor que vai receber um R A por parâmetro e eu vou colocar esse r a que veio por parâmetro no meu atributo e também vai receber em nome e eu vou colocar esse nome que veio por parâmetro no meu atributo Ou seja simplesmente Para instanciar um objeto utilizando um r a e o nome e se eu quiser obter o nome Eu uso as o método get nome bom E se eu quiser obter um r a partir de uma Instância da classe aluno Eu uso o Galaxy r a São essas as ideias bom então vamos falar sobre o tipo abstrato de dados no tipo abstrato de dados eu vou ter um Construtor has tá E nesse Construtor Eu tenho um maxxion C = 100 indicando aqui que o número máximo de elementos = 100 e se a pessoa não colocar nada então o número máximo de elementos vai ser igual assim eu prefiro olhar essas implementações utilizando o próprio código então no material de apoio você tem aqui aluno. CPP e aluno. H que são os que eu já falei tem também o resto.

H E essa estrutura de essa esse tipo abstrato de dados tem um base que pontos tpp que a implementação que eu vou apresentar hoje tem esse rest application pontos CPP que é a implemento que é uma uso dessa minha réstia. H e tem esse linear para o ponto CPP que nós não vamos ver na aula de hoje nós veremos na próxima aula então se você quiser compilar esses arquivos não esqueça você teria que colocar os e mais mais aluno. Se app desde que Pontos CPP e rest application a Pepê isso funcionaria você não pode colocar o líder Pub.

CPP E por quê Porque senão você teria duas implementações da classe mexe estou você coloco Basic pontos IP ou Linea pro bivolt CP só você não faria gemas mais asteriscos pontos CPP nesse caso aqui porque daria esse erro que vocês viram agora então vamos olhar o resto. H no resto. H nós temos o Construtor tá como eu já estava falando Max itans igual acende dizendo se a pessoa não disser nada então o valor default será sem temos também um de instrutor para deslocar os recursos temos também um método chamado Expo para verificar se eu já preenchi por exemplo se eu coloquei sem eu quero saber se eu já preenchi todos temos um método Guedes lento para saber quantos elementos realmente estão nessa estrutura temos uma I will start right on utility tom vou falar sobre eles o print e alguns atributos privados aqui embaixo por exemplo o Max iTunes algum outro que eu vou falar daqui a pouco e assim por diante Deixa eu só ver qual são os outros nós temos o que é terrestre um método privado O que é terrestre temos o Max A então o número máximo de elementos na minha estrutura temos o Len número de elementos que realmente estão na minha estrutura e temos esse último aqui aluno* structure que significa um ponteiro aqui significa o meu vetor de objetos aluno Vamos começar com um método privado get it has tá só para saber qual é a função de resto que nós estamos utilizando bem aqui tá eu vou abrir o arquivo res.

se mexe na base que ponto CPP na aula de hoje nós estamos estudando desde que Pontos CPP e ao final desse arquivo existe a implementação do GAP has Então qual é a função de resto que nós estamos utilizando todo o aluno vai ter um R A então dentro de aluno teremos um r a e esse é real vai ser um número é só um número qualquer 10 100 1000 nós queremos utilizar esse r a como o índice do vetor entretanto ele pode extrapolar os limites do vetor para que isso não ocorra eu composto o módulo Ou melhor o resto da divisão pelo número de elementos que tem no meu vetor Então se no meu vetor tem sem elementos eu quero que os índices sejam Diz ela até 99 essa função aqui aluno. br a mod Max ai tá mas ela vai pegar o RH do aluno e vai gerar um valor entre 0 e 99 na hora de hoje nós vamos assumir que essa função aqui não gera a colisões então Esses códigos que estão em bens que Pontos CPP eles assumem a não existência de Horizontes um outro método que a gente precisa olhar vamos passar já pro metros e metros de diâmetro e Atom inside I Tom e de Elite aqui eu vou começar com o cliente então vou procurar o Vitor me enviarem aqui dentro do meu arquivo CPP desde que ponto CPP e vou colocar este muito e ainda aqui em evidência vamos entender primeiro os parâmetros que estão sendo passados para o Vitor ir viagem Então primeiramente está sendo passado um parâmetro que é um objeto aluno e esse objeto está sendo Pará passado como referência temos outro parâmetro que é uma variável do tipo booleana e essa variável também está sendo passada por referência daí você se pergunta porque eu estou passando por referência a resposta é a seguinte alguém que vai chamar essa função ela terá que declarar a o principal um algo o seguinte sentido aluno aluno e daí ela vai ter que dar também para esse aluno o RH que eu vou ter que buscar por exemplo lá Faria aluno aluno e diria o RH por exemplo 10 colocaria o nome Brasil então a pessoa alguém gerou um aluno Mas ela tá querendo dizer essa pessoa quiser o aluno ela pensa Eu gostaria muito de ter as informações desse aluno um Eu queria um nome desse aluno entre a tanta não tem o nome desse aluno só tem um índice o nome desse aluno está na tabela hash se ela já criou a variável e depois o que que ela vai fazer ela vai invocar na tabela resto por exemplo aga. io Eaton e Seria algo como h.

net viagem e ela passaria esse aluno como parâmetro Então seria aluno, uma variável booleana que ela passaria aqui e essa função entre ver a Então tem que ela Faria ela faria uma busca na estrutura de dados interna se achar o elemento ela vai colocar o valor na própria variável aluno e como ela foi passada por referência eu sei que o que eu quiser com a variável aluno aqui dentro vai ocorrer aqui fora então A ideia é que esse parâmetro aqui se primeiro parâmetro ele vai me passar a chave de busca e ele já é o local onde eu tenho que colocar o aluno caso encontro na minha tabela da implementação foi feita dessa forma tão voltando para cá como eu vou fazer então a implementação o aluno tiver por parâmetro vai me dar a localização no Array como Invocando o método Get The Rest que eu já falei para vocês então a location = get Fast aluno ele vai me devolver um inteiro entre 0 e o tamanho do Array eu sei que eu tenho que ir nessa posição buscar o aluno então eu vou né uma estrutura que é o meu vetou nesta posição e obtenho qual o objeto que está lá e coloca na variável Alves É sim o aluno que veio por parâmetro tiver um R A diferente do RH que estava na minha na minha estrutura de dados eu digo pão de igual a false de novo estamos assumindo aqui que não temos colisões não vamos procurar em nenhum outro lugar se não estava justamente naquele índice eu não vou procurar um lugar nenhum porque porque eu estou assumindo que não existem condições aqui tá caso contrário por exemplo o aluno o RH do aluno que veio por parâmetro é igual ao RH que estava na minha estrutura de dados então eu coloco o Fofão igual a true para fora dessa função a pessoa saber olha realmente ele encontrou e eu vou colocar aluna igual aos isso vai fazer com que esse aluno que veio por parâmetro agora tem o mesmo conteúdo de alta então a pessoa que chamou essa função vai ter na sua variável localmente o valor que estava no na minha estrutura de dados bom então essa ideia eu dou muito enviai Tom é interessante entender esses esses parâmetros aqui passada como referências é opção bom exercício bom e as outras funções em Street Fighter e de leite Airton elas são um pouquinho mais fáceis insert ai Tom ela simplesmente recebe um aluno por parâmetro esse aluno eu vou colocar em algum lugar dentro da minha estrutura interna onde eu vou colocar depende da função de resto Então usa location igual a get it has aluno ou seja essa função de guerra terrestre aluna vai pegar o Eva e vai colocar vai criar devolver um inteiro entre 0 e o tamanho do vetor menos um então eu vou nessa posição na minha estrutura passa o instrutor location é igual aluno ou seja uso RH do aluno para dizer a posição e nessa posição eu coloco a Lu oi e daí eu coloco excelente mas mais para dizer para interpretar de mais um ou o número de elementos que estão na estrutura para basicamente isso insertion está fazendo ele funciona se não houver em condições se houver coalizão então por exemplo esse aluno aqui vai ser colocado em cima de um outro aluno com RH diferentes por quê Porque os dois apontaram para o mesmo lugar então saibam esse código não funcionaria na presença de colisões ele assume ausência de condições e o deleite aí tá Mack ele é muito semelhante a um insert Python aqui no de Elite até o procuro a localização usando essa minha função get rest novamente e daí o quê que eu faço eu vou naquela posição de memória structure location eu digo structure location é igual aluno só que esse aluno sem nenhum parâmetro por quê Porque o aluno sem nenhum parâmetro ele automaticamente me diz que a web a e vai ser igual a menos um o que para mim indica que é um aluno inválido e um nome aqui igual a vazão Então vai ser essa minha interpretação e aqui vai ter um lento menos menos dizendo Olha eu consegui remover um aluno de novo só que funciona bem se não houver em condições e e o print ele vai ser simplesmente um for pela estrutura imprimindo todos os campos inclusive os campos iguais a menos um Então você tem um aluno que não existe vai imprimir o r = -1 e aqui vai imprimir também o nome igual a vazio então ele imprimir todo mundo que está no Array indistintamente a função get Cash eu já mencionei para vocês acredita que só falte mencionar a função as funções que estão no topo desse arquivo 1 e o Construtor aqui ele simplesmente a louca região de memória dinamicamente ou seja de ló com um vetor o destrutor desloca esse vetor essas variáveis aqui esses atributos aqui simplesmente dizem o número de elementos que realmente estão na minha estrutura pluga máximo de elementos que podem existir nessa minha estrutura e eu respondo ele verifica se nem é igual a Max ato bom Então essa é a minha implementação utilizando ser mais e como seria o uso dela uso dela a gente pode ver nesse has underline application. CPP e eu vou direto aqui para função Nem que a função que importa da função meio para cima acredito que vocês entendam basicamente tudo o que que eu estou colocando aqui o estou gerando 10 alguma rece capaz de suportar 10 alunos ou seja resto alunos Régis 10 aqui então vou criar um vetor de 10 elementos e onde nesses elementos eu possa colocar alunos e os é reagir dos alunos que eu quero colocar são esses aqui mil 12704 31. 300 e assim por diante é e o número 10 aí foi bem escolhido por quê Porque é fácil saber as condições dos rios eu vou colocar a pessoa com esse r a e com esse nome vai ser o primeiro aluno segundo aluno vai ser com esse r a e com esse nome o terceiro ano vai ser esse a e esse nome é isso que eu vou fazer mais adiante é mas por hora saiba que como são só dez elementos eu sei que 12 que esse número aqui esse 12704 ele vai colidir com esse um dois três quatro porque porque eles terminam com quatro e o resto da divisão por 10 vai dar o mesmo valor é ótima mas isso aqui significa simplesmente que eu estou criando R as Estou criando o nome espectivos e aqui dentro desse for eu tô enterando por todos esses reais e todos esses nomes e estou colocando na minha tabela hash são alunos has ontem ser Titan aluno e aqui eu estou dando um alunos rece ponto print para verificar Onde estão localizados os alunos eu vou colocar os temas mais aqui vou compilar o código e vou colocar.

/A ponto antes para saber o que é que ficou dentro da minha estrutura bom então o print da minha estrutura após as sessões foram esses aqui e daí você vai perceber ou é mas tem um dois três quatro cinco apenas cinco elementos aqui os outros estão com menos um indicando que estão vazios e daí você se pergunta então o que que aconteceu acho que tinha mais gente ela dentro certo certo vamos ver e o que que aconteceu foi Pedro ele foi colocado inicialmente na posição quatro entretanto Paulo foi colocado em cima do Pedro porque porque o Paulo e o Pedro eles têm uma colisão eu falei essa estrutura aquela funcionaria perfeitamente não houvesse tem condições então provavelmente lá fora não dá mais para ver o Pedro por conta da colisão com o Paulo e por conta da colisão que teve com Paulo vou ter que comprar de novo Ah tá e na verdade eu nem consigo ver o Paulo porque teve ainda uma outra coisa visão que ainda tirou o Paulo dessa posição que foi a colisão com a Samanta então eu coloquei o Pedro nessa posição depois eu coloquei o Paulo em cima dele e por fim eu coloquei a Samanta em cima do Paulo então só para você entender código está funcionando apenas se não houvesse tem condições e oi e daí só para mostrar para vocês que está funcionando como funciona eu criei aqui embaixo um novo aluno Oi e esse novo aluno ele tem ra12 704 eu vou voltar aqui para o começo do código ele ficar quem tem esse r a quem tem Sra é o Pedro Então eu estou procurando alguém com Sra Oh e vamos ver o que que ele acha para mim ir É sobre o quê que foi que ele imprimiu E aí Ah tá eu criei o aluno eu creio um booleano found e depois eu invoquei esse retriever ai Tom depois de invocar este material então eu procurei por esse aluno tá e verifiquei o quê que foi retornado como esse 12704 já não existe mais o que que vai acontecer esse aluno.