Estruturas de Dados - Listas Fechadas

Prévia do material em texto

Listas Fechadas
Estruturas de Dados
Profa. Carla Koike ­ CIC
   
Tipos de listas encadeadas
Início
Lista aberta com encadeamento simples OK!
Início
Lista aberta com encadeamento duplo OK!
   
Tipos de listas encadeadas, cont.
Início
Lista fechada com encadeamento simples
Lista fechada com encadeamento duplo
Início
   
Listas fechadas com encadeamento
 simples
Mudanças em relação a lista aberta com encadeamento simples:
● O último nó agora possui um próximo: será o primeiro nó!
● Primeiro e último são convenções, pois uma lista circular tem 
início nem fim.
● A partir de qualquer ponto da lista, podemos alcançar qualquer 
outra posição da lista.
   
Listas Fechadas com 
Encadeamento Duplo
Início
● Código de uma lista fechada com encadeamento simples:
● lista_circular_simples.c
● Código de uma lista fechada com encadeamento duplo:
● circular_double_linked_list.c
   
Exercício: Problema de Josephus
● Um grupo de soldados se encontra circundado por uma 
força inimiga esmagadora.... Não há esperanças de vitória sem a chegada de reforços, mas existe 
somente um cavalo disponível para escapar. Os soldados entram em acordo para determinar qual deles deverá escapar e trazer ajuda, eles formam um 
círculo e um número n é sorteado num chapéu. Um de seus nomes é sorteado também. Começando pelo soldado cujo nome foi sorteado, eles começam 
a contar ao longo do círculo em sentido horário. Quando a contagem alcança n, esse soldado é retirado do círculo e a contagem reinicia com o soldado 
seguinte. O processo continua de maneira que, toda vez que n é alcançado, outro soldado sai do círculo. Todo soldado retirado do círculo nçao entra 
mais na contagem. O último soldado que restar deverá montar no cavalo e escapar.
● A entrada do programa é o número n e uma lista de 
nomes, que será o seqüenciamento do círculo em sentido 
horário, começando pelo soldado a partir do qual a 
contagem será iniciada.
● O programa deverá imprimir os nomes na seqüência em 
que são eliminados e o nome do soldado que escapará.
   
Exercício: Problema de Josephus, 
cont.
● Lista circular? Simples ou duplamente encadeada?
● Operações: 
– criar lista com todos os nomes
– sortear valor de n e nome inicial.
– eliminar elemento e imprimir seu nome
● Adaptar um dos programas mostrados (lista circular 
simples ou lista circular duplamente encadeada) para 
resolver o problema de Josephus.
   
Exercício: Soma de inteiros    
(super) longos
● O hardware  da maioria dos computadores só permite inteiros 
de um tamanho máximo específico. Se precisamos representar 
inteiros positivos de tamanhos arbitráriamente grandes e 
escrever uma função que retorne a soma de dois números 
inteiros deste tipo, as listas circulas oferecem uma solução 
interessante
● A idéia é usar uma lista circular para armazenar cada valor: 
cada nó armazena alguns dígitos do número. Por exemplo, o 
número 1234 5678 9012 3456, seria amazenado como:
­1 3456 9012 5678 1234
   
Soma de inteiros(super) longos, cont
● Somar dois números equivale a ter duas listas circulares e ir 
somando cada uma das suas células, armazenando o resultado 
em outra lista (somente os quatro dígitos menos significativos 
do resultado devem ser armazenados, enquanto o quinto dígito 
mais significativo, se houver, será transportado para a próxima 
soma).
­1 3455 9057 3676 2265
­1 9999 0044 7998 1030
­1 3456 9012 5678 1234
   
Exercício: Manipulação Polinomial 1
● Uma lista pode ser usada para representar um 
polinômio. Cada nó representa o termo e contém a 
potência e o coeficiente desse termo. Por exemplo, o 
polinômio p(x) = ­3x5 + 6x3 ­ 7x + 8, seria representado 
por:
­3 6 ­7 85 3 1 0Início Null
   
Exercício: Manipulação Polinomial 1
● Escreva funções para:
– imprimir o polinômio
– somar dois polinômios;
– multiplicar dois polinômios;
– calcular a derivada desse polinômio
   
Exercício: Manipulação Polinomial 2
● Uma lista pode ser usada para representar um 
polinômio em três variáveis (x,y,z). Cada nó 
representa um termo e contém a potência, o 
coeficiente e a variável desse termo. Por exemplo, o 
polinômio p(x,y,z) = ­3x5 + 6y3 ­ 7z + 8, poderia ser 
representado por uma lista encadeada:
­3 6 ­7 85   x 3    y 1   z 0    .Início Null
   
Exercício: Manipulação Polinomial 2
● Determine qual tipo de lista seria mais eficiente para 
realizar as seguintes operções:
– calcular a derivada parcial desse polinômio em relação 
a qualquer uma de suas variáveis
– avaliar o polinômio para valores dados de x, y e z
● Implemente um programa que realize as operações 
doexercício anterior e as definidas acima com este 
tipo de polinômio.