Ponteiros e Listas Encadeadas

Prévia do material em texto

ESTRUTURA DE DADOS
Professora : Jane
Aula 7
Ponteiros e Listas Encadeadas
PONTEIRO
 Motivação 
Em breve, estudaremos as listas lineares 
encadeadas. Nessas listas, o tamanho necessário de 
memória não é pré-definido, como nas listas sequencias. 
Nas listas lineares encadeadas, que chamaremos 
apenas de listas encadeadas daqui em diante, a 
alocação do espaço necessário de memória ocorre 
em tempo de execução, pois simplesmente não é 
possível determinar até onde a lista irá crescer. 
2
 Como armazenar informações relacionadas, na 
memória, sem trabalhar de forma indexada, como 
fazíamos com o vetor ? 
Resposta : A solução é saber o endereço de cada 
área alocada para acessar a informação nela 
armazenada.
 Mas como manipular endereços de memória ? 
Resposta : Usando ponteiro
3
OPERADOR DE ENDEREÇO E DE INDIREÇÃO
 Exemplo 1 :
int x = 10, 
y, 
*p; //lê-se : p é um ponteiro para int
p = &x; //p recebe o endereço de x
y = *p; // y recebe o conteúdo da área apontada por p
cout << “x vale = “ << x << endl
<< “y vale = “ << y << endl
<< “*p vale = “ << *p << endl
<< “p vale = “ << p << endl; 4
Teste o arquivo 
Aula7_PonteirosEx1.cpp 
int x = 10, y, *p;
p = &x; //p recebe o endereço de x
y = *p; // y recebe o conteúdo da área apontada por p
Suponha que o endereço Como se trabalha ? 
de memória de x é 1000 
5
10
1000
10
10 
10
Representação gráfica 
abaixo !
p
x
y
y
x
p
6
EXEMPLO 2 :
int x = 10, *p, *q, *r;
p = &x; //p recebe o endereço de x
q = p; 
*q = 20; // o conteúdo da área apontada por q recebe 20
r = NULL; // r recebe NULL
cout << "x vale " << x << endl
<< "*q vale " << *q << endl
<< "*p vale " << *p << endl
<< "p vale " << p << endl
<< "q vale " << q << endl 
<< "r vale " << r << endl; 7
Aula7_PonteirosEx2.cpp
int x = 10, *p, *q, *r;
p = &x; //p recebe o endereço de x
q = p; 
*q = 20; // o conteúdo da área apontada por q recebe 20
r = NULL; // r recebe NULL
8
10 
20
r
p q
x
9
ARITMÉTICA DE PONTEIROS
 Considere
int v[ ] = {10,20,30,40,50}, *p, *q;
int x = 2, y;
Acompanhe, passo a passo :
Passo 1 : p = v; //equivale a p = &v[0];
Passo 2 : q = &v[1];
Passo 3 : p++;
Passo 4 : (*q)++;
Passo 5 : x += *p + *q;
Passo 6 : y = *p++;
Passo 7 : Qual o valor de *p ?
10
EXEMPLO 3 : CONSIDERE O TRECHO
struct aluno {
int matricula;
float media;
};
aluno a, b; //a e b são variáveis do tipo aluno
aluno *p; // p é um ponteiro para struct
a.matricula = 10;
a.media = 6.8;
p = &a; // p aponta para a struct a 
b = a; // atribui uma struct a outra
(*p).matricula = 100; //acessa o campo matricula de *p
(*p).media = 9.5; //acessa o campo media de *p
Note : *p é a struct apontada por p, pois p recebeu o
endereço de a.
11
OUTRA FORMA .... MAIS USADA :
Ao invés de fazer 
(*p).matricula = 100; //acessa o campo matricula
(*p).media = 9.5;
podemos fazer :
pmatricula = 100; //acessa o campo matricula
pmedia = 9.5;
12
Vamos 
usar a 
forma 
abaixo !
LEMBRANDO...
 Usar o ponto com struct
<variável struct> . <campo da struct>
 Usar o operador seta com struct
<ponteiro para struct>  <campo da struct>
13
TAREFAS :
Considere 
struct caixa {
char c; // refere-se a cor : P (preta) ou B (branca) 
float preco;
} ;
caixa *p, *q, *r;
caixa x, y, z;
14
Assinale V (verdadeiro) ou F (falso). Caso seja 
verdadeiro, exemplifique com ilustração gráfica, mas 
se for falso, reescreva uma possível forma correta.
a) r = &x;
b) p = r;
c) q = y;
d) r = NULL;
e) p = *x;
f) *q = NULL;
g) *p = *x;
h) z.c = ‘B’;
i) rpreco = 12.99;
j) p.preco = 99.99;
k) (*p)c = ‘P’; 15
Complete o restante 
em casa.
LISTAS LINEARES ENCADEADAS
OU
LISTAS ENCADEADAS
 No curso veremos:
 Listas simplesmente encadeadas (não circulares)
 Listas duplamente encadeadas (não circulares)
 Listas simplesmente encadeadas circulares 
 Listas duplamente encadeadas circulares (fora do escopo 
do curso). 
16
LISTAS SIMPLESMENTE ENCADEADAS
NÃO CIRCULARES (LSE) : UM PONTEIRO EM CADA NÓ E O ÚLTIMO
PONTEIRO É NULL.
 Lista simplesmente encadeada com 3 nós
 Lista simplesmente encadeada com 1 nó
q
 Lista simplesmente encadeada vazia. r
(ponteiro NULL) 17
1 5 3
100
p
LISTA SIMPLESMENTE ENCADEADA CIRCULAR (LSEC)
Exemplos :
 Lista vazia
 Lista com 1 nó
 Lista com 3 nós
18
100
1 5 3
Em outra aula 
veremos mais 
detalhadamente 
LSEC .
a
NULL
q
p
LISTA DUPLAMENTE ENCADEADA
(NÃO CIRCULAR) 
Exemplos :
 Lista vazia a NULL
 Lista com 1 nó q
 Lista com 3 nós
p
19
1
10 20 30
O ponteiro 
pode apontar 
para qualquer nó.
Em outra aula 
veremos mais 
detalhadamente 
LDE.
PILHA DINÂMICA E FILA DINÂMICA
 Se tivermos uma lista encadeada em que as inserções 
e remoções ocorram sempre na mesma extremidade, 
esta lista será especificamente uma pilha dinâmica. 
Lembre-se : critério LIFO para pilha.
 Se tivermos uma lista encadeada em que as inserções 
ocorram sempre em uma extremidade e as remoções 
ocorram sempre em outra extremidade, esta lista 
será especificamente uma fila dinâmica.
Lembre-se : critério FIFO para fila.
Em outra aula falaremos mais de 
Pilha dinâmica e Fila dinâmica
20
COMENTÁRIO :
As abreviações LSE, LSEC e 
LDE não são oficiais. Portanto, 
são aqui usadas apenas por 
razões didáticas.
21
LISTA 
SIMPLESMENTE 
ENCADEADA 
(NÃO CIRCULAR)
22p
LISTA SIMPLESMENTE ENCADEADA
 Cada nó de uma lista simplesmente encadeada terá no 
mínimo 2 campos (VER EXEMPLOS ANTERIORES).
 Em cada nó de uma lista simplesmente encadeada 
podemos armazenar: inteiros ou reais ou caracteres ...
 Exemplo de uma lista simplesmente encadeada, em que é 
representada a matrícula e a média de cada aluno :
p
23
112 9.5 342 8.0
LISTA SIMPLESMENTE ENCADEADA 
DE INTEIROS ... REPRESENTAÇÃO
p
Cada nó é um agregado com dois campos :
 Um dado, que no caso é um inteiro
 Uma ligação (link) para o próximo nó. Ou seja, um 
ponteiro que armazena o endereço do nó seguinte. 
24
1 5 3
linklink link
dado dado dado
REPRESENTAÇÃO
Se estivermos trabalhando com dados inteiros, 
poderemos definir uma struct da seguinte forma :
struct no {
int dado;
struct no *link;
};
Daí, podemos declarar :
no *p; // p apontará para o início de uma lista
// ou p poderá ser inicializado com NULL 25
ANALISANDO ...
 Como deverá estar a lista inicialmente ? VAZIA !
É preciso fazer p = NULL;
p
 E depois ... Como armazenar, por exemplo, um valor, 
criando uma lista simplesmente encadeada com 
apenas 1 nó ?
Vejamos ...
26
CRIANDO LISTAS SIMPLESMENTE ENCADEADAS
Definindo
struct no {
int dado;
struct no *link;
};
no *p; // p irá apontar para o início da lista
O trecho abaixo criará uma lista com 1 nó :
p = new no;
pdado = 100;
plink = NULL;
27
Veja em aula as 
representações 
gráficas, que são super
importantes !
O que fazer se quisermos adicionar mais um nó com o 
valor 200 após o 1º. nó criado no trecho anterior ? 
Há 2 formas possíveis:
Forma 1 :
p = new no;
pdado = 100;
p link = NULL;
q = new no;
p link= q;
qdado = 200;
q link =NULL;
28
Veja em aula as 
representações 
gráficas, que são 
super importantes !
Forma 2 :
p = new no;
pdado = 100;
p link = NULL;
p link = new no;
p linkdado = 200;
p linklink = NULL;
29
Para casa : 
Faça as representações 
gráficas deste trecho.
CONSIDERAÇÕES
 Considere a 1ª forma (slide 27). A lista criada pode 
ser, graficamente, representada por
 Se fizermos delete q; teremos :
30
q e plink
ficarão 
indefinidos
O QUE FAZER COM Q E PLINK ?
 Devemos aterrá-los ! Ou seja : atribuir NULL.
31
SE FOSSE UMA LISTA DE ALUNOS ...
Representação de cada nó seria :
struct no {
int matricula;
string nome;
float media;
struct no *link;
};
struct no *p; //p apontará para o início da lista
32
TRABALHAR COM STRING É MAIS FÁCIL ...
 Se fôssemos atribuir valores a um novo nó :
p = new no;
pmatricula = 112;
p nome = “Maricota Silva”; 
pmedia = 9.8;
p link = NULL;
p
33
112 9.8
Maricot
a Silva
Este trecho cria uma 
lista com 1 nó 
apenas.
Atenção :
Para fazer entrada de 
dados usando string :
getline(cin,pnome);
Para saída de dados :
cout << pnome;
TAREFAS :
 Considere o programa indicado acima, que cria uma 
lista simplesmente encadeada com n nós ( n >= 0) 
através de sucessivas inserções no início da lista.
1) Faça um teste de mesa com a função insereFrente, 
considerando a lista inicialmente vazia (exemplo 1) e a 
lista com 1 ou mais nós (exemplo 2).
2) Teste a função imprimir do programa dado.
3) Teste a função que remove o 1º. nó da lista.
34
Use o arquivo 
Aula7_LSE_básico.cpp 
4) Adicione código ao programa dado e escreva uma função 
em C++ para substituir o valor do último nó de uma LSE 
não vazia por um valor inteiro passado como parâmetro.
 Protótipo da função : 
void substituir(no *, int);
35
5) Faça uma função em C++ para contar o número de nós 
de uma lista simplesmente encadeada qualquer, ou seja, 
a lista pode estar vazia ou não.
 Protótipo : int contaNos(no *);
 Retorno : A quantidade de nós da lista, que pode ser zero.
36
6) Escreva uma função em C++ para realizar uma 
busca ou pesquisa seqüencial na lista, retornando 
NULL (fracasso na busca) ou o endereço do nó 
com o valor encontrado (sucesso na busca). 
 Parâmetros: ponteiro para o início da lista e valor 
a ser procurado
 Retorno : NULL (fracasso na busca) ou o 
endereço do nó com o valor encontrado
(sucesso na busca).
37
ATENÇÃO !!
 As funções implementadas com Listas Simplesmente 
Encadeadas são semelhantes às funções que deverão 
ser implementadas com LSEC (lista simplesmente 
encadeada circular) ou LDE (lista duplamente 
encadeada). 
38