Por Ariadne Costa Gomes
1. Para que serve uma lista?
Uma lista serve para interligar os elementos de um conjunto.
2. Quais operações podem ser realizadas com uma lista?
Podem ser realizadas com uma lista as seguintes operações: Inserir, Retirar e Localizar.
3. Descreva sua facilidade durante a execução de um programa.
As listas são estruturas muito flexíveis, porque podem crescer sem diminuir de tamanho durante a execução de um programa, de acordo com a demanda.
4. Como podem ser as operações com os itens na lista?
Itens podem ser acenados, inseridos ou retirados de uma lista.
5. O que pode ser feito com uma lista muito grande ou duas listas pequenas?
Duas listas podem ser concatenadas para formar uma lista única, assim como uma lista pode ser partida em duas ou mais listas.
6. Quando é aconselhável o seu uso?
Listas são adequadas para aplicações nas quais não é possível prever a demanda por memória, permitindo a manipulação de quantidades imprevisíveis de dados, de formato também imprevisível.
7. Em que são úteis às listas?
Listas são úteis em aplicações tais como manipulação simbólica, gerência de memória, simulação e compiladores.
8. Como é feita a definição em uma lista?
Uma lista linear é uma sequência de zero ou mais itens, x1, x2....,xn, na qual x1 é de um determinado item e xn representa o tamanho da lista linear.
9. Descreva sua propriedade principal:
Sua principal propriedade estrutural envolve as posições relativas dos itens em uma dimensão. Assumindo n>=1, x1 é o primeiro item da lista e xné o último item da lista.
– xi precede xi+1 para i = 1, 2, , n − 1
– xi sucede xi−1 para i = 2, 3, , n
– o elemento xi é dito estar na i-ésima posição da lista.
10. Das várias estruturas que podem ser utilizadas, quais estudamos?
Listas Lineares.
11. Descreva sobre os cinco pontos relacionados à implementação de uma lista.
1. FLVazia(Lista). Faz a lista ficar vazia.
2. Insere(x, Lista). Insere x após o último item da lista.
3. Retira(p, Lista, x). Retorna o item x que está na posição p da lista,
retirando-o da lista e deslocando os itens a partir da posição p+1
para as posições anteriores.
4. Vazia(Lista). Esta função retorna true se lista vazia; senão retorna
false.
5. Imprime(Lista). Imprime os itens da lista na ordem de ocorrência.
12. Escreva a estrutura necessária para implementação de uma lista com arranjo.
Os itens são armazenados em
um array de tamanho suficiente
para armazenar a lista.
• O campo Último aponta para a
posição seguinte a do último ele-
mento da lista.
• O i-ésimo item da lista está arma-
zenado na i-ésima posição do ar-
ray, 1 ≤ i <Último.
• A constante MaxTam define o ta-
manho máximo permitido para a
lista.
13. Escreva as funções utilizadas para operar sobre a lista.
void FLVazia(TipoLista ∗Lista)
{ Lista−>Primeiro = INICIOARRANJO; Lista−>Ultimo = Lista−>Primeiro ; }
int Vazia(TipoLista Lista)
{ return ( Lista .Primeiro == Lista .Ultimo ) ; } /∗ Vazia ∗/
void Insere(TipoItem x , TipoLista ∗Lista)
{ i f ( Lista −> Ultimo > MAXTAM)
pr int f ( "Lista esta cheia\n" ) ;
else { Lista −> Item[ Lista −> Ultimo − 1] = x;
Lista −> Ultimo++;
}
} /∗ Insere ∗/
void Retira(TipoApontador p, TipoLista ∗Lista , TipoItem ∗Item)
{ int Aux;
i f (Vazia(∗Lista ) | | p >= Lista −> Ultimo)
{ pr int f ( "Erro : Posicao nao existe \n" ) ;
return;
} ∗Item = Lista −> Item[p − 1];
Lista −> Ultimo−−;
for (Aux = p; Aux < Lista −> Ultimo ; Aux++)
Lista −> Item[Aux − 1] = Lista −> Item[Aux] ;
} /∗ Retira ∗/
void Imprime(TipoLista Lista)
{ int Aux;
for (Aux = Lista .Primeiro − 1; Aux <= (Lista .Ultimo − 2); Aux++)
pr int f ( "%d\n" , Lista . Item[Aux] .Chave) ;
} /∗ Imprime ∗/
14. Escreva as vantagens de utilizar listas com arranjos.
Economia de memória (os apontadores são implícitos
nesta estrutura).
15. Escreva as desvantagens de utilizar listas com arranjos.
– custo para inserir ou retirar itens da lista, que pode causar um
deslocamento de todos os itens, no pior caso;
– em aplicações em que não existe previsão sobre o crescimento da
lista, a utilização de arranjos em linguagens como o Pascal pode
ser problemática porque nesse caso o tamanho máximo da lista
tem de ser definido em tempo de compilação.
16. Descreva a implementação de listas com apontadores.
• Cada item é encadeado com o seguinte mediante uma variável do tipo
Apontador.
• Permite utilizar posições não contíguas de memória.
• É possível inserir e retirar elementos sem necessidade de deslocar os
itens seguintes da lista.
• Há uma célula cabeça para simplificar as operações sobre a lista.
17. Escreva as estruturas necessárias para implementar listas com apontadores.
typedef int TipoChave;
typedef struct {
TipoChave Chave;
/∗ outros componentes ∗/
} TipoItem;
typedef struct TipoCelula ∗TipoApontador ;
typedef struct TipoCelula {
TipoItem Item;
TipoApontador Prox;
} TipoCelula;
typedef struct {
TipoApontador Primeiro , Ultimo;
} TipoLista;
• A lista é constituída de células.
• Cada célula contém um item da
lista e um apontador para a cé-
lula seguinte.
• O registro TipoLista contém um
apontador para a célula cabeça
e um apontador para a última cé-
lula da lista.
18. Escreva as funções necessárias para trabalha com listas utilizando apontadores.
void FLVazia(TipoLista ∗Lista)
{ Lista−>Primeiro = (TipoApontador ) malloc(sizeof (TipoCelula ) ) ;
Lista−>Ultimo = Lista−>Primeiro ; Lista−>Primeiro−>Prox = NULL;
}
int Vazia(TipoLista Lista)
{ return ( Lista .Primeiro == Lista .Ultimo ) ; }
void Insere(TipoItem x , TipoLista ∗Lista)
{ Lista−>Ultimo−>Prox = (TipoApontador ) malloc(sizeof (TipoCelula ) ) ;
Lista−>Ultimo = Lista−>Ultimo−>Prox; Lista−>Ultimo−>Item = x;
Lista−>Ultimo−>Prox = NULL;
}
void Retira(TipoApontador p, TipoLista ∗Lista , TipoItem ∗Item)
{ /∗−−O item a ser retirado e o seguinte ao apontado por p−−∗/
TipoApontador q;
i f (Vazia(∗Lista ) | | p == NULL | | p−>Prox == NULL)
{ pr int f ( " Erro : Lista vazia ou posicao nao existe \n" ) ;
return;
}
q = p−>Prox; ∗Item = q−>Item; p−>Prox = q−>Prox;
i f (p−>Prox == NULL) Lista−>Ultimo = p;
free(q) ;
}
void Imprime(TipoLista Lista)
{ TipoApontador Aux;
Aux = Lista .Primeiro−>Prox;
while (Aux != NULL)
{ pr int f ( "%d\n" , Aux −>Item.Chave) ; Aux = Aux −>Prox ; }
}
19. Quais as vantagens de utilizar listas com apontadores?
– Permite inserir ou retirar itens do meio da lista a um custo constante
(importante quando a lista tem de ser mantida em ordem).
– Bom para aplicações em que não existe previsão sobre o
crescimento da lista (o tamanho máximo da lista não precisa ser
definido a priori).
20. Qual a desvantagem de utilizar listas com apontadores?
Utilização de memória extra para armazenar os apontadores.
Post a Comment