Upload
jaeger
View
57
Download
0
Embed Size (px)
DESCRIPTION
Listas lineares. Denise Guliato Faculdade de Computação – UFU www.facom.ufu.br/~guliato. Vários slides foram adaptados de Nina Edelwais e Renata Galante Estrutura de Dados – Série de Livros Didáticos - Informática - UFRGS. Listas lineares. Lista encadeada circular. - PowerPoint PPT Presentation
Citation preview
Listas linearesListas lineares
Denise GuliatoFaculdade de Computação – UFUwww.facom.ufu.br/~guliato
Vários slides foram adaptados de Nina Edelwais e Renata GalanteEstrutura de Dados – Série de Livros Didáticos - Informática - UFRGS
Listas Listas lineareslineares
Lista encadeada Lista encadeada circularcircular
LL encadeada circular
LL encadeada circularLL encadeada circular
PtLista
L1 L2 L4L3
• Elo do último nodo indica endereço do primeiro
• Lista pode ser percorrida a partir de qualquer nodo
• Lista com 1 só nodo: elo do nodo aponta para ele mesmo
PtLista
L1
Crédito do slide para Nina Edelwais e Renata Galante Denise Guliato
LL encadeada circular
Operações básicasOperações básicas
• Criar uma lista
• Inserir novo nodo
• Remover um nodo
• Consulta um nodo
• Destruir lista
AlgoritmosAlgoritmos
Semelhantes a LL encadeada simples
Crédito do slide para Nina Edelwais e Renata Galante Denise Guliato
AlgoritmoAlgoritmo: criar lista circular: criar lista circularLista* Cria_lista(void)Lista* Cria_lista(void)
Lista* Cria_lista(void){ return NULL;}
Inserção de um novo nodoInserção de um novo nodo
• Definir a posição de inserção• Alocar o novo nodo• Preencher com valor• Encadear adequadamente
LL encadeada circular
Crédito do slide para Nina Edelwais e Renata Galante Denise Guliato
Inserção de um novo nodo Inserção de um novo nodo num dos extremos da listanum dos extremos da lista
Ptlista
Inserir um nodo em uma lista circular Inserir um nodo em uma lista circular vaziavazia
L1
Ptlista
Inserção de um novo nodo Inserção de um novo nodo num dos extremos da listanum dos extremos da lista
Onde inserir ????
Inserção de um novo nodo no inicio da Inserção de um novo nodo no inicio da listalista
PtlistaL1 L2 L4L3
L1 L2 L4L3
Ptlista
Inserção de um novo nodo Inserção de um novo nodo num dos extremos da listanum dos extremos da lista
Onde inserir ????
Inserção de um novo nodo no final da listaInserção de um novo nodo no final da lista
PtlistaL1 L2 L4L3
L1 L2 L4L3
Ptlista
Lista* Insere_elem(Lista* Ptl, int elem) { Lista *Ptnodo, *aux; Ptnodo = (Lista*)malloc(sizeof(struct no)); if (Ptnodo == NULL) return Ptl;
Ptnodo->info = elem;
if (Ptl == NULL) // lista vazia { Ptl = Ptnodo; Ptnodo->prox = Ptl; } else //lista nao esta vazia,insere no final { aux = Ptl; while (aux->prox != Ptl) aux = aux->prox; Ptnodo->prox = Ptl; aux->prox = Ptnodo; } return Ptl;}
Algoritmo: Algoritmo: inserir um nodo no final da listaLista* Insere_elem(Lista* Ptl,int elem)
Remoção de um nodoRemoção de um nodoLL encadeada circular
PtLista
PtLista
L1 L2 L4L3
L1 L2 L4
Remover
• Localizar posição do nodo
• Adequar encadeamentos
• Liberar nodo
Crédito do slide para Nina Edelwais e Renata Galante Denise Guliato
Remoção de um nodoRemoção de um nodo
Remover nodo de uma lista vazia
Ptlista NÃO É POSSÍVEL
Remoção de um nodoRemoção de um nodo
Remover nodo de uma lista vazia
Ptlista NÃO É POSSÍVEL
Remover o nodo de uma lista com um único nodo
L1
Ptlista
Ptlista
Remoção de um nodoRemoção de um nodo
Remover o primeiro nodo de uma lista qualquer
L1 L2 L4L3
L2 L3 L4
Remover
PtLista
PtLista
slide adaptado de Nina Edelwais e Renata Galante Denise Guliato
Remoção de um nodoRemoção de um nodo
Remover o nodo qualquer de uma lista
L1 L2 L4L3
L1 L2 L4
Remover
PtLista
PtLista
Slide adaptado de Nina Edelwais e Renata Galante Denise Guliato
Remoção de um nodoRemoção de um nodo
• Caso 1: lista vazia
• Caso 2:nodo a ser removido é o primeiro e único da lista
• Caso 3:nodo a ser removido é o primeiro mas não é o único
• Caso 4:nodo a ser removido é qualquer outro nodo da lista
Lista* Remove_elem(Lista* Ptl, int elem){ Lista *ant,*atual,*aux; if (Ptl == NULL) //lista vazia return Ptl;
atual = Ptl; ant = NULL; while (atual->prox != Ptl && atual->info != elem) { ant = atual; atual = atual->prox; }//continua
Algoritmo:Algoritmo: Remover um nodo de LL Encadeada Circular dado o elemLista* Remove_elem(Lista *Ptl, int elem)
Algoritmo (cont): Algoritmo (cont): Remover nodo de LL Encadeada Circular dado o elem
if (atual->info == elem) { if (ant == NULL) //primeiro nodo sera removido { aux=Ptl; while (aux->prox != Ptl) aux = aux->prox; //aux aponta para o ultimo nodo da lista if (aux == Ptl) //eh primeiro e o ultimo Ptl = NULL; else { // eh o primeiro mas nao o ultimo Ptl = atual->prox; aux->prox = Ptl; } } else ant->prox = atual->prox; free(atual); } return Ptl; }
LL encadeada circular
Consulta nodo da listaConsulta nodo da listaLL encadeada circular
• Iniciar sempre acessando primeiro nodo da lista
• Seguir acessando de acordo com campos de elo
• Para quando encontrar novamente o primeiro nodo da lista
L1 L2 L4L3
PtLista
L5
Crédito do slide para Nina Edelwais e Renata Galante Denise Guliato
int Consulta_nodo(Lista* Ptl, int pos, int *elem){ int cont; Lista *pt; if( Ptl == NULL || pos <= 0) return 0;
cont = 1; pt = Ptl; while(pt->prox != Ptl && cont < pos) { pt=pt->prox; cont++; } if (cont == pos) { *elem = pt->info; return 1; } else return 0;}
Algoritmo: Algoritmo: Consulta K-esimo nodo da Lista
int Consulta_nodo(Lista *Ptl, int pos, int*elem)
AlgoritmoAlgoritmo: destruir lista circulardestruir lista circularLista* Libera_lista(Lista *Ptl)Lista* Libera_lista(Lista *Ptl)
Lista* Libera_lista(Lista* Ptl){ Lista *pt, *aux; if (Ptl == NULL) return NULL; pt = Ptl; while (pt->prox != Ptl) { aux = pt; pt = pt->prox; free(aux); } free(pt); return NULL; // Ptl = NULL; return Ptl;}
AlgoritmoAlgoritmo: destruir lista destruir lista circularcircular
int Tamanho_lista(Lista *Ptl)int Tamanho_lista(Lista *Ptl)int Tamanho_lista(Lista* Ptl){ Lista *pt; int cont;
if (Ptl == NULL) return 0;
pt = Ptl; cont = 1; while (pt->prox != Ptl) { pt = pt->prox; cont++; } return cont;}
Lista encadeada circularLista encadeada circular
• Podemos melhorar o custo computacional da inserção?
• Como?
• Fazendo Ptl apontar para o ultimo nodo da lista circular
Lista encadeada circularLista encadeada circular
• Ptlista aponta para o último nodo da lista:
L1 L2 L4L3
Ptlista
Lista* Insere_elem(Lista* Ptl, int elem) { Lista *Ptnodo; Ptnodo = (Lista*)malloc(sizeof(struct no)); if (Ptnodo == NULL) return Ptl;
Ptnodo->info = elem;
if (Ptl == NULL) // lista vazia { Ptl = Ptnodo; Ptnodo->prox = Ptl; } else //lista nao esta vazia { Ptnodo->prox = Ptl->prox; Ptl->prox = Ptnodo; Ptl = Ptnodo; } return Ptl;}
Algoritmo: Algoritmo: inserir um nodo no final da listaLista* Insere_elem(Lista* Ptl,int elem)
Lista encadeada circularLista encadeada circular
• Como ficaria a função de remoção???
Lista* Remove_elem(Lista* Ptl, int elem){ Lista *ant,*atual,*aux; if (Ptl == NULL) //lista vazia return Ptl;
atual = Ptl->prox; ant = Ptl; while (atual!= Ptl && atual->info != elem) { ant = atual; atual = atual->prox; } if (atual->info == elem) { if (atual == ant) //único nodo Ptl = NULL; else { ant->prox = atual->prox; if (atual == Ptl) //ultimo nodo a ser removido Ptl = ant; } free(atual); } return Ptl; }
Algoritmo:Algoritmo: Remover um nodo de LL Encadeada Circular dado o elemint Remove_elem(Lista *Ptl, int elem)
Algoritmo (cont): Algoritmo (cont): Remover nodo de LL Encadeada Circular dado o elem
Exercício Exercício (baseado no problema de Josephus)(baseado no problema de Josephus)
Considere o seguinte jogo:N pessoas identificadas por um nome e um número
inteiro estão sentadas em círculo, organizadas aleatoriamente. Um número é sorterado no intervalo [1,N]. A pessoa associada a este número sai do círculo. Um novo número é sorteado. Contando da pessoa seguinte àquela que saiu, a enésima pessoa sai do círculo. O sorteio continua até que reste apenas uma pessoa.
Exercício para entregarExercício para entregar
Faça um programa que, usando a lladaec.h, forme o circulo de pessoas, lembrando que são N pessoas sentadas aleatoriamente. Sorteie, a cada iteração um número, e retire uma pessoa do círculo, conforme as regras do jogo. A cada saída, grave em disco a posição e o numero de quem saiu.
No final do jogo, grave o nome e o número da pessoa que sobrou e indique seu premio ou castigo.