30
Listas lineares 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

  • 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

Page 1: Listas lineares

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

Page 2: Listas lineares

Listas Listas lineareslineares

Lista encadeada Lista encadeada circularcircular

Page 3: Listas lineares

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

Page 4: Listas lineares

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

Page 5: Listas lineares

AlgoritmoAlgoritmo: criar lista circular: criar lista circularLista* Cria_lista(void)Lista* Cria_lista(void)

Lista* Cria_lista(void){ return NULL;}

Page 6: Listas lineares

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

Page 7: Listas lineares

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

Page 8: Listas lineares

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

Page 9: Listas lineares

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

Page 10: Listas lineares

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)

Page 11: Listas lineares

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

Page 12: Listas lineares

Remoção de um nodoRemoção de um nodo

Remover nodo de uma lista vazia

Ptlista NÃO É POSSÍVEL

Page 13: Listas lineares

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

Page 14: Listas lineares

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

Page 15: Listas lineares

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

Page 16: Listas lineares

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

Page 17: Listas lineares

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)

Page 18: Listas lineares

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; }

Page 19: Listas lineares

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

Page 20: Listas lineares

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)

Page 21: Listas lineares

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;}

Page 22: Listas lineares

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;}

Page 23: Listas lineares

Lista encadeada circularLista encadeada circular

• Podemos melhorar o custo computacional da inserção?

• Como?

• Fazendo Ptl apontar para o ultimo nodo da lista circular

Page 24: Listas lineares

Lista encadeada circularLista encadeada circular

• Ptlista aponta para o último nodo da lista:

L1 L2 L4L3

Ptlista

Page 25: Listas lineares

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)

Page 26: Listas lineares

Lista encadeada circularLista encadeada circular

• Como ficaria a função de remoção???

Page 27: Listas lineares

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)

Page 28: Listas lineares

Algoritmo (cont): Algoritmo (cont): Remover nodo de LL Encadeada Circular dado o elem

Page 29: Listas lineares

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.

Page 30: Listas lineares

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.