list.h

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

#ifndef LIST_H__
#define LIST_H__

#include <stdexcept>

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_;			// 链表内元素的个数

public:

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

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

	/* 析构函数, 释放所占用的资源
	 */
	~List() {
		Itor p, q;
		p = head_->next;
		while (p != head_) {	// 循环删除所有结点
			q = p;
			p = p->next;
			delete q;
		}
		delete head_;			// 删除头结点
	} // ~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

}; // List


#endif  // LIST_H__