Please enable JavaScript.
Coggle requires JavaScript to display documents.
Conjuntos e dicionários - Coggle Diagram
Conjuntos e dicionários
sets
pode ser descrito como uma coleção não ordenada (possivelmente vazia) de itens distintos chamados elementos do conjunto.
definido por uma listagem explícita de seus elementos (por exemplo, S = {2, 3, 5, 7}) ou pela especificação de uma propriedade que todos os elementos do conjunto e somente eles devem satisfazer (por exemplo, S = {n : n é um número primo menor que 10})
Operações
verificar a pertinência de um determinado item em um determinado conjunto; encontrar a união de dois conjuntos, que compreende todos os elementos em um ou em ambos; e encontrar a interseção de dois conjuntos, que compreende todos os elementos comuns nos conjuntos.
Formas de implementação
O primeiro considera apenas conjuntos que são subconjuntos de algum grande conjunto U, chamado de conjunto universal
A segunda e mais comum maneira de representar um conjunto para fins de computação é usar a estrutura de lista para indicar os elementos do conjunto
se um conjunto for representado por uma lista, dependendo da aplicação em questão, pode valer a pena manter a lista em ordem ordenada.
Dicionários
dicionário é um tipo de dado abstrato, ou seja, um conjunto com as operações de busca (pesquisa), inserção e exclusão definidas em seus elementos.
Registro
compreendem vários campos, cada um responsável por manter um determinado tipo de informação sobre uma entidade que o registro representa
Chave
É usado para identificar as entidades representadas pelos registros (por exemplo, o ID do aluno).
Exemplo
Registro do aluno pode conter campos para o ID do aluno, nome, data de nascimento, sexo, endereço residencial, especialização e assim por diante
Hash
baseado na ideia de distribuir chaves entre um array unidimensional H [0..m − 1] chamado de tabela de hash.
A distribuição é feita calculando, para cada uma das chaves, o valor de alguma função predefinida h chamada função hash. Essa função atribui um inteiro entre 0 e m − 1, chamado de endereço de hash, a uma chave.
Hashing aberto
No hash aberto, as chaves são armazenadas em listas vinculadas anexadas às células de uma tabela de hash. Cada lista contém todas as chaves com hash para sua célula
operações
-
Exclusão
é realizada procurando uma chave a ser excluída e, em seguida, removendo-a de sua lista.
Eficiência
todas elas são theta(1) no caso médio se o número de chaves n for aproximadamente igual ao tamanho m da tabela de hash.