[原创] 一个链表类.... - C++教室 - C++论坛

中学者

等　级：版主
威　望：20
帖　子：3554
专家分：80
注　册：2007-9-14
结帖率：33.33%

楼主

问题点数：0 回复次数：2

[原创] 一个链表类....

自己折腾了一天，还是不如人意.....算是练练手吧，这个类原本是写上迭代器的，后面加了又删，删了又加，始终写不好...最后就不要了....不过作为学习来说，目的算是达到了-----异常安全.
能帮忙加上迭代器的就加加...谢谢 ^ ^.

[size=1.5]/*****************************************************************
** HighlightCodeV3.0 software by yzfy(雨中飞燕) http:// **
*****************************************************************/
#ifndef DATASTRUCT_H_
#define DATASTRUCT_H_
#include<iostream>
#include<vector>
#include<cassert>

template<typename _Ty>
class Linklist
{
    struct node_
    {
        _Ty value_;
        node_* next,*pre;
        node_ * first;
        node_(const _Ty& value): value_(value)
        {
            pre=next=first=0;
        }
        ~node_(){ std::cout<<" destroty......"<<std::endl;}
    } ;
    typedef typename Linklist<_Ty>::node_*  pointer;
    typedef typename Linklist<_Ty>::node_ const*  const_pointer;
    typedef typename Linklist<_Ty>::node_&  reference;
    typedef typename Linklist<_Ty>::node_&  const_reference;
public:
    Linklist();
    Linklist(const Linklist<_Ty>& source);
    Linklist<_Ty>& operator=(const Linklist<_Ty>& source);
    ~Linklist();

    bool empty() const { return (head_==0); }
    int size() const { return size_; }
    pointer begin() { return head_; }
    pointer end() { return tail_; }
    const_pointer begin() const { return head_; }
    const_pointer end() const { return tail_; }
    void Insert(const _Ty& value,pointer at_);
    void Delete(pointer at_);
    pointer Linklist<_Ty>::Find(int pos)
    {
        return find(pos);
    }
    const_pointer Find(int pos) const
    {
        return find(pos);
    }
    void print() const
    {
        for(node_* it=head_;it!=0;it=it->next )
            std::cout<<it->value_<<" ";
        std::cout<<std::endl;
    }
private:
    pointer link(pointer at_f,pointer at_,pointer at_l)
    {
        if(at_f!=0) at_f->next=at_;
        if(at_l!=0)    at_l->pre=at_;
        at_->pre=at_f;
        at_->next=at_l;
        at_->first=head_;
        return at_;
    }
    pointer allocated()
    {
        return static_cast<pointer>(::operator new(sizeof(node_)));
    }
    void destroy(pointer des_)
    {
        des_->~node_();
    }
    pointer find(int pos) const
    {
        assert(pos>0&&pos<=size_);
        if(pointer check=head_)
        {
            for(;pos>1;--pos) check=check->next;
            return check;
        }
        return 0;
    }
    void copy_(const Linklist<_Ty>& source);
private:
    pointer  head_,tail_;
    int size_;
};
//  具体实现
template<typename _Ty>
void Linklist<_Ty>::copy_(const Linklist<_Ty>& source)
{
    pointer iter=begin(),iter_pre=begin(),h_=begin();
    for(const_pointer cPtr=source.begin();cPtr!=0;cPtr=cPtr->next)
    {
        iter=allocated();
        new (iter)node_(cPtr->value_);
        if(h_)
        {
            iter_pre=link(iter_pre,iter,0);
            iter_pre->first=h_;
        }
        else
        {
            iter_pre=link(iter_pre,iter,0);
            iter_pre->first=h_=iter_pre;
        }
        iter=iter->next;
    }
    head_=iter_pre?iter_pre->first:0;
    tail_=iter_pre;
    size_=source.size_;
}
template<typename _Ty>
inline Linklist<_Ty>::Linklist():head_(0),tail_(0),size_(0)
{
}
template<typename _Ty>
Linklist<_Ty>::Linklist(const Linklist<_Ty>& source):head_(0),tail_(0),size_(0)
{
    copy_(source);
}
template<typename _Ty>
Linklist<_Ty>& Linklist<_Ty>::operator=(const Linklist<_Ty>& source)
{
    if( this!=&source) copy_(source);
    return *this;
}
template<typename _Ty>
Linklist<_Ty>::~Linklist()
{
    for(node_* d=begin(),*t;d!=0;d=t)
    {
        t=d->next;
        destroy(d);
        ;;operator delete(d);
    }
}
template<typename _Ty>
void Linklist<_Ty>::Insert(const _Ty& value,pointer at_)
{
    node_* node=allocated();
    new (node)node_(value);
    if( head_==0)
    {
        head_=tail_=link(0,node,0);
        node->first=head_;
    }
    else if( at_==head_)
    {
        head_=link(0,node,head_);
        for(;node;node=node->next)
            node->first=head_;
    }
    else if( at_==tail_)  tail_=link(at_,node,0);
    else link(at_->pre,node,at_);
    size_++;
}
template<typename _Ty>
void Linklist<_Ty>::Delete(pointer at_)
{
    assert(at_!=0);
    if( head_==0)  throw "it is empty so that delete....";
    if( at_==head_)
    {
        if(tail_==head_ ) tail_=0;
        head_=head_->next;
        for(node_* t_=head_;t_;t_=t_->next)
        t_->first=head_;
    }
    else if( at_=tail_)  tail_=link(tail_->pre->pre,tail_->pre,0);
    else link(at_->pre->pre,at_->pre,at_->next);
    destroy(at_);
    ::operator delete(at_);
    size_--;
}
#endif[/size]

[[it] 本帖最后由中学者于 2008-6-8 11:44 编辑 [/it]]

搜索更多相关主题的帖子: 链表　