linkedlist.h

该压缩文件夹内有诸多常用算法和数据结构的c++模板编程实现

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#define NULL 0 
template<class T>
class Node
{
	
public:	

	T info;
	Node<T> *next;
	Node (T a,Node<T> *p=NULL)
	{
		info=a;
		next=p;
	}
private:
};
template<class T>
class LinkedList
{
public:
	LinkedList()
	{
		head=tail=NULL;
	}
	int size()
	{
		if (head==NULL)
		{
			return 0;
		}
		Node<T> *h=head;
		int i;
		for (i=1;h!=tail;i++)
		{
			h=h->next;
		}
		return i;
	}
	T get(int index)
	{
		T e;
		if (index<0||index>=size())
		{
			return e;
		}
		Node<T> *h=head;
		int i;
		for (i=0;i!=index;i++)
		{
			h=h->next;
		}
		return h->info;
	}
	bool add(int index,T e)
	{
		if(index<0||index>size())
		{
			return false;
		}
		if (index==size())
		{
			add(e);
		}
		else
		{
			Node<T> *h=head,*pre=head;
			Node<T> *p=new Node<T>(e);
			int i;
			for(i=0;i!=index;i++)
			{
				pre=h;
				h=h->next;
			}
			if (index==0)
			{
				p->next=h;
				head=p;
			}
			else
			{
				p->next=h;
				pre->next=p;
			}
		}
		return true;
	}
	void add(T e)
	{
		if (head==NULL)
		{
			tail=new Node<T>(e);
			head=tail;
		}
		else
		{
			tail->next=new Node<T>(e);
			tail=tail->next;
		}
	}
	int find(T e)
	{
		int i;
		for (i=0;i<size();i++)
		{
			if (e==get(i))
			{
				return i;
			}
		}
		return -1;
	}
	bool remove(int index)
	{
		if (index<0||index>=size())
		{
			return false;
		}
		if(head==tail)
		{
			tail=NULL;
			delete head;
			head=NULL;
		}
		else if(index==0)
		{
			Node<T> *h=head;
			head=head->next;
			delete h;
		}
		else if (index==size()-1)
		{
			Node<T> *h=getNode(index-1);
			delete tail;
			h->next=NULL;
			tail=h;
		}
		else
		{
			Node<T>* pre=getNode(index-1);
			Node<T>* h=pre->next;
			pre->next=h->next;
			delete h;
		}
		return true;
	}
	void clear()
	{
		int i;
		for (i=0;i<size();i++)
		{
			remove(0);
		}
	}
	void gather(LinkedList<T> list)
	{
		int i;
		for (i=0;i<list.size();i++)
		{
			add(list.get(i));
		}
	}
	~LinkedList()
	{
		/*Node<T> *p=NULL;
		while(head==tail)
		{
			p=head;
			delete p;
			head=head->next;
		}
		delete head;*/
		clear();
	}
protected:
	Node<T> *head,*tail;
	Node<T> *getNode(int index)
	{
		if (index<0||index>=size())
		{
			return NULL;
		}
		int i;
		Node<T> *h=head;
		for (i=0;i!=index;i++)
		{
			h=h->next;
		}
		return h;
	}
private:
};
#endif