GABARITO_Lista8 ESTRUTURA DE DADOS

Prévia do material em texto

Lista 8 - Pilha e Fila dinâmicas 
 
 
 
Para as questões 1 e 2, considere o tipo : 
 
struct no { 
 int dado; 
 struct no *link; 
}; 
 
Pilha 
 
1) Faça um programa em C++ com listas simplesmente encadeadas de inteiros, em 
que seja solicitada uma quantidade n de nós para a lista. Note que n deve ser um 
número maior ou igual a zero. 
 
 Após esta entrada, faça o que se pede: 
 
a) Empilhe n números inteiros positivos. 
 
 Protótipo da função : no* empilhar(no *, int ); 
 Parâmetros : Ponteiro para o início da lista e o valor inteiro a ser inserido 
 Retorno : Ponteiro para o início da lista (topo da pilha) 
 
 
b) Desempilhe todos os elementos, imprimindo apenas os valores pares. 
 
 
 Protótipo da função : int desempilhar(no * &); //Atenção !!!! 
 Parâmetros : Ponteiro para o início da lista 
 Retorno : o número inteiro desempilhado 
 
Solução : 
 
#include <iostream> 
 
using namespace std; 
 
//Tipo 
struct no { 
 int dado; 
 struct no *link; 
 }; 
 
//Protótipos 
 
no* empilhar(no *, int ); 
 
int desempilhar(no * &); 
 
 
void imprimir(no *); 
 
//Prog. principal 
int main() 
{ 
 no *primeiro = NULL; //declara o ponteiro e inicializa a pilha 
 
 int n, valor, cont; 
 
 do { 
 cout << "Informe a quantidade de nos (>= 0) : "; 
 cin >> n; 
 if (n < 0) 
 cout << "ERRO : quantidade invalida de nos." << endl; 
 }while (n < 0); 
 
 
 //Loop que cria a lista com n nós. 
 
 cont = 0; 
 while (cont < n) 
 { 
 cout << "Digite um valor para inserir na frente da lista (EMPILHAR): "; 
 cin >> valor; 
 if (valor > 0) 
 { 
 cont++; //conta mais um valor a ser empilhado 
 primeiro = empilhar(primeiro, valor); //faz uma inserção na frente da lista 
 } 
 } 
 
 //Chamei a função imprimir, apenas para lhes mostrar que a lista está OK ! 
 cout << "\nLista apos os empilhamentos : " << endl; 
 imprimir(primeiro); 
 
 cout << endl; 
 cout << "Desempilhando tudo e exibindo apenas os valores pares. " << endl; 
 while (primeiro != NULL) //enquanto pilha não vazia 
 { 
 valor = desempilhar(primeiro); 
 if (valor % 2 == 0) 
 cout << " " << valor; 
 } 
 
 cout <<endl << endl; 
 
 system("pause"); 
} 
 
 
 
 
//Definições das funções 
 
no *empilhar(no *p, int valor) 
{ 
 no *q; //Variável local 
 
 q = new no; // aloca dinamicamente memória para um nó 
 q->dado = valor; // Note o operador seta 
 q->link = p; 
 return q; 
 
} 
 
void imprimir(no *p) 
{ 
 while (p != NULL) 
 { 
 cout << " " << p->dado; 
 p = p->link; 
 } 
} 
 
 
int desempilhar(no * &p) //VEja o & que indica passagem por referência 
{ 
 no *aux; 
 int valor; 
 
 aux = p; 
 p = p->link; 
 valor = aux->dado; 
 delete aux; //LIBERA A ÁREA DE MEMÓRIA APONTADA POR aux 
 return valor; 
} 
 
 
Fila 
 
2) Faça um programa em C++ para criar uma fila dinâmica de inteiros positivos, 
através de sucessivas inserções ou enfileiramentos. Ao ser digitado um valor 
negativo ou nulo, a criação da fila deverá ser encerrada. Não esqueça de tratar fila 
vazia. 
 
 Após a criação da fila, faça o que se pede : 
 
a) Imprima na tela os dados da fila. 
b) Desenfileire um valor, apresentando-o na tela, após a mensagem “Elemento 
desenfileirado “. 
c) Conte o número de dados da fila. 
d) Desenfileire tudo, apresentando na tela apenas os dados ímpares. 
 
 
Solução : 
 
#include <iostream> 
 
using namespace std; 
 
//tipo 
struct no { 
 int dado; 
 struct no *link; 
 }; 
 
//protótipos 
 
void enfileirar(no * &, no * &, int); 
 
int desenfileirar(no * &, no * &); //considerando fila não vazia 
 
void imprimir(no *); 
 
int contarNos(no *); 
 
 
//prog. principal 
 
int main() 
{ 
 int valor; 
 no *inicio, *fim; 
 
 //a) 
 
 inicio = fim = NULL; //inicializa a fila 
 
 cout << "\t\tCriando uma fila de inteiros positivos" 
 << endl << endl; 
 for ( ; ; ) 
 { 
 cout << "Digite um valor positivo : "; 
 cin >> valor; 
 if (valor <= 0) 
 break; 
 
 enfileirar(inicio,fim,valor); 
 
 } 
 
 //b) 
 
 cout << "\nFila de inteiros positivos : "; 
 imprimir(inicio); 
 
 
 //c) 
 
 if (inicio != NULL) 
 cout << "\nElemento desenfileirado : " 
 << desenfileirar(inicio,fim); 
 else 
 cout << "\nFila vazia. " << endl; 
 
 //d) 
 
 cout << "\nQuantidade de nos apos uma retirada da fila : " 
 << contarNos(inicio); 
 
 cout << endl << endl; 
 
} 
 
//Definições das funções 
 
 
void enfileirar(no * &i, no * &f, int valor) 
{ 
 no *novoNo; 
 
 novoNo = new no; 
 novoNo->dado = valor; 
 novoNo->link = NULL; 
 if (i == NULL) //fila vazia 
 i = f = novoNo; 
 else 
 { 
 f->link = novoNo; 
 f = novoNo; 
 } 
 
} 
 
 
//Esta função só deverá ser chamada para fila não vazia 
int desenfileirar(no * &i, no * &f) 
{ 
 no *aux; 
 int valor; 
 
 valor = i->dado; 
 aux = i; 
 i = i->link; 
 if (i == NULL) 
 f = NULL; 
 delete aux; 
 return valor; 
} 
 
 
 
void imprimir(no *p) 
{ 
 while (p != NULL) 
 { 
 cout << " " << p->dado; 
 p = p->link; 
 } 
} 
 
 
 
int contarNos(no *p) 
{ 
 int contador; 
 
 contador = 0; 
 while (p != NULL) 
 { 
 contador++; 
 p = p->link; 
 } 
 return contador; 
}