Exercícios Resolvidos de Estrutura de Dados 2ª Etapa.

Lista de Exercícios

1.      Dê o conceito de Pilha.
R: É uma lista linear em que todas as inserções, e retiradas e, geralmente todos os acessos são feitos em apenas um extremo da lista.

2.      Qual é o modelo utilizado?
R: O Modelo é o de um monte de pratos em uma prateleira, sendo conveniente retirar ou adicionar pratos na parte superior.

3.      Explique a disposição dos itens em uma pilha.
R: Os itens são colocados um sobre o outro.  O item inserido mais recentemente está no  topo, e o inserido menos recentemente está no fundo.

4.      Qual teoria está associada e explique o seu funcionamento associado à Pilha?
R: Esta imagem está associada com a teoria de autômato, na qual o topo de uma pilha é considerado como o receptáculo de uma cabeça de leitura/gravação que pode empilhar e desempilhar itens da pilha.

5.      Qual é sua propriedade?
R: O último item inserido é o primeiro item que pode ser retirado da lista .  São chamadas listas LIFO (“last-in, First-out).

6.      Qual a ordem utilizada?
R: Existe uma ordem linear para pilhas, do mais recente para o menos recente.

7.      Para que é ideal?
R: É ideal pra estruturas aninhadas de profundidade imprevisível.

8.      Explique sobre a seqüência de obrigações.
R: A ordem de remoção garante que as estruturas mais internas serão processadas antes das mais externas.

9.      Qual a natureza de sua estrutura?
R:  As pilhas ocorrem em estruturas de natureza recursiva(como árvores).

10.  Comente sobre os três itens de estruturas em aplicações.
R:  1ª – Quando é necessário caminhar em um conjunto de dados e guardar uma lista de coisas a fazer posteriormente.
      2ª – O controle de seqüência de chamadas de subprogramas.
      3ª – A sintaxe de expressões aritméticas.

11.  Descreva o conjunto de operações e suas finalidades.
FPVazia(pilha). Faz a pilha ficar vazia.
Vazia(Pilha). Retorna true se a pilha está vazia; caso contrário retorna false.
Empilha(x,pilha). Insere o item x no topo da pilha.
Desempilha(Pilha,x). Retorna o item x no topo da pilha, retirando-a da pilha.
Tamanho(Pilha). Essa função retorna o número de itens da pilha.

12.  Comente sobre implementação de Pilhas por meio de Arranjo.
R: Os itens da pilha são armazenados em posições contíguas de memória

13.  Quais os três itens observados para a estrutura de Pilhas com Arranjo?
* Os itens são armazenados  em um array do tamanho da pilha.
* O outro campo de mesmo registro contém um apontador para o item no topo da pilha.
* A constante MaxTam define o tamanho máximo permitido para a pilha.

14.  Escreva a estrutura de uma Pilha usando Arranjo.
#difine MaxTam 1000
typedef int TipoApontador
typedef int TipoChave
typedef struct {
TipoChave Chave;
}TipoItem;
typedef struct {
TipoItem Item;
TipoApontador Topo;
}TipoPilha;

15. Escreva as funções utilizadas por Pilhas utilizadas por Arranjo.

void FPVazia(TipoPilha _Pilha)

     { Pilha−>Topo = 0; }

    int Vazia(TipoPilha Pilha)

    { return (Pilha .Topo == 0); }

    void Empilha(TipoItem x , TipoPilha _Pilha)

    { i f (Pilha−>Topo == MaxTam) pr int f ( "Erro : pilha esta cheia\n" ) ;

    else { Pilha−>Topo++; Pilha−>Item[Pilha−>Topo − 1] = x ; }

    }

    void Desempilha(TipoPilha _Pilha , TipoItem _Item)

    { i f (Vazia(_Pilha ) ) pr int f ( "Erro : pilha esta vazia\n" ) ;

    else { _Item = Pilha−>Item[Pilha−>Topo − 1]; Pilha−>Topo −−; }

    }

    int Tamanho(TipoPilha Pilha)

    { return (Pilha .Topo) ; }

16.  Descreva sobre implementação de Pilhas por Apontadores.
R: Há uma célula cabeça no topo para facilitar a implementação das operações empilha e desempilha quando a pilha está fazia.

17.  Quais os três itens observados para construção de Pilhas com Apontadores?
* O campo tamanho evita a contagem do número de itens na função tamanho.
* Cada célula de uma pilha contém um item da pilha e um apontador para outra célula.
* O Registro TipoPilha contém um apontador para o topo da pilha (célula cabeça) e um apontador para o fundo da pilha.

18. Escreva a estrutura de uma Pilha por meio de Apontadores.

typedef int TipoChave;

     typedef struct {

     int Chave;

     /_ outros componentes _/

     } TipoItem;

     typedef struct TipoCelula _TipoApontador;

     typedef struct TipoCelula {

     TipoItem Item;

     TipoApontador Prox;

     } TipoCelula;

     typedef struct {

     TipoApontador Fundo, Topo;

     int Tamanho;

     } TipoPilha;

19. Escreva as funções utilizadas por Pilha com Apontadores.

void FPVazia(TipoPilha _Pilha)

{ Pilha−>Topo = (TipoApontador ) malloc(sizeof(TipoCelula ) ) ;

Pilha−>Fundo = Pilha−>Topo;

Pilha−>Topo−>Prox = NULL;

Pilha−>Tamanho = 0;

}

int Vazia(TipoPilha Pilha)

{ return (Pilha .Topo == Pilha .Fundo) ; }

void Empilha(TipoItem x , TipoPilha _Pilha)

{ TipoApontador Aux;

Aux = (TipoApontador ) malloc(sizeof(TipoCelula ) ) ;

Pilha−>Topo−>Item = x;

Aux−>Prox = Pilha−>Topo;

Pilha−>Topo = Aux;

Pilha−>Tamanho++;

}

void Desempilha(TipoPilha _Pilha , TipoItem _Item)

{ TipoApontador q;

i f (Vazia(_Pilha ) ) { pr int f ( "Erro : l ista vazia\n" ) ; return; }

q = Pilha−>Topo;

Pilha−>Topo = q−>Prox;

_Item = q−>Prox−>Item;

free(q) ; Pilha−>Tamanho−−;

}

int Tamanho(TipoPilha Pilha)

{ return (Pilha .Tamanho) ; }