dlinlist.h

数据结构c++-书的一些源代码

template <class T> class DLinList;			//前视定义,否则友元无法定义
template <class T>							//模板类型为T
class DListNode
{
	friend class DLinList<T>;					//定义类DLinList<T>为友元
private:
	DListNode<T> *next;    				//指向后一结点的指针
	DListNode<T> *prior;	    				//指向前一结点的指针
	T data;								//定义为公有成员方便使用
public:
	//构造函数1,用于构造头结点
	DListNode(DListNode<T> *pNext = NULL, DListNode<T> *pPrior = NULL)
		{next = pNext;	prior = pPrior;}

	//构造函数2,用于构造其他结点
	DListNode(const T& item, DListNode<T> *pNext = NULL, DListNode<T> *pPrior = NULL)
		{data = item;	next = pNext; prior = pPrior;}

	~DListNode(void){}				//析构函数
};

//单链表类的定义
template <class T>
class DLinList
{
private:
	DListNode<T> *head;				//头指针
	int size;							//当前的数据元素个数
public:
	DLinList(void);						//构造函数
	~DLinList(void);					//析构函数

	int ListSize(void) const;				//取当前数据元素个数
	void Insert(const T& item, int i);		//前插
	T Delete(int i);						//删除
	T GetData(int i);					//取元素
};
 
//单链表类的实现  
template <class T> 
DLinList<T>::DLinList(void)					//构造函数
{
	head = new DListNode<T>();			//头指针指向头结点
//	head->next = head;
	head->prior = head;			
	size = 0;							//size的初值为0
}

template <class T>
DLinList<T>::~DLinList(void)				//析构函数
{ 
	DListNode<T> *p, *q;
	p = head;						//p指向第一个结点
	while(p != NULL)				//循环释放结点空间直至初始化状态
	{
   		q = p;
		p = p->next;
		delete q;
	}
	size = 0;							//结点个数置为初始化值0
	head = NULL;
}

template <class T>
int DLinList<T>::ListSize(void) const			//取当前数据元素个数并返回
{
	return size;
}

template <class T>
void DLinList<T>::Insert(const T& item, int i)				//插入
//在第i个结点后插入一个元素值为item的新结点
//参数i的取值范围为：0≤i≤size
{
	if(i < 0 || i > size)
	{
		cout << "参数i越界出错！"  << endl;
		exit(0);
	}

	DListNode<T> *p = head->next;			//p指向第一个数据元素结点
	int j = 0;								//从0开始计数
	while(p != NULL && j < i)				//寻找第i个结点
	{
		p = p->next;
		j++;
	}

	//构造新结点p，p的data域值为item，next域值为 p->next
	DListNode<T> *q = new DListNode<T>(item, p->prior->next, p->prior);

	p->prior->next = q;								//新结点插入第i个结点前
	p->prior = q;								//新结点插入第i个结点前
	size++;									//元素个数加1
}

template <class T>
T DLinList<T>::Delete(int i)				//删除
//删除第i个数据元素并返回。参数i的取值范围为：0≤i≤size-1
{
	if(size == 0) 
	{
		cout << "链表已空无元素可删！" << endl;
		exit(0);
	}

	if(i < 0 || i > size-1)
	{
		cout << "参数i越界出错！" << endl;
		exit(0);
	}

	
	DListNode<T> *p = head->next;			//p指向第一个数据元素结点
	int j = 0;								//从0开始计数
	while(p != NULL && j < i)				//寻找第i个结点
	{
		p = p->next;
		j++;
	}

	p->prior->next = p->next;					//第i个结点脱链
	p->next->prior = p->prior;					//第i个结点脱链
	T x = p->data;
	delete p;								//释放第i个结点空间
	size--;									//结点个数减1
	return x;								//返回第i个结点的data域值
}

template <class T>
T DLinList<T>::GetData(int i)				//取数据元素
//取第i个数据元素并返回。参数i的取值范围为：0≤i≤size-1
{
	if(i < 0 || i > size-1)
	{
		cout << "参数i越界出错！" << endl;
		exit(0);
	}

	DListNode<T> *p = head->next;			//p指向第一个数据元素结点
	int j = 0;								//从0开始计数
	while(p != NULL && j < i)				//寻找第i个结点
	{
		p = p->next;
		j++;
	}
	return p->data;
}