INE5408-03208A|INE5609-03238B (20181) - Estruturas de Dados

Disponível a partir de: quinta-feira, 21 jun. 2018, 15:10
Data de entrega: quinta-feira, 21 jun. 2018, 18:05
Arquivos requeridos: linked_list.h ( Baixar)
Número máximo de arquivos: 10
Tipo de trabalho: Trabalho individual

Arquivos requeridos

linked_list.h

#ifndef STRUCTURES_LINKED_LIST_H
#define STRUCTURES_LINKED_LIST_H
#include <stdexcept>  // C++ exceptions

#include <cstdint>

namespace structures {

template<typename T>
class LinkedList {
 public:
    //!*
    /*!
    @brief Contrutor da lista sem passagem de parametros
    * size_ é inicializado com 0
    */
    LinkedList() {
        head = nullptr;
        size_ = 0;
    }
    //!*
    /*!
    @brief Destrutor da lista
    * size_ é inicializado com 0
    * Criação de dois Node temporários
    * Node atual recebe o ponteiro de head
    * Percorre a lista elemento a elemento deletando o elemento anterior
    */
    ~LinkedList() {
        clear();
    }
    //!*
    /*!
    @brief Metodo clear
    * Chama o metodo pop size_ vezes
    */
    void clear() {
        while (!empty()) {
            pop_front();
        }
    }
    //!*
    /*!
    @brief Metodo que insere no inicio da lista
    @param "data" valor a ser inserido
    * Chama o método insert passando data como parametro
    */
    void push_front(const T& data) {
        insert(data, 0);
    }
    /*!
    @brief Metodo que insere no final da lista
    @param "data" valor a ser inserido
    * Chama o método insert passando data como parametro
    */
    void push_back(const T& data) {
        insert(data, size_);
    }
    //*******************************************************************
    void insert(const T& data, std::size_t index) {  // inserir na posição
        // COLOQUE SEU CODIGO AQUI...
    }
    void insert_sorted(const T& data) {  // inserir em ordem
        // COLOQUE SEU CODIGO AQUI...
    }
    T& at(std::size_t index) {  // acessar um elemento na posição index
        // COLOQUE SEU CODIGO AQUI...
    }
    T pop(std::size_t index) {  // retirar da posição
        // COLOQUE SEU CODIGO AQUI...
    }
    //*******************************************************************

    //!*
    /*!
    @brief Metodo que retira do inicio da lista
    * Chama o método pop passando 0 como parametro
    */
    T pop_front() {
        return pop(0);
    }
    //!*
    /*!
    @brief Metodo que retira do final da lista
    * Chama o método pop passando size_ como parametro
    */
    T pop_back() {
        return pop(size_-1);
    }
     //!*
    /*!
    @brief Metodo que retira um dado especifico
    @param "data" é o dado a ser retirado
    *chama o metodo find passando como parametro data
    *chama o metodo pop passando como parametro o retorno de find
    */
    void remove(const T& data) {
        pop(find(data));
    }
    //!*
    /*!
    @brief metodo que retorna se a lista esta vazia
    *rerifica se size_ é igual a zero
    @return retorna um bool contendo a verificação anterior
    */
    bool empty() const {
        return (size_ == 0);
    }
    //*******************************************************************
    bool contains(const T& data) const {  // contém
        // COLOQUE SEU CODIGO AQUI...
    }
    std::size_t find(const T& data) const {  // posição do dado
        // COLOQUE SEU CODIGO AQUI...
    }
    //*******************************************************************
    //!*
    /*!
    @brief metodo que retorna o tamanho da lista
    @return retorna size_
    */
    std::size_t size() const {
        return size_;
    }

 private:
    class Node {  // Elemento
     public:
        explicit Node(const T& data):
            data_{data}
        {}

        Node(const T& data, Node* next):
            data_{data},
            next_{next}
        {}

        T& data() {  // getter: dado
            return data_;
        }

        const T& data() const {  // getter const: dado
            return data_;
        }

        Node* next() {  // getter: próximo
            return next_;
        }

        const Node* next() const {  // getter const: próximo
            return next_;
        }

        void next(Node* node) {  // setter: próximo
            next_ = node;
        }

     private:
        T data_;
        Node* next_{nullptr};
    };

    Node* end() {  // último nodo da lista
        auto it = head;
        for (auto i = 1u; i < size(); ++i) {
            it = it->next();
        }
        return it;
    }

    Node* head{nullptr};
    std::size_t size_{0u};
};

}  // namespace structures

#endif

Carregando