Estruturas-Dinamica

Prévia do material em texto

Ponteiros
● São Estruturas de dados semelhantes as variáveis que tem como 
valor de armazenamento um endereço de memória que comporta 
uma estrutura de dados simples ou complexa.
● Ex:
int p = NULL; → Ponteiro p (*p) do tipo inteiro;
● Esse ponteiro tem a capacidade de guardar um endereço de 
memória que suporta um valor do tipo inteiro. Esse ponteiro 
armazena uma estrutura simples;
p = new(int); → atribui ao ponteiro um endereço de memória 
vazio, com capacidade de um inteiro.
*p = 10; → altera o conteúdo do endereço de memória alocado no 
ponteiro.
 
Ponteiros
p
0x210F9A
*p
0x210F9A
Modelo A Modelo B
10
Modelo A – o valor de p = 0x210F9A
Modelo B – o valor de *p = 10
 
Listas Dinâmicas
● Essas estruturas utilizam formatos de 
manipulação de dados e um marcador 
lógico que indica diretamente o próximo 
elemento da lista, contudo não apresentam 
uma quantidade pré-definida de elementos
● Os marcadores dinâmicos utilizam 
estruturas de alocação direta de memória 
RAM chamados de ponteiros.
 
Listas Dinâmicas
● Os ponteiros são estruturas de dados que 
armazenam, como conteúdo, endereços de 
memória RAM.
● Apesar de não tratarmos os valores de 
memória manualmente, os ponteiros podem 
 realizar trocas e atribuições como uma 
variável simples
● As estruturas de listas dinâmicas podem ter 
1 ou mais ponteiros como referência.
 
Listas Dinâmicas
● As operações com listas dinâmicas são as 
mesmas das listas estáticas: inclusão 
(início, fim e qualquer posição), exclusão 
(início, fim e qualquer posição) e 
impressão/pesquisa.
 
Listas Dinâmicas
● Estrutura de uma lista dinâmica
typedef struct listad;
struct listad{
int ra;
listad *prox;
};
listad inicio=null, novo=null, aux=null;
 
Listas Dinâmica – Inclusão 
no fim
subrotina ld_inclui_fim
 se(inicio == nulo)
 inicio = aloca(elemento);
 leia(inicio);
 inicio → prox = nulo;
 senão inicio
 aux = inicio;
 enquanto(aux → prox != nulo)
 aux = aux → prox;
 novo = aloca(elemento);
 leia(novo);
 aux → prox = novo;
 fim 
 
Listas Dinâmica – Inclusão 
no fim
void ld_inclui_fim(){
novo = new(listad); // ou em C inicio = malloc(sizeof(listad));
printf(“ digite o RA: %d”, inicio->ra);
scanf(“%d”, &novo->ra);
novo->prox = null;
 if(inicio == null)
 inicio = novo;
else {
 aux = inicio;
 while(aux->prox != null)
 aux = aux->prox;
 aux->prox = novo; }
 }
 
Listas Dinâmica – Inclusão no 
fim
fim_lista=0x5fe234:49fff
A B C
proximo
 
Listas Dinâmica – Inclusão no 
fim
fim_lista=0x5fe234:49fff
A B C
proximo
D
novo
 
Listas Dinâmica – Inclusão no 
fim
fim_lista=0x9AAA:00123
A B C
proximo
D
novo
 
Listas Dinâmicas – Inclusão 
no início
subrotina ld_inclui_inicio
 inicio
 se(inicio == nulo)
inicio = aloca(elemento);
leia(inicio);
inicio → prox = nulo;
 senão inicio
 novo = aloca(elemento);
 leia(novo);
 novo → prox = inicio;
novo = inicio;
 fim
 fim
 
Listas Dinâmicas – Inclusão 
no início
void ld_inclui_inicio(){
 novo = new(listad); // ou em C inicio = malloc(sizeof(listad));
printf(“ digite o RA: %d”, inicio->ra);
scanf(“%d”, &novo->ra);
novo->prox = null;
 if(inicio == null)
 inicio = novo;
else{
 novo->prox = inicio;
inicio = novo;
 }
 }
 
Listas Dinâmica – Inclusão no 
fim
fim_lista=0x5fe234:49fff
A B C
proximo
 
Listas Dinâmica – Inclusão no 
fim
fim_lista=0x5fe234:49fff
A B C
proximo
D
novo
início
 
Listas Dinâmica – Inclusão no 
fim
fim_lista=0x5fe234:49fff
A B C
proximo
D
novo
início
 
Listas Dinâmica – Inclusão no 
fim
fim_lista=0x5fe234:49fff
A B C
proximo
D
novo
início
 
Listas Estáticas - Exclusão
subrotina exclui_inicio
 se(inicio == nulo)
 Escreva(“lista vazia”)
 senão inicio
 inicio = inicio → prox 
 fim
 
Listas Estáticas - Exclusão
void exclui_inicio(){
 if(inicio == null)
 printf(“lista vazia”)
else{
 aux = inicio;
delete(aux); // Em C dispose(aux); 
inicio = inicio->prox;
 }
}
 
Listas Dinâmica – Exclusão no 
início
fim_lista=0x5fe234:49fff
A B C
proximo
D
início
 
Listas Dinâmica – Exclusão no 
início
fim_lista=0x5fe234:49fff
A B C
proximo
D
início
 
Listas Dinâmica – Exclusão no 
início
fim_lista=0x5fe234:49fff
A B C
proximo
D
início
 
Listas Estáticas - Exclusão
subrotina ld_exclui_fim
 se(inicio == nulo)
 Escreva(“lista vazia”)
 senão inicio
 ultimo = inicio;
 penultimo = inicio;
 enquanto( ultimo → prox != nulo)
 ultimo = ultimo → prox;
 enquanto( penultimo → prox != ultimo)
 penultimo = penultimo → prox
 penultimo → prox = nulo;
 fim
 
Listas Estáticas - Exclusão
void ld_exclui_fim(){
 if(inicio == null)
 printf(“lista vazia”)
 else{
 ultimo = inicio;
 penultimo = inicio;
 while( ultimo-> prox != null)
 ultimo = ultimo->prox;
 while( penultimo-> prox != ultimo)
 penultimo = penultimo-> prox
 penultimo-> prox = nulo;
 delete(ultimo); // dispose(ultimo);
 }
 
Listas Dinâmica – Exclusão no 
fim
A B C
proximo
D
início
ultimo
 
Listas Dinâmica – Exclusão no 
fim
A B C
proximo
D
início
ultimo
 
Listas Dinâmica – Exclusão no 
fim
A B C
proximo
D
início
ultimo
 
Listas Dinâmica – Exclusão no 
fim
A B C
proximo
D
início
ultimo
 
Listas Dinâmica – Exclusão no 
fim
A B C
proximo
D
início
ultimo
inícioinício
penultimo
 
Listas Dinâmica – Exclusão no 
fim
A B C
proximo
D
início
ultimo
inícioinício
penultimo
 
Listas Dinâmica – Exclusão no 
fim
A B C
proximo
D
início
ultimo
inícioinício
penultimo
 
Listas Dinâmica – Exclusão no 
fim
A B C
proximo
D
início
ultimo
inícioinício
penultimo
 
Listas Dinâmica – Exclusão no 
fim
A B C
proximo
D
início
ultimo
inícioinício
penultimo
 
Recursividade
● Metodologia de interação (loop) que utiliza uma 
estrutura diferenciada através do empilhamento das 
execuções de uma subrotina
● A recursão é estruturada em:
– Condição de Parada → momento em que o código 
irá parar de empilhar execuções e deverá retornar 
um valor;
– Código Recursivo → chamada da própria subrotina 
através de uma função acumulativa
● Os código recursivos são mais rápidos e simples que 
os comandos de repetição usuais.
 
Recursividade
● Exemplo:
int somatorio (int x){
 if(x == 1) {
return(1);}
 else 
return(x + somatorio(x-1));
}
 
Recursividade
● Exemplo:
int fatorial (int x){
 if(x == 1) {
return(1);}
 else 
return(x * fatorial(x-1));
}
 
Recursividade
if(x == 1) return(1)
elsereturn(3+somatorio(2))
printf(somatorio(3));
if(x == 1) return(1)
elsereturn(2+somatorio(1))
if(x == 1) return(1) somatorio(1)
somatorio(2)
somatorio(3)
1
3
6Árvores Binárias
● É uma estrutura de dados utilizada na distribuição das informações 
seguindo um padrão pré-determinado
● O padrão utilizado é o seguinte:
– O primeiro elemento incluído na árvore é classificado como raíz;
– Os próximos elementos a serem adicionados serão incluídos a 
direita, se o seu valor for maior que a raíz, e a esquerda caso o 
valor do elemento seja menor que a raíz.
● Seu sistema de busca dos elementos podem auxiliar na melhoria de 
desempenho na ordenação desses elementos ou no próprio acesso 
a eles.
● Os elementos mais externos sem conexão com outros elementos são 
chamados de nós folhas e os demais nós raizes.
 
Árvores Binárias
Esquerda
10
Direita
raiz
8 15
1295
 
Árvores Binárias
● A estrutura de uma árvore binário em linguagem C:
typedef struct arvore;
struct arvore
{
 int val; → conteúdo do nó
 arvore *e; → indicador (ponteiro) da ramificação à esquerda
 arvore *d;→ indicador (ponteiro) da ramificação a direita
};
arvore raiz = NULL, aux = NULL; aux2 = NULL;
 
Árvores Binárias
● Criação de um novo elemento na memória no formato do elemento 
da árvore
void novo_no()
{
 aux = new(arvore);
 aux->e = NULL;
 aux->d = NULL;
 std::cin>>aux->val;
}
 
Árvores Binárias
● Inserção recursiva seguindo as regras de árvores binárias
*arvore insere(arvore *novo, arvore *tmp)
{
 if(tmp == NULL)
 {
 return(novo);
 }
 else{
 if(novo->val > tmp->val)
 tmp->d = insere(novo->val, tmp->d);
 if(novo->val < tmp->val)
 tmp->e = insere(novo->val, tmp->e);
 return(tmp);
 } 
}
 
Árvores Binárias
● Buscas em Árvores Binárias são metodologias de como acessar os 
elementos da árvore binária
void preordem(arvore *tmp)
{
 if(tmp != NULL)
 {
 cout<<tmp->val;
 preordem(tmp->e);
 preordem(tmp->d);
 }
}
 
Árvores Binárias
● Buscas em Árvores Binárias são metodologias de como acessar os 
elementos da árvore binária
void emordem(arvore *tmp)
{
 if(tmp != NULL)
 {
 emordem(tmp->e);
 cout<<tmp->val;
 emordem(tmp->d);
 }
}
 
Árvores Binárias
● Buscas em Árvores Binárias são metodologias de como acessar os 
elementos da árvore binária
void posordem(arvore *tmp)
{
 if(tmp != NULL)
 {
 posordem(tmp->e);
 posordem(tmp->d);
 cout<<tmp->val;
 }
}
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 21
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45