Baixe o app para aproveitar ainda mais
Prévia do material em texto
Sistemas de Informação FACET - Faculdade de Ciências Exatas TP2 Mauricio Santana Bispo Giullison Ramos Vinícius Ribeiro Willian Dias Atividade apresentada como forma de avaliação parcial para a disciplina Programação Orientada à Objetos. Prof. Alexaandre Ramos Fonseca Diamantina – MG Maio - 2015 Programação Orientada à Objetos – COM016 Trabalho Prático II – 2015/1 Introdução O trabalho prático apresentado tem como objetivo, o treinamento do uso de estruturas básicas das linguagens C e C++ que são consideradas pré- requisito para o nosso curso. Uma primeira utilização de classes pré-definidas pela linguagem, como, por exemplo, string, ifstream e vector. A criação de classes simples e sua programação em C++, incluindo a criação de construtores, destrutores, funções sobrecarregadas, constantes, alocação dinâmica de memória, etc. Questão 1 Descrição 1 A primeira questão do trabalho pede para que, o usuário insira o nome do arquivo e um padrão a ser procurado dentro dele. O programa deverá abrir o arquivo, contar e imprimir na saída padrão o número de vezes que a string fornecida ocorre no arquivo. Implementação Primeiramente foi definida uma classe e todo o cabeçalho do programa. Tp2.h: Class Tp2 – Classe principal do programa, para melhor compreender as implementações da programação orientada a objetos, foi definida essa classe. Public: - As definições públicas que podem ser acessadas por todos. Std::string texto – String que irá receber o conteúdo do arquivo. int arq(std::string padrao) – Método da classe que abre e verifica a ocorrência de casamento de padrões. Esse método recebe como parâmetro, uma string, que será o padrão a ser procurado. No tp2.cpp, é definido todo o código funcional das declarações feitas na classe Tp2. ifstream arq1(nome.c_str()) – Ifstream método da fstream padrão da linguagem, faz a abertura do arquivo, de forma padrão ela abre o arquivo em modo de leitura. Ifstream requer uma constante char*, por tanto se chama a função c_str() em cima da string passada para fazer a conversão. while(arq1 >> s) – O argumento chefe nessa condição, é o operador de fluxo, que encontra um espaço ou salto de linha e vai retornando a string. if(s == padrao) – Essa condição, é a condição que verifica o casamento entre o padrão informado pelo usuário e a string no arquivo. count++ - Variável de contagem, onde, se houve casamento de padrão, então count recebe mais 1. arq1.close() – Método da biblioteca fstream que, faz o fechamento do arquivo. Análise de Complexidade Eficiência temporal -> operação realizada mais vezes é o teste da condição de continuidade do ciclo while, que é dependente do tamanho do arquivo, ou seja, n. Logo, T(n) = O(n) -> (Linear) Eficiência espacial -> O gasto de memória, será relativo ao tamanho do arquivo passado, também n. Logo, S(n) = O(n) -> (Linear). Questão 2 Descrição 2 A segunda questão do trabalho pede para que, o usuário insira o nome do arquivo e um padrão a ser procurado dentro dele. O arquivo deverá ser lido e cada palavra nele contido deverá ser armazenada em um vector<string> vet. Percorra o vetor, mostrando todas as palavras lidas na saída padrão. Isto feito, ordene as palavras, utilizando o algoritmo genérico sort() : #include <algorithm> sort(vet.begin(),vet.end()); Imprima as palavras em ordem alfabética na saída padrão. Implementação Obs: A construção do programa 2, foi feita em cima do programa 1, visto que contem as mesmas funcionalidades, com adição apenas da estrutura vector, e uma função de ordenação e impressão da string vector. Tp2.h std::vector<std::string> palavras – Define uma variável (Objeto) vector do C++, essa variável vai receber todas as strings contidas no arquivo do usuário. Tp2.cpp palavras.push_back(s) – O método push_back(), insere o elemento passado ao final do vetor. No caso estará jogando cada string passada a s, para o vector palavras. void Tp2::pl() – Método que ordena [sort()] as strings presentes no vector palavras, além de imprimir todos os elementos do vector. Análise de Complexidade Eficiência temporal -> operação realizada mais vezes é o teste da condição de continuidade do ciclo while, que é dependente do tamanho do arquivo, ou seja, n. Logo, T(n) = O(n) -> (Linear) Eficiência espacial -> O gasto de memória, será relativo ao tamanho do arquivo passado, também n. Logo, S(n) = O(n) -> (Linear). Apesar de a complexidade ser a mesma do primeiro, o segundo usa apenas uma operação de inserção e não faz a comparação, mas tem a impressão de n repetições. Lista Simplesmente Encadeada (Questão 3) Descrição ³ A proposta da terceira questão do trabalho é a criação e implementação de uma lista simplesmente encadeada, onde o usuário tenha a opção de inserir, pesquisar, remover e exportar os dados armazenados na lista, que nesse caso seriam inteiros. O programa deverá imprimir uma interface simples que ofereça opções para todas as alternativas apontadas acima, pedir uma opção de entrada de dados, criar a lista e caso o usuário queira exportar os dados armazenados na lista, seja em impressão na tela ou gravação em um arquivo. Implementação A primeira etapa foi a criação da classe lista declarada dentro do header lista_simples.h, onde também foram definidos todos os métodos da classe. lista_simples.h: Class lista – Classe principal do programa, definida para abranger toda a manutenção da lista. Public: - As definições públicas que podem ser acessadas por todos. lista ( ) – Construtor da classe. Inicializa a lista setando o ponteiro inicial e final para zero (nesse momento a lista está criada mas não tem nenhum nó) e atribuindo valor zero ao contador de nós ~lista ( ) – Destrutor da classe. Deleta todos os nós da lista com suporte de um ponteiro que pecorre toda a estrutura removendo nó-a-nó. void leitura (istream& ) – Método que obtem os dados a serem inseridos na lista. A função pode receber um ‘cin’ que lê dados do teclado, como pode receber um arquivo como parametro, e usá-lo para ler os dados a serem inseridos na lista. Ou seja, quando o método é chamado, recebe o inteiro de alguma das fontes citadas acima e passa esse inteiro para o método insere, que é chamado dentro de leitura ainda. void insere (int) – Método que cria o primeiro nó da lista caso ela esteja vazia, ou adiciona outro nó caso a lista já tenha algum nó. Dentro do método temos diversos casos de inserção, visto que a inserção dos inteiros já é feita ordenada (em ordem crescente). A inserção Recebe o inteiro a ser inserido como parâmetro, e retorna void. bool verifica (int) – Método da classe que abre a lista e verifica a ocorrência do inteiro recebido como parâmetro na lista. Esse método faz parte do processo de inserção e de remoção (que será apresentado a seguir), visto que a inserção não pode permitir que um inteiro não pode ser inserido duas vezes na lista. void remove (int) – Método que efetua a remoção do inteiro (recebido como parâmetro) da lista. Antes de tentar remover, chamamos o método verifica para saber se o inteiro esta na lista, caso não esteja, imprimimos um alerta e retornamos. Caso o inteiro esteja na lista vamos procura-lo e executar a remoção. Temos diversos casos para remoção, já que o processo é diferente para determinadas ‘posições’ do inteiro na lista. void exporta (ostream& ) – Método que exporta a listaarmazenada ao decorrer da execução do programa. Recebe como parâmetro um arquivo ou apenas um ‘cout’. Se receber um ‘cout’ imprime a lista na tela, e se recebe um arquivo a função grava a lista no arquivo, e fecha o mesmo. Private: - As definições privadas que não podem ser acessadas por todos. struct no { } – Definição da estrutura de cada nó da lista. Dentro da estrutura, declaramos: int valor: Variável que irá armazenar o inteiro inserido. no* prox: Ponteiro que irá apontar para o nó que armazena o inteiro sucessor. Dessa forma, todos os nós terão uma ligação com um próximo nó, com exceção apenas do nó final, o qual o ponteiro prox irá apontar para nada (0). no* inicial – Ponteiro que vamos usar para apontar o primeiro nó da lista. no* final – Ponteiro que vamos usar para apontar o último nó da lista. int qt – Inteiro contador para armazenar o numero de nós da estrutura. main.cpp: O main.cpp é onde vamos imprimir o menu do programa e obter a escolha do usuário para chamar cada caso encima do objeto declarado para a classe. Fizemos a declaração de um inteiro opcao que será usado nos menus para armazenar a escolha do usuário, e logo em seguida fizemos um switch case para direcionar o programa para o método escolhido. O caso 1 (inserção) conta com um segundo menu, que pergunta ao usuário de que fonte os dados devem ser inseridos. Se o usuário escolhe inserir do teclado, o programa chama o método leitura passando ‘cin’ como parâmetro. O método vai ler o inteiro que usuário digitar no teclado e inseri-lo na lista. No caso de o usuário escolher inserir dados de um arquivo na lista, então é declarado um arquivo (“lista_entrada.txt”) como sendo arquivo de leitura, e o método leitura é chamado dentro de um while que repete enquanto não atingir o final do arquivo declarado como fonte de dados. Nesse caso passamos o arquivo de leitura como parâmetro para a função. O caso 2 (pesquisa) apenas pede ao usuário que digite um inteiro e passa esse inteiro como parâmetro do método verifica, que retorna ‘true’ se o numero pesquisado está na lista, ou ‘false’ se ele não está a lista. O caso 3 (remover) pede ao usuário que digite um inteiro e passa esse inteiro como parâmetro do método remove, que verifica se o inteiro está na lista, e se sim, remove o mesmo. O caso 4 (exportar) imprime um segundo menu que pergunta ao usuário se os dados devem ser exportados apenas para a tela ou para um arquivo. Caso o usuário escolha a primeira opção, o programa chama o método exporta passando ‘cout’ como parâmetro, mas se o usuário optar por exportar para um arquivo é declarado um arquivo de saída (“lista_saida.txt”) e esse arquivo é passado como parâmetro para o método exporta, e então voltamos ao menu inicial. O caso 5 chama exit(0) para sair do programa. Análise de Complexidade Eficiência temporal -> Uma lista simplesmente encadeada com tamanho de n nós tem complexidade O(n) no seu pior caso, pois qualquer operação que se tenha que fazer encima dessa estrutura de dados vai ter seu desempenho/eficiência temporal dado em função do seu tamanho. Logo, T(n) = O(n) -> (Linear) Eficiência espacial -> O gasto de memória, também será dado em função do tamanho da estrutura, também O(n). Logo, S(n) = O(n) -> (Linear). Conclusão O trabalho descrito, poderia ser simplesmente implementado no programa main(), como função sem a necessidade de implementar uma classe e seu objeto(s). Porem como a temática do Trabalho prático era o treinamento nas estruturas da linguagem C++, os programas foram feitos em paradigma de orientação a objetos (Programação orientada a objetos). Em caso de trabalhos futuros com esse mesmo TP, poderiamos usar a estrutura para aperfeiçoar o código fonte, com uso dos objetos chamando os métodos de forma econômica. Referências Bibliográficas Stack Overflow stackoverflow.com/ Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required. Take the 2-minute tour. cplusplus.com - The C++ Resources Network www.cplusplus.com/ Description of the most important classes, functions and objects of the Standard Language Library, with descriptive fully-functional short programs as examples:. Treinamento em Linguagem C++ - Módulo 2 - 2ª Edição Editora Pearson Brasil Tales Rodrigues Jardim Graduando em Sistemas de Informação e monitor da disciplina COM016 do curso de Sistemas de Informação da UFVJM - 2015/1.
Compartilhar