list.h

实现了图的主要操作:（1）分别用邻接矩阵和邻接表实现图的基本操作（包括图的广度和深度优先搜索）；(2）判断该图是否连通

#include "link.h"

template <class Elem> 
class mylist 
	: public Link<Elem>
{
	private:
		Link<Elem> *head;
		Link<Elem> *tail;
		Link<Elem> *fence;
		int leftcnt,rightcnt;
		void init()
		{
			fence = tail = head = new Link<Elem>;
			leftcnt = rightcnt = 0;
		}
		void removeall()
		{
			while(head != NULL)
			{
				fence = head;
				head = head->next;
				delete fence;
			}
		}
	public:
		mylist() {init();}
		~mylist() {removeall();}
		void clear() {removeall(); init();}
		void setStart() {fence =  head; rightcnt += leftcnt; leftcnt = 0;}
		void setEnd() {fence = tail; leftcnt += rightcnt; rightcnt = 0;}
		bool insert(const Elem & E)
		{
			fence->next = new Link<Elem> (E,fence->next);
			if(tail == fence) tail = fence->next;
			rightcnt++;
			return true;
		}
		bool append(const Elem & E)
		{
			tail = tail->next = new Link<Elem> (E,NULL);
			rightcnt++;
			return true;	
		}
		bool remove(Elem & E)
		{
			if(fence->next == NULL) return false;
			E = fence->next->element;
			Link<Elem> * tmp = fence->next;
			if(tail == tmp) tail = fence;
			delete tmp;
			return true;
		}
		int leftLength() {return leftcnt;}
		int rightlength() {return rightcnt;}
		bool setPos(int pos)
		{
			if(pos<0 || pos > rightcnt+leftcnt) return false;
			fence = head;
			for(int i=0;i<pos;i++) 
			{
				fence = fence->next;
			}
			return true;
		}
		bool next()
		{
			if(fence == tail) return false;
			fence = fence->next;
			rightcnt--;
			leftcnt++;
			return true;
		}
		bool getValue(Elem & it)
		{
			if(rightcnt == 0) return false;
			it = fence->next->element;
			return true;
		}
};