linkedlist.h

字符频度统计

#ifndef LINKED_LIST_CLASS
#define LINKED_LIST_CLASS

#include "ListNode.h"

template <class T>
class LinkedList
{
public:

	LinkedList();
	virtual ~LinkedList();
	void ClearList();
	void InsertRear(const T & item);
	bool Find(const T & item);
	bool Remove(const T & item);
	ListNode<T> *FindPrev(const T & item);
	ListNode<T> *FindItem(const T & item);
	ListNode<T> *GetHead() const;
	int Length();
	friend ostream & operator<<(ostream & os,const LinkedList<T> & list);
	int IsEmpty(){return head->GetNextNode()==NULL;}

private:
	ListNode<T> *head,*tail;
};

template <class T>
LinkedList<T>::LinkedList()
{
	head=tail=new ListNode<T>;
}

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

template <class T>
int LinkedList<T>::Length()
{
	ListNode<T> *p=head->GetNextNode();
	int count=0;
	while(p!=NULL)
	{
		count++;
		p=p->GetNextNode();
	}
	return count;
}

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

template <class T>
void LinkedList<T>::InsertRear(const T & item)
{
	tail=tail->link=new ListNode<T>(item,tail->link);
}

template <class T>
bool LinkedList<T>::Find(const T & item)
{
	ListNode<T> *p=head->link;
	if(p==NULL)
		return 0;
	while(p!=NULL)
	{
		if(p->data==item)
			return 1;
		p=p->link;
	}
	return 0;
}

template <class T>
ListNode<T> * LinkedList<T>::FindItem(const T & item)
{
	if(head->link==NULL)
		return NULL;
	ListNode<T> *p=head->link;
	while(p!=NULL)
	{
		if(p->data==item)
		{
			return p;
		}
		p=p->link;
	}
	return NULL;
}

template <class T>
ListNode<T> * LinkedList<T>::FindPrev(const T & item)
{
	if(!Find(item))
		return NULL;
	ListNode<T> *Prev,*p;
	Prev=head;
	p=head->link;
	while(p!=NULL&&p->data!=item)
	{
		p=p->link;
	}
	while(Prev->link!=p)
	{
		Prev=Prev->link;
	}
	return Prev;
}

template <class T>
ListNode<T> * LinkedList<T>::GetHead() const
{
	return head;
}

template <class T>
bool LinkedList<T>::Remove(const T & item)
{
	ListNode<T> *p=FindPrev(item),*q;
	q=p->link;
	p->link=q->link;
	if(q==tail)
		tail=p;
	delete q;
	return 1;
}

template <class T>
ostream & operator<<(ostream & os,const LinkedList<T> & list)
{
	ListNode<T> *p=list.GetHead()->GetNextNode();
	while(p!=NULL)
	{
		os<<setw(6)<<p->data<<" "<<endl;
		p=p->GetNextNode();
	}
	return os;
}


#endif