list.h

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

#ifndef LIST_H__
#define LIST_H__

#include <stdexcept>
using namespace std;

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

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

	ListNode *prev, *next;		// 上一个结点和下一个结点
	T data;						// 数据
}; // ListNode


template <typename T>
class List {			// 循环双链表
private:
	ListNode<T>* head_;	// 头结点, 不用来存放数据
	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 ListNode<T>* Itor;		// 迭代器类型

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

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


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

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

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

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


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


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

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

	/* 查询链表中从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 insert(Itor pos, const T& e) {
		Itor new_node =
			new ListNode<T>(pos->prev, pos, e);		// 生成新结点并插入
		pos->prev->next = new_node;
		pos->prev = new_node;

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

	/* 删除位置pos的元素
	 * pos必须不是end(), 否则抛出std::invalid_argument异常
	 */
	void remove(Itor pos) {
		if ( pos == end() ) {						// 前提被违反
			throw std::invalid_argument(
					"List::remove(Itor pos) : requirement ( pos != end() ) violated\n"
				);
		}

		pos->prev->next = pos->next;				// 逻辑上删除结点
		pos->next->prev = pos->prev;

		--size_;									// 调整大小

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

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

	/* 查询链表是否为空
	 */
	bool isEmpty() const {
		return size_ == 0;
	} // isEmpty() const


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

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

		return result;
	} // clone()

}; // List


#endif  // LIST_H__