05.Listas

Prévia do material em texto

Aula 05
Listas
Rodolfo Carneiro Cavalcante
Universidade Federal de Alagoas – UFAL
Campus Arapiraca
8 de Maio de 2015
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 1 / 44
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 2 / 44
Introduc¸a˜o
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 3 / 44
Introduc¸a˜o
Introduc¸a˜o
Uma das formas mais simples de interligar elementos de um conjunto
Itens podem ser acessados e inseridos ou retirados de uma lista
Duas listas pode ser concatenadas para formar uma lista u´nica
Uma lista pode ser partida em duas ou mais listas
Lista linear
sequeˆncia de zero ou mais itens x1, x2, ..., xn, na qual xi de um
determinado tipo
n e´ o tamanho da lista
assumindo que n ≥ 1, x1 e´ o primeiro item da lista, e xn e´ o u´ltimo
item da lista
para 1 < k < n, xk e´ precedido por xk−1 e seguido por xk+1
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 4 / 44
Introduc¸a˜o
Introduc¸a˜o
TAD Lista
Conjunto de operac¸o˜es para uma lista depende de cada aplicac¸a˜o
Operac¸o˜es comuns:
criar lista vazia
verificar se a lista esta´ vazia
inserir novo item imediatamente apo´s o item xi
retirar o item xi
localizar o item xi para examinar e/ou alterar o conteu´do de seus
componentes
combinar duas ou mais listas em uma lista u´nica
partir uma lista em duas ou mais listas
fazer uma co´pia da lista linear
ordenar os itens da lista em ordem ascendente ou descendente, de
acordo com alguns de seus componentes
pesquisar a ocorreˆncia de um item com um valor particular em algum
de seus componentes
Imprimir os itens da lista na ordem e ocorreˆncia
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 5 / 44
Introduc¸a˜o
Introduc¸a˜o
Pilhas e filas sa˜o tipos especiais de listas lineares
Particularidades na implementac¸a˜o das operac¸o˜es de inserc¸a˜o e
retirada de elementos
Pilhas sa˜o listas lineares em que inserc¸o˜es, remoc¸o˜es e acessos a
elementos ocorrem em apenas uma das extremidades
Filas sa˜o listas lineares em que todas as inserc¸o˜es de novos elementos
sa˜o realizadas em uma das extremidades da lista e as remoc¸o˜es sa˜o
feitas na outra extremidade
Listas lineares tem inserc¸o˜es e retiradas em qualquer posic¸a˜o da lista
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 6 / 44
Introduc¸a˜o
Introduc¸a˜o
Da mesma forma que as filas e pilhas, existem va´rias estruturas de
dados que podem ser utilizadas para implementar listas lineares
Cada uma com suas vantagens e desvantagens
Durante o projeto de implementac¸a˜o de listas e´ importante identificar
as operac¸o˜es que sera˜o mais frequentes
Na˜o existe uma u´nica implementac¸a˜o eficiente para todas as
operac¸o˜es
Por exemplo, na˜o ha´ implementac¸a˜o eficiente para ambas as
operac¸o˜es a seguir:
1 ter acesso fa´cil ao item xi para i qualquer
2 inserir ou remover elementos em uma posic¸a˜o i qualquer
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 7 / 44
Introduc¸a˜o
Introduc¸a˜o
A operac¸a˜o 1 e´ mais eficiente com implementac¸a˜o por meio de
arranjos ou estruturas auto-referenciadas?
E a operac¸a˜o 2?
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 8 / 44
Introduc¸a˜o
Introduc¸a˜o
A operac¸a˜o 1 e´ mais eficiente com implementac¸a˜o por meio de
arranjos
Por meio da alocac¸a˜o sequencial em memo´ria, acessar um ı´ndice do
vetor e´ uma operac¸a˜o muito ra´pida
Se utilizarmos uma estrutura auto-referenciada, precisamos percorrer
todas as ce´lulas da estrutura ate´ a ce´lula i
Mas se eu precisar inserir um elemento em uma posic¸a˜o i qualquer
utilizando um array (operac¸a˜o 2)?
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 9 / 44
Introduc¸a˜o
Introduc¸a˜o
A operac¸a˜o 1 e´ mais eficiente com implementac¸a˜o por meio de
arranjos
Por meio da alocac¸a˜o sequencial em memo´ria, acessar um ı´ndice do
vetor e´ uma operac¸a˜o muito ra´pida
Se utilizarmos uma estrutura auto-referenciada, precisamos percorrer
todas as ce´lulas da estrutura ate´ a ce´lula i
Mas se eu precisar inserir um elemento em uma posic¸a˜o i qualquer
utilizando um array(operac¸a˜o 2)?
E´ preciso realocar todos os itens xk , k > i
Nesse caso, a implementac¸a˜o com estruturas auto-referenciadas e´ mais
eficiente
E´ preciso apenas criar uma nova ce´lula e fazer xi−1 apontar para xi e xi
apontar para xi+1
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 10 / 44
Implementac¸a˜o com Arranjos
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 11 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Itens da lista sa˜o armazenados em posic¸o˜es cont´ıguas de memo´ria
Lista pode ser percorrida em qualquer direc¸a˜o
Inserc¸a˜o de um novo item pode ser realizada apo´s o u´ltimo item com
custo constante
Assim como nas pilhas e filas
No entanto, a inserc¸a˜o de um novo item no meio da lista requer um
deslocamento de todos os itens localizados apo´s o ponto de inserc¸a˜o
Retirar um item do in´ıcio da lista requer um deslocamento de itens
para preencher o espac¸o deixado vazio
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 12 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Assim como nas implementac¸o˜es anteriores, um vetor e´ utilizado para
armazenar os itens da lista
Da mesma forma, e´ necessa´rio que esse vetor tenha tamanho
suficiente para comportar os itens da lista
Esse tamanho deve ser fixo ou na˜o deve precisar ser alterado com
frequeˆncia
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 13 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 1: Estrutura de dados Lista (arranjo)
template <class T>class Lista{
private:
T *itens;
int ultimo, maxTam;
public:
Lista(int maxTam);
bool vazia();
void imprime();
void insere(T item);
void insere(T item, int pos);
int pesquisa(T item);
T retira(int pos);
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 14 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
A estrutura que guarda a lista e´ um vetor
T* itens;
O ı´ndice ultimo guarda a ultima posic¸a˜o da lista + 1 unidade
O tamanho ma´ximo da lista (maxTam) e´ usado para indicar o limite
do vetor
Temos duas operac¸o˜es insere
uma para inserir um elemento no fim da lista – similar a uma fila
uma para inserir um elemento em uma posic¸a˜o arbitra´ria
Temos ainda a operac¸a˜o de pesquisar por um item na lista e retirar
um item de uma posic¸a˜o
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 15 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 2: Estrutura de dados Lista: criar Lista vazia
template <class T>Lista<T>::Lista(int maxTam){
this->maxTam = maxTam;
this->itens = new T[maxTam];
this->ultimo = 0;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 16 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
O construtor da classe Lista faz as devidas inicializac¸o˜es
a ultima posic¸a˜o da lista sera´ a posic¸a˜o 0
o tamanho ma´ximo sera´ passado como paraˆmetro para o construtor
o vetor itens e´ inicializado dinamicamente
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 17 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 3: Estrutura de dadoslista: verificar se esta´ vazia
template <class T> bool Lista<T>::vazia(){
return this->ultimo==0;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 18 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 4: Estrutura de dados lista: imprimir elementos
imprimir(){
se (nao vazia){
para i de 0 ate ultimo-1{
imprima(itens[i ]);
i++
}
senao
imprima(“lista vazia”);
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 19 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 5: Estrutura de dados lista: inserir elemento na u´ltima posic¸a˜o
insere(item){
se(ultimo == maxTam)
imprima(“lista cheia!”);
senao{
itens[ultimo] = item;
ultimo++;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 20 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 6: Estrutura de dados lista: inserir elemento em posic¸a˜o ar-
bitra´ria
insere(item, pos){
se(ultimo == maxTam)
imprima(“lista cheia!”);
senao{
para i de ultimo − 1 ate pos + 1{
itens[i] = itens[i-1];
i−−;
}
itens[pos] = item;
ultimo++;
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 21 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
A inserc¸a˜o de um elemento na u´ltima posic¸a˜o e´ trivial
E´ preciso verificar se ha´ espac¸o vazio na lista
Insere o elemento na u´ltima posic¸a˜o
A inserc¸a˜o de um elemento em uma posic¸a˜o arbitra´ria exige o
deslocamento de todos os elementos apo´s a posic¸a˜o desejada para a
esquerda
Operac¸a˜o de alto custo quando a lista possui muitos elementos
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 22 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 7: Estrutura de dados lista: pesquisar elemento
pesquisa(item){
se(nao vazia()){
para i de 0 ate ultimo-1{
se (itens[i] == item)
retorne i;
i++;
}
}
retorne -1;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 23 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Algoritmo 8: Estrutura de dados lista: recuperar elemento em posic¸a˜o
arbitra´ria
retira(pos){
se (pos<ultimo){
item = itens[pos];
para i de pos ate ultimo-2;
itens[i] = itens[i+1];
i++;
ultimo−−;
retorne item;
}
retorne 0;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 24 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Assim como a operac¸a˜o de inserir um item em posic¸a˜o arbitra´ria, a
operac¸a˜o de remover um item de uma posic¸a˜o arbitra´ria requer o
deslocamento de todos os itens em posic¸o˜es subsequentes a posic¸a˜o
de retirada
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 25 / 44
Implementac¸a˜o com Arranjos
Implementac¸a˜o com Arranjos
Considerac¸o˜es
Tem como vantagem a economia de memo´ria, pois os apontadores
sa˜o impl´ıcitos nessa estrutura
Na˜o ha´ necessidade de se guardar memo´ria na estrutura para
armazenar um ponteiro para a pro´xima posic¸a˜o da lista
Desvantagens:
custo para inserir ou retirar itens da lista – pode causar um
deslocamento de todos os itens, no pior caso
em aplicac¸o˜es em que na˜o existe previsa˜o sobre o crescimento da lista,
a utilizac¸a˜o de arranjos pode exigir a realocac¸a˜o de memo´ria
operac¸a˜o de alto custo em termos de tempo e memo´ria, pois e´ preciso
alocar uma nova a´rea com mais posic¸o˜es do que a atual e copiar todos
os itens para ela
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 26 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Suma´rio
1 Introduc¸a˜o
2 Implementac¸a˜o com Arranjos
3 Implementac¸a˜o com Estruturas Auto-Referenciadas
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 27 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Tambe´m chamada de lista encadeada ou lista ligada
Cada item da lista conte´m a informac¸a˜o que e´ necessa´ria para
alcanc¸ar o pro´ximo item
Esta implementac¸a˜o permite utilizar posic¸o˜es na˜o cont´ıguas de
memo´ria
E´ poss´ıvel inserir e retirar elementos sem haver necessidade de
deslocar os itens seguintes da lista
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 28 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
a figura a seguir ilustra a representac¸a˜o dessa forma:
implementac¸a˜o
a estrutura de dados lista usando estruturas auto-referenciadas sa˜o
constitu´ıdas de ce´lulas
a classe Lista conte´m uma refereˆncia para a ce´lula da cabec¸a e uma
refereˆncia para armazenar a posic¸a˜o corrente na lista
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 29 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Para inserir um item no fim da lista
cria-se uma nova ce´lula xn para o item
faz a lista apontar para a nova ce´lula como sendo o fim da lista
faz essa nova ce´lula apontar para NULL
Para inserir um item em uma posic¸a˜o arbitra´ria i
cria-se uma nova ce´lula
faz a ce´lula xi−1 apontar para a nova ce´lula
faz a nova ce´lula apontar para a ce´lula xi
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 30 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 9: Estrutura de dados Lista: ce´lula
template <class T> class Celula{
public:
T item;
Celula* prox;
Celula(){
prox = NULL;
}
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 31 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 10: Estrutura de dados Lista
template <class T>class Lista{
private:
Celula<T> *primeiro, *ultimo;
public:
Lista();
bool vazia();
void imprime();
void insere(T item);
void insere(T item, int pos);
Celula<T>* pesquisa(T item);
T retira(int pos);
};
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 32 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 11: Estrutura de dados Lista: Construtor
template <class T>Lista<T>::Lista(){
this->primeiro = new Celula<T>;
this->ultimo = this->primeiro;
this->primeiro->prox = NULL;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 33 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 12: Estrutura de dados Lista: verificar se esta´ vazia
template <class T>bool Lista<T>::vazia(){
return this->primeiro == this->ultimo;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 34 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 13: Estrutura de dados Lista: imprimir elementos da lista
imprime(){
se(nao vazia){
Celula *p = primeiro->prox;
enquanto(p != Nulo){
imprima(p->item);
p = p->prox;
}
}
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 35 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 14: Estrutura de dados Lista: inserir elemento na u´ltima posic¸a˜o
insere(item){
ultimo->prox = new Celula();
ultimo = ultimo->prox;
ultimo->item = item;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 36 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 15: Estrutura de dados Lista: inserir elemento em posic¸a˜o ar-
bitra´ria
insere(item,pos){
Celula* p = primeiro->prox;
para i de 0 ate pos − 1{
p = p->prox;
i++;
}
Celula* aux = new Celula();
aux->item = item;
aux->prox = p->prox;
p->prox = aux;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 37 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 16: Estrutura de dados Lista: pesquisar item
pesquisa(item){
Celula* p = primeiro->prox;
enquanto(p != Nulo){
se(p->item==item)
return p;
else
p = p->prox;
}
retorne Nulo;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 38 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Algoritmo 17: Estrutura de dados Lista: retirar item
retirar(pos){
item = Nulo;
se(nao vazia){
Celula* p = primeiro;
para i de 0 ate pos{
p = p->prox;
i++;
}
Celula *q = p->prox;
item = q->item;
p->prox = q->prox;
delete q;
}
retorne item;
}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 39 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Implementac¸a˜o com Estruturas Auto-Referenciadas
Considerac¸o˜es sobre estruturas auto-referenciadas
Esse tipo de implementac¸a˜o permite inserir ou retirar itens do meio
da lista a um custo baixo, aspecto importante quando a lista deve ser
mantida em ordem
Em aplicac¸o˜es em que na˜o existe previsa˜o sobre o crescimento da
lista, e´ conveniente usar listas encadeadas, dado que o tamanho
ma´ximo da lista na˜o precisa ser definido a priori
a maior desvantagem desse tipo de implementac¸a˜o e´ a utilizac¸a˜o de
memo´ria extra para armazenar as refereˆncias (os ponteiros prox)
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 40 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Exerc´ıcio
Questa˜o 1
Implemente uma func¸a˜o que recebe duas listas lineares
(implementadas com arranjo) e retorna a junc¸a˜o dessas duas listas
A operac¸a˜o de junc¸a˜o deve entrelac¸ar os elementos das duas listas da
seguinte forma:
seja l1 = {xl11, xl12, xl13, xl14} e l2 = {xl21, xl22, xl23, xl24}
a junc¸a˜o resultante seria l3 = {xl11, xl21, xl12, xl22, xl13, xl23, xl14, xl24}
Sejam as listas l1 = {1, 3, 5, 7} e l2 = {2, 4, 6, 8}, o resultado da
operac¸a˜o de junc¸a˜o sera´ l3 = {1, 2, 3, 4, 5, 6, 7, 8}
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 41 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Exerc´ıcio
Questa˜o 2
Implemente uma func¸a˜o que recebe um vetor de valores inteiros com
n elementos e construa uma lista encadeada armazenando os
elementos do vetor nos no´s da lista
Se for recebido o vetor v[5] = {3,8,1,7,2}, a func¸a˜o deve retornar
uma nova lista cujo primeiro no´ tem a informac¸a˜o 3, o segundo no´
tem a informac¸a˜o 8, e assim por diante.
Se o vetor tiver zero elementos, a func¸a˜o deve ter como valor de
retorno uma lista vazia
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 42 / 44
Implementac¸a˜o com Estruturas Auto-Referenciadas
Exerc´ıcio
Formato da entrega
Enviar atividade para o ambiente virtual
Envie os arquivos fontes (mesmo que apenas um) compactados com
rar ou zip, com o nome nome aluno1 e nome aluno2.zip
Exemplo: alunos Wilcklison Jonesclayson e Joilson dos Teclados
Arquivo zip: Wilcklison e Joilson.zip
O seu programa deve ser executado em uma ma´quina com Ubuntu
com compilador gcc(g++)
Se o arquivo na˜o esta´ compilando/executando, envie assim mesmo e
nos comenta´rios informe o problema e onde suspeita estar localizado
o problema no co´digo.
Sera´ descontado 10% da nota por cada hora de atraso.
Rodolfo Carneiro Cavalcante (UFAL) Aula 05Listas 8 de Maio de 2015 43 / 44
	Introdução
	Implementação com Arranjos
	Implementação com Estruturas Auto-Referenciadas