微软的VS208所使用的PJ STL（注1）中的list是双链表，但在某些场合，一个轻量级的单链表会更加合适。单链表非常常见，这里就不去细说了，本文的slist（single linked list）单链表实现了链表的基本功能，如有需要，以后还会扩充的。slist单链表（带头结点）的示意图如下所示：
完整的C++代码如下：
//带头结点的单链表
//by MoreWindows( http://blog.csdn.net/MoreWindows )
template<class T>
struct Node
{
T val;
Node *next;
Node(T &n)
{
this->val = n;
this->next = NULL;
}
};
template<class T>
class slist
{
public:
slist();
~slist();
void push_front(T &t);
bool find(T &t);
bool remove(T &t);
bool removeAll(T &t);
void clear();
int size();
public:
int m_nListDataCount;
Node<T> *m_head;
};
template<class T>
slist<T>::slist()
{
m_head = NULL;
m_nListDataCount = 0;
}
template<class T>
slist<T>::~slist()
{
Node<T> *p, *pnext;
for (p = m_head; p != NULL; p = pnext)
{
pnext = p->next;
free(p);
}
m_nListDataCount = 0;
}
template<class T>
void slist<T>::push_front(T &t)
{
Node<T> *pNode = (Node<T> *)malloc(sizeof(Node<T>));
pNode->val = t;
pNode->next = m_head;
m_head = pNode;
m_nListDataCount++;
}
template<class T>
bool slist<T>::find(T &t)
{
for (Node<T> *p = m_head; p != NULL; p = p->next)
if (p->val == t)
return true;
return false;
}
template<class T>
int slist<T>::size()
{
return m_nListDataCount;
}
//删除链表中第一个值为t的结点
template<class T>
bool slist<T>::remove(T &t)
{
Node<T> *pNode, *pPreNode;
pPreNode = pNode = m_head;
while (pNode != NULL)
{
if (pNode->val == t)
{
if (pPreNode != pNode)
pPreNode->next = pNode->next;
else
m_head = NULL;
free(pNode);
m_nListDataCount--;
return true;
}
pPreNode = pNode;
pNode = pNode->next;
}
return false;
}
//会删除链表中所有值为t的结点
template<class T>
bool slist<T>::removeAll(T &t)
{
bool flagDeleteNode = false;
Node<T> *pNode, *pPreNode;
pPreNode = pNode = m_head;
while (pNode != NULL)
{
if (pNode->val == t)
{
pPreNode->next = pNode->next;
free(pNode);
pNode = pPreNode->next;
m_nListDataCount--;
flagDeleteNode = true;
}
else
{
pPreNode = pNode;
pNode = pNode->next;
}
}
return flagDeleteNode;
}
template<class T>
void slist<T>::clear()
{
Node<T> *cur = m_head;
while (cur != NULL)
{
Node<T> *next = cur->next;
free(cur);
cur = next;
}
m_head = NULL;
}
该slist完成了从头部插入，查找和删除数据等链表的基本操作，下一篇将使用这个slist来完成一个哈希表，请关注下一篇——《STL系列之九 探索hash_set》
注1．STL分为很多版本，微软的VS系列使用的是PJ STL。而《STL源码剖析》书中主要使用SGI STL。
转载请标明出处，原文地址：http://blog.csdn.net/morewindows/article/details/7186471