Loading...

Tuesday, 21 August 2012

Linked List (C++)

Linked list

/////////
multy.h
/////////
template <class T>
class Multy
{
    struct Node
    {
        T data;
        Node *next;
        Node(T d, Node *n = 0):data(d), next(n) {}
    };
    Node *head;

public:
    Multy(Node *h = 0):head(h){}
    ~Multy();
    bool isEmpty();
    T pop_back();
    T pop_front();
    int GetSize();

    void insert(Node *loc, T data);
    void push_back(T data);
    void push_front(T data);
    void erase(Node *loc);
    void display();

    Node *search(T data);
    Node *search(char* str);

    bool *Bsearch(T data);
    bool *Bsearch(char* str);
    bool check(T data);

    bool operator==(const Multy&)const;
    bool operator!=(const Multy&)const;
    Multy &operator= (const Multy &other);
    Multy &operator+= (const Multy &other);
    Multy &operator-= (const Multy &other);
    Multy &operator/= (const Multy &other);

    friend Multy<T>* Union (Multy<T>* multy1,Multy<T>* multy2);
    friend Multy<T>* Section (Multy<T>* multy1,Multy<T>* multy2);
    friend Multy<T>* Difference (Multy<T>* multy1,Multy<T>* multy2);
};
template <class T> Multy* Union (Multy<T>* multy1,Multy<T>* multy2);
template <class T> Multy* Section (Multy<T>* multy1,Multy<T>* multy2);
template <class T> Multy* Difference (Multy<T>* multy1,Multy<T>* multy2);
/////////////
multy.cpp
////////////
#include <iostream>
#include <cstring>

using namespace std;

// destructor
template <class T>
Multy<T>::~Multy()
{
    Node *tmp;
    while(head) {
        tmp = head;
        head = head->next;
        delete tmp;
    }
}

// insert d before loc
template <class T>
void Multy<T>::insert(Node *loc, T d)
{
    Node *new_node = new Node(d,0);
    if(!head) {
        head = new_node;
        return;
    }
    if(loc == head) {
        push_front(d);
        return;
    }
    Node *cur = head;
    while(cur->next) {
        if(cur->next == loc) {
            new_node->next = cur->next;
            cur->next = new_node;
            return ;
        }
        cur = cur->next;
    }
}

template <class T>
void Multy<T>::push_back(T d)
{
    Node *new_node = new Node(d,0);
    if(!head) {
        head = new_node;
        return;
    }
    Node *cur = head;
    while(cur) {
        if(!cur->next) {
            cur->next = new_node;
            return;
        }
        cur = cur->next;
    }
}

template <class T>
void Multy<T>::push_front(T d)
{
    Node *new_node = new Node(d,0);
    if(!head) {
        head = new_node;
        return;
    }
    new_node->next = head;
    head = new_node;
    return;
}

template <class T>
T Multy<T>::pop_back()
{
    Node *cur = head;
    while(cur) {
        if(!cur->next) {
            T data (cur->data);
            delete cur;
            head = NULL;
            return data;
        }
        else {
            if(!cur->next->next)  {
                T data (cur->next->data);
                cur->next = NULL;
                delete cur->next;
                return data;
            }
        }
        cur = cur->next;
    }
    return NULL;
}

template <class T>
T Multy<T>::pop_front()
{
    if(!head) return NULL;
    Node *tmp = head;
    T data (head->data);
    if(head->next) {
        head = head->next;
        delete tmp;
        return data;
    }
    delete tmp;
    head = NULL;
    return data;
}
template <class T>
int Multy<T>::GetSize()
{
    int count = 0;
    Node *tmp = head;
    while(tmp!= NULL){
        count++;
        tmp=tmp->next;
    }
    return count;
}
template <class T>
bool Multy::isEmpty(){
    return head == NULL ? false : true;
}

template <class T>
void Multy<T>::erase(Node *loc)
{
    if(loc == head) {
        Node *tmp = head;
        head = head->next;
        delete tmp;
        return;
    }
    Node *cur = head;
    while(cur) {
        if(cur->next == loc) {
            cur->next = loc->next;
            delete loc;
        }
        cur = cur->next;
    }
}
template <class T>
class Multy<T>::Node* Multy<T>::search(T d)
{
    if(!head) return NULL;
    Node* cur = head;
    while(cur) {
        if(cur->data == d)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
template <class T>
class Multy<char*>::Node* Multy<T>::search(char* str)
{
    if(!head) return NULL;
    Node* cur = head;
    while(cur) {
        if(cmpstr(cur->data,str) == 0)
            return cur;
        cur = cur->next;
    }
    return NULL;
}
template <class T >
bool Multy<char*>::Bsearch(char* str)
{
    if(!head) return false;
    Node* cur = head;
    while(cur) {
        if(cmpstr(cur->data,str) == 0)
            return true;
        cur = cur->next;
    }
    return false;
}
template <class T>
bool Multy<T>::Bsearch(T d)
{
    if(!head) return false;
    Node* cur = head;
    while(cur) {
        if(cur->data == d)
            return true;
        cur = cur->next;
    }
    return false;
}
template <class T>
void Multy<T>::display()
{
    if(!head) return;
    Node *cur  = head;
    while(cur) {
        cout << cur->data << " " << endl;
        cur = cur->next;
    }
    cout << endl;
}
template <class T>
bool Multy::check(T data){

    try{
        Node *new_node = new Node(data,0);
        delete new_node;
    }
    catch (...){
        return false;
    }
    return true;
}
template<class T>
bool Multy<T>::operator== (const Multy<T> &multy1) const{
    if((multy1.isEmpty() == true) && (head == NULL))
        return true;
    int count = 1;
    Node *tmp = head;
    while(tmp != NULL){
        if(multy1.Bsearch(tmp->data) == false)
            return false;
        count++;
        tmp=tmp->next;
    }
    if(multy1.GetSize() != count)
        return false;
    return true;
}
template<class T>
bool Multy<T>::operator!= (const Multy<T> &multy1) const{
    if((multy1.isEmpty() == true) && (head == NULL))
        return false;
    int count = 1;
    Node *tmp = head;
    while(tmp != NULL){
        if(multy1.Bsearch(tmp->data) == true)
            return false;
        count++;
        tmp=tmp->next;
    }
    if(multy1.GetSize() == count)
        return false;
    return true;
}
template<class T>
Multy<T>& Multy::operator= (const Multy<T> &other){

    if(this != other){
        if(head != NULL)
            ~Multy();
        while(other.isEmpty()){
            push_back(other.pop_front());
        }
    }

    return *this;
}
template<class T>
Multy<T>& Multy::operator+= (const Multy<T> &other){
    return Union(this,other);
}
template<class T>
Multy<T>& Multy::operator-= (const Multy<T> &other){
    return Section(this,other);
}
template<class T>
Multy<T>& Multy::operator-= (const Multy<T> &other){
    return Difference(this,other);
}
template <class T>
Multy* Union (Multy<T>* multy1,Multy<T>* multy2){
    Multy<T> *myMulty = new Multy<T>(NULL);
    T data;
    while(multy1->isEmpty()){
        data = multy1->pop_front();
        if((multy2->Bsearch(data)) == true){
            multy2->erase(multy2->search(data));
        }
        myMulty->push_back(data);
    }
    while(multy2->isEmpty()){
        myMulty->push_back(multy2->pop_front());
    }
    return myMulty;
}
template <class T>
Multy* Section (Multy<T>* multy1,Multy<T>* multy2){
    Multy<T> *myMulty = new Multy<T>(NULL);
    T data;
    while(multy1->isEmpty()){
        data = multy1->pop_front();
        if((multy2->Bsearch(data)) == true){
            myMulty->push_back(data);
        }
    }
    return myMulty;
}
template <class T>
Multy* Difference (Multy<T>* multy1,Multy<T>* multy2){
    Multy<T> *myMulty = new Multy<T>(NULL);
    T data;
    while(multy1->isEmpty()){
        data = multy1->pop_front();
        if((multy2->Bsearch(data)) == false){
            myMulty->push_back(data);
        }

    }
    return myMulty;
}
////////////
main.cpp
//////////
#include <iostream>
#include "multiplicity.h"

using namespace std;

int main() {

    Multy<int> *Multy1 = new Multy<int>(NULL);
    Multy<double> *Multy2 = new Multy<double>(NULL);

    cout << "push_back() 20, 30 40, 50\n\n";
    Multy1->push_back(20);
    Multy1->push_back(30);
    Multy1->push_back(40);
    Multy1->push_back(50);
    Multy1->display();

    cout << "push_front() 10\n\n";
    Multy1->push_front(10);
    Multy1->display();

    cout << "erase 30\n\n";
    Multy1->erase(Multy1->search(30));
    Multy1->display();

    cout << "insert 30 before 40\n\n";
    Multy1->insert(Multy1->search(40),30);
    Multy1->display();

    cout << "pop_back()\n";
    cout << Multy1->pop_back() << " just back popped\n\n";
    Multy1->display();

    cout << "pop_front()\n";
    cout << Multy1->pop_front() << " just front popped\n\n";
    Multy1->display();

    return 0;
}

No comments:

Post a Comment