單鏈表Slist類模板界面及其函數(shù)實現(xiàn)

BUPT-BYR 2010-12-20

展開全文

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

單鏈表節(jié)點類型：
template<typename T>
struct Snode {
Snode* next_;
T value_;
Snode(T const& t = T(), Snode *next = 0) //初始化，構(gòu)造函數(shù)；
: next_(next), value_(t){ }
};

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

/********************************************/
單鏈表類模板界面：
template<typename T> struct Sitr; //迭代子類預(yù)聲明；
template<typename T>
struct Slist {
    typedef T Value_type;       //自述；
    typedef Snode<T> Node_type; //自述；
    typedef Node_type Node;     //節(jié)點別名，簡記；
    typedef Sitr<T> Iterator;   //迭代子別名；
    Node* first_;               //唯一的成員變量；
    Slist(void);                //構(gòu)造函數(shù)；
    virtual ~Slist() ;         //析構(gòu)函數(shù)；
    void clear(void);           //清空函數(shù)；
    bool empty(void) const;     //判空函數(shù)；
    int size(void) const;       //返回鏈表中元素個數(shù)；
    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之后一個節(jié)點；
};
template<typename T>
void swap(Slist<T>& a, Slist<T>& b); //交換兩個鏈表內(nèi)容；

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

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

具體函數(shù)的實現(xiàn)：

構(gòu)造函數(shù)：
template<typename T>
Slist<T>::Slist(void) : first_(0)
{ }

析構(gòu)函數(shù)：
template<typename T>
Slist<T>::~Slist(void)
{
clear();
}

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

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

返回鏈表元素個數(shù)：
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指向單鏈表中某個節(jié)點；
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指向節(jié)點之后的一個節(jié)點；
template<typename T>
typename Slist<T>::Iterator
Slist<T>::erase_after(Iterator pos)
{
// pos指向鏈表中某個節(jié)點；
//pos的后繼存在；
Node* p = pos.me_;
Node* q = p->next_; //q 指向被刪除節(jié)點；
p->next_ = q->next_;
delete q;
return Iterator(p->next_);
}

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