线性表——（3）双向链表

#include"ListNode.h"

template<class T>
class DoubleList
{
public:
	DoubleList() {
		head = new ListNode<T>();
		head->p_prior = head;
		head->p_next = head;
	}
	~DoubleList() {
		Clear();
		delete head;
	}
	void Clear();	// 清空
	int Length() const; // length
	ListNode<T>* Find(T item);	// 查找item，返回指针，找不到返回空
	int GetItem(int n, T &targ);	// 查找n号元素，存入targ
	int Insert(int n, const T targ);	//	将targ插入n号前
	int Delete(int n);	// 删除n号

private:
	ListNode<T>* head;
};

template<class T>
inline void DoubleList<T>::Clear()
{
	ListNode<T>* p = head->p_next;
	ListNode<T>* pdel;
	while (p != head) {
		pdel = p;
		p = pdel->p_next;
		delete pdel;
	}
	p->p_prior = head;
	p->p_next = head;
}

template<class T>
inline int DoubleList<T>::Length() const
{
	int count = 0;
	ListNode<T>* p = head->p_next;
	while (p != head) {
		++count;
		p = p->p_next;
	}
	return count;
}

template<class T>
inline ListNode<T>* DoubleList<T>::Find(T item)
{
	ListNode<T>* prior = head->p_prior;
	ListNode<T>* next = head->p_next;
	while (prior->p_next != next && prior != p_next) {
		if (prior->data == item)
			return prior;
		if (next->data == item)
			return next;
		prior = prior->p_prior;
		next = next->p_next;
	}
	return NULL;
}

template<class T>
inline int DoubleList<class T>::GetItem(int n, T & targ)
{
	if (n < 0)
		return 0;
	ListNode<T>* p = head;
	for (int i = 0; i < n; ++i) {
		p = p->p_next;
		if (p == head)
			return 0;
		T data = p->data;
		return data;
	}
}

template<class T>
inline int DoubleList<T>::Insert(int n, const T targ)
{
	if (n < 0)
		return 0;
	ListNode<T>* p_newnode = new ListNode<T>(targ);
	ListNode<T>* p = head;
	for (int i = 0; i < n; ++i) {
		p = p->p_next;
		if (p == head)
			return 0;
	}
	p_newnode->p_next = p->p_next;
	p_newnode->p_prior = p;
	p->p_next = p_newnode;
	p->p_next->p_prior = p_newnode;
	return 1;
}

template<class T>
inline int DoubleList<T>::Delete(int n)
{
	if (n < 0)
		return 0;
	ListNode<T>* p = head;
	ListNode<T>* pdel;
	for (int i = 0; i < n; ++i) {
		p = p->p_next;
		if (p == head)
			return 0;
	}
	pdel = p;
	p->p_prior->p_next = p->p_next;
	p->p_next->p_prior = p->p_prior;
	delete pdel;
	return 1;
}