Estrutura de Dados - Aula 01

Prévia do material em texto

1
Estrutura de Dados
Alocação de memória
Prof. Elias Oliveira
2
Alocação de memória
⚫ Existem três maneiras de reservarmos espaço de memória para o 
armazenamento de informações:
⚫ Uso de variáveis globais (e estáticas).
⚫ Uso de variáveis locais.
⚫ Alocação dinâmica - Requisições ao sistema em tempo de execução.
3
Alocação de memória
⚫ Uso de variáveis globais (e estáticas). O espaço reservado para uma variável 
global existe enquanto o programa estiver sendo executado.
⚫ Uso de variáveis locais. Neste caso o espaço fica reservado apenas enquanto 
a função que declarou a variável está sendo executada, sendo liberado para 
outros usos quando a execução da função termina. 
⚫ As variáveis globais ou locais podem ser simples ou vetores, sendo que no 
caso dos vetores, é preciso informar o número máximo de elementos ou 
tamanho do vetor. 
⚫ A partir do tamanho informado, o compilador reserva o espaço 
correspondente.
4
Alocação de memória
• Alocação dinâmica. 
• O espaço alocado dinamicamente permanece reservado 
até que explicitamente seja liberado pelo programa. 
• Uma vez que o espaço é liberado fica disponível para 
outros usos. 
• Se o espaço alocado não for liberado explicitamente pelo 
programa, este será automaticamente liberado quando a 
sua execução terminar. 
5
Comparando Alocação de memória
Alocação estática:
• Vantagem: Possibilita acesso direto ao local da 
memória, uma vez que os dados se encontram 
armazenados de forma contígua ou sequencial.
• Consequentemente, em alguns casos, as operações de 
busca podem ter custo constante O(1).
6
Comparando Alocação de memória
Alocação estática:
• Desvantagem: É preciso determinar em tempo de codificação, quanto 
espaço é necessário. 
• Esta estimativa pode ser difícil de ser estabelecida e está sujeita a 
flutuações ao longo da execução.
• A alocação sequencial na memória prejudica as operações de inserção 
e remoção, uma vez que a sequencialidade dos dados precisa
• ser preservada. 
• Com isso, no pior caso, o custo destas operações pode ser de O(n).
7
Comparando Alocação de memória
Alocação dinâmica:
• Vantagem: não é necessário fixar o tamanho da estrutura.
• Evita o desperdício de espaço, e o risco de ficar sem espaço é 
reduzido. 
• Não existe restrição do número de inserções e remoções. 
• As operações de inserção e remoção não requerem de nenhum 
esforço adicional uma vez que envolvem somente o ajuste dos 
ponteiros.
8
Comparando Alocação de memória
Alocação dinâmica:
• Desvantagem: Como consequência da não linearidade na 
alocação dos dados, o acesso a um determinado elemento i 
torna necessário o percurso pelos i – 1 elementos anteriores na 
sequência.
• Esta propriedade, que caracteriza o acesso sequencial aos 
dados, torna a operação de busca por um elemento de custo 
O(n).
9
Estrutura de Dados
TAD LISTA 
Prof. Elias Oliveira
10
Listas
⚫ Existem certas estruturas clássicas que se comportam como padrões 
uma vez que são utilizadas na prática em diversos domínios de 
aplicação.
⚫ Existem duas formas de implementação : vetores e ponteiros.
⚫ Iremos iniciar com a TAD Listas.
11
Listas
⚫ As listas estão presentes em 
muitas atividades do dia a dia 
como, por exemplo, uma lista de 
compras de supermercado.
⚫ Um conjunto qualquer de 
elementos pode ser 
representado através de uma 
lista linear. 
12
Listas
⚫ Listas são estruturas flexíveis que possibilitam as inserções e 
remoções em qualquer posição.
⚫ Definição: uma estrutura linear, finita cuja ordem é dada a partir da 
inserção dos seus elementos componentes. 
⚫ As listas são estruturas compostas, constituídas por dados de forma a 
preservar a relação de ordem linear entre eles. 
⚫ Cada elemento na lista pode ser um dado primitivo ou complexo.
13
Listas lineares
⚫ Uma estrutura é dita linear uma vez que seus elementos 
componentes se encontram organizados de forma que todos, a 
exceção do primeiro e último, possuem um elemento anterior e um 
posterior, somente.
14
Listas lineares
• As características básicas da estrutura de dados lista são as seguintes:
• Homogênea. Todos os elementos da lista são do mesmo tipo.
• A ordem nos elementos é decorrente da sua estrutura linear, no entanto os elementos não 
estão ordenados pelo seu conteúdo, mas pela posição ocupada a partir da sua inserção.
• Para cada elemento existe anterior e seguinte, exceto o primeiro, que não possui anterior, e o 
último, que não possui seguinte.
• É possível acessar e consultar qualquer elemento na lista.
• É possível inserir e remover elementos em qualquer posição.
15
Interface do TAD Lista
// Cria uma lista vazia
Lista Criar ()
//insere numa dada posição na lista.
add (Lista , dado, posição)
// Retorna o elemento de uma dada 
posição
get (Lista l, posição);
// Remove o elemento de uma 
determinada posição
remove (Lista l, posição);
// Retorna 1 a lista vazia ou zero não vazia
int Vazia (Lista l);
// Retorna 1 cheia, ou zero vazia.
int Cheia (Lista l);
// Retorna a quantidade de elementos na 
lista.
int Tamanho (Lista l);
//Busca por um determinado elemento 
Busca (Lista l, dado);
//Altera valor do elemento 
set(Lista l, dado, posição);
16
TAD Lista usando alocação estática
⚫ Estruturas de dados que funcionam armazenando dados em um 
único vetor têm muitas vantagens e limitações em comum:
⚫ A estrutura de vetor pode ser usada para representar uma lista. 
⚫ Embora sejam fáceis de implementar Estruturas de dados que usam 
vetores tem alguns problemas.
17
Lista Linear
⚫ Vetores oferecem acesso com tempo constante a qualquer valor no vetor. Isto é o 
que permite que get(Lista l, posição)e set(Lista l, dado, 
posição); sejam executados em tempo constante.
⚫ Adicionar ou remover um elemento perto do meio de uma lista significa que um 
grande número de elementos precisam ser deslocado para abrir espaço para o 
elemento recém-adicionado ou para preencher a lacuna criada pelo elemento 
excluído.
⚫ É por isso que as operações add(Lista , dado, posição) e Remove 
(Lista l,posição); têm tempos de execução que dependem de número de 
elementos e posição.
18
Lista Linear add()
19
Lista Linear remove()
20
Lista Linear
⚫ Vetores não podem expandir ou encolher. Quando o número de 
elementos na estrutura de dados excede o tamanho de base,
⚫ Um novo vetor precisa ser alocado e os dados do vetor antigo 
precisam ser copiados para o novo vetor. Esta é uma operação cara.
21
Lista Linear - add
22
Lista Linear - remove
23
Prática – Listas estáticas
⚫ 1 - Crie uma lista e Reproduza as operações 
24
TAD Lista usando alocação dinâmica
⚫ A alocação de memória é gerenciada sob demanda em tempo de 
execução. 
⚫ Os elementos componentes são organizados em posições não 
contíguas, ficando espalhados ao longo da memória.
⚫ Não é preciso definir o tamanho da estrutura uma vez que o espaço é 
alocado na medida da necessidade.
25
TAD Lista usando alocação dinâmica
⚫ Graficamente, a estrutura de dados para a 
implementação de listas utilizando ponteiros 
é a seguinte:
26
TAD Lista usando alocação dinâmica
⚫ Por exemplo, uma lista com valores de 
ponteiros a endereços reais tem
a seguinte forma::
27
TAD Lista usando alocação dinâmica
⚫ O espaço total de memória gasto pela estrutura é proporcional ao 
número de elementos nela armazenados
⚫ Cada novo elemento inserido na estrutura é alocado um espaço de 
memória para armazená-lo.
⚫ Não é possível garantir que os elementos armazenados na lista 
ocuparão um espaço de memória contíguo, e, portanto não é possível 
ter acesso direto aos elementos da lista. 
⚫ Para isto, é preciso definir a estrutura do nó, como uma estrutura 
auto-referenciada contendo, além do conteúdo de informação, um 
ponteiro ao próximo elemento na sequência. 
28
TAD Lista usando alocação dinâmica
29
TAD Lista usando alocação dinâmica
30
TAD Lista usando alocação dinâmica
31
Variações da TAD Lista
Lista ordenada
• Uma lista ordenadaé uma lista onde seus elementos 
componentes são organizados de acordo a um critério de 
ordenação com base em um campo chave. 
• A ordem estabelecida determina que a inserção de um 
determinado elemento na lista irá a acontecer no lugar correto. 
• A lista pode ser ordenada de forma crescente ou decrescente.
• A função responsável pela busca por um determinado conteúdo 
na lista pode ser adaptado de forma a tornar a busca mais 
eficiente.
32
Variações da TAD Lista
Lista circular
• A convenção consiste em manter a última célula apontando para a primeira. 
• Precisa ser estabelecido um critério de parada de forma a evitar que o percurso na 
lista não encontre nunca o fim. 
• Uma forma padrão é estabelecido com base no número de elementos existentes na 
lista.
33
Variações da TAD Lista
Lista duplamente encadeada
Quando for conveniente o percurso da lista de trás para frente, inclui-se um atributo extra 
na estrutura de dados, contendo um ponteiro para a célula anterior. 
Custo extra no espaço requerido e no trabalho nas inserções e remoções
Simplifica a remoção, pois não mais precisamos procurar a célula anterior (O(n)), uma 
vez que esta pode ser acessada diretamente através do ponteiro correspondente.
34
Bibliografia
⚫ Estrutura de dados/ José Marcio Benite Ramos; Liluyoud Cury de Lacerda; 
Sara Luize Oliveira Duarte; UFMT; Porto Velho, 2013.ISBN 978-85-68172-
02-5. Disponível em: 
http://proedu.rnp.br/bitstream/handle/123456789/1531/15.3_versao_Final_c
om_ISBN-Estrutura_de_Dados_07.07.14.pdf?sequence=1&isAllowed=y
⚫ Cortés, Mariela Inés. Estrutura de dados– 3. ed. – Fortaleza, CE, 2015. 
ISBN: 978-85-7826-440-6. Disponível em: 
https://educapes.capes.gov.br/bitstream/capes/204083/2/Livro_Computaca
o_Estrutura%20de%20Dados.PDF
⚫ Pat, Morin. tradução e adaptação para o português do Brasil:João Araújo - 
Estruturas de Dados Abertas(em Java). Edição 0.1G – 18/08/2021- 
Disponível em: https://github.com/jaraujouerj/Estruturas-de-Dados-Abertos 
http://proedu.rnp.br/bitstream/handle/123456789/1531/15.3_versao_Final_com_ISBN-Estrutura_de_Dados_07.07.14.pdf?sequence=1&isAllowed=y
http://proedu.rnp.br/bitstream/handle/123456789/1531/15.3_versao_Final_com_ISBN-Estrutura_de_Dados_07.07.14.pdf?sequence=1&isAllowed=y
https://educapes.capes.gov.br/bitstream/capes/204083/2/Livro_Computacao_Estrutura%20de%20Dados.PDF
https://educapes.capes.gov.br/bitstream/capes/204083/2/Livro_Computacao_Estrutura%20de%20Dados.PDF
https://github.com/jaraujouerj/Estruturas-de-Dados-Abertos
	Slide 1: Estrutura de Dados
	Slide 2: Alocação de memória
	Slide 3: Alocação de memória
	Slide 4: Alocação de memória
	Slide 5: Comparando Alocação de memória
	Slide 6: Comparando Alocação de memória
	Slide 7: Comparando Alocação de memória
	Slide 8: Comparando Alocação de memória
	Slide 9: Estrutura de Dados
	Slide 10: Listas
	Slide 11: Listas
	Slide 12: Listas
	Slide 13: Listas lineares
	Slide 14: Listas lineares
	Slide 15: Interface do TAD Lista
	Slide 16: TAD Lista usando alocação estática
	Slide 17: Lista Linear
	Slide 18: Lista Linear add()
	Slide 19: Lista Linear remove()
	Slide 20: Lista Linear
	Slide 21: Lista Linear - add
	Slide 22: Lista Linear - remove
	Slide 23: Prática – Listas estáticas
	Slide 24: TAD Lista usando alocação dinâmica
	Slide 25: TAD Lista usando alocação dinâmica
	Slide 26: TAD Lista usando alocação dinâmica
	Slide 27: TAD Lista usando alocação dinâmica
	Slide 28: TAD Lista usando alocação dinâmica
	Slide 29: TAD Lista usando alocação dinâmica
	Slide 30: TAD Lista usando alocação dinâmica
	Slide 31: Variações da TAD Lista
	Slide 32: Variações da TAD Lista
	Slide 33: Variações da TAD Lista
	Slide 34: Bibliografia