Please enable JavaScript.
Coggle requires JavaScript to display documents.
MAPA MENTAL 5 Daniel Nascimento (dns3) - Coggle Diagram
MAPA MENTAL 5 Daniel Nascimento (dns3)
Abstract Data Types and Data Structures
existem duas implementações tradicionais para o tipo de dados lista: a lista vinculada e a lista baseada em array.
O tipo de dados lista pode, portanto, ser implementado usando uma lista vinculada ou um array. Até mesmo o termo “matriz” é ambíguo, pois pode se referir a um tipo de dados ou a uma implementação.
“Matriz” é comumente usado em programação de computadores para significar um bloco contíguo de locais de memória, onde cada local de memória armazena um item de dados de comprimento fixo.
No entanto, array também pode significar um tipo de dados lógico composto por uma coleção (normalmente homogênea) de itens de dados, com cada item de dados identificado por um número de índice.
a estrutura de dados usada para implementar uma matriz esparsa é um grande array bidimensional que armazena apenas relativamente poucos valores diferentes de zero.
uma variável inteira é um membro do tipo de dados inteiro. A adição é um exemplo de operação no tipo de dados inteiro. Deve ser feita uma distinção entre o conceito lógico de um tipo de dados e sua implementação física em um programa de computador.
ADT
Um tipo de dados abstrato (ADT) é a realização de um tipo de dados como um componente de software. A interface do ADT é definida em termos de um tipo e um conjunto de operações nesse tipo. O comportamento de cada operação é determinado pelas suas entradas e saídas.
Um ADT não especifica como o tipo de dados é implementado. Esses detalhes de implementação ficam ocultos para o usuário do ADT e protegidos contra acesso externo, um conceito conhecido como encapsulamento.
Uma estrutura de dados é a implementação de um ADT. Em uma linguagem orientada a objetos como C++, um ADT e sua implementação juntos formam uma classe. Cada operação associada ao ADT é implementada por uma função ou método membro.
apresenta a terminologia e motiva o processo de design incorporado na abordagem de três etapas para selecionar uma estrutura de dados. Essa motivação decorre da necessidade de gerenciar a tremenda complexidade do computador
O termo “estrutura de dados” geralmente se refere a dados armazenados na memória principal de um computador. O termo relacionado estrutura de arquivos geralmente se refere à organização de dados em armazenamento periférico, como uma unidade de disco ou CD.
LISTA
O conceito mais importante relacionado às listas é o de posição.
Definimos uma lista como uma sequência ordenada e finita de itens de dados conhecidos como elementos. “Ordenado” nesta definição significa que cada elemento possui uma posição na lista.
Nas implementações de listas simples discutidas neste capítulo, todos os elementos da lista possuem o mesmo tipo de dados, embora não haja objeção conceitual a listas cujos elementos possuem tipos de dados diferentes se a aplicação assim o exigir.
a lista ADT pode ser usada para listas de números inteiros, listas de caracteres, listas de registros de folha de pagamento e até mesmo listas de listas.
Dizemos que uma lista está vazia quando não contém elementos. O número de elementos armazenados atualmente é chamado de comprimento da lista. O início da lista é chamado de cabeça, o final da lista é chamado de cauda.
a primeira posição na lista é denotada como 0. Assim, se houver n elementos na lista, eles receberão as posições de 0 a n − 1 como ha0, a1, ..., an− 1i.
Implementação de lista baseada em array
AList herda da classe abstrata List e, portanto, deve implementar todas as funções-membro de List. A parte privada da classe AList contém os membros de dados da lista baseada em array. Isso inclui listArray, o array que contém os elementos da lista.
Como listArray deve ser alocado em algum tamanho (FIXO), o tamanho do array deve ser conhecido quando o objeto de lista for criado.
Com este parâmetro o usuário pode indicar o número máximo de elementos permitidos na lista.
Se nenhum parâmetro for fornecido, então ele assume o valor defaultSize, que é assumido como um valor constante definido adequadamente.
Como cada lista pode ter um array de tamanhos diferentes, cada lista deve lembrar seu tamanho máximo permitido. O membro de dados maxSize atende a esse propósito.
A qualquer momento, a lista contém, na verdade, um número de elementos que pode ser menor que o máximo permitido pelo array. Este valor é armazenado em listSize.
Como listArray, maxSize, listSize e curr são todos declarados privados, eles só podem ser acessados por métodos da classe AList.
1 more item...
Listas vinculadas
A segunda abordagem tradicional para implementar listas faz uso de ponteiros e geralmente é chamada de lista vinculada.
A lista vinculada utiliza alocação dinâmica de memória, ou seja, aloca memória para novos elementos da lista conforme necessário.
Uma lista vinculada é composta por uma série de objetos, chamados de nós da lista.
Como um nó de lista é um objeto distinto (em oposição a simplesmente uma célula em um array), é uma boa prática criar uma classe de nó de lista separada.
Um benefício adicional da criação de uma classe de nó de lista é que ela pode ser reutilizada pelas implementações vinculadas para as estruturas de dados de pilha e fila apresentadas posteriormente neste capítulo.
Os objetos na classe Link contêm um campo de elemento para armazenar o valor do elemento e um campo next para armazenar um ponteiro para o próximo nó na lista. A lista construída a partir de tais nós é chamada de lista vinculada individualmente, ou lista unidirecional, porque cada nó da lista possui um único ponteiro para o próximo nó.
1 more item...
Implementações de elementos
Se os elementos forem registros de folha de pagamento, pode ser desejável que o nó da lista armazene um ponteiro para o registro em vez de armazenar uma cópia do próprio registro. Essa alteração permitiria que vários nós de lista (ou outras estruturas de dados) apontassem para o mesmo registro, em vez de fazer cópias repetidas do registro. isso não apenas pode economizar espaço, mas também significa que uma modificação no valor de um elemento é refletida automaticamente em todos os locais onde ele é referenciado.
A desvantagem de armazenar um ponteiro para cada elemento é que o ponteiro requer espaço próprio. Se os elementos nunca forem duplicados, esse espaço adicional adicionará sobrecarga desnecessária.
As implementações C++ para listas apresentadas nesta seção dão ao usuário da lista a escolha de armazenar cópias de elementos ou ponteiros para elementos.
Se é mais vantajoso usar ponteiros para elementos compartilhados ou cópias separadas depende da aplicação pretendida. Em geral, quanto maiores os elementos e mais duplicados, maior a probabilidade de os ponteiros para elementos compartilhados serem a melhor abordagem.
Um segundo problema enfrentado pelos implementadores de uma classe de lista (ou qualquer outra estrutura de dados que armazene uma coleção de elementos de dados definidos pelo usuário) é se todos os elementos armazenados devem ser do mesmo tipo.
1 more item...
Comparação de implementações de lista
As listas baseadas em array têm a desvantagem de que seu tamanho deve ser predeterminado antes que o array possa ser alocado.
As listas baseadas em array não podem crescer além do tamanho predeterminado.
Sempre que a lista contém apenas alguns elementos, uma quantidade substancial de espaço pode ser ocupada em um array praticamente vazio. As listas vinculadas têm a vantagem de só precisarem de espaço para os objetos que realmente estão na lista.
Não há limite para o número de elementos em uma lista encadeada, desde que haja memória de armazenamento livre disponível. A quantidade de espaço exigida por uma lista vinculada é Θ(n), enquanto o espaço exigido pela implementação da lista baseada em array é Ω(n), mas pode ser maior.
1 more item...