Coleção (tipo de dados abstratos) - Collection (abstract data type)

Em ciência da computação , uma coleção é um agrupamento de algum número variável de itens de dados (possivelmente zero) que têm algum significado compartilhado para o problema que está sendo resolvido e precisam ser operados juntos de alguma forma controlada. Geralmente, os itens de dados serão do mesmo tipo ou, em linguagens que suportam herança, derivados de algum tipo ancestral comum. Uma coleção é um conceito aplicável a tipos de dados abstratos e não prescreve uma implementação específica como uma estrutura de dados concreta , embora frequentemente haja uma escolha convencional (consulte Container para discussão da teoria de tipo ).

Exemplos de coleções incluem listas , conjuntos , multisets , árvores e gráficos .

Arrays de tamanho fixo (ou tabelas) geralmente não são considerados uma coleção porque contêm um número fixo de itens de dados, embora geralmente desempenhem um papel na implementação de coleções. Matrizes de tamanho variável são geralmente consideradas coleções.

Coleções lineares

Muitas coleções definem uma ordem linear particular, com acesso a uma ou ambas as extremidades. A estrutura de dados real que implementa tal coleção não precisa ser linear - por exemplo, uma fila de prioridade geralmente é implementada como um heap , que é um tipo de árvore. Coleções lineares importantes incluem:

Listas

Em uma lista, a ordem dos itens de dados é significativa. Itens de dados duplicados são permitidos. Exemplos de operações em listas são pesquisar um item de dados na lista e determinar sua localização (se houver), remover um item de dados da lista, adicionar um item de dados à lista em um local específico, etc. Se o principal As operações na lista consistem na adição de itens de dados em uma extremidade e na remoção de itens de dados na outra; geralmente é chamada de fila ou FIFO . Se as operações principais forem a adição e remoção de itens de dados em apenas uma extremidade, será chamada de pilha ou LIFO . Em ambos os casos, os itens de dados são mantidos na coleção na mesma ordem (a menos que sejam removidos e reinseridos em outro lugar) e, portanto, esses são casos especiais da coleção de listas. Outras operações especializadas em listas incluem classificação, onde, novamente, a ordem dos itens de dados é de grande importância.

Pilhas

Uma pilha é uma estrutura de dados LIFO com duas operações principais: push , que adiciona um elemento ao "topo" da coleção, e pop , que remove o elemento superior.

Filas

Filas prioritárias

Em uma fila de prioridade, os rastreamentos do item de dados mínimo ou máximo na coleção são mantidos, de acordo com algum critério de ordenação, e a ordem dos outros itens de dados não importa. Pode-se pensar em uma fila de prioridade como uma lista que sempre mantém o mínimo ou o máximo na cabeça, enquanto os elementos restantes são mantidos em uma sacola.

Filas duplas

Filas prioritárias duplas

Coleções associativas

Em vez disso, outras coleções podem ser interpretadas como uma espécie de função: dada uma entrada, a coleção produz uma saída. Coleções associativas importantes incluem:

Um conjunto pode ser interpretado como um multiconjunto especializado, que por sua vez é uma matriz associativa especializada, em cada caso, limitando os valores possíveis - considerando um conjunto representado por sua função de indicador .

Jogos

Em um conjunto, a ordem dos itens de dados não importa (ou é indefinida), mas itens de dados duplicados não são permitidos. Exemplos de operações em conjuntos são a adição e remoção de itens de dados e a pesquisa de um item de dados no conjunto. Alguns idiomas suportam conjuntos diretamente. Em outros, os conjuntos podem ser implementados por uma tabela hash com valores fictícios; apenas as chaves são usadas para representar o conjunto.

Multisets

Em um multiset (ou bag), como em um conjunto, a ordem dos itens de dados não importa, mas, neste caso, itens de dados duplicados são permitidos. Exemplos de operações em multisets são a adição e remoção de itens de dados e a determinação de quantas duplicatas de um determinado item de dados estão presentes no multiset. Multisets podem ser transformados em listas pela ação de classificação.

Matrizes associativas

Em uma matriz associativa (ou mapa, dicionário, tabela de pesquisa), como em um dicionário, uma pesquisa em uma chave (como uma palavra) fornece um valor (como uma definição). O valor pode ser uma referência a uma estrutura de dados composta. Uma tabela hash geralmente é uma implementação eficiente e, portanto, esse tipo de dados costuma ser conhecido como "hash".

Gráficos

Em um gráfico, os itens de dados têm associações com um ou mais outros itens de dados na coleção e são como árvores sem o conceito de uma raiz ou relacionamento pai-filho, de modo que todos os itens de dados são pares. Exemplos de operações em gráficos são travessias e pesquisas que exploram as associações de itens de dados à procura de alguma propriedade específica. Os gráficos são freqüentemente usados ​​para modelar situações do mundo real e para resolver problemas relacionados. Um exemplo é o protocolo Spanning tree , que cria uma representação gráfica (ou malha) de uma rede de dados e descobre quais associações entre nós de comutação precisam ser quebradas para transformá-la em uma árvore e, assim, evitar que os dados circulem em loops.

Arvores

Em uma árvore, que é um tipo especial de gráfico, um item de dados raiz tem associado a ele algum número de itens de dados que, por sua vez, têm associado a eles alguns outros itens de dados no que é frequentemente visto como um relacionamento pai-filho . Cada item de dados (exceto a raiz) tem um único pai (a raiz não tem pai) e algum número de filhos, possivelmente zero. Exemplos de operações em árvores são a adição de itens de dados para manter uma propriedade específica da árvore para realizar a classificação, etc. e travessias para visitar itens de dados em uma sequência específica.

As coleções de árvores podem ser usadas para armazenar dados hierárquicos naturalmente, que são apresentados em forma de árvore, como sistemas de menu e arquivos em diretórios em um sistema de armazenamento de dados.

Árvores especializadas são usadas em vários algoritmos. Por exemplo, a classificação de heap usa um tipo de árvore chamada heap .

Conceito abstrato vs. implementação

Conforme descrito aqui, uma coleção e os vários tipos de coleções são conceitos abstratos. Existe na literatura uma confusão considerável entre os conceitos abstratos da ciência da computação e suas implementações específicas em várias linguagens ou tipos de linguagens. Asserções de que coleções como listas, conjuntos, árvores, etc. são estruturas de dados, classes ou tipos de dados abstratos devem ser lidas com isso em mente. Coleções são, antes de mais nada, abstrações úteis na formulação de soluções para problemas de computação. Vistos sob essa luz, eles retêm links importantes para conceitos matemáticos subjacentes que podem ser perdidos quando o foco está na implementação.

Por exemplo, uma fila de prioridade é frequentemente implementada como um heap, enquanto uma matriz associativa é frequentemente implementada como uma tabela hash, portanto, esses tipos abstratos são frequentemente referidos por esta implementação preferida, como um "heap" ou "hash", embora isso não é estritamente correto.

Implementações

Algumas coleções podem ser tipos de dados primitivos em uma linguagem, como listas, enquanto coleções mais complexas são implementadas como tipos de dados compostos em bibliotecas, às vezes na biblioteca padrão . Exemplos incluem:

Referências

links externos