STL系列之八 slist单链表

长平狐 发布于 2012/12/10 17:19
阅读 42
收藏 0

微软的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


 


原文链接:http://blog.csdn.net/morewindows/article/details/7186471
加载中
返回顶部
顶部