Baixe o app para aproveitar ainda mais
Prévia do material em texto
Laboratório de Programação II Departamento de Ciência da Computação UFJF Aula de hoje • TAD Pilha – Pilha com Lista Encadeada • TAD Fila – Fila com Lista Encadeada • Pilha é uma lista onde todas as inclusões e exclusões de nós são feitas em uma única extremidade. • Usa-se o critério de retirar em primeiro lugar o último nó que foi incluído na lista. • FILO (First In Last Out) Pilhas 3 Fila • Fila é uma lista onde todas as inclusões são feitas em uma extremidade e todas as exclusões na outra extremidade. • Usa-se o critério de retirar em primeiro lugar o primeiro nó incluído na lista. • Este critério é chamado de FIFO (First In First Out). • Esta estrutura é equivalente a uma fila de banco. Pilha e Fila • Vamos trabalhar com representações de Pilha e Fila com encadeamento dos nós. • O TAD Nó já foi apresentado para listas encadeadas, mas vamos revisa-lo. class No { private: float info; No* prox; public: No(); ~No(); void atribInfo(float val); void atribProx(No* p); float consultaInfo(); No * consultaProx(); }; No::No() { } void No::atribInfo(float val) { info = val; } void No::atribProx(No* p) { prox = p; } float No::consultaInfo() { return info; } No* No::consultaProx() { return prox; } No::~No() { } Pilha Encadeada class PilhaEncadeada { private: No* topo; // ponteiro p/ o No do topo public: PilhaEncadeada(); ~PilhaEncadeada(); float consultaTopo(); void empilha(float val); // insere No no Topo void desempilha(); // elimina No do Topo bool vazia(); // verifica se está vazia }; Xn Xn – 1 X2 X1 topo Pilha Encadeada // construtor PilhaEncadeada::PilhaEncadeada() { topo = NULL; } // destrutor PilhaEncadeada::~PilhaEncadeada() { No* p = topo; while(topo != NULL) { topo = p->consultaProx(); delete p; p = topo; } } Pilha Encadeada void PilhaEncadeada::empilha(float val){ No* p = new No(); p->atribInfo(val); p->atribProx(topo); topo = p; } void PilhaEncadeada::desempilha(){ No* p; if(topo != NULL) { p = topo; topo = p->consultaProx(); delete p; } else { cout << “Erro” << endl; exit(1); } } Pilha Encadeada float PilhaEncadeada::consultaTopo() { if(topo != NULL) return topo->consultaInfo(); else { cout << “Pilha vazia!“ << endl; exit(1); } } bool PilhaEncadeada::vazia() { if(topo == NULL) return(true); else return(false); } Fila Encadeada class FilaEncadeada { private: No *ini, *fim; // ponteiros para os No’s extremos public: FilaEncadeada(); ~FilaEncadeada(); float consultaInicio(); void entra(float val); // insere No no fim void sai(); // elimina No do início da fila bool vazia(); // verifica se fila está vazia }; Fila Encadeada FilaEncadeada::FilaEncadeada() { ini = NULL; fim = NULL; } FilaEncadeada::~FilaEncadeada() { No* p = ini; while(ini != NULL) { ini = p->consultaProx(); delete p; p = ini; } fim = NULL; } bool FilaEncadeada::vazia() { if(ini == NULL) return true; else return false; } Fila Encadeada void FilaEncadeada::entra(float val){ No* p = new No(); p->atribInfo(val); p->atribProx(NULL); if(fim == NULL) ini = p; else fim->atribProx(p); fim = p; } float FilaEncadeada::consultaInicio(){ if(ini != NULL) return ini->consultaInfo(); else { cout << “Fila vazia!“ << endl; exit(1); } } Fila Encadeada void FilaEncadeada::sai() { No* p; if(ini != NULL){ p = ini; ini = p->consultaProx(); if(ini == NULL) fim = NULL; delete p; } else { cout << “Fila vazia” << endl; exit(1); } } Exercícios 1. Desenvolver a operação, tanto para o TAD Pilha quanto para o TAD Fila, Imprimir(). Esta operação deve mostrar os elementos da pilha do topo para o final e do início para fim da fila. Exercícios 2. Modifique o TAD Pilha Encadeada de forma que este guarde o número de itens que estão na Pilha. Implemente uma operação tamanho() que retorna quantos itens possuem na pilha. 3. Implementar uma função Inverte() que, dado um vetor V com n números reais, cria e retorna um novo vetor com os elementos de V na ordem inversa. Utilizar uma pilha para realizar esta inversão. A função Inverte() não deve ser uma operação do TAD PilhaEncadeada. Exercícios 4. Considere uma pilha P vazia e uma fila F não vazia. Utilizando as operações de fila (vazia, entra e sai) e pilha (vazia, empilha e desempilha), e uma variável auxiliar do tipo float, escreva uma função que inverta a ordem dos elementos da fila. Exercícios 5. Desenvolver uma função (não uma operação) para, dadas duas filas F1 e F2, criar e retornar uma nova fila que representa a concatenação destas duas filas (sem repetição de valores). Considere que as filas F1 e F2 não possuem valores repetidos e tanto F1 quanto F2 tornam-se vazias após a concatenação. Obs: Deve-se implementar uma operação lógica para verificar se um valor não se encontra na fila antes de adicioná-lo à esta fila. Exercícios 6. Utilizando as operações de manipulação de pilhas (vazia, empilha, desempilha) , uma pilha auxiliar Paux e uma variável do tipo float, escrever uma função para remover um item com valor C de uma posição qualquer da pilha. Exemplo: Pilha (9, 2, 5, 6, 1) Topo = 9 Remove(5) Saída: Pilha (9, 2, 6, 1) Topo = 9 Exercícios 7. Escreva um programa para converter um número de notação decimal em um número expresso em um sistema de número cuja base (ou raiz) é um número entre 2 e 9. A conversão é realizada pela divisão repetitiva, pela base, à qual um número está sendo convertido, e então tomando-se os restos da divisão na ordem inversa. Por exemplo, para converter para binário, o número 6 exige três de tais divisões: 6/2 = 3 com resto 0, 3/2=1 com resto 1 e, finalmente, 1/2 = 0 com resto 1. Os restos 0, 1 e 1 são colocados na ordem inversa, de modo que o binário equivalente de 610 é igual a 110 na base 2. Exercícios 8. Usando obrigatoriamente uma estrutura de pilha, implemente uma função que verifica se um dado vetor de N inteiros é um palíndromo, ou seja, se ele é o mesmo quando lido da esquerda para a direita ou da direita para a esquerda. Exemplo: {1,2,3,4,5,4,3,2,1} é palíndromo, {1,2,3,6,7,8} não é palíndromo. Exercícios 9. Faça um programa para verificar se uma expressão aritmética está com o número de parênteses corretamente balanceado, ou seja, para cada parêntese aberto deve existir um parêntese fechado. Exemplo: (3+(4*3)/2)+1 está ok, mas (((3 * 4)+ 2) não está!
Compartilhar