GABARITO_Lista6 ESTRUTURA DE DADOS

Prévia do material em texto

Lista 6 – Fila seqüencial 
 
 FILA SEQUENCIAL SIMPLES 
 
 
1) Faça um programa em C++ para apresentar um menu várias vezes, com as seguintes 
opções : 
 MENU 
1- Enfileirar um número inteiro positivo. 
2- Desenfileirar tudo e imprimir apenas os valores que são múltiplos de 5. 
3- Terminar o programa 
 
 Implemente, adequadamente, cada opção fornecida. 
 
Solução : 
 
#include <iostream> 
 
using namespace std; 
 
 
#define TAM 10 
 
//Tipo 
 
struct fila { 
 int v[TAM], 
 inicio, 
 fim; 
 }; 
 
 
 
//Definições das funções 
 
int enfileirar(fila &f, int valor) 
{ 
 
 if (f.fim == TAM - 1) // testa fila cheia - é uma operação 
 { 
 cout << "ERRO : fila cheia." << endl; 
 return 0; // sinaliza fracasso 
 } 
 f.fim++; // ajusta fim 
 f.v[f.fim] = valor; // armazena o valor fim da fila 
 return 1; // sinaliza sucesso 
} 
 
 
 
 
 
 
int desenfileirar(fila &f, int &valor) 
{ 
 
if (f.inicio > f.fim) // testa fila vazia 
{ 
 return 0; // sinaliza fracasso 
} 
valor = f.v[f.inicio]; // retira do início 
f.inicio++; //ajusta o início 
return 1; // sinaliza sucesso 
} 
 
 
//Prog. principal 
int main() 
{ 
 
 fila f; 
 
 int valor, 
 opcao, // opção do menu 
 sinal; 
 
 
 //inicializa a fila f - Note que as inicializações podem também ser feitas dessa forma ! 
 
 f.inicio = 0; 
 f.fim = -1; 
 
do { 
 cout << "\n######################################################### \n\n"; 
 cout << "\t\tMENU" << endl; 
 cout << "1- Enfileirar um número inteiro positivo." << endl 
 << "2- Desenfileirar tudo e imprimir apenas os valores que são multiplos de 5." 
 << endl 
 << "3- Terminar o programa " << endl; 
 cout << "\n\nOPCAO => "; 
 cin >> opcao; 
 cout << "\n######################################################### \n\n"; 
 switch (opcao) 
 { 
 case 1 : cout << "Digite um valor inteiro para ser enfileirado : "; 
 cin >> valor; 
 if (valor > 0) 
 { 
 sinal = enfileirar(f,valor); 
 if (sinal == 0) 
 cout << "Fila cheia" << endl; 
 } 
 else 
 cout << "Valor não foi infileirado, pois nao é inteiro positivo. "; 
 break; 
 
 
 
 case 2 : cout << "Resultado do desenfileiramento : " ; 
 sinal = desenfileirar(f,valor); 
 while (sinal != 0) //enquanto fila não vazia 
 { 
 if (valor % 5 == 0) 
 cout << valor << " "; 
 sinal = desenfileirar(f,valor); 
 } 
 cout << endl; 
 break; 
 
 case 3 : cout << "FIM DO PROGRAMA." << endl; 
 system("pause"); 
 break; 
 
 default : cout << "OPCAO INVALIDA." << endl; 
 
 } // fim do switch 
 
 } while (opcao != 3); 
 
} 
 
 
2) Faça um programa em C++ para ler uma sequência de caracteres (vetor de char) e 
enfileirá-los. Em seguida, desenfileire todos os caracteres e empilhe-os em uma pilha P 
seguindo as orientações: 
 Converta as letras para maiúsculas antes de empilhá-las 
 Qualquer outro caracter, empilhe sem alteração. 
 
Ao final, desempilhe tudo, exibindo o resultado na saída padrão. 
 
 
Solução : 
 
 
#include <iostream> 
 
using namespace std; 
 
 
#define TAM 10 
 
struct fila { 
 char v[TAM]; 
 int inicio, 
 fim; 
 }; 
 
struct pilha { 
 char v[TAM]; 
 int topo; 
 }; 
 
 
 
//Definições das funções 
 
//funções para fila simples 
 
int enfileirar(fila &f, char valor) 
{ 
 // Testa fila cheia - é uma operação - Note que o fim foi inicializado com -1. 
 // Por esta razão, a fila está cheia quando o fim valer TAM-1 
 if (f.fim == TAM - 1) 
 { 
 cout << "ERRO : fila cheia." << endl; 
 system("pause"); 
 return 0; // sinaliza fracasso 
 } 
 //Fila não cheia ... pode enfileirar 
 f.fim++; // ajusta fim 
 f.v[f.fim] = valor; // armazena o valor fim da fila 
 return 1; // sinaliza sucesso 
} 
 
char desenfileirar(fila &f) //testa fila vazia na main 
{ 
 char valor = f.v[f.inicio]; // retira do início 
 f.inicio++; //ajusta o início 
 return valor; // sinaliza sucesso 
} 
 
 
//funções para pilha 
 
void empilhar(pilha &p, char valor) 
{ 
 
 if (p.topo == TAM - 1) // testa pilha cheia 
 { 
 cout << "ERRO: PILHA CHEIA.\n FIM DO PROGRAMA\n\n"; 
 system("pause"); 
 exit(0); 
 } 
 ++p.topo; 
 p.v[p.topo] = valor; 
} 
 
 
char desempilhar(pilha &p) 
{ 
 char valor; 
 
 //trato pilha vazia na main 
 valor = p.v[p.topo]; 
 p.topo--; 
 return(valor); // retorna o valor desempilhado 
} 
 
 
 
 
 
//Prog. principal 
int main() 
{ 
 char entrada[2*TAM], 
 valor; 
 
 pilha p; 
 fila f; 
 
 
 //Inicializa a fila simples - note que esta inicialização é possível ! 
 //Por esta razão, podem ocorrer leves ajustes nas funções de enfileirar e desenfileirar 
 
 f.inicio = 0; 
 f.fim = -1; 
 
 // inicializa a pilha 
 
 p.topo = -1; 
 
 // Lendo a sequência de char 
 
 cout << "Digite uma sequencia de caracteres : "; 
 gets(entrada); 
 for (int i = 0; i < strlen(entrada); i++) 
 enfileirar(f,entrada[i]); 
 
 while (!(f.inicio > f.fim)) //enquanto fila não vazia 
 { 
 valor = desenfileirar(f); 
 
 if (isalpha(valor)) 
 empilhar(p,toupper(valor)); 
 else 
 empilhar(p,valor); 
 } 
 
 cout << "Resultado do desempilhamento : " << endl; 
 while (p.topo != -1) //enquanto pilha não vazia 
 cout << " " << desempilhar(p); 
 
 cout << endl << endl; 
 system("pause"); 
 
} 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 FILA SEQUENCIAL CIRCULAR 
 
 
 
3) Faça um programa em C++ para apresentar um menu várias vezes, com as seguintes 
opções : 
 MENU 
 
1- Enfileirar um valor inteiro não nulo 
2- Desenfileirar um valor, exibindo na tela o seu dobro 
3- Desenfileirar tudo, exibindo os valores desenfileirados sem alterações 
4- Terminar o programa 
 
 Implemente, adequadamente, cada opção fornecida usando funções para enfileirar e 
desenfileirar. 
 
Solução : 
 
 
#include <iostream> 
 
using namespace std; 
 
#define TAM 10 
 
struct fila { 
 int v[TAM], 
 inicio, 
 fim, 
 quantidade; // total de elementos na fila 
}; 
 
 
//Definições das funções 
 
int enfileirar(fila &f, int valor) 
{ 
 
 if (f.quantidade == TAM) // testa fila cheia - é uma operação 
 { 
 return 0; // retorna fracasso 
 } 
 if (f.fim == (TAM - 1)) // se é o último índice do vetor 
 f.fim = 0; 
 else 
 f.fim++; // incrementa o fim 
 f.v[f.fim] = valor; // armazena o valor no fim da fila 
 f.quantidade++; // ajusta a quantidade de dados da fila 
 return 1; 
} 
 
 
 
 
int desenfileirar(fila &f) 
{ 
//testa fila vazia na main 
int valor; 
 
valor = f.v[f.inicio]; // pega o dado do início 
if (f.inicio == (TAM -1)) //se inicio vale o último índice do vetor 
 f.inicio = 0; 
else 
 f.inicio++; //ajusta o início 
 
f.quantidade--; //decrementa a quantidade 
return valor; // sinaliza sucesso 
 
} 
 
 
//Prog. principal 
int main() 
{ 
 int valor, 
 opcao, // opção do menu 
 sinal; 
 
 fila f; //fila circular 
 
 
 //inicializa a fila 
 
 f.inicio= 0; 
 f.fim = -1; 
 f.quantidade = 0; 
 
 
 
 do { 
 cout << "\n#################################################### \n\n"; 
 cout << "\t\tMENU" << endl; 
 cout << "1- Enfileirar um valor inteiro não nulo" << endl 
 << "2- Desenfileirar um valor, exibindo na tela o seu dobro " << endl 
 << "3- Desenfileirar tudo, exibindo os valores desenfileirados em alteracoes." 
 << endl 
 << "4- Terminar o programa" << endl << endl; 
 cout << "OPCAO => "; 
 cin >> opcao; 
 
 
 
 
 
 
 
 
 
 switch (opcao) 
 { 
 case 1 : cout << "Digite um valor inteiro para ser enfileirado : "; 
 cin >> valor; 
 if (valor > 0) 
 { 
 sinal = enfileirar(f,valor); 
 if (sinal == 0) 
 cout << "Fila cheia" << endl; 
 } 
 else 
 cout << "Valor não positivo. "; 
 break; 
 
 
 case 2 : cout << "Resultado ... " << endl; 
 
 if (f.quantidade != 0) 
 { 
 valor = desenfileirar(f); 
 cout << "Dobro do valor desenfileirado = " 
 << 2*valor << endl; 
 } 
 else 
 cout << "Fila vazia."; 
 
 break; 
 
 case 3 : cout << "Resultado do desenfileiramento : " ; 
 while (f.quantidade != 0) //testa fila vazia 
 { 
 valor = desenfileirar(f); 
 cout << valor << " "; 
 } 
 break; 
 
 case 4 : cout << "FIM DO PROGRAMA." << endl; 
 system("pause"); 
 break; 
 
 default : cout << "OPCAO INVALIDA." << endl; 
 
 } // fim do switch 
 
 
 } while (opcao != 4); 
 
} 
 
 
 
4) Faça um programa que leia um vetor de char e enfileire seus dados em duas filas : fila A 
(fila simples – de char ) e fila B (fila circular com contador – de inteiros) da seguinte forma: 
 
 
 Se o caracter for dígito, converta-o para dígito e enfileire-o em B. 
 Se o caracter for letra, enfileire-o em A. 
 Qualquer outro caracter não deverá ser enfileirado. 
 
Ao final, desenfileire as filas B e A, nesta ordem, exibindo os seus dados. 
 
Solução : 
 
 
 
#include <iostream> 
#include <cctype> // para as funções 
#include <string> 
 
using namespace std; 
 
#define TAM 6 
 
struct filaCirc { 
 int v[TAM], 
 inicio, 
 fim, 
 quantidade; // total de elementos na fila 
 }; 
 
struct filaSimples { 
 int v[TAM], 
 inicio, 
 fim; 
 }; 
 
//Definições das funções 
 
//funções para fila circular 
 
int enfileirarCircular(filaCirc &f, int valor) { 
 
 if (f.quantidade == TAM) // testa fila cheia - é uma operação 
 { 
 cout << "ERRO : fila B cheia." << endl; 
 return 0; // sinaliza fracasso 
 } 
 if (f.fim == (TAM - 1)) // se é o último índice do vetor 
 f.fim = 0; 
 else 
 f.fim++; // incrementa o fim 
 f.v[f.fim] = valor; // armazena o valor no fim da fila 
 f.quantidade++; // ajusta a quantidade de dados da fila 
 return 1; 
} 
 
 
 
int desenfileirarCircular(filaCirc &f) { 
int valor; 
 
valor = f.v[f.inicio]; // pega o dado do início 
if (f.inicio == (TAM -1)) //se inicio vale o último índice do vetor 
 f.inicio = 0; 
else 
 f.inicio++; //ajusta o início 
f.quantidade--; //decrementa a quantidade 
return valor; // sinaliza sucesso 
 
} 
 
//funções para fila simples 
int enfileirarSimples(filaSimples &f, char valor) 
{ 
 
 if (f.fim == TAM - 1) // testa fila cheia - é uma operação 
 { 
 cout << "ERRO : fila A cheia." << endl; 
 return 0; //é falso que desenfileirou 
 } 
 f.fim++; // ajusta fim 
 f.v[f.fim] = valor; // armazena o valor fim da fila 
 return 1; //sinaliza sucesso no enfileiramento 
} 
 
char desenfileirarSimples(filaSimples &f) 
{ 
 char valor; 
 //fila vazia é testada na main 
 valor = f.v[f.inicio]; // retira do início 
 f.inicio++; //ajusta o início 
 return valor; // sinaliza sucesso 
} 
 
//Prog. principal 
 
int main() 
{ 
 char entrada[2*TAM], 
 valorA, valor; 
 
 int valorB, sinal; 
 
 filaSimples A; //fila de caracteres 
 filaCirc B; 
 
 
 //inicializa a fila A 
 
 A.inicio = 0; 
 A.fim = -1; 
 
 
 //inicializa fila B 
 
 B.inicio = 0; 
 B.quantidade = 0; 
 B.fim = -1; 
 
 cout << "Digite uma sequencia de char : "; 
 gets(entrada); 
 
 cout << "\nEnfileirando ... " << endl; 
 for (int i = 0; entrada[i] != '\0' ; i++) 
 { 
 valor = entrada[i]; 
 if (isdigit(valor)) 
 { 
 sinal = enfileirarCircular(B,valor-48); 
 if (sinal == 0) 
 cout << "Fracasso do enfileiramento do numero " << valor << endl; 
 } 
 else 
 if (isalpha(valor)) 
 { 
 sinal = enfileirarSimples(A,valor); 
 if (sinal == 0) 
 cout << "Fracasso do enfileiramento do caracter " << valor << endl; 
 } 
 } 
 
 cout << "\n\nDesenfileirando ... " << endl << endl; 
 cout << "\nDesenfileirando fila B .... " << endl; 
 while (B.quantidade != 0) { 
 valorB = desenfileirarCircular(B); 
 cout << valorB << " "; 
 } 
 
 cout << "\nDesenfileirando ... fila A .... " << endl; 
 while (!(A.inicio > A.fim)) 
 { 
 valorA = desenfileirarSimples(A); 
 cout << valorA << " "; 
 } 
 
 cout << endl << endl; 
 system("pause"); 
 
 
}