Aula12_Listas_Encadeadas

Prévia do material em texto

Listas Lineares - Implementac¸a˜o em C
Professor:
Silvio Luiz Bragatto Boss
e-mail:
silvioboss@utfpr.edu.br
Universidade Tecnolo´gica Federal do Parana´ - UTFPR
Coordenac¸a˜o de Informa´tica - COINF
Curso de Engenharia de Computac¸a˜o
Disciplina de Estrutura de Dados I
Listas Lineares - Alocac¸a˜o Encadeada
Suma´rio
1 Listas Lineares - Alocac¸a˜o Encadeada
Algoritmo Percorre uma lista
Algoritmo Insere no final da lista
Algoritmo Remove do final da lista
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Algoritmo inicializaLista
Na inicializac¸a˜o da lista encadeada, o ponteiro L, que ira´
apontar para o primeiro no´ da lista, recebe um valor nulo
(NULL);
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Algoritmo inicializaLista
Na inicializac¸a˜o da lista encadeada, o ponteiro L, que ira´
apontar para o primeiro no´ da lista, recebe um valor nulo
(NULL);
Como a lista encadeada na˜o possui nenhum no´, L aponta para
um valor nulo.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Algoritmo inicializaLista
Na inicializac¸a˜o da lista encadeada, o ponteiro L, que ira´
apontar para o primeiro no´ da lista, recebe um valor nulo
(NULL);
Como a lista encadeada na˜o possui nenhum no´, L aponta para
um valor nulo.
Procedimentos Realizados
Atribui NULL ao ponteiro L
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Algoritmo inicializaLista
Na inicializac¸a˜o da lista encadeada, o ponteiro L, que ira´
apontar para o primeiro no´ da lista, recebe um valor nulo
(NULL);
Como a lista encadeada na˜o possui nenhum no´, L aponta para
um valor nulo.
Procedimentos Realizados
Atribui NULL ao ponteiro L
Paraˆmetros
O ponteiro L
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Exemplo de Implementac¸a˜o
void iniLista(no **L) {
*L = NULL;
}
// **L e´ o enderec¸o da varia´vel L (o ponteiro
para a lista L)
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Algoritmo percorreLista
Percorre todos os itens da lista;
Para percorrer os itens da lista e´ necessa´rio comec¸ar pelo
in´ıcio da lista.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Algoritmo percorreLista
Percorre todos os itens da lista;
Para percorrer os itens da lista e´ necessa´rio comec¸ar pelo
in´ıcio da lista.
Procedimentos Realizados
Declare um ponteiro P (do tipo no);
P sera´ um ponteiro auxiliar utilizado para percorrer a lista;
P recebe o valor de L, ou seja, P recebe o enderec¸o do
primeiro no´ da lista;
Enquanto P apontar para um no´ na˜o nulo na lista L fac¸a:
P recebe o enderec¸o do pro´ximo no´ da lista (P = P→link)
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Declare um ponteiro P (do tipo no).
P sera´ um ponteiro auxiliar utilizado para percorrer a lista.
no * P;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
P recebe o valor de L, ou seja, P recebe o enderec¸o do
primeiro no´ da lista.
P = *L;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Enquanto P apontar para um no´ na˜o nulo na lista L fac¸a
P recebe o enderec¸o do pro´ximo no´ da lista (P = P→link)
While (P != NULL)
P = P->link;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Paraˆmetros
O ponteiro L (que aponta para o primeiro no´ da lista L).
Exemplo de Implementac¸a˜o - Percorre e Exibe
void percorreLista(no **L) {
no *P;
P = *L;
// P recebe o endereco do primeiro no da lista
printf("\n Exibe itens da lista");
while(P != NULL) {
printf("\n %d", P->info);
P = P->link;
}
}
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Algoritmo insereFinalLista
Insere um item no final da lista.
Procedimentos Realizados
Declare um ponteiro N (do tipo no);
N sera´ um ponteiro para o novo no;
Declare um ponteiro P (do tipo no);
P sera´ um ponteiro auxiliar utilizadopara percorrer a lista;
Aloca espac¸o de memo´ria para o novo no´ e atribui o enderec¸o desta
localizac¸a˜o de memo´ria para N;
O campo info de N recebe o valor do item a ser inserido;
Se L for igual a NULL enta˜o L recebe o valor de N (a lista esta´ vazia)
Sena˜o
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Sena˜o
P recebe o valor de L, ou seja, P recebe o enderec¸o do
primeiro no´ da lista.
Enquanto o campo link de P for diferente de nulo fac¸a:
P recebe o enderec¸o do pro´ximo no´ da lista (neste ponto, P
conte´m o valor do atual u´ltimo no´ da lista, e o item sera´
inserido depois de P).
O no´ apontado por P, ira´ apontar para o novo no´ apontado
por N.
O campo link de N recebe NULL.
Paraˆmetros
O ponteiro L (que aponta para o primeiro no´ da lista L)
Valor do item a ser inserido na lista.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Declare um ponteiro N (do tipo no).
N sera´ um ponteiro para o novo no´.
no * N;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Declare um ponteiro P (do tipo no).
P sera´ um ponteiro usado para percorrer a lista.
no * P;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Aloca espac¸o de memo´ria para o novo no´ e atribui o enderec¸o
desta localizac¸a˜o de memo´ria para N.
N = (no *) malloc (sizeof(no));
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
O campo info de N recebe o valor do item a ser inserido.
N→info = X;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Se L for igual a NULL enta˜o
L recebe o valor de N (a lista esta´ vazia)
if (*L == NULL)
*L = N;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
P recebe o valor de L.
P recebe o enderec¸o do primeiro no´ da lista.
P = *L;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Neste ponto, P aponta para o u´ltimo no´ da lista
while (P->link != NULL)
P = P->link;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
O no´ apontado por P, ira´ apontar para o novo no´ apontado
por N
P->link = N;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
O campo link de N recebe NULL
N->link = NULL;
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Algoritmo removeFinalLista
Remove o u´ltimo no´ da lista.
Para eliminar um no´ da lista, o no´ predecessor deve ser conhecido (pois
este passara´ a ser o u´ltimo no´ da lista.
Procedimentos realizados
Declare um ponteiro P (do tipo no).
P sera´ um ponteiro auxiliar utilizado para percorrer a lista.
Declare um ponteiro ANT (do tipo no).
ANT sera´ um ponteiro auxiliar utilizado para guardar a posic¸a˜odo no´ anterior a P.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Se L for diferente de NULL fac¸a
Se o campo link do no´ apontado por L for igual a NULL fac¸a
(a lista so´ tem um no´)
Recupere o valor do no´
Libere o espac¸o ocupado pelo no´ apontado por L (free(L)).
O valor NULL e´ atribu´ıdo a L - ( a lista esta´ vazia)
Sena˜o
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX
Listas Lineares - Alocac¸a˜o Encadeada
Listas Lineares - Alocac¸a˜o Encadeada
Sena˜o
P recebe o valor do segundo no´ da lista.
ANT recebe o valor do primeiro no´.
Enquanto o campo link do no´ apontado por P for diferente de
nulo fac¸a
P recebe o enderec¸o do pro´ximo no´ da lista
ANT recebe o enderec¸o do pro´ximo no´ da lista
Neste ponto, P aponta para o u´ltimo no´ e ANT para o
penu´ltimo. Recupere o valor do no´.
O campo link do no´ apontado por ANT recebe NULL.
Libera o espac¸o do no´ apontado por P.
Silvio Luiz Bragatto Boss UTFPR
Listas LATEX