Estrutura de dados - Data structure

Uma estrutura de dados conhecida como tabela hash .

Na ciência da computação , uma estrutura de dados é um formato de organização, gerenciamento e armazenamento de dados que permite acesso e modificação eficientes. Mais precisamente, uma estrutura de dados é uma coleção de valores de dados, as relações entre eles e as funções ou operações que podem ser aplicadas aos dados, ou seja, é uma estrutura algébrica sobre os dados .

Uso

Estruturas de dados servem como base para tipos de dados abstratos (ADT). O ADT define a forma lógica do tipo de dados. A estrutura de dados implementa a forma física do tipo de dados.

Diferentes tipos de estruturas de dados são adequados para diferentes tipos de aplicativos e alguns são altamente especializados para tarefas específicas. Por exemplo, bancos de dados relacionais normalmente usam índices de árvore B para recuperação de dados, enquanto implementações de compilador geralmente usam tabelas hash para procurar identificadores.

As estruturas de dados fornecem um meio de gerenciar grandes quantidades de dados com eficiência para usos como grandes bancos de dados e serviços de indexação da Internet. Normalmente, estruturas de dados eficientes são fundamentais para projetar algoritmos eficientes . Alguns métodos de design formal e linguagens de programação enfatizam as estruturas de dados, ao invés de algoritmos, como o principal fator de organização no design de software. As estruturas de dados podem ser usadas para organizar o armazenamento e a recuperação de informações armazenadas na memória principal e na memória secundária.

Implementação

As estruturas de dados geralmente são baseadas na capacidade de um computador de buscar e armazenar dados em qualquer lugar de sua memória, especificado por um ponteiro - uma string de bits, representando um endereço de memória , que pode ser armazenado na memória e manipulado pelo programa. Assim, a matriz e as estruturas de dados de registro são baseadas na computação dos endereços de itens de dados com operações aritméticas , enquanto as estruturas de dados vinculadas são baseadas no armazenamento de endereços de itens de dados dentro da própria estrutura.

A implementação de uma estrutura de dados geralmente requer a escrita de um conjunto de procedimentos que criam e manipulam instâncias dessa estrutura. A eficiência de uma estrutura de dados não pode ser analisada separadamente dessas operações. Essa observação motiva o conceito teórico de um tipo de dado abstrato , uma estrutura de dados que é definida indiretamente pelas operações que podem ser realizadas sobre ela e as propriedades matemáticas dessas operações (incluindo seu custo de espaço e tempo).

Exemplos

Python 3. O tipo padrão hierarchy.png

Existem vários tipos de estruturas de dados, geralmente construídas sobre tipos de dados primitivos mais simples :

  • Uma matriz é um número de elementos em uma ordem específica, normalmente todos do mesmo tipo (dependendo do idioma, os elementos individuais podem ser todos forçados a ser do mesmo tipo ou podem ser de quase qualquer tipo). Os elementos são acessados ​​usando um índice inteiro para especificar qual elemento é necessário. Implementações típicas alocam palavras de memória contíguas para os elementos de arrays (mas nem sempre isso é uma necessidade). As matrizes podem ter comprimento fixo ou redimensionável.
  • Uma lista vinculada (também chamada apenas de lista ) é uma coleção linear de elementos de dados de qualquer tipo, chamados de nós, onde cada nó possui um valor para si e aponta para o próximo nó na lista vinculada. A principal vantagem de uma lista vinculada em relação a uma matriz é que os valores sempre podem ser inseridos e removidos com eficiência sem realocar o restante da lista. Algumas outras operações, como o acesso aleatório a um determinado elemento, são mais lentas em listas do que em matrizes.
  • Um registro (também chamado de tupla ou estrutura ) é uma estrutura de dados agregada . Um registro é um valor que contém outros valores, normalmente em número e sequência fixos e geralmente indexados por nomes. Os elementos dos registros geralmente são chamados de campos ou membros .
  • Uma união é uma estrutura de dados que especifica quais dos vários tipos primitivos permitidos podem ser armazenados em suas instâncias, por exemplo, float ou inteiro longo . Compare com um registro , que pode ser definido para conter um float e um inteiro; enquanto em um sindicato, há apenas um valor de cada vez. Espaço suficiente é alocado para conter o tipo de dados de membro mais amplo.
  • Uma união marcada (também chamada de variante , registro de variante , união discriminada ou união disjunta ) contém um campo adicional que indica seu tipo atual, para segurança de tipo aprimorada.
  • Um objeto é uma estrutura de dados que contém campos de dados, como um registro, bem como vários métodos que operam no conteúdo dos dados. Um objeto é uma instância na memória de uma classe de uma taxonomia . No contexto da programação orientada a objetos , os registros são conhecidos como estruturas de dados simples e antigas para distingui-los dos objetos.

Além disso, gráficos e árvores binárias são outras estruturas de dados comumente usadas.

Suporte de linguas

A maioria das linguagens assembly e algumas linguagens de baixo nível , como BCPL (Basic Combined Programming Language), carecem de suporte integrado para estruturas de dados. Por outro lado, muitas linguagens de programação de alto nível e algumas linguagens assembly de alto nível, como MASM , têm sintaxe especial ou outro suporte interno para certas estruturas de dados, como registros e matrizes. Por exemplo, as linguagens C (um descendente direto de BCPL) e Pascal suportam structs e registros, respectivamente, além de vetores ( arrays unidimensionais ) e arrays multidimensionais.

A maioria das linguagens de programação apresenta algum tipo de mecanismo de biblioteca que permite que implementações de estrutura de dados sejam reutilizadas por diferentes programas. As linguagens modernas geralmente vêm com bibliotecas padrão que implementam as estruturas de dados mais comuns. Os exemplos são a C ++ Standard Template Library , o Java Collections Framework e o Microsoft .NET Framework .

Linguagens modernas também geralmente suportam programação modular , a separação entre a interface de um módulo de biblioteca e sua implementação. Alguns fornecem tipos de dados opacos que permitem aos clientes ocultar detalhes de implementação. Linguagens de programação orientadas a objetos , como C ++ , Java e Smalltalk , normalmente usam classes para esse propósito.

Muitas estruturas de dados conhecidas têm versões concorrentes que permitem que vários threads de computação acessem uma única instância concreta de uma estrutura de dados simultaneamente.

Veja também

Referências

Bibliografia

Leitura adicional

links externos