Trabalho de casa nº 4
Review of Attempt 1
Started on: Sábado, 24 Março 2007, 00:04
Completed on: Sábado, 31 Março 2007, 03:26
Tempo gasto: 7 dias 2 horas
1
Considere uma reimplementação do TAD fila usando os seguintes tipos para lista, fila:
struct lista{int val[34];}
struct fila {int cabeca, cauda; struct lista l;};
Comente (descreva o funcionamento) e indique quais as novas implicações desta abordagem, relativamente à que foi vista na aula prática.
Resposta:
Nesta abordagem é usado um array que vai conter os valores. Como uma fila é uma estrutura dinâmica e pode crescer infinitamente, esta abordagem torrna-se pouco eficiente uma vez que um array em C tem um tamanho fixo, Contudo, pode-se definir este array com um tamanho suficientemente grande para conter a fila.
Outro problema desta abordagem é o caso em que a fila pode estar cheia. Devemos então usar um array circular para evitar esse problema.
Podemos fazer operações como as seguintes para este tipo de dados.
struct fila f;
f.cabeca = 1;
f.cauda = 2;
f.l.val[0] = 1;
fl.val[1] = 2;
por exemplo o algoritmo de inserção poderia ser algo como:
void insere(fila * f, int x)
{
if( f->cauda + 1 >= 34 )
{
printf("\nEstá a inserir fora dos limites fila");
exit(1);
}
f->l->val[f->cauda++ ] = x;
}
2
Se a implementação do tipo lista fosse:
struct lista{ int val;
lista *prox;
lista *ant;};
1. Como chamaria a esse tipo de lista?
2. Quais as implicações na inserção e remoção?
3. Quais as vantagens de usar este tipo?
Resposta:
1. Lista Duplamente Ligada.
2. A inserção é feita em três etapas. Primeiro criamos o novo nó a inserir. Depois, procuramos a posição onde vamos inserir e, finalmente, fazemos os redireccionamentos dos apontadores de forma a que o nó fique 'ligado à lista'.
Usando um apontador auxiliar para determinar a posição onde se vai inserir o novo nó. A pesquisa termina com o apontador auxiliar a apontar para o nó que deve ser o proximo do nó que vamos inserir. Depois o próximo do novo nó passa a ser o nó onde estamos. O anterior do novo nó passa a ser o anterior do nó onde estamos. O seguinte do anterior do nó onde estamos passa a ser o novo nó e, finalmente, o anterior do nó onde estamos passa a ser o nó que estamos a inserir. (Isto se o nó for para inserir no meio da lista). Inserir na cabeça ou na cauda é semelhante ou até mais simples.
A remoção segue os mesmo tipo de redirecionamento de apontadores e pesquisa da inserção. Percorremos a lista até estarmos no nó anterior ao que vai ser removido.
Pomos esse nó a apontar para o próximo do próximo e o anterior deste ultimo a apontar para o nó onde estamos. Por fim libertamos da memoria o proximo do nó onde estamos (o nó a eliminar).
3. Uma das principais vantagens
relativamente às listas simples está na facilidade com
que é possível implementar as operações
de inserir, remover, etc., utilizando um só apontador
auxiliar, uma vez que a partir de um dado nó é sempre
possível aceder ao seu próximo e ao seu anterior.
Podemos deslocar-nos para o nó anterior ou para o nó
seguinte de um dado nó com igual facilidade. Além disso, uma lista duplamente ligada permite-nos remover um nó qualquer
da lista em tempo constante, usando apenas um ponteiro para esse nó.