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.
Nenhum comentário:
Postar um comentário