EDA 3

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

Estrutura de Dados e Arquivos
(adaptado do material do prof. Nicolas Anquetil)
Unidade 3
Técnicas de encadeamento
Lista ordenada
Encadeamento circular
Encadeamento duplo
Nós cabeça e sentinela
Lista ordenada
Uma lista ordenada deve manter o conteúdo das células ordenado segundo um critério definido, de forma que durante o acesso sequencial a seus dados essa ordem seja respeitada.
Lista ordenadas podem ser usadas para ordenar números ou nomes
A ordem deve ser garantida pela rotina de inserção de novos dados, já que a retirada de um dado não altera a ordem.
A rotina de inserção deve procurar a posição de inserção de forma que o valor de seu dado seja maior ao anterior e menor ou igual o posterior.
Lista ordenada
A inserção da célula intermediária deve ser feita de forma que o elemento anterior aponte para o novo elemento e o novo elemento aponte para o posterior.
Lista ordenada
A inserção da célula intermediária deve ser feita de forma que o elemento anterior aponte para o novo elemento e o novo elemento aponte para o posterior.

Lista ordenada
A inserção da célula intermediária deve ser feita de forma que o elemento anterior aponte para o novo elemento e o novo elemento aponte para o posterior.


Lista ordenada
A inserção da célula intermediária deve ser feita de forma que o elemento anterior aponte para o novo elemento e o novo elemento aponte para o posterior.



Exercício
1) Implemente em C uma rotina que insira um número (real, passado como parâmetro) numa lista encadeada garantindo que a lista continue sempre ordenada em ordem crescente.
Técnicas de encadeamento
A lista encadeada que apresentamos é o caso mais simples.
Existem variações que podem se tornar úteis em diferentes casos:
Encadeamento circular
Encadeamento duplo
Nodos cabeça e sentinela
Encadeamento circular
Vimos na unidade precedente como implementar uma lista encadeada que tem um apontador de início, cada celula apontando para a próxima até que a última aponta para NULL
Na lista circular, em vez de apontar para nada (“NULL”), o último nó contem um ponteiro sobre o primeiro elemento da fila.
Encadeamento circular
A vantagem da lista encadeada circular é que qualquer elemento da lista pode servir de início para uma busca.
Exemplo:
Considere uma lista encadeada circular implementando os dias da semana para um calendário. A mudança do “dia” no calendário se faz avançando o apontador da lista para a próxima célula:
segunda
terça
quarta
quinta
sexta
sábado
domingo
Exercício em sala
1) Escreva um algoritmo de busca de um dado numa lista encadeada circular que receba o dado como parâmetro e retorne TRUE se encontrar ou FALSE em caso contrário. Implemente o algoritmo de forma que a cabeça da lista seja sempre o último dado lido, para que a busca seguinte comece a partir da última pesquisa. 
Encadeamento duplo
A implementação básica da lista encadeada permite percorrer a lista num sentido só (da cabeça para o final)
Para achar o nó anterior a um nó N, temos que percorrer a lista do inicio até chegar ao nó cujo “prox” é N
Pode ser interessante ter a possibilidade de percorrer uma lista nos dois sentidos e assim achar rapidamente o predecessor e o sucessor de qualquer nó
Encadeamento duplo
Para isso podemos usar uma lista duplamente encadeada:
As desvantagens dessa implementação são:
Usa mais memória (dois ponteiros para cada elemento)
Operações de inserção e remoção são mais complexas (quatro ponteiros a atualizar)
A vantagens é que a lista é muito mais flexível, permitindo percursos nos dois sentidos
Exercício em sala
1) Escreva um algoritmo de busca de um dado numa lista duplamente encadeada ordenada que receba o dado como parâmetro e retorne TRUE se encontrar ou FALSE em caso contrário. Implemente o algoritmo considerando que o início da busca se fará pelo meio da lista e que a direção de busca deve ser decidida dinamicamente em função do valor procurado. 
Exercícios em laboratório
1) Implementar as operações de procura de um elemento, inserção na ordem e remoção de dado passado como parâmetro para a lista encadeada circular.
2) Mesmo exercício com uma lista duplamente encadeada
3) Mesmo exercício com uma lista duplamente encadeada circular escolhendo dinamicamente a direção da busca e alterando a cabeça da lista de forma que ela esteja sempre no meio da lista encadeada (mesmo número de células a direita ou a esquerda).
Nó cabeça
Considere a seguinte solução para o problema da inserção numa lista encadeada ordenada:
void insereNaOrdem(lista *p_L, float x) {
 cel *tmp,*pos;
 tmp=(cel*)malloc(sizeof(cel));
 tmp->val=x;
 if(((*p_L)==NULL)||(*p_L)->val>x)){
	 tmp->prox=*p_L;
		 *p_L=tmp;
		 return;
 }
 pos=*p_L; 
 while((pos->prox!=NULL)&&(pos->prox->val<x)) {
		pos=pos->prox;
 }
 tmp->prox=pos->prox; 
 pos->prox=tmp;			
}
Nó cabeça
Ao inserir um novo elemento dentro de uvma lista ordenada, temos três casos distintos a tratar:
O elemento deve ser inserido no meio da lista.
O elemento deve ser inserido no início da lista (ele será o primeiro elemento)
O elemento deve ser inserido no final da lista (ele será o último elemento)
Esses vários casos obrigam a ter trechos de código diferentes o que complica a implementação da inserção
No caso da remoção temos os mesmos problemas
Nó cabeça
Para simplificar a implementação, podemos suprimir o caso especial: inserção/remoção do primeiro nó
Vamos introduzir um nó cabeça, vazio que impedirá que esse caso especial ocorra
A lista mesmo vazia sempre contem o nó cabeça
Em caso algum se deve remover o nó cabeça
Não se deve inserir nodos antes do nó cabeça

Nó cabeça
A nova solução para o problema da inserção numa lista encadeada ordenada seria:
void insereNaOrdem(lista p_L, float x) {
 cel *tmp,*pos;
 tmp=(cel*)malloc(sizeof(cel));
 tmp->val=x;
 pos=p_L; // cabeça 
 while((pos->prox!=NULL)&&(pos->prox->val<x)) {
		 pos=pos->prox;
 }
	tmp->prox=pos->prox; 
 pos->prox=tmp; 			
}
Nó cabeça
Além do mais, já que o nó cabeça fica vazio, poderíamos tentar nos aproveitar dele para armazenar outras informações, por exemplo o tamanho da lista
Isso só é possível se o tipo dos elementos da lista for compatível com a informação que queremos armazenar.
Ex.: Não podemos armazenar o tamanho da lista no nó cabeça de uma lista de caracteres (tamanho inteiro não pode ser armazenado num nó “caractere”).
Nó sentinela
De maneira semelhante, ao procurar o lugar de um elemento numa lista ordenada, temos sempre que cuidar de maneira diferente o caso onde o elemento é o maior de todos (último elemento da lista)
Para suprimir esse problema, podemos usar um nó sentinela que vai conter o elemento maior que pode ser inserido na lista (ex.: MAXINT)
Esse nó sentinela fica sempre no final da lista
Assim todo elemento a inserir será sempre menor que o elemento do nó sentinela e não precisamos mais nos preocupar com esse caso especial
Nó sentinela
A nova solução para o problema da inserção numa lista encadeada ordenada seria:
void insereNaOrdem(lista p_L, float x) {
 cel *tmp,*pos;
 tmp=(cel*)malloc(sizeof(cel));
 tmp->val=x;
 pos=p_L; // cabeça 
 while(pos->prox->val<x) {
		 pos=pos->prox;
 }
 tmp->prox=pos->prox;
 pos->prox=tmp;			
}
Nós cabeça e sentinela
Os nós cabeça e sentinela devem ser inseridos quando da inicialização da lista encadeada:
void init(lista *p_L)
{ // cabeça
 (*p_L) = (lista)malloc(sizeof(cel)); 
	(*p_L)->val=0;
 // sentinela
 (*p_L)->prox = (lista)malloc(sizeof(cel)); (*p_L)->prox->val=MAXINT;
}
Nó sentinela
Esta solução supõe que podemos definir um valor máximo para os elementos da lista o que nem sempre é possível (ex.: qual seria o valor máximo de uma lista de alunos?)
O problema é que se temos um controle total sobre os ponteiros que formam
a lista, nem sempre temos controle sobre os valores que serão inseridos na lista.
Exercício
1) Adapte o algoritmo de busca implementado para a lista duplamente encadeada, considerando que exista o nó cabeça e o nó sentinela, que nesse caso guardariam mínimo e máximo de valores possíveis de busca.