www.pudn.com > compressor.zip > LinkedList.h

#ifndef LINKED_LIST_CLASS 
#define LINKED_LIST_CLASS 
#include  
#include  
#include  
#include  
#include "ListNode.h" 
template  
class HashTable;				 
 
template  
class LinkedList 
{ 
	friend class HashTable; 
private: 
	ListNode *header, *tail; 
 
	ListNode* GetNode(const T& item,  
		ListNode* next = NULL); 
 
public: 
	LinkedList(); 
	LinkedList(const LinkedList& list); 
	~LinkedList(); 
 
	void ClearList(); 
	void CopyList(const LinkedList& list); 
	LinkedList& operator = (const LinkedList& list); 
	 
	void Print() const; 
	bool IsEmpty() const; 
	int  Length() const; 
	 
	ListNode* Max() const; 
	ListNode* Min() const; 
	 
	ListNode* Locate(int pos) const; 
    ListNode* IsMemberOf(const T& item) const; 
    int Find(const T& item) const; 
 
	T& DataOfNode(int i); 
	T& operator [] (int i); 
 
	void InsertAt(const T& item, int i); 
	void InsertFront(const T& item); 
	void InsertRear(const T& item); 
	void InsertOrder(const T& item); 
 
 
    bool DeleteFront(T& item); 
	bool DeleteNode(const T& item); 
	bool DeleteAt(int pos, T& item); 
	bool DeleteMax(T& item); 
	bool DeleteMin(T& item); 
 
 
	friend ostream& operator << (ostream& os,  
		                         const LinkedList& item); 
 
}; 
template  
LinkedList::LinkedList():header(NULL), tail(NULL) 
{} 
 
template  
LinkedList::~LinkedList() 
{ 
	ClearList(); 
} 
 
template  
void LinkedList::Print() const 
{ 
	if(this->IsEmpty())  
	{ 
		cout<<"Á´±íΪ¿Õ£¡"; 
	} 
	ListNode* currPtr=header; 
	while(currPtr!=NULL){ 
		cout<data<link<link; 
	} 
} 
 
template  
void LinkedList::ClearList() 
{ 
	ListNode * currPtr=header; 
	while(currPtr!=NULL){ 
		header=currPtr->link; 
		delete currPtr; 
		currPtr=header; 
	} 
	tail=NULL; 
} 
 
template 
int LinkedList::Length() const 
{ 
	int j=0; 
	ListNode * currPtr=this->header; 
	while(currPtr!=NULL){ 
		currPtr=currPtr->link; 
		j++; 
	} 
	return j; 
} 
 
template  
ListNode* LinkedList::GetNode(const T& item,  
		ListNode* next ) 
{ 
	ListNode * newNode=new ListNode(item,next); 
	assert(newNode!=NULL); 
		return newNode; 
} 
  
template  
bool LinkedList::IsEmpty() const 
{ 
	return header==NULL; 
} 
 
template  
void LinkedList::InsertFront(const T& item) 
{ 
	ListNode * newNode=this->GetNode(item); 
	if(IsEmpty()){ 
		this->header=this->tail=newNode; 
	} 
	else{ 
		newNode->link=this->header; 
		this->header=newNode; 
	} 
} 
 
template  
void LinkedList::InsertRear(const T& item) 
{ 
	ListNode * newNode=this->GetNode(item); 
	if(this->IsEmpty()){ 
		this->header=this->tail=newNode; 
	} 
	else{ 
		tail->link=newNode; 
		this->tail=newNode; 
	} 
} 
 
template 
ListNode * LinkedList::Locate(int pos) const 
{ 
	ListNode * currPtr; 
	int i=1; 
	currPtr=header; 
	while(currPtr!=NULL&&ilink; 
		i++; 
	} 
	return currPtr; 
} 
 
template  
void LinkedList::InsertAt(const T& item, int i) 
{ 
	ListNode * newNode=this->GetNode(item); 
	ListNode * currPtr; 
	currPtr=this->Locate(i-1); 
	if(this->IsEmpty()){ 
		this->header=this->tail=newNode; 
	} 
	else if(currPtr==header!=NULL){ 
		newNode->link=header; 
		header=newNode; 
	} 
	else if(currPtr->link==NULL){ 
		tail->link=newNode; 
		tail=newNode; 
	} 
	else{ 
		newNode->link=currPtr->link; 
		currPtr->link=newNode; 
	} 
} 
 
template 
bool LinkedList:: DeleteFront(T& item) 
{ 
	ListNode * currPtr=this->header; 
	if(this->header==NULL){ 
		return false; 
	} 
	else{ 
		header=currPtr->link; 
		item=currPtr->data; 
		delete currPtr; 
	} 
	return true; 
} 
 
template 
ListNode* LinkedList::IsMemberOf(const T& item) const 
{ 
	ListNode * currPtr=this->header; 
	while(currPtr!=NULL&&currPtr->data!=item){ 
		currPtr=currPtr->link; 
	} 
	return currPtr; 
} 
 
 
template 
int LinkedList::Find(const T& item) const 
{ 
	int j=1; 
	ListNode * currPtr=this->header; 
	while(currPtr!=NULL&&currPtr->data!=item){ 
		currPtr=currPtr->link; 
		j++; 
	} 
	return j; 
} 
 
template 
bool LinkedList::DeleteNode(const T& item) 
{ 
	T it; 
	if(this->IsEmpty()) 
	{ 
		return false; 
	} 
	ListNode * currPtr=this->IsMemberOf(item); 
	ListNode * prevPtr=Locate(this->Find(item)-1); 
	if(currPtr==NULL){ 
		return false; 
	} 
	else{ 
		if(currPtr==header){ 
			DeleteFront(it); 
		} 
		else{ 
 		  prevPtr->link=currPtr->link; 
		  delete currPtr; 
		} 
		return true; 
	} 
} 
 
template 
bool LinkedList::DeleteAt(int pos,T& item) 
{ 
	if(this->IsEmpty()){ 
		return false; 
	} 
	ListNode * currPtr=this->Locate(pos); 
	ListNode * prevPtr=this->Locate(pos-1); 
	if(currPtr==NULL){ 
		return false; 
	} 
	else{ 
		if(currPtr==header){ 
			this->DeleteFront(item); 
		} 
		else{ 
			item=currPtr->data; 
			prevPtr->link=currPtr->link; 
			delete currPtr; 
		} 
		return true; 
	} 
} 
 
template 
ListNode* LinkedList::Max() const 
{ 
	ListNode * currPtr=this->header; 
 
	ListNode* currPtr=currPtr->link, 
		*MaxPtr=header; 
	while(currPtr!=NULL) 
	{ 
		if(MaxPtr->data < currPtr->data) 
			MaxPtr=currPtr; 
		currPtr=currPtr->link; 
	} 
	return MaxPtr; 
} 
 
template 
ListNode* LinkedList::Min() const 
{ 
	ListNode* currPtr=header->link, 
	*MinPtr=header; 
	while(currPtr!=NULL) 
	{ 
		if(MinPtr->data > currPtr->data) 
			MinPtr=currPtr; 
		currPtr=currPtr->link; 
	} 
	return MinPtr; 
} 
 
 
template 
bool LinkedList::DeleteMax(T& item) 
{ 
	ListNode * tempPtr=this->Max(); 
	if(tempPtr==NULL){ 
		return false; 
	} 
	item=tempPtr->data; 
	this->DeleteNode(item); 
	return true; 
} 
 
		 
template 
bool LinkedList::DeleteMin(T& item) 
{ 
	ListNode * tempPtr=this->Min(); 
	if(tempPtr==NULL){ 
		return false; 
	} 
	item=tempPtr->data; 
	this->DeleteNode(item); 
	return true; 
} 
 
template 
T& LinkedList::DataOfNode(int i) 
{ 
	assert(i>=0&&i<=this->Length()); 
	ListNode* tempPtr=this->Locate(i); 
	return tempPtr->data; 
} 
 
 
template 
T& LinkedList::operator [] (int i) 
{ 
	return DataOfNode(i); 
} 
 
template 
ostream& operator << (ostream& os, const LinkedList& item) 
{ 
	ListNode* tempPtr=item.header; 
	while(tempPtr!=NULL){ 
		os<data<link<link; 
	} 
	return os; 
} 
 
template 
istream& operator >> (istream& is, LinkedList& item) 
{ 
} 
#endif