19 - aulaIP-ListaEncadeada

7/25/2019 19 - aulaIP-ListaEncadeada

1/37

Introduo a Programao

Listas Encadeadas


2/37

Tpicos da Aula

Hoje aprenderemos que existem, alm devetores, estruturas de dados dinmicasque

podem armazenar colees de dados

Estruturas Dinmicas e Vetores

Conceito de listas encadeadasListas Encadeadas x Vetores

Funes de manipulao de listas encadeadas

Variaes de listas encadeadas

2


3/37

3

Vetores

Declarao de vetor implica na especificao de seutamanho

No se pode aumentar ou diminuir tamanho

Outra alternativa no uso de vetores alocar

dinamicamente o espao necessrio e guardar

endereo inicial do vetor

Porm, depois de determinado o tamanho do vetor,

no podemos liberar posio de memria arbitrria

Possvel desperdcio ou falta de memria!


4/37

4

Estruturas Dinmicas

Uma estrutura de dado dinmica consiste emuma estrutura que pode aumentar ou diminuir

de tamanho de acordo com a necessidade da

aplicao (do programador)

Evita desperdcio e/ou falta de memria

Programador encarregado de requisitar e

liberar espaos de memria explicitamente

Uso de alocao dinmica

Requer mais esforo por parte doprogramador!


5/37

5

Listas Encadeadas

Uma lista encadeada uma estrutura dinmica quepode ser utilizada para armazenar um conjunto de

dados

Junto a cada elemento deve-se armazenar o

endereo para o prximo elemento (elementos

encadeados)

Elemento + ponteiro = n da lista

Diferentemente de vetores, elementos geralmente no so

armazenados em espaos contguos de memria

Caso no exista prximo elemento, o ponteiro para oprximo elemento NULL


6/37

6

Listas Encadeadas

Para cada novo elemento inserido na lista, aloca-seum espao de memria para armazen-lo

Para remover elemento deve-se liberar o endereo

de memria reservado para armazenar o elemento

O acesso aos elementos sempre seqencialNo se pode garantir que os elementos ocuparo um

espao de memria contguo (no se pode localizar

elementos com base em um deslocamento constante)


7/37

7

Listas Encadeadas x Vetores

Listas Encadeadas+Uso eficiente da memria

- Complexidade de manipulao da estrutura

- Informao deve ser guardada em uma estrutura

que guarda tambm um endereo (requer maismemoria por informao armazenada)

Vetores

+Simplicidade no acesso (manipulao) aos

elementos da estrutura

- Desperdcio ou falta de memria

- Menor Flexibilidade


8/37

8

Representao de Listas Encadeadas

info1

primeiro

struct lista {int info ; /* info pode ser de qualquer tipo */struct lista* prox;

} ;typedef struct lista Lista ;

p

r

o

x

info2

p

r

o

x

info3

Informaoarmazenadano n da

lista

Armazena oendereo doprximo n

Armazenaendereo

nulo

fim


9/37

9

Representando Listas Encadeadas na

Memria

info3

NULL

info2

112

124

info1100

104

108

112

116

120

124

128

Memria

Lista* inicio;

inicio

100

info

prox

info1

inicio

p

r

o

x

info2

p

r

o

x

info3


10/37

10

Insero de Elementos em Listas

Encadeadas

Diferentes formas de inserir um elemento nalista:

No comeo

Mais simples

No fim

Neste caso deve-se percorrer a lista toda


11/37

11

Inserindo Elementos no Incio de

Listas Encadeadas

/* insero incio da lista */Lista* lst_insere(Lista* inicio,int i){Lista* novo = (Lista*) malloc(sizeof(Lista));novo->info = i ;

novo->prox = inicio ;return novo ;

}

info1

inicio

info2 info3 info4

Novo

Endereo docomeo da

listaRetorna endereoinicial atualizado


12/37

12

Inserindo Elementos no Fim de Listas

Encadeadas

/* insero fim da lista */Lista* lst_insere(Lista* inicio,int i){Lista* novo = (Lista*) malloc(sizeof(Lista));novo->info = i ;novo->prox = NULL ;

if (inicio == NULL){inicio = novo;} else {

Lista* p = inicio;while (p->prox != NULL){

p = p->prox;}

p->prox = novo;}return inicio ;

}

Se lista estiver vazia,

iniciovai guardarendereo de novo

Seno temos que percorrer listaat ltimo n, para faz-lo

apontar para novo


13/37

13

Usando Funo de Insero de Listas

Encadeadas

int main() {Lista* inicio;inicio = NULL;inicio = lst_insere(inicio,23); /* insere 23 */inicio = lst_insere(inicio,45); /* insere 45 */

...return 0 ;}

No esquecer de atualizar avarivel que guarda endereo

inicial da lista a cada insero!

Variavel que armazena endereo inicialda lista deve ser inicializada comNULL!


14/37

14

Imprimindo Listas Encadeadas

void lst_imprime(Lista* inicio){Lista* p; /*varivel auxiliar para percorrer a

lista */for(p = inicio; p != NULL; p = p->prox){

printf ( info = %d\n , p->info ) ;}

}

Lao para percorrer todos os nsda lista


15/37

15

Verificando se a Lista Est Vazia

/* funo vazia: retorna 1 se vazia ou 0 se novazia */int lst_vazia(Lista* inicio){int vazio = 0;if (inicio == NULL)

vazio = 1;return vazio;}

/* verso compacta da funo lst_vazia */int lst_vazia ( Lista* inicio ){return(inicio == NULL) ;

}


16/37

16

Buscando um Elemento em Listas

Encadeadas

Lista* lst_busca(Lista* inicio,int v){int achou = 0;Lista* p = inicio ;

while (p != NULL && !achou) {if (p->info == v)

achou = 1 ;elsep = p->prox;

}return p;

}

Retorna o endereodo primeironque contm o elemento

buscado

Se no achouelemento, retornao endereo nulo!


17/37

17

Removendo Elementos de Listas

Encadeadas

Dois casos devem ser tratados para a remoo deum elemento da lista

info1

inicio

info2 info3 info4

Remoo do primeiro elemento da lista

info1

inicio

info2 info3 info4

Remoo de um elemento no meio da lista


18/37

18


EncadeadasLista* lst_retira(Lista* inicio,int v){Lista* ant = NULL; /* guarda elemento anterior */Lista* p = inicio;

while(p != NULL && p->info != v){ant = p ;

p = p->prox ;

}/* verifica se achou o elemento */if (p != NULL) {

if (ant == NULL)inicio = p->prox;

elseant->prox = p->prox;

free(p) ;}return inicio ;

}

Procura elementona lista,guardando

endereo do

anterior

Retorna endereo inicial da lista

Elemento no inicio, retiraelemento do incio

Retira elemento do meio


19/37

19

Liberando Listas Encadeadas

void lst_libera(Lista* inicio){Lista* p = inicio ;Lista* t;

while(p != NULL ) {

t = p->prox;free(p); /* libera a memria apontada por p*/p = t; /* faz p apontar para o prximo */

}}

Guarda o endereodo prximon para poder libera-lo na

prxima iterao


20/37

20

Comparando Listas Encadeadas

int lst_igual(Lista* lst1,Lista* lst2){Lista* p1 ;Lista* p2 ;int igual = 1for(p1 = lst1,p2 = lst2; p1!=NULL && p2!=NULL && igual;

p1=p1->prox,p2=p2->prox){

if(p1->info!= p2->info )igual = 0;

}return(p1 == p2 && igual) ;

}Se os elementos testados foremiguais, deve-se ainda ver sep1ep2apontam paraNULL(tamanhos

das listas iguais)


21/37

21

Utilizando Funes de Manipulao de

Lista de Inteiros

#include #include lista.hint main() {

Lista * ls ; /* declara uma lista no iniciada */ls = NULL; /*inicia lista vazia */ls = lst_insere(ls,23); /* insere o elemento 23 */

ls = lst_insere(ls,45); /* insere o elemento 45 */ls = lst_insere(ls,56); /* insere o elemento 56 */ls = lst_insere(ls,78); /* insere o elemento 78 */lst_imprime(ls); /* imprime: 78 56 45 23 */ls = lst_retira(ls,78);

lst_imprime(ls); /* imprime: 56 45 23 */ls = lst_retira(ls,45);lst_imprime(ls); /* imprime: 56 23 */lst_libera(ls);return 0 ;

}


22/37

22

Listas podem variar quanto ao:Tipo de encadeamento

Simples

CircularesDuplas

Circulares e Duplas

Contedo

Tipos PrimitivosTipos Estruturados

Variaes de Listas Encadeadas

J vimosanteriormente


23/37

2323

Listas Circulares

lista

info1 info3info2

Estrutura do n da lista idntica a da lista

simplesmente endadeadaNo h noo de primeiro e ltimo n da lista

Para saber se toda lista foi percorrida deve-se

guardar o endereo do primeiro n a ser lido e

comparar com o endereo do n que est sendo lido


24/37

2424

Imprimindo uma Lista Circular

void lcirc_imprime (Lista* inicio) {Lista* p = inicio; /* faz p apontar para on inicial *//* testa se lista no vazia*/if (p != NULL){

do {printf(%d\n,p->info);p = p->prox;

} while (p != inicio);

}A condio de parada dolao quando o n a serpercorrido for igual ao n

inicial


25/37

25

Lista duplamente encadeada

inicio

info1 info3info2

Permite percorrer a lista em dois sentidos

Cada elemento deve guardar os endereos do

prximo elemento e do elemento anterior

Facilita percorrer a lista em ordem inversa

Retirada de elemento cujo endereo conhecido se

torna mais simples

Acesso ao n anterior para ajustar encadeamento no

implica em percorrer a lista toda

info4


26/37

26

Estrutura de Listas Duplamente

Encadeadas

inicio

struct lista2 {int info ;

struct lista2* prox;

struct lista2* ant;} ;typedef struct lista2 Lista2 ;

Armazena oendereo doprximo n fim

info1

p

ro

x

a

nt

info1

p

ro

x

info1

a

n

t

Armazena oendereo don anterior


27/37

2727

inicio

info1 info3info2

novo

Inserindo Elementos no Incio de

Listas Duplamente Encadeadas

Lista2* lst2_insere (Lista2* inicio, int v) {

Lista2* novo = (Lista2*) malloc(sizeof(Lista2));

novo->info = v; novo->prox = inicio;

novo->ant = NULL;/* verifica se lista no est vazia */

if (inicio != NULL)

inicio->ant = novo;

return novo;

}

Insero no comeo da lista


28/37

2828

inicio

info1 info3info2

novo

Insero no fim da lista


Duplamente Encadeadas


29/37

2929



Lista2* lst2_insere (Lista2* inicio, int v) {

Lista2* novo = (Lista2*) malloc(sizeof(Lista2));

novo->info = v; novo->prox = NULL;

if (inicio == NULL) {

novo->ant = NULL;

inicio = novo} else {

Lista2* p;

while (p->prox != NULL) [

p = p->prox;

}p->prox = novo;

novo->ant = p;

}

return inicio;

}

Se lista estiver vazia,

endereo do n anterior anovo NULL

Seno temos que fazer com que o ltimon aponte para novo e n anterior de

novo seja o antigo ltimo n


30/37

30

Lista2* lst_busca (Lista2* lista, int v)

{Lista2* p;

int achou = 0

for (p = lista; p != NULL && !achou; p = p->prox)

if (p->info == v)achou = 1;

return p;

}

Buscando um Elemento em Listas


Mesma lgica aplicada a listas simplesmenteencadeadas


31/37

31


Duplamente EncadeadasTrs casos devem ser tratados para a remoo de

um elemento da lista

Remoo de um elemento no meio da lista

info1

inicio

info2 info3 info4

info1

inicio

info2 info3 info4

Remoo de um elemento do fim da lista

info1

inicio

info2 info3 info4

Remoo do primeiro elemento da lista

R d El t d Li t


32/37

32

Lista2* lst2_retira (Lista2* inicio, int v) {

Lista2* p = busca(inicio, v);

if (p != NULL){

if (inicio == p)

inicio = p->prox;

elsep->ant->prox = p->prox;

if (p->prox != NULL)

p->prox->ant = p->ant;

free(p);}

return inicio;

}



Usando a funode busca

Retira elemento do

comeo da lista

Retira do meio

S acerta o encadeamento do ponteiropara o anterior se NOfor o ltimo

elemento

Li t Ci l D l t


33/37

33

lista

info1 info3info2

Lista Circular Duplamente

Encadeada

Permite percorrer a lista nos dois sentidos, apartir de um ponteiro para um elemento

qualquer

I i i d S tid I


34/37

3434

void l2circ_imprime_inverso (Lista2* lista){

Lista2* p = lista;

if (p != NULL)do {

p = p->ant;

printf(%d\n,p->info);

} while (p != lista);

}

Imprimindo no Sentido Inverso com

um Lista Circular Duplamente

Encadeada

Avana para o nanterior


35/37

35

typedef struct retangulo {

float b; /* base */

float h; /* altura */

} Retangulo;

Lista de Tipos Estruturados

Uma lista pode ser composta de elementos estruturados

Considere o tipo Retangulo

OU

typedef struct lista {

Retangulo info;

struct lista *prox;

} Lista;

Podemos definir uma lista cujos ns contenham ouum

retngulo ouum ponteiro para um retngulo

typedef struct lista {

Retangulo* info;

struct lista *prox;

} Lista;

I i d N Li t d


36/37

36

Lista* insere (Lista* inicio,float b, float h) {

Lista *novo;

novo = (Lista*)malloc(sizeof(Lista));

novo->info.b = b;

novo->info.h = h;

novo->prox = inicio

return novo;}

Inserindo um N em uma Lista de

Tipos Estruturados

N da lista contm um retngulo

I i d N d Li t d Ti


37/37

37

Inserindo um N de uma Lista de Tipos

Estruturados

Lista* insere (Lista* inicio,float b, float h){Retangulo *r;

r = (Retangulo*) malloc(sizeof(Retangulo));Lista* novo = (Lista*)malloc(sizeof(Lista));r->b = b;r->h = h;novo->info = r;novo->prox = inicio;return novo;

}

N da lista contm um ponteiro para um retngulo

Espao para a estruturaRetangulodeve tambm seralocado

Documents

19 - aulaIP-ListaEncadeada