GABARITO_Lista4 ESTRUTURA DE DADOS

Prévia do material em texto

Lista 4 - Lista Sequencial 
 
 
1) Considere um programa para manipular fichas de alunos, sendo que cada ficha 
possui nome, matricula e media. Faça um programa em C++, usando struct, que 
ofereça, repetidamente, um menu de opções para : 
 
1- Inserir ficha 
2 –Remover ficha 
3 – Imprimir fichas 
4 – Ordenar fichas 
5 – Terminar o programa 
 
Ao ser escolhida uma opção, deverá ser executada uma função para realizar a tarefa 
desejada. Para a opção 4, deverá ser realizada a ordenação pela matrícula do aluno. 
 
Solução : 
 
#include <iostream> 
#include <string> 
 
using namespace std; 
 
// Definindo constante com define 
 
#define TAM 5 
 
// Definindo um novo tipo com struct 
// struct possibilita agregar dados de tipos diferentes (ou até de tipos iguais). 
 
 
struct ficha { 
 char nome[40]; 
 int mat; 
 float media; 
 }; 
 
// Protótipos ou declarações das funções 
 
void imprimirFichas(ficha v[], int quant); 
int removerFicha(ficha v[], int matricula, int quant); //trabalha com lista não ordenada 
int inserirFicha(ficha v[], ficha f, int quant); //trabalha com lista não ordenada 
int buscaSequencial(ficha v[], int mat, int quant); //trabalha com lista não ordenada 
void ordenaSelecao(ficha v[], int quant); 
 
 
 
 
 
 
 
 
// Programa principal 
 
int main() 
{ 
 ficha v[TAM]; //declara um vetor v com capacidade para TAM elementos do tipo ficha 
 ficha f; //declara f uma variável do tipo ficha 
 
 int quant, matricula, opcao; 
 
 
 quant = 0; // inicializa a quantidade de fichas da lista de fichas 
 
 for ( ; ; ) 
 { 
 cout << "\n\n\tMENU\n\n"; 
 cout << " 1 - Inserir ficha \n"; 
 cout << " 2 - Remover ficha\n"; 
 cout << " 3 - Imprimir fichas\n"; 
 cout << " 4 - Ordenar - ordenacao por selecao \n"; 
 cout << " 5 - Terminar o programa\n"; 
 cout << "\n\n OPCAO => "; 
 cin >> opcao; 
 
 cout << "\n\n"; 
 switch (opcao) 
 { 
 case 1 : 
 cout << "Matricula ? "; 
 cin >> f.mat; 
 cout << "Media ? "; 
 cin >> f.media; 
 
 getchar(); //limpa o buffer, para possibilitar a entrada do vetor de char 
 
 cout << "Nome ? "; 
 gets(f.nome); //gets pega o nome e o sobrenome - usar para vetor de char 
 quant = inserirFicha(v,f,quant); //insere uma ficha f em v 
 break; 
 
 
 case 2 : cout << "Matricula da ficha para remocao ? "; 
 cin >> matricula; 
 
 quant = removerFicha(v,matricula,quant); //remove de v uma ficha 
 break; 
 
 
 case 3 : 
 imprimirFichas(v,quant); //percorre o vetor de fichas, imprimindo seus dados. 
 break; 
 
 
 case 4 : cout << "Ordenando o vetor v por selecao : " << endl; 
 ordenaSelecao(v,quant); 
 break; 
 
 case 5 : cout << "Terminando o programa ..."; 
 exit(0); //Termina o programa, não importa de onde seja chamada. 
 
 default : cout << "Opcao invalida"; 
 
 } // fim switch 
 
 
 } // fim for 
 
 return 0; 
} 
 
 
// Definição das funções 
 
 
 void imprimirFichas(ficha v[], int quant) 
{ 
 cout << "\nFICHAS : \n"; 
 
 for (int i = 0; i < quant; i++) 
 cout << "\n\nNome : " << v[i].nome << " Media : " << v[i].media 
 << " Matricula : " << v[i].mat << endl; 
} 
 
 
int inserirFicha(ficha v[], ficha f, int quant) 
{ 
 if (quant == TAM) //Testa se lista está cheia 
 cout << "\nCadastro cheio !"; 
 else 
 { 
 strcpy(v[quant].nome, f.nome); //copia f.nome para v[quant].nome . 
 v[quant].media = f.media; 
 v[quant].mat = f.mat; 
 
 quant++; 
 } 
 return quant; 
} 
 
 
 
 
 
 
 
int removerFicha(ficha v[], int matricula, int quant) 
{ 
 int posicao; 
 
 if (quant == 0) 
 cout << "Cadastro vazio"; 
 else 
 { 
 posicao = buscaSequencial(v,matricula,quant); //chama a função buscaSequencial 
 if (posicao >= 0) // testa se elemento existe 
 { 
 quant--; 
 v[posicao] = v[quant]; 
 } 
 else 
 cout << "ERRO: Matricula não encontrada"; 
 } 
 return quant; 
 
} 
 
 
int buscaSequencial(ficha v[], int mat, int quant) 
{ 
 //Deve retornar o índice (sucesso) ou -1 (fracasso) 
 
 for (int i = 0; i < quant;i++) 
 if (v[i].mat == mat) //se a matrícula mat do campo mat de v[i] é igual ao mat passado 
 return i; // achou e retorna o índice da ficha v[i] 
 
 //fora do for : 
 
 return -1; // não achou - retorna valor que é impossível como índice 
 
} 
 
 
 
void troca(ficha v[],int i, int j) //função para auxiliar na ordenaSelecao 
{ 
 ficha aux; 
 
 aux = v[i]; 
 v[i] = v[j]; 
 v[j] = aux; 
 
} 
 
 
 
 
 
void ordenaSelecao(ficha v[ ], int n) // n é o número de elementos em v 
{ 
 int i, j, menor; 
 
 for (j = 0; j < n-1; j++) 
 { 
 menor = j; 
 for (i = j+1; i < n; i++) 
 if (v[i].mat < v[menor].mat) 
 menor = i; 
 troca(v,j,menor); 
 } 
} 
 
 
 
 
 2) Escreva um programa em C++ que leia os dados de clientes de uma livraria 
(nome, código de identificação, tipo de leitura preferido (por exemplo: R – romance, F – 
ficção E – esoterismo O - outros) e telefone), inserindo-os, em ordem crescente pelo 
código, em um vetor de nome cadastro. Após a criação da lista, seu programa deverá 
solicitar opções de um menu (via teclado) que podem ser: 
 
 P (pesquisar) : Ler uma identificação e buscar o cliente (usar busca binária); 
 I (inserir) : Inserir um novo cliente de forma ordenada 
 R (retirar) : Retirar um cliente, mantendo a ordem 
 
Comentário : A cada conjunto de dados lidos de um cliente, chame na main, a função 
que faz a inserção de um cliente. Tal função também será chamada, quando selecionada 
a opção I do menu. 
 
Solução : 
 
#include <iostream> 
#include <string> 
 
using namespace std; 
 
// Definindo constante com define 
 
#define TAM 50 
 
// Definindo um novo tipo com struct 
// struct possibilita agregar dados de tipos diferentes (ou até de tipos iguais). 
 
struct ficha { 
 char nome[40], 
 telefone[14], 
 tipoLeitura;//Pode ser R ou F ou O ... 
 int codigo; 
 }; 
 
 
// Protótipos ou declarações das funções 
 
void imprimirFichas(ficha v[], int quant); 
bool removerOrdenada(ficha v[], int cod, int &quant); //trabalha com lista ordenada - 
quant é passsada por referência - Veja o & 
bool inserirOrdenada(ficha v[], ficha f, int &quant); //trabalha com lista ordenada - 
quant é passada por referência 
int buscaBinaria(ficha v[], int mat, int quant); //trabalha com lista ordenada 
 
 
 
// Programa principal 
 
int main() 
{ 
 ficha cadastro[TAM]; //declara umvetor cadastro 
 ficha f; //declara f uma variável do tipo ficha 
 
 int quant, //quantidade de fichas no cadastro 
 sinal, //sinaliza sucesso ou fracasso na inserção ou remoção 
 codigo, 
 posicao, 
 conta; 
 
 char opcao; //opção do menu - pode ser I, M, R ... 
 
 
 //NOTE: O \t equivale ao TAB 
 cout << "\t\tCADASTRO DE CLIENTES DE UMA LIVRARIA. " << endl << endl; 
 cout << "Digite a quantidade inicial de clientes (no maximo " << TAM << " clientes ): " ; 
 cin >> quant; 
 if (quant == TAM) 
 cout << "ERRO : Lista cheia. " << endl; 
 else 
 { 
 conta = 0; 
 while(conta < quant) 
 { 
 cout << "Matricula ? "; 
 cin >> f.codigo; 
 cin.get(); //limpa o enter 
 cout << "Nome ? "; 
 cin.getline(f.nome,40); 
 cout << "Escolha o tipo de leitura (R - romance F - ficcao E - esoterismo O - outros) : "; 
 cin >> f.tipoLeitura; 
 cin.get(); // limpa o enter 
 cout << "Telefone ? "; 
 cin.getline(f.telefone,14); 
 sinal = inserirOrdenada(cadastro,f,conta); //conta é incrementado dentro da função 
 
 
 if (sinal == false) // Não se tem garantia de que o usuário digitará corretamente até TAM 
 { 
 cout << "ERRO : cadastro cheio. "; 
 break; //sai do loop 
 } 
 } 
 } 
 
 
 imprimirFichas(cadastro,quant); //Há quant fichas no vetor cadastro 
 
 system("pause"); 
 system("cls"); 
 
 for ( ; ; ) 
 { 
 cout << "\n\n\tMENU\n\n"; 
 cout << " P - Pesquisar ficha \n"; 
 cout << " I - Inserir ficha \n"; 
 cout << " R - Remover ficha \n"; 
 cout << " M - Mostrar os dados do cadastro. \n"; 
 cout << " T - Terminar o programa\n"; 
 cout << "\n\n OPCAO => "; 
 cin >> opcao; 
 cout << "\n\n"; 
 switch (opcao) 
 { 
 case 'p' : 
 case 'P' : 
 cout << "Codigo para busca ? "; 
 cin >> codigo; 
 
 posicao = buscaBinaria(cadastro,codigo,quant); 
 if (posicao < 0) 
 cout << codigo << " nao encontrado. Portanto, cliente inexistente. " << endl; 
 else 
 cout << "Cliente de codigo " << codigo << " encontrado. " << endl; 
 
 break; 
 
 case 'i' : 
 case 'I' : 
 cout << "Matricula ? "; 
 cin >> f.codigo; //Note que não estou checando se codigo é nulo, etc... 
 cin.get(); 
 cout << "Nome ? "; 
 cin.getline(f.nome,40); 
 cout << "Escolha o tipo de leitura ... R - romance, F - ficcao E - esoterismo 
O - outros : "; 
 cin >> f.tipoLeitura; 
 cin.get(); 
 
 cout << "Telefone ? "; 
 cin.getline(f.telefone,14); 
 if (quant == TAM) 
 cout << "ERRO : Lista cheia. " << endl; 
 else 
 { 
 sinal = inserirOrdenada(cadastro,f,quant); 
 if (sinal == false) 
 cout << "ERRO : Cliente ja existente. " << endl; 
 } 
 break; 
 
 case 'r' : 
 case 'R' : cout << "Digite o codigo do cliente para remocao ? "; 
 cin >> codigo; 
 sinal = removerOrdenada(cadastro, codigo,quant); 
 if (sinal == false) 
 cout << "ERRO : Fracasso na remocao. " << codigo << endl; 
 break; 
 
 case 'm' : 
 case 'M' : imprimirFichas(cadastro,quant); //percorre o vetor de fichas 
 break; 
 
 case 't' : 
 case 'T' : cout << "Terminando o programa ..." << endl; 
 system("pause"); 
 exit(0); //Termina o programa, não importa de onde seja chamada. 
 
 default : cout << "Opcao invalida"; 
 } // fim switch 
 
 
 } // fim for 
 
 return 0; 
} 
 
 
// Definição das funções 
 
//Esta função imprime apenas o nome e o código. Você pode mandar que sejam 
impressas outros dados dos clientes. 
void imprimirFichas(ficha v[], int quant) 
{ 
 cout << "\nCadastro ordenado pelo codigo : \n"; 
 for (int i = 0; i < quant; i++) 
 cout << "\n\nNome : " << v[i].nome << " - Codigo: " << v[i].codigo << endl; 
} 
 
 
 
bool inserirOrdenada(ficha v[], ficha f, int &quant) //quant é passada por referência. 
{ 
 int posicao; 
 
 posicao = buscaBinaria(v,f.codigo,quant); 
 if (posicao >= 0) 
 return false; // nao vai inserir uma ficha de mesmo codigo 
 int i = 0; 
 while (f.codigo > v[i].codigo && i < quant) 
 i++; 
 posicao = i; // armazena a posição onde o valor deverá ser armazenado 
 // Desloca os elementos, mantendo a ordem 
 for (i = quant; i > posicao; i--) 
 v[i] = v[i-1]; 
 // Insere na posição correta 
 v[posicao] = f; 
 // Incrementa a quantidade de nós na lista 
 quant++; 
 return true; // sucesso na inserção 
 
 
} 
 
 
bool removerOrdenada(ficha v[], int codigo, int &quant) 
{ 
 int posicao; 
 
 if (quant == 0) 
 return false; //fracassou a remoção 
 else 
 { 
 posicao = buscaBinaria(v,codigo,quant); //chama a função buscaBinaria 
 if (posicao >= 0) // testa se elemento existe, ou seja, se está em alguma posição possível 
 { 
 quant--; //decrementa a quantidade de fichas no cadastro 
 for (int i = posicao; i < quant; i++) //Copia, deslocando os elementos 
 v[i] = v[i+1]; 
 
 } 
 else 
 { 
 return false; 
 } 
 } 
 
} 
 
 
 
 
 
int buscaBinaria(ficha v[], int cod, int quant) 
{ 
 int ini = 0, 
 fim = quant-1, 
 meio; 
 
 while (ini <= fim) 
 { 
 meio = (ini+fim)/2; 
 if (v[meio].codigo == cod) 
 return meio; //retorna o índice do elemento que está no meio 
 if (cod < v[meio].codigo) 
 fim = meio -1; 
 else 
 ini = meio + 1; 
 } 
 return -1; //sinaliza que não achou o elementos 
 
}