esame-150211.cpp

#include <iostream>

using namespace std;

template <typename H> class Table {
    public:
        virtual void del(H x) = 0;
        virtual void insert(H x) = 0;
        virtual H* max() = 0;
        virtual H* min() = 0;
        virtual void print() = 0;
};

template <typename H> class Node{
    private:
        H key;
        Node<H>* next;
    public:
        Node(H x){
            key = x;
            next = NULL;
        }
        H getKey() { return key; }
        H* getPrtKey() { return &key; }
        Node<H>* getNext() { return next; }
        void setKey(H key) { this->key = key; }
        void setNext(Node<H>* next) { this->next = next; }
};

template <typename H> class MyTable: public Table<H> {
    private:
        int size;
        Node<H>* head, *tail;

    public:
        MyTable(){
            size = 0;
            head = tail = NULL;
        }
        bool isEmpty(){
            if(!head)
                return true;
            return false;
        }
        void print() {
            Node<H>* temp = head;
            cout << "[";
            while(temp){
                cout << temp->getKey();
                if(temp->getNext()) cout << ",";
                temp = temp->getNext();
            }
            cout << "]" << endl;
        }
        void insert(H x){
            size++;
            Node<H>* temp = new Node<H>(x);
            if(isEmpty()){
                head = tail = temp;
                return;
            }
            tail->setNext(temp);
            tail = temp;
        }
        H* max(){
            if(isEmpty()){
                return NULL;
            }
            Node<H>* temp = head;
            H* n = head->getNext()->getPrtKey();
            while(temp){
                if(temp->getKey() > *n)
                n = temp->getPrtKey();
                temp = temp->getNext();
            }
            return n;
        }

        H* min(){
            if(isEmpty()){
                return NULL;
            }
            Node<H>* temp = head;
            H* n = head->getNext()->getPrtKey();
            while(temp){
                if(temp->getKey() < *n)
                    n = temp->getPrtKey();
                temp = temp->getNext();
            }
            return n;
        }
        void del(H x){
            Node<H>* temp = head;
            Node<H>* temp2 = NULL;
            Node<H>* prev = NULL;
            Node<H>* prev2 = NULL;
            size --;
            while(temp){
                if(temp->getKey() == x){
                    temp2 = temp;
                    prev2 = prev;
                }
                prev = temp;
                temp = temp->getNext();
            }
            if(!prev2){
                head = temp2->getNext();
                return;
            }
            prev2->setNext(temp2->getNext());
            delete(temp2);
        }
};

template <typename H> class OrderedTable: public Table<H>{
    private:
        int size;
        Node<H>* head, *tail;

    public:
        OrderedTable(){
            size = 0;
            head = tail = NULL;
        }
        bool isEmpty(){
            if(!head)
                return true;
            return false;
        }
        void print() {
            Node<H>* temp = head;
            cout << "[";
            while(temp){
                cout << temp->getKey();
                if(temp->getNext()) cout << ",";
                temp = temp->getNext();
            }
            cout << "]" << endl;
        }
        void insert(H x){
            size++;
            Node<H>*news = new Node<H>(x);
            Node<H>*prev = NULL;
            Node<H>*temp = head;

            if(isEmpty()){
                head = tail = news;
                return;
            }
            if(temp->getKey() > x && temp == head){
                head = news;
                news->setNext(temp);
                return;
            }
            prev = temp;
            temp = temp->getNext();
            while(temp){
                if(temp->getKey() > x && temp == tail){
                    prev->setNext(news);
                    news->setNext(temp);
                    return;
                }
                if(temp->getKey() > x){
                    prev->setNext(news);
                    news->setNext(temp);
                    return;
                }
                prev = temp;
                temp = temp->getNext();
            }
            tail->setNext(news);
            tail = news;
        }

        H* max(){
            if(isEmpty()){
                return NULL;
            }
            return tail->getPrtKey();
        }

        H* min(){
            if(isEmpty()){
                return NULL;
            }
            return head->getPrtKey();
        }
        void del(H x){
            Node<H>* temp = head;
            Node<H>* temp2 = NULL;
            Node<H>* prev = NULL;
            Node<H>* prev2 = NULL;
            size --;
            while(temp){
                if(temp->getKey() == x){
                    temp2 = temp;
                    prev2 = prev;
                }
                prev = temp;
                temp = temp->getNext();
            }
            if(!prev2){
                head = temp2->getNext();
                return;
            }
            if(temp2 == tail)
                tail = prev2;
            prev2->setNext(temp2->getNext());
            delete(temp2);
        }
};

template <typename H> class NodeCir{
    private:
        H key;
        NodeCir<H>* next, *prev;
    public:
        NodeCir(H x){
            key = x;
            next = prev = NULL;
        }
        H getKey() { return key; }
        NodeCir<H>* getNext() { return next; }
        NodeCir<H>* getPrev() { return prev; }
        void setKey(H key) { this->key = key; }
        void setNext(NodeCir<H>* next) { this->next = next; }
        void setPrev(NodeCir<H>* prev) { this->prev = prev; }
};

template <typename H> class CircularTable: public Table<H>{
    private:
        int size;
        NodeCir<H>* current;

    public:
        CircularTable(){
            size = 0;
            current = NULL;
        }
        bool isEmpty(){
            if(!current)
                return true;
            return false;
        }
        void insert(H x){
            NodeCir<H>* temp = new NodeCir<H>(x);
            if(isEmpty()){
                current = temp;
                temp->setNext(current);
                temp->setPrev(current);
                return;
            }
            current->getPrev()->setNext(temp);
            temp->setPrev(current->getPrev());
            temp->setNext(current);
            current->setPrev(temp);
        }

        void del(H x){
            NodeCir<H>* temp = current->getPrev();
            NodeCir<H>* sup = current;
            while(temp != current){
                if(temp->getKey() == x){
                    sup->setPrev(temp->getPrev());
                    temp->getPrev()->setNext(sup);
                    delete(temp);
                    return;
                }
                sup = temp;
                temp = temp->getPrev();
            }
        }

        void print(){
            NodeCir<H>* temp = current;
            cout << "[" << temp->getKey() << ",";
            temp = current->getNext();
            while(temp != current){
                cout << temp->getKey();
                if(temp->getNext() != current){
                    cout << ",";
                }
                temp = temp->getNext();
            }
            cout << "]" << endl;
        }

        H* max() {}
        H* min() {}
};

int main(){
    /*MyTable<int>* T = new MyTable<int>();
    T->insert(3);
    T->insert(7);
    T->insert(1);
    T->insert(8);
    T->insert(5);
    T->insert(2);
    T->insert(6);
    T->insert(1);
    T->insert(8);
    T->print();
    T->del(8);
    T->del(7);
    T->del(1);
    T->print();
    cout << "Elemento MAX " << *(T->max()) << endl;
    cout << "Elemento MIN " << *(T->min()) << endl;

    OrderedTable<int>* T = new OrderedTable<int>();
    T->insert(3);
    T->insert(7);
    T->insert(1);
    T->insert(8);
    T->insert(5);
    T->insert(2);
    T->insert(6);
    T->insert(1);
    T->insert(8);
    T->print();
    T->del(8);
    T->del(7);
    T->del(1);
    T->print();
    cout << "Elemento MAX " << *(T->max()) << endl;
    cout << "Elemento MIN " << *(T->min()) << endl;
*/
    CircularTable<int>* T = new CircularTable<int>();
    T->insert(3);
    T->insert(7);
    T->insert(1);
    T->insert(8);
    T->insert(5);
    T->insert(2);
    T->insert(6);
    T->insert(1);
    T->insert(8);
    T->print();
    T->del(8);
    T->del(7);
    T->del(1);
    T->print();

    return 0;
}