dclinkedlist.h

该程序是用vc开发的对动态数组进行管理的DLL

/* 双向循环链表
 * 
 */

#ifndef DOUBLE_CIRCULAR_LINKEDLIST_CLASS
#define DOUBLE_CIRCULAR_LINKEDLIST_CLASS

#include <stdlib.h>
#include "dnode.h"

template <class T>
class DCLinkedList
{
protected:
	// 指向表头的指针和当前节点的指针
	DNode<T> *header, *currPtr;
		
	// 表中的元素个数和当前的位置值
	int size;

public:
	// 构造函数
	DCLinkedList(void);
	DCLinkedList(const DCLinkedList<T> &L);

	// 析构函数
	~DCLinkedList(void);

	// 赋值运算符、相等运算符
	DCLinkedList<T>& operator= (const DCLinkedList<T> &L);
	bool operator== (const DCLinkedList<T>& L) const;

	// 检查表状态的函数
	int ListSize(void) const;               
	bool ListEmpty(void) const;

	// 遍历表的函数
	void Reset(bool bheader = true);	// 是从表头开始遍历，还是表尾（反向遍历）
	void Next(void);
	void Prev(void);
	bool EndOfList(void) const;

	// 插入函数
	void InsertList(const DCLinkedList<T>& L);
	void InsertFront(const T &item);
	void InsertRear(const T &item);
	void InsertAt(const T &item);
	void InsertAfter(const T &item);

	// 删除函数
	void DeleteFront(void);
	void DeleteRear(void);
	void DeleteAt(void);

	// 访问／修改数据
	T& Data(void);
	bool Find(const T& item);

	// 清空表的函数
	void ClearList(void);
};

// 构造函数
template <class T>
DCLinkedList<T>::DCLinkedList(void):size(0)
{
	// 创建“哨位”节点
	currPtr = header = new DNode<T>();
}

// 构造函数
template <class T>
DCLinkedList<T>::DCLinkedList(const DCLinkedList<T>& L):size(0)
{
	// 创建“哨位”节点
	currPtr = header = new DNode<T>();
	InsertList(L);
}

// 析构函数
template <class T>
DCLinkedList<T>::~DCLinkedList(void)
{
	ClearList();
	delete header;
}

// 将 L 拷贝到当前表尾
template <class T>
void DCLinkedList<T>::InsertList(const DCLinkedList<T> &L)
{
	// 用指针 P 遍历表（header 是“哨位”节点）
	DNode<T> *p = L.header->right;

	// 往当前表的表尾插入 L 的每个元素
	while (p != L.header)
	{
		InsertRear(p->data);
		p = p->right;
	}
}

template <class T>
int DCLinkedList<T>::ListSize(void) const
{
	// 不包括哨位节点
	return size;
}

template <class T>
bool DCLinkedList<T>::ListEmpty(void) const
{
	return (size == 0);
}

template <class T>
void DCLinkedList<T>::Reset(bool bheader)
{
	if (bheader) 
		currPtr = header->right;	// 真正的表头
	else
		currPtr = header->left;	// 表尾
}

template <class T>
void DCLinkedList<T>::Next(void)
{
	currPtr = currPtr->right;
}

template <class T>
void DCLinkedList<T>::Prev(void)
{
	currPtr = currPtr->left;
}

template <class T>
bool DCLinkedList<T>::EndOfList(void) const
{
	return (currPtr == header);
}

// 插入函数
template <class T>
void DCLinkedList<T>::InsertFront(const T &item)
{
	Reset();
	InsertAt(item);
}

template <class T>
void DCLinkedList<T>::InsertRear(const T &item)
{
	currPtr = header;
	InsertAt(item);
}

template <class T>
void DCLinkedList<T>::InsertAt(const T &item)
{
	DNode<T> *newNode = new DNode<T>(item);
	currPtr->InsertLeft(newNode);
	currPtr = newNode;
	size++;
}

template <class T>
void DCLinkedList<T>::InsertAfter(const T &item)
{
	Next();
	InsertAt(item);
}

// 删除函数
template <class T>
void DCLinkedList<T>::DeleteFront(void)
{
	Reset();
	DeleteAt();
}

template <class T>
void DCLinkedList<T>::DeleteRear(void)
{
	Reset(false);
	DeleteAt();
}

template <class T>
void DCLinkedList<T>::DeleteAt(void)
{
	// 若表为空或已到表尾，则返回
	if (currPtr == header)
		return;

	DNode<T> *p = currPtr->right;
	delete (currPtr->DeleteNode());
	currPtr = p;
	size --;
}

// 访问／修改数据
template <class T>
T& DCLinkedList<T>::Data(void)
{
	// 若表为空或已到表尾，则出错
	if (currPtr == header)
		throw "DCLinkedList::Data: invalid reference";

	return currPtr->data;
}

template <class T>
bool DCLinkedList<T>::Find(const T& item)
{
	for (Reset(); !EndOfList(); Next())
		if (Data() == item)
			return true;

	return false;
}

template <class T>
DCLinkedList<T>& DCLinkedList<T>::operator= (const DCLinkedList<T>& L)
{
	if (this == &L)      // 无法赋值给自身
		return *this;
	
	ClearList();
	InsertList(L);
	return *this;
}

template <class T>
void DCLinkedList<T>::ClearList(void)
{
	Reset();
	while (currPtr != header)
		DeleteAt();
}

template <class T>
bool DCLinkedList<T>::operator== (const DCLinkedList<T>& L) const
{
	// 如果大小不同，返回
	if (size != L.size)
		return false;
	
	// 判断两链表的元素是否相等（与元素的顺序无关）
	DNode<T> *p = header->right, *pl;

	// p 中的每个元素 pl 中都能找到吗
	while (p != header)
	{
		pl = L.header->right;
		while (pl != L.header)
		{
			if (p->data == pl->data)
				break;
			pl = pl->right;
		}
		if (pl == L.header)	// 没找到
			return false;
		p = p->right;
	}
	
	// pl 中的每个元素 p 中都能找到吗
	pl = L.header->right;
	while (pl != L.header)
	{
		p = header->right;
		while (p != header)
		{
			if (pl->data == p->data)
				break;
			p = p->right;
		}
		if (p == header)	// 没找到
			return false;
		pl = pl->right;
	}
	
	return true;
}

#endif	// DOUBLE_CIRCULAR_LINKEDLIST_CLASS