dllist.h

C、C++语言实现的数据结构重要算法和程序 比较全。

//--------------------------//
//                          //
//      双向有序链表类      //
//                          //
//--------------------------//
  
#if !defined(_INC_DLLIST_OO)
#define _INC_DLLIST_OO

#include<stdlib.h>
#include "D:\vc_h_file\DNode.h"

template<class T>
class DLList
{
 private:
	 DNode<T> *front,*currptr;
	 int size;
 public:
	 DLList();
     ~DLList();
     int Size()const;
     int Empty()const;
     int Locate(T item)const;
     T GetData(int pos)const;
     void Insert(T item);
     void Delete(int pos);
     void Clear();
};

template<class T>
DLList<T>::DLList()
{
	front=new DNode<T>;
	if(front==NULL)
	{
		cerr<<"overflow\n"<<endl;
		exit(1);
	}
	currptr=front;
	size=0;
}

template<class T>
DLList<T>::~DLList()
{
	while(front->NextDNodeRight()!=front)
		front->NextDNodeRight()->Delete();
	 delete front;
}

template<class T>
int DLList<T>::Size()const
{
	return(size);
}

template<class T>
int DLList<T>::Empty()const
{
	if(size==0)
		return(1);
	 return(0);
}

template<class T>
int DLList<T>::Locate(T item)const
{
	int i;
	DNode<T> *ptr;
	ptr=front->NextDNodeRight();
	for(i=0;ptr!=front;i++)
	{
		if(item==ptr->data)     
			return(i);
		ptr=ptr->NextDNodeRight();
	}
	return(-1);
}

template<class T>
T DLList<T>::GetData(int pos)const
{
	int i;
	DNode<T> *ptr;
	if(pos<0||pos>size-1)
	{
		cerr<<"Pos is out of range!\n"<<endl;
		exit(1);
	}
	ptr=front->NextDNodeRight();
	for(i=0;i<pos;i++)
		ptr=ptr->NextDNodeRight();
	return(ptr->data);
}

template<class T>
void DLList<T>::Insert(T item)
{
	DNode<T> *ptr;
	if(size==0)
	{
		front->InsertRight(item);
		currptr=front->NextDNodeRight();
	}
	else
	{
		ptr=currptr;
		if(item<=ptr->data)          
		{
			while(ptr!=front&&item<ptr->data)
				ptr=ptr->NextDNodeLeft();
			ptr->InsertRight(item);
			currptr=ptr->NextDNodeRight();
		}
		else
		{
			while(ptr!=front&&item>ptr->data)
				ptr=ptr->NextDNodeRight();
			ptr->InsertLeft(item);
			currptr=ptr->NextDNodeLeft();
		}
	}
	size++;
}

template<class T>
void DLList<T>::Delete(int pos)
{
	int i;
	DNode<T> *ptr;
	if(pos<0||pos>size-1)
	{
		cerr<<"Pos in Delete is illegal"<<endl;
		exit(1);
	}
	ptr=front->NextDNodeRight();
	for(i=0;i<pos;i++)
		ptr=front->NextDNodeRight();
	if(ptr==currptr)
	{
		if(ptr->NextDNodeRight()==front)
			currptr=ptr->NextDNodeLeft();
		else
			currptr=ptr->NextDNodeRight();
	}
	ptr->Delete();
	size--;
}

template<class T>
 void DLList<T>::Clear()
{
	while(front->NextDNodeRight()!=front)
		front->NextDNodeRight()->Delete();
	currptr=front;
	size=0;
}

#endif //_INC_DLLIST_OO