Listas Ligadas – Conceitos Avançados Estruturas de Dados e Algoritmos 04/11/2015 Fábio Lopes Caversan 1 Listas Circulares Dado um ponteiro p para um nó numa lista linear Não é possível atingir nenhum dos nós que antecedem o Node p Ao atravessar uma lista, o ponteiro externo deve ser preservado para não perdemos a lista Numa lista circular o campo Next do último nó, ao invés de ponteiro nulo, contém um ponteiro para o primeiro nó 04/11/2015 Fábio Lopes Caversan 2 list Último nó Primeiro nó Atingi-se qualquer ponto da lista, não importando o ponto de partida Não existe mais um “primeiro” e “último” nó natural Uma convenção é considerar o último nó como apontado pelo ponteiro externo (list). E o nó seguinte torna-se o primeiro nó Último nó: list Primeiro nó: list.Next Permite incluir/remover elemento a partir do início ou do final de uma lista Por convenção: ponteiro nulo representa uma lista circular vazia 04/11/2015 Fábio Lopes Caversan 3 Pilha como lista circular Seja stack um ponteiro para o último nó de uma lista circular O primeiro nó é o topo da pilha A função Empty pode ser: Empty () { return (stack == NULL); } 04/11/2015 Fábio Lopes Caversan 4 Chamando Push(x) public void Push (object x) { Node p; p = new Node ( ); Push é mais complexa para lista circulares do que para listas lineares p.Info = x; if (Empty ()) stack = p; else p.Next = stack.Next; stack.Next = p; } 04/11/2015 Fábio Lopes Caversan 5 Chamando Pop () public object Pop () { object x; Node p; if (Empty ()) throw new Exception (“Underflow da pilha”); p = stack.Next; x = p.Info; if ( p == stack) stack = NULL; /* só havia um nó na pilha */ else stack.Next = p.Next; p = NULL; return x; } 04/11/2015 Fábio Lopes Caversan 6 Agora é vez das filas . . . É mais fácil representar uma fila como lista circular do que lista linear É usado apenas um único ponteiro p p é o final da fila e nó seguinte é seu início A função Empty() é idêntica à da pilha Remove () é idêntica à pop, basta substituir stack por queue que é um ponteiro para a fila 04/11/2015 Fábio Lopes Caversan 7 Chamando Insert(x) Insert (x) equivale a: Insert (int x) { Node p; p = new Node( ); p.Info = x; if (Empty()) queue = p; else p.Next = queue.Next; queue.Next = p; queue = p; return; } 04/11/2015 Push (x); queue = queue.Next; Isso significa que para inserir um elemento no final de uma fila circular, o elemento é inserido no início da fila e o ponteiro da lista circular avança um elemento para que o novo elemento ocupe o final. Fábio Lopes Caversan 8 Operações primitivas para listas circulares InsertAfter(x) é semelhante à rotina das listas lineares public object DeleteAfter (Node p) { object x; Node q; if (( p == NULL || (p == p.Next)) throw new Exception(“Não há próximo nó para remover”); q = p.Next; x = q.Info; p.Next = q.Next; q = NULL; return x; Fábio Lopes Caversan } 04/11/2015 9 O problema de Josephus Solução com lista circular Um grupo de soldados circundado por uma força inimiga esmagadora Não há esperanças de vitória O negócio é escapar . . . Mas só existe um cavalo disponível!!!! Que tal um acordo para escolher o soldado felizardo ? 04/11/2015 Fábio Lopes Caversan 10 É sorteado um número n de um chapéu e também o nome de um soldado Iniciando no soldado, eles começam a contar no sentido horário O soldado no qual a contagem n é finalizado, é retirado do círculo A contagem reinicia no soldado seguinte ao retirado do círculo Todo soldado que sair do círculo, não entra mais no processo O último soldado é o felizardo para escapar com o cavalo 04/11/2015 Fábio Lopes Caversan 11 Listas duplamente ligadas Uma lista circular tem vantagens sobre uma lista linear Mas apresenta várias deficiências: não dá para percorrê-la no sentido contrário, nem um nó pode ser ser eliminado, em função de apenas um ponteiro para esse nó Para sobrepujar a deficiências acima, o mais adequado é utilizar a lista duplamente ligada 04/11/2015 Fábio Lopes Caversan 12 nulo nulo Lista linear duplamente ligada Lista circular duplamente ligada sem cabeçalho 04/11/2015 Fábio Lopes Caversan 13 Observações Cada nó tem dois ponteiros: um para seu predecessor e outro para seu sucessor De fato os termos predecessor e sucessor não fazem sentido, porque a listas duplamente ligadas são simétricas As listas duplamente ligadas podem ser lineares ou circulares e, podem conter ou não nó de cabeçalho Um nós tem três campos: Info, Prior e Next que contem ponteiros para os nós em ambos os lados 04/11/2015 Fábio Lopes Caversan 14 Inserindo um novo primeiro elemento numa lista duplamente ligada novo Info Info null info null novo null Info Info Info null 04/11/2015 Fábio Lopes Caversan 15 Inserindo um novo elemento no meio de uma lista duplamente ligada novo Info Info null info null novo Info Info null 04/11/2015 info null Fábio Lopes Caversan 16 Inserindo um novo último elemento numa lista duplamente ligada novo Info Info null info null novo null Info Info info null 04/11/2015 Fábio Lopes Caversan 17 Apagando o primeiro elemento Info Info Info null Excluído null null 04/11/2015 null Info null Fábio Lopes Caversan Info null 18 Apagando o elemento do meio Info Info Info null null Info null 04/11/2015 Excluído null null Fábio Lopes Caversan Info null 19 Apagando o último elemento Info Info Info null null Info null 04/11/2015 Infp Excluído null Fábio Lopes Caversan null null 20 Representando o nó public class Node { object info; Node prior, next; ... // Gets e Sets }; 04/11/2015 Fábio Lopes Caversan 21 Eliminação de um nó em listas duplamente ligadas public object Delete (Node p) { object x; Node q,r; if (p == NULL) throw new Exception(“Renovação vazia”); x = p.Info; q = p.Prior; r = p.Next; q.Next = r; r.Prior = q; p = NULL; return; } 04/11/2015 Fábio Lopes Caversan 22 Inserindo um nó com informação x à direita de p InsertAfter (Node p, int x) { Node q,r; if (p == NULL) throw new Exception(“Inserção vazia”); q = new Node ( ); q.Info = x; r = p.Next; r.Prior = q; q.Next = r; q.Left = p; p.Next = q; return; } 04/11/2015 Fábio Lopes Caversan 23