Estruturas de Dados - Lista de exercícios 2

1. 1. Dar um algoritmo para ``apagar'' uma pilha em alocação ligada, isto é, devolver todos os seus elementos à lista livre.
   2. Digamos que esta operação ocorre com muita frequência, de que maneira você alteraria a representação da pilha (em alocação ligada) para acelerar a operação?
2. Escreva um algoritmo para inverter uma lista linear ligada, de modo que seus elementos apareçam na ordem inversa.
3. Considere listas circulares (em alocação ligada), não vazias, apontadas por PTR1 e PTR2 e o seguinte algoritmo:

        P:=link(PTR1);
        link(PTR1):=link(PTR2);
        link(PTR2):=P;
        PTR1:=PTR2;
        PTR2:=nil

   1. Qual o resultado da execução deste algoritmo?
   2. Qual o resultado se PTR1 e PTR2 apontam para dois elementos distintos da mesma lista circular?
4. O seguinte método para codificar despachos diplomáticos foi adotado: primeira etapa - todas sequências não-vogais incluindo o espaço em branco e os caracteres de pontuação são invertidas; segunda etapa - a mensagem inteira resultante é invertida dando origem à mensagem codificada.

   Por exemplo a mensagem original

             PROBLEMAS HIPER-INTERESSANTES.

   passa a ser

             RPOLBEMAH SIPE-RITNERESSATNE.S

   após a primeira etapa e finalmente é codificada como

             S.ENTASSERENTIR-EPIS HAMEBLOPR

   após a segunda etapa.

   O embaixador recebeu uma mensagem codificada como se segue:

             TS.ECOXES ES TRIAR MAMPRO CEUGENSO CE SE. VENTERGU

   Escreva um algoritmo que ajude o embaixador a decodificar mensagens assim codificadas. Use alocação ligada (onde cada elemento contém um caractere no campo de info), pois o embaixador não sabe a priori o tamanho da mensagem. (Tente aproveitar o resultado da questão 2 acima.)

 
• About this document ...