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

来源：百度文库 编辑：神马文学网 时间：2024/06/12 05:33:49
/************************************/单链表节点类型：
template
struct Snode {
Snode* next_;
T value_;
Snode(T const& t = T(), Snode *next = 0) //初始化，构造函数；
: next_(next), value_(t){ }
};/**********************************/ 
/********************************************/
单链表类模板界面：
template struct Sitr; //迭代子类预声明；
template
 struct Slist {
    typedef T Value_type;       //自述；
    typedef Snode Node_type; //自述；
    typedef Node_type Node;     //节点别名，简记；
    typedef Sitr 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
void swap(Slist& a, Slist& b); //交换两个链表内容；/*************************************************/
/***********************************************/具体函数的实现：构造函数：
template
Slist::Slist(void) : first_(0)
{ }

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

清空函数：
template
void Slist::clear(void)
{
while(first_ != 0)
{
Node* h = first_;
first_ = first_->next_;
delete h;
}
} 判空函数：
template
bool Slist::empty(void) const
{ return first_ == 0; }

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

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

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

删除表头：
template
void Slist::pop_front(void)
{ //前提条件，表非空；
Node* oh = first_;
first_ = oh->next_;
delete oh;
} 返回指向第一个元素的迭代子：
template
typename Slist::Iterator Slist::begin(void)
{
return Iterator(first_);
}

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

template
Sitr Slist::end(void)
{
return Sitr(0);
} 在表头添加：
template
void Slist::push_front(const T& t)
{
first_ = new Node(t, first_);
}

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

删除pos指向节点之后的一个节点；
template
typename Slist::Iterator
Slist::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_);
}/**************************************************/
单链表Slist类模板界面及其函数实现 函数模板 类模板 链表List 类模板界面 利用C 模板，代替虚函数，实现类的静态多态性（加入性能测试部分） - woaidongmao - C 博客 轻松实现类VC界面 - VC知识库文章 JSF实现的自选语言界面 wordpress模板各文件函数解析 《社会主义及其实现道路》 使用 Velocity 实现客户端和服务器端模板 使用调用外部程序函数实现API函数高级功能 双界面卡的发展研究及其技术构架 逆向 C -- 识别类及其构造函数 - FISH 的专栏 - CSDNBlog javascript中trim函数的实现 声明函数指针并实现回调 oracle用sum函数实现累加 用函数实现Excel隔行着色 楼主 javascript实现通用表单验证函数 prototype.js常用函数及其用法 prototype.js常用函数及其用法 单片高频函数发生器MAX038及其应用 prototype.js常用函数及其用法 Excel中指数、对数函数及其应用 分页技术及其实现1 科学创业及其实现途径