dblinkedlist.h

数据结构及C++相关的一些小程序

template<class T>
class DbLinkedList
{
	public:
		DbLinkedList();                                //缺省参数的构造函数
		DbLinkedList(T a);                             //以头节点内容为参数的构造函数
		void display() const;                          //显示链表的全部内容
		T front() const;                               //返回链表头节点的值
		T back() const;                                //返回链表尾节点的值
		void insertNode(const T& insertItem);          //在当前操作位置插入一个节点
		void push_back(const T& item);                 //在链表尾部之后添加一个节点
        void push_front(const T& item);                //在链表头部之前添加一个节点
		void destroy();                                //删除给链表分配的内存空间
		friend void DoubleSort( T a[], int n);
	private:
		node<T> *currentPos;                           //指向当前操作的节点的位置
		node<T> *head;                                 //指向头节点的指针
		node<T> *tail;                                 //指向尾节点的指针
};


template<class T>
DbLinkedList<T>::DbLinkedList()
{
   currentPos=NULL;
   head=NULL;
   tail=NULL;
}


template<class T>
DbLinkedList<T>::DbLinkedList(T a)
{  
   head=new node<T>(a);
   tail=head;
   currentPos=head;
}


template<class T>
void DbLinkedList<T>::display() const
{
	node<T> *current;
	current=head;
	while(current!=NULL)
	{
		cout<<current->info<<" ";
		current=current->next;
	}
}


template<class T>
T DbLinkedList<T>::front() const
{
	return head->info;
}


template<class T>
T DbLinkedList<T>::back() const
{
	return tail->info;
}


template<class T>
void DbLinkedList<T>::insertNode(const T& insertItem)
{
	node<T> *trailCurrent;
	node<T> *newNode;
	newNode=new node<T>(insertItem);
	trailCurrent=currentPos->prev;
	trailCurrent->next=newNode;
	newNode->prev=trailCurrent;
    newNode->next=currentPos;
	currentPos->prev=newNode;
	currentPos=newNode;
}


template<class T>
void DbLinkedList<T>::push_back(const T& item)
{
	node<T> *newNode;
	newNode=new node<T>(item);
	tail->next=newNode;
	newNode->prev=tail;
    newNode->next=NULL;
	tail=tail->next;
	currentPos=tail;
}


template<class T>
void DbLinkedList<T>::push_front(const T& item)
{
	node<T> *newNode;
    newNode=new node<T>(item);
    head->prev=newNode;
    newNode->next=head;
	newNode->prev=NULL;
	head=newNode;
	currentPos=head;
}


template<class T>
void DbLinkedList<T>::destroy()
{
    node<T> *temp;
	while(head!=NULL)
	{
		temp=head;
		head=head->next;
		delete temp;
	}
	tail=NULL;
}