单链表Slist类模板界面及其函数实现

/************************************/

单链表节点类型：
template<typename T>
struct Snode {
Snode* next_;
T value_;
Snode(T const& t = T(), Snode *next = 0) //初始化，构造函数；
: next_(next), value_(t){ }
};

/**********************************/ 

/********************************************/
单链表类模板界面：
template<typename T> struct Sitr; //迭代子类预声明；
template<typename T>
 struct Slist {
    typedef T Value_type;       //自述；
    typedef Snode<T> Node_type; //自述；
    typedef Node_type Node;     //节点别名，简记；
    typedef Sitr<T> Iterator;   //迭代子别名；
    Node* first_;               //唯一的成员变量；
    Slist(void);                //构造函数；
    virtual ~Slist() ;          //析构函数；
    void clear(void);           //清空函数；
    bool empty(void) const;     //判空函数；
    int size(void) const;       //返回链表中元素个数；
    T& front(void);             //返回链表中第一个元素的引用；
    Iterator begin(void);       //返回指向第一个元素的迭代子；
    Iterator end(void)t;        //返回链表的右边界； 
    void push_front(const T& t);//在表头添加；
    Iterator insert_after(Iterator pos, T const& t); //插入在pos之后；
    void pop_front(void);       //删除表头第一个元素；
    Iterator erase_after(Iterator pos); //删除pos之后一个节点；
};
template<typename T>
void swap(Slist<T>& a, Slist<T>& b); //交换两个链表内容；

/*************************************************/

/***********************************************/

具体函数的实现：

构造函数：
template<typename T>
Slist<T>::Slist(void) : first_(0)
{ }

析构函数：
template<typename T>
Slist<T>::~Slist(void)
{
clear();
}

清空函数：
template<typename T>
void Slist<T>::clear(void)
{
while(first_ != 0)
{
Node* h = first_;
first_ = first_->next_;
delete h;
}
}

 

判空函数：
template<typename T>
bool Slist<T>::empty(void) const
{ return first_ == 0; }

返回链表元素个数：
template<typename T>
int Slist<T>::size(void) const
{
int result = 0;
for(Node* cur = first_; cur != 0; cur = cur->next_)
++result;
return result;
}

返回对第一个元素的引用：
template<typename T>
T& Slist<T>::front(void)
{ //前提条件，表非空；
return first_->value_ ;
}

在表头添加：
template<typename T>
void Slist<T>::push_front(const T& t)
{
first_ = new Node(t, first_);
}

删除表头：
template<typename T>
void Slist<T>::pop_front(void)
{ //前提条件，表非空；
Node* oh = first_;
first_ = oh->next_;
delete oh;
}

 

返回指向第一个元素的迭代子：
template<typename T>
typename Slist<T>::Iterator Slist<T>::begin(void)
{
return Iterator(first_);
}

返回链表右边界：
template<typename T>
typename Slist<T>::Iterator Slist<T>::end(void)
{
return Iterator(0);
}
//////////////////////////////////////////////////
同上：
template<typename T>
Sitr<T> Slist<T>::begin(void)
{
return Sitr<T>(first_);
}

template<typename T>
Sitr<T> Slist<T>::end(void)
{
return Sitr<T>(0);
}

 

在表头添加：
template<typename T>
void Slist<T>::push_front(const T& t)
{
first_ = new Node(t, first_);
}

在迭代子pos指向的元素后添加：
template<typename T>
typename Slist<T>::Iterator
Slist<T>::insert_after(Iterator pos, T const& t)
{
  //前提条件，pos指向单链表中某个节点；
Node* p = new Node(t, pos.me_->next_);
pos.me_->next_ = p;
return Iterator(p);
}

 

删除表头:
template<typename T>
void Slist<T>::pop_front(void)
{ //前提条件，表非空；
Node* oh = first_;
first_ = oh->next_;
delete oh;
}

删除pos指向节点之后的一个节点；
template<typename T>
typename Slist<T>::Iterator
Slist<T>::erase_after(Iterator pos)
{
// pos指向链表中某个节点； 
//pos的后继存在；
Node* p = pos.me_;
Node* q = p->next_; //q 指向被删除节点；
p->next_ = q->next_;
delete q;
return Iterator(p->next_);
}

/**************************************************/