linkedlist.h

该程序用ＶＣ实现了一个小型文件压缩与解压缩功能的程序

#ifndef LINKED_LIST_CLASS
#define LINKED_LIST_CLASS
#include <iostream.h>
#include <stdlib.h>
#include <iomanip.h>
#include <assert.h>
#include "ListNode.h"
template <class T>
class HashTable;				

template <class T>
class LinkedList
{
	friend class HashTable<T>;
private:
	ListNode<T> *header, *tail;

	ListNode<T>* GetNode(const T& item, 
		ListNode<T>* next = NULL);

public:
	LinkedList();
	LinkedList(const LinkedList<T>& list);
	~LinkedList();

	void ClearList();
	void CopyList(const LinkedList<T>& list);
	LinkedList<T>& operator = (const LinkedList<T>& list);
	
	void Print() const;
	bool IsEmpty() const;
	int  Length() const;
	
	ListNode<T>* Max() const;
	ListNode<T>* Min() const;
	
	ListNode<T>* Locate(int pos) const;
    ListNode<T>* 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<T>& item);

};
template <class T>
LinkedList<T>::LinkedList():header(NULL), tail(NULL)
{}

template <class T>
LinkedList<T>::~LinkedList()
{
	ClearList();
}

template <class T>
void LinkedList<T>::Print() const
{
	if(this->IsEmpty()) 
	{
		cout<<"链表为空！";
	}
	ListNode<T>* currPtr=header;
	while(currPtr!=NULL){
		cout<<setw(20)<<"currPtr node :"<<currPtr<<endl
		<<setw(20)<<"data:"<<currPtr->data<<endl
		<<setw(20)<<"next node :"<<currPtr->link<<endl;
		currPtr=currPtr->link;
	}
}

template <class T>
void LinkedList<T>::ClearList()
{
	ListNode<T> * currPtr=header;
	while(currPtr!=NULL){
		header=currPtr->link;
		delete currPtr;
		currPtr=header;
	}
	tail=NULL;
}

template<class T>
int LinkedList<T>::Length() const
{
	int j=0;
	ListNode<T> * currPtr=this->header;
	while(currPtr!=NULL){
		currPtr=currPtr->link;
		j++;
	}
	return j;
}

template <class T>
ListNode<T>* LinkedList<T>::GetNode(const T& item, 
		ListNode<T>* next )
{
	ListNode<T> * newNode=new ListNode<T>(item,next);
	assert(newNode!=NULL);
		return newNode;
}
 
template <class T>
bool LinkedList<T>::IsEmpty() const
{
	return header==NULL;
}

template <class T>
void LinkedList<T>::InsertFront(const T& item)
{
	ListNode<T> * newNode=this->GetNode(item);
	if(IsEmpty()){
		this->header=this->tail=newNode;
	}
	else{
		newNode->link=this->header;
		this->header=newNode;
	}
}

template <class T>
void LinkedList<T>::InsertRear(const T& item)
{
	ListNode<T> * newNode=this->GetNode(item);
	if(this->IsEmpty()){
		this->header=this->tail=newNode;
	}
	else{
		tail->link=newNode;
		this->tail=newNode;
	}
}

template<class T>
ListNode<T> * LinkedList<T>::Locate(int pos) const
{
	ListNode<T> * currPtr;
	int i=1;
	currPtr=header;
	while(currPtr!=NULL&&i<pos){
		currPtr=currPtr->link;
		i++;
	}
	return currPtr;
}

template <class T>
void LinkedList<T>::InsertAt(const T& item, int i)
{
	ListNode<T> * newNode=this->GetNode(item);
	ListNode<T> * 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<class T>
bool LinkedList<T>:: DeleteFront(T& item)
{
	ListNode<T> * currPtr=this->header;
	if(this->header==NULL){
		return false;
	}
	else{
		header=currPtr->link;
		item=currPtr->data;
		delete currPtr;
	}
	return true;
}

template<class T>
ListNode<T>* LinkedList<T>::IsMemberOf(const T& item) const
{
	ListNode<T> * currPtr=this->header;
	while(currPtr!=NULL&&currPtr->data!=item){
		currPtr=currPtr->link;
	}
	return currPtr;
}


template<class T>
int LinkedList<T>::Find(const T& item) const
{
	int j=1;
	ListNode<T> * currPtr=this->header;
	while(currPtr!=NULL&&currPtr->data!=item){
		currPtr=currPtr->link;
		j++;
	}
	return j;
}

template<class T>
bool LinkedList<T>::DeleteNode(const T& item)
{
	T it;
	if(this->IsEmpty())
	{
		return false;
	}
	ListNode<T> * currPtr=this->IsMemberOf(item);
	ListNode<T> * 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<class T>
bool LinkedList<T>::DeleteAt(int pos,T& item)
{
	if(this->IsEmpty()){
		return false;
	}
	ListNode<T> * currPtr=this->Locate(pos);
	ListNode<T> * 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<class T>
ListNode<T>* LinkedList<T>::Max() const
{
	ListNode<T> * currPtr=this->header;

	ListNode<T>* currPtr=currPtr->link,
		*MaxPtr=header;
	while(currPtr!=NULL)
	{
		if(MaxPtr->data < currPtr->data)
			MaxPtr=currPtr;
		currPtr=currPtr->link;
	}
	return MaxPtr;
}

template<class T>
ListNode<T>* LinkedList<T>::Min() const
{
	ListNode<T>* currPtr=header->link,
	*MinPtr=header;
	while(currPtr!=NULL)
	{
		if(MinPtr->data > currPtr->data)
			MinPtr=currPtr;
		currPtr=currPtr->link;
	}
	return MinPtr;
}


template<class T>
bool LinkedList<T>::DeleteMax(T& item)
{
	ListNode<T> * tempPtr=this->Max();
	if(tempPtr==NULL){
		return false;
	}
	item=tempPtr->data;
	this->DeleteNode(item);
	return true;
}

		
template<class T>
bool LinkedList<T>::DeleteMin(T& item)
{
	ListNode<T> * tempPtr=this->Min();
	if(tempPtr==NULL){
		return false;
	}
	item=tempPtr->data;
	this->DeleteNode(item);
	return true;
}

template<class T>
T& LinkedList<T>::DataOfNode(int i)
{
	assert(i>=0&&i<=this->Length());
	ListNode<T>* tempPtr=this->Locate(i);
	return tempPtr->data;
}


template<class T>
T& LinkedList<T>::operator [] (int i)
{
	return DataOfNode(i);
}

template<class T>
ostream& operator << (ostream& os, const LinkedList<T>& item)
{
	ListNode<T>* tempPtr=item.header;
	while(tempPtr!=NULL){
		os<<setw(20)<<"currPtr Node:"<<tempPtr<<endl;
		os<<setw(20)<<"data:"<<tempPtr->data<<endl;
		os<<setw(20)<<"next Node:"<<tempPtr->link<<endl;
		os<<endl;
		tempPtr=tempPtr->link;
	}
	return os;
}

template<class T>
istream& operator >> (istream& is, LinkedList<T>& item)
{
}
#endif