データ構造(c+)チェーンテーブル

チェーンテーブルの基本構造

<pre name="code" class="cpp">#include <iostream>
using namespace std;

class OutOfBounds
{
    public:
        void out(){
            cout << "ERROR:OutOfBounds" << endl;
        }
};

class NoMem
{
    public:
        void out(){
            cout << "ERROR:NoMem" << endl;
        }
};

template<class T>
class Chain;

template<class T>
class ChainNode
{

    friend class Chain<T>;

    private:
        T data;
        ChainNode<T>* link;
};

template<class T>
class Chain
{
    public:
        Chain(){
            first = NULL;
            last = first;
            length = 0;
        }
        ~Chain();
        Chain<T>& Append(const T& data);
        void Output(ostream& out) const;
        bool Insert(int k,const T& data);
        bool Delete(int k);
    private:
        ChainNode<T>* first;
        ChainNode<T>* last;
        int length;
};

template<class T>
Chain<T>::~Chain(){
    ChainNode<T>* next;
    while(first){
        next = first->link;
        delete first;
        first = next;
    }
}

template<class T>
bool Chain<T>::Insert(int k,const T& data){
    if(k<0||k>length){
        throw OutOfBounds();
        return false;
    }
    
    ChainNode<T>* p = first;

    for(int i=1;i<k && p;++i)
        p = p->link;
    if(!p)
        return false;
        
    ChainNode<T>* new_Node = new ChainNode<T>;
    new_Node->data = data;
    if(k){
        new_Node->link = p->link;
        p->link = new_Node;
    }else{
        new_Node->link = first;
        first = new_Node;
    }
    return true;
}

template<class T>
bool Chain<T>::Delete(int k){
    if(k<1||k>length){
        throw OutOfBounds();
        return false;
    }

    ChainNode<T>* p = first;
    if(k==1)
        first = first->link;
    else{
        ChainNode<T>* q = first;
        for(int i=1;i<k-1 && q;++i)
            q = q->link;
        
        if(!q||!q->link)
            return false;
        p = p->link;
        q->link = p->link;
    }

    delete p;
    return true;

}

template<class T>
Chain<T>& Chain<T>::Append(const T& data){
    ChainNode<T>* new_Node = new ChainNode<T>;
    new_Node->link = NULL;
    new_Node->data = data;

    if(!last){
        first = last = new_Node;
    }else{
        last->link = new_Node;
        last = new_Node;
    }

    ++length;
    return *this;
}

template<class T>
void Chain<T>::Output(ostream& out) const{
    ChainNode<T>* current = first;
    while(current){
        out << current->data << " ";
        current = current->link;
    }
}

template<class T>
ostream& operator<<(ostream& out,Chain<T>& L){
    L.Output(out);
    return out;
}

int main()
{
    Chain<int> L;
    L.Append(1);
    L.Append(2);
    L.Append(3);
    L.Insert(3,11);
    L.Delete(1);

    cout << L << endl;

    return 0;
}