Please enable JavaScript.
Coggle requires JavaScript to display documents.
abstract data types and data structures, 4.0 - LIst, Stacks and Queues -…
abstract data types and data structures
tipos de dados
uma coleção de valores ou um único valor
Abstract Data Type (ADT)
deifinem um tipo de dado em termo de valores e operações
a implementação de um ADT é uma estrutura de dados
data item
uma parte da informação do tipo(type)
alguns conceitos
encapsulation
esconder detalhes de implementação dos usuários do ADT e proteger de acesso externo
data menbers
as variáveis que definem o espaço necessário para a "data" e armazenam informações
abstração
simplificar sistemas complexos ocultando detalhes desnecessários
4.0 - LIst, Stacks and Queues
4.1 - Listas
definição: sequência finita ordenada de intens
do mesmo tipo ou não
processo de definição do ADT
classe "list"
E = marcador de posição
no ADT declaramos as informações públicas e privadas, as funções, as variáveis...
possui um constructor, um destructor e clear
4.1.1 - Array-Based list implementation
deve ser implementado na classe list
cada função terá o seu tempo de excução
Dynamic Array
permite mudar o tamanho do array para se tornar mais flexível
ex: uso de vetores
4.2.1 - Linked Lists
possui ponteiros e "dynamic memory allocation"
head = primeiro elemento
tail = ultimo elemento
curr = posição atual
uma série de "nodes" (nós)
armazenam um valor, e apontam para o nó seguinte
função insert e remove
precisam inserir ou remover e em seguida atualizar o ponteiro
Freelists
servem para armazenamento e economia de memória
alocam e mantem blocos de memória para reutilização imediata
usamos em progrmas em a(s) lista(s) crescem ou diminuem com frequência
4.1.3 - comparison of list implementation
Array-Based List
Tem um tamanho pré determinado que pode ser limitante
não possuem desperdício de espaço ( com os ponteiros )
mais rápidos em achar a posição do elemento
para inserir e remover elementos precisamos mexer na lista toda
Linked List
só precisam do espaço que está nela
Não possuem limite de tamanho
melhor para tamanhos desconhecidos ou muito variáveis
precisam percorrer toda a listapara achar uma posição
para inserir e remover elementos basta ajustar os ponteiros
de modo geral: quando o array estiver mais da metade cheio se torna melhor
4.4.1 - Element Implementation
podemos armazenar:
ponteiro
várias listas podem apontar para a mesma cópia
Quando não sâo elementos homogêneos usamos um outro ponteiro para armazenar o tipo de cada elemento
também podemos usar o início da lista como "tipo"
elemento
toda vez que inserirmos um elemento ele será duplicado
Problema do gerênciamento de memória
quando tornamos um objeto inacessível mas não apagamos. Causa um vazamento de memória