slist.h

一个我的数据结构解题集合

#ifndef SLIST_H__
#define SLIST_H__

#include <stdexcept>

template <typename T>
struct SListNode {	// 单链表的结点类型
	/* 默认构造函数
	 */
	SListNode()
		: next(0) {}

	/* 带参数的构造函数
	 * s: 下一结点 v: 数据
	 */
	SListNode(SListNode *s, const T& v)
		: next(s), data(v) {}

	SListNode *next;			// 下一个结点
	T data;						// 数据
}; // SListNode


template <typename T>
class SList {				// 循环单链表
private:
	SListNode<T>* head_;	// 头结点, 不用来存放数据
	SListNode<T>* tail_;	// 尾结点, 指向最后一个存放数据的结点
	int size_;				// 链表内元素的个数

	int *refcnt_;			// 引用计数

	/* 释放所有占用的资源
	 */
	void dispose() {
		Itor p, q;
		p = head_->next;
		while (p != head_) {	// 遍历删除所有结点
			q = p;
			p = p->next;
			delete q;
		}
		delete head_;			// 删除头结点
		delete refcnt_;			// 删除引用计数
	} // dispose()

public:

	typedef SListNode<T>* Itor;		// 迭代器类型

	/* 构造函数, 初始化为一个空链表
	 */
	SList() {
		head_ = new SListNode<T>;
		refcnt_ = new int(1);
		size_ = 0;
		head_->next = head_;
		tail_ = head_;
	} // SList()


	/* 拷贝构造函数, 通过引用计数实现句柄语义
	 * 注意: 通过拷贝构造函数得到的SList并不拥有独立的结点
	 */
	SList(const SList& that) {
		head_ = that.head_;
		tail_ = that.tail_;
		size_ = that.size_;
		refcnt_ = that.refcnt_;
		++(*refcnt_);				// 引用计数加1
	} // SList(const SList&)


	SList& operator=(const SList& that) {
		++(*that.refcnt_);			// 引用计数加1, 置于函数首行防止自复制产生错误

		if ( --(*refcnt_) <= 0 )
			dispose();

		head_ = that.head_;
		tail_ = that.tail_;
		size_ = that.size_;
		refcnt_ = that.refcnt_;

		return *this;
	} // operator=(const SList&)


	/* 析构函数, 如果没有别的引用, 释放所占用的资源
	 */
	~SList() {
		if ( --(*refcnt_) <= 0 ) 
			dispose();
	} // ~List()


	/* 查询链表的第一个元素的迭代器
	 * 链表元素在 [ begin(), end() ) 区间内
	 * 如果链表为空, 不抛出异常, 但 begin() == end()
	 */
	Itor begin() {
		return head_->next;
	} // begin()

	/* 查询链表的刚好超过最后一个元素的迭代器
	 * 链表元素在 [ begin(), end() ) 区间内
	 */
	Itor end() {
		return head_;
	} // end()

	/* 查询链表的头结点 (第一个保存数据的结点的前一结点) 的迭代器
	 * 链表元素在 ( head(), tail() ] 区间内
	 */
	Itor head() {
		return head_;
	} // head()

	/* 查询链表的尾结点 (最后一个保存数据的结点) 的迭代器
	 * 链表元素在 ( head(), tail() ] 区间内
	 * 如果链表为空, 不抛出异常, 但 head() == tail()
	 */
	Itor tail() {
		return tail_;
	} // tail()

	/* 查询链表中从pos开始的第一个元素e
	 * 如果找到, 返回其迭代器; 否则返回end()迭代器
	 */
	Itor search(Itor pos, const T& e) {

		// 遍历整个链表来查找
		for ( ; ( pos != end() ) && ( pos->data != e ); pos=pos->next )
			;		// 空循环体
		return pos;

	} // search(Itor, const T&)

	/* 在位置pos后插入元素e
	 */
	void insertAfter(Itor pos, const T& e) {
		Itor new_node =
			new SListNode<T>(pos->next, e);			// 生成新结点并插入
		pos->next = new_node;

		if ( pos == tail() )						// 需要调整tail_指针
			tail_ = new_node;

		++size_;									// 调整大小
	} // insertAfter(Itor, const T&)

	/* 删除位置pos的下一个元素
	 * pos->next必须不是end(), 即pos必须不是tail()
	 * 否则抛出std::invalid_argument异常
	 */
	void removeNext(Itor pos) {
		if ( pos == tail() ) {						// 前提被违反
			throw std::invalid_argument(
					"SList::removeNext(Itor pos) : requirement ( pos != tail() ) violated\n"
				);
		}

		if ( pos->next == tail() )					// 需要调整tail_指针
			tail_ = pos;

		Itor bye = pos->next;
		pos->next = bye->next;						// 逻辑上删除结点
		--size_;									// 调整大小

		delete bye;									// 释放结点 (物理上删除结点)
	} // removeNext(Itor pos)

	/* 查询链表的所含元素的个数
	 */
	int size() const {
		return size_;
	} // size() const

	/* 克隆函数, 声称一个本链表的克隆,
	 * 实现深拷贝 (SList的默认复制行为实现的是句柄语义, 不执行深拷贝)
	 */
	SList clone() {
		SList result;

		for (Itor i=begin(); i!=end(); i=i->next) {
			result.insertAfter(result.tail(), i->data);
		}

		return result;
	} // clone()

}; // SList


#endif  // SLIST_H__