Resumo Tipo de dados e estrutura de dados

É muito difícil para mim entender esses termos. Eu pesquisei no google e li um pouco na Wikipedia, mas ainda não tenho certeza. Eu determinei até agora que:

Abstract Data Type é uma definição de novo tipo, descreve suas propriedades e operações.

Estrutura de dados é uma implementação do ADT. Muitos ADT podem ser implementados como a mesma estrutura de dados.

Se bem, matriz como ADT significa uma coleção de elementos e como estrutura de dados, como é armazenada na memória. A pilha é ADT com operações push, pop, mas podemos dizer sobre a estrutura de dados da pilha, se eu quis dizer que usei a pilha implementada como uma matriz no meu algoritmo? E por que heap não é ADT? Pode ser implementado como árvore ou matriz.

Simplificando, um ADT (Abstract Data Type) é mais uma descrição lógica, enquanto uma Estrutura de Dados é concreta.

Pense em um ADT como uma imagem dos dados e das operações para manipulá-los e alterá-los.

Uma estrutura de dados é o coisa real e concreta . Pode ser implementado e usado dentro de um algoritmo.

ADT é para uma interface ( o que faz ) o que é uma estrutura de dados para uma classe ( como faz ).

Alguns exemplos:

ADT: List
DS:  ArrayList, LinkedList...

ADT: Map
DS:  HashMap, TreeMap...

Eu acho que você entendeu.

Resumo Tipo de dados: O ADT pode ser definido como um conjunto de valores de dados e operações associadas que são especificadas com precisão, independentemente de qualquer implementação específica. Portanto, um Tipo de Dados Abstrato é uma coleção organizada de informações e um conjunto de operações usadas para gerenciar essas informações. O conjunto de operações define a interface do ADT. Desde que o ADT atenda às condições da interface, não importa realmente como o ADT é implementado. Como no ADT, os valores e operações dos dados são definidos com precisão matemática, e não como uma implementação em uma linguagem de computador, podemos raciocinar sobre os efeitos das operações, relações com outros tipos abstratos de dados, se um programa implementa o tipo de dados etc.

A diferença básica entre o tipo de dados abstratos (ADT) e o tipo de dados concreto é que os últimos nos permitem examinar a representação concreta, enquanto os primeiros nos ocultam a representação. Um ADT pode ser ADT puro ou ADT atualizável. Um ADT puro é aquele em que todas as operações são funções puras. Isso significa que as operações não têm efeitos colaterais. Em particular, eles não modificam ou atualizam os argumentos de entrada. Eles apenas usam esses argumentos para gerar saída, que são novos valores do ADT (ou de outros tipos). A maioria dos tipos de concreto é pura. Por exemplo, nenhuma operação em números inteiros realmente modifica um número inteiro. Em vez disso, todas as operações como '+' produzem novos resultados.

Um ADT atualizável é aquele em que algumas operações realmente alteram os valores do ADT. Por exemplo, suponha que tivéssemos uma operação chamada 'pop' que pegou uma pilha como argumento e a modificou. (“No lugar”, “destrutivamente”) removendo o item de maior prioridade. Essa operação seria considerada impura e todo o ADT também seria impuro. Um ADT pode ser um ADT definido pelo usuário.

Sabemos que um Tipo de Dados Abstrato é um tipo de dados que satisfaz as duas condições a seguir:

1. A representação, ou definição, do tipo e das operações estão contidas em uma única unidade sintática.

2. A representação dos objetos do tipo está oculta das unidades de programa que usam o tipo, portanto, somente as operações diretas possíveis nesses objetos são aquelas fornecidas na definição do tipo.

Um tipo de dados abstrato definido pelo usuário deve fornecer:

1. Uma definição de tipo que permite que as unidades de programa declarem variáveis ​​do tipo, mas oculta a representação dessas variáveis.

2. Um conjunto de operações para manipular objetos do tipo.

Um exemplo de um tipo de dado abstrato definido pelo usuário é a estrutura. 'C' fornece quatro tipos básicos: int, char, float e double. No entanto, 'C' também fornece ao programador a capacidade de definir seus próprios tipos. Estrutura é um exemplo. Uma estrutura é um agregado de partes diferentes, onde cada parte é de algum tipo existente.

struct abc

{int x;

float y;

};

A definição de estrutura acima não cria nenhuma variável, mas cria um novo tipo. Variáveis ​​desse tipo podem ser criadas de maneira semelhante às variáveis ​​de um tipo incorporado.

struct abc a;

A palavra-chave typedef nos permite criar novos nomes de tipos para nossos novos tipos.

Por exemplo:

typedef struct abc AB;

onde AB é um novo nome de tipo que agora pode ser usado para criar novos tipos.

AB b;

Estruturas de dados: A seguir, são apresentados os recursos característicos das estruturas de dados:

1. Ele contém itens de dados do componente, que podem ser atômicos ou outra estrutura de dados (ainda um domínio).

2. Um conjunto de operações em um ou mais dos itens do componente.

3. Define regras sobre como os componentes se relacionam entre si e com a estrutura como um todo (asserções).

Estruturas de dados:

Uma estrutura de dados pode ser estática ou dinâmica. Uma estrutura de dados estática tem um tamanho fixo. Esse significado é diferente do significado de modificador estático. Matrizes são estáticas; Depois de definir o número de elementos que ele pode conter, o número não muda. Uma estrutura de dados dinâmica cresce e diminui no tempo de execução, conforme exigido pelo seu conteúdo. Uma estrutura de dados dinâmica é implementada usando links.

As estruturas de dados podem ainda ser categorizadas em estruturas de dados lineares e estruturas de dados não lineares. Nas estruturas de dados lineares, cada componente possui um predecessor e sucessor exclusivos, exceto o primeiro e o último elementos, enquanto que no caso de estruturas de dados não lineares, não existe essa restrição, pois os elementos podem ser organizados da maneira desejada, restrita pela maneira como usamos para representam esses tipos.

Primeiro, terminologias em estruturas de dados podem ser muito confusas.

O ADT é como a teoria, modelo ou orientação, etc., que informa como uma estrutura de dados deve se comportar, que tipo de operações deve suportar etc. Três tipos de dados abstratos fundamentais são contêineres, dicionários e filas prioritárias. Por exemplo, dicionário, diz-nos que toda estrutura de dados que implementa este dicionário ADT deve suportar pares de valores-chave, pesquisar com base em chaves, inserção de itens, encontrar sucessor e predecessor de uma determinada chave etc.

Agora, tudo o que implementa isso acima do ADT é a estrutura de dados (DS) , estrutura de dados são coisas reais que você implementa em seus problemas e encontra nas bibliotecas. No caso de dicionário, você pode optar por implementá-lo via matriz ou lista vinculada.

Eu acho que a verdadeira confusão surge quando alguém nomeia o DS como ADT, por exemplo, algumas pessoas chamam o DS mencionado como 'Dictionary' em vez de DictImplementation, o que é perfeitamente legal, apenas causa alguma confusão.

Ref: Skiena: O manual de design de algoritmos