www.pudn.com > 编译原理LALR(1)文法分析器.zip > List.h

/********************/ 
/*	  链表模板类	*/ 
/********************/ 
 
#include  
#include  
 
template class List;				 
 
template 
class ListNode 
{ 
friend class List; 
friend class CGRAMA;						 
public: 
	ListNode():link(NULL){ }							//默认构造函数 
	ListNode(const Type &item):data(item),link(NULL){ }	//带参数的构造函数 
private: 
	Type data; 
	ListNode *link; 
}; 
 
template 
class List 
{ 
friend class CGRAMA; 
public: 
	List():first(NULL),last(NULL){ }					//默认构造函数 
 
	void MakeEmpty()									//链表置空 
	{ 
		ListNode *q; 
		while(first!=NULL){ 
			q=first; 
			first=q->link; 
			delete q; 
		} 
		delete first; 
	} 
 
	int Length() const									//返回链表长度 
	{ 
		int i(0); 
		for(ListNode *p=first;p;p=p->link) i++; 
		return i; 
	} 
 
	ListNode *Find(Type value) 
	{ 
			ListNode *p=first->link; 
		while(p!=NULL&&p->data!=value)	p=p->link; 
		return p; 
	} 
 
	void Insert(Type value)								//插入结点 
	{	 
		if(first==NULL)									//若头结点为空 
		{ 
			first=last=new ListNode(value); 
			last->link=NULL; 
		} 
		else 
		{ 
			ListNode *temp=new ListNode(value); 
			last->link=temp; 
			last=last->link; 
			last->link=NULL; 
		} 
	} 
 
	void Remove(Type value)								//删除结点 
	{ 
		ListNode *p; 
		if(first==NULL) return; 
		if(first->data==value){							//要删除的结点是头结点 
			p=first;							 
			first=first->link; 
			delete p; 
			return ; 
		} 
		else{											//要删除的结点不是头结点 
			for(ListNode *q=first;q->link;q=q->link)	 
				if(q->link->data==value){ 
					p=q->link; 
					q->link=p->link; 
					delete p; 
					return ; 
				} 
		} 
	} 
 
	void Print()										//输出链表元素 
	{ 
		for(ListNode *p=first;p;p=p->link) 
			cout<data; 
	} 
 
	void PutToArray(char *&buf)							//输出到数组 
	{ 
		int len=Length(); 
		buf=new char[len]; 
		int i=0; 
		for(ListNode *p=first;p;p=p->link) 
		{ 
			buf[i]=p->data; 
			i++; 
		} 
	} 
 
	void DelRepeated()									//删除重复元素 
	{ 
		ListNode *q,*t,*p; 
		for(q=first;q;q=q->link) 
		{ 
			p=q; 
			while(p->link){ 
				if(p->link->data==q->data){ 
					t=p->link; 
					p->link=t->link; 
					delete t; 
					} 
				else p=p->link; 
			} 
		} 
	} 
 
	int Contains(Type value)							//是否包含该元素 
	{ 
		for(ListNode *p=first;p;p=p->link) 
			if(p->data==value) 
				return 1; 
		return 0; 
	} 
 
	int GetCode(Type value)								//返回元素在链表中的位置 
	{ 
		int i=0; 
		for(ListNode *p=first;p;p=p->link,i++) 
			if(p->data==value) 
				return i; 
		return 0; 
	} 
 
	int operator == (List &right)					//重载"==" 
	{ 
		ListNode *p; 
		for(p=first;p;p=p->link) 
			if(right.Contains(p->data)==0) 
				return 0; 
		for(p=right.first;p;p=p->link) 
			if(Contains(p->data)==0) 
				return 0; 
		return 1; 
	} 
 
	List &operator = (const List &right)	//重载"=" 
	{ 
		MakeEmpty(); 
		Add(right); 
		return *this; 
	} 
 
	int IsEmpty()										//判断链表是否为空 
	{ 
		if(Length()==0) 
			return 1; 
		return 0; 
	} 
 
	void Add(const List &right)							//加入一个链表所有元素 
	{ 
		for(ListNode *p=right.first;p;p=p->link) 
		{ 
			if(!Contains(p->data)) 
			 Insert(p->data); 
		} 
	} 
 
	int MergeString(List &right) 
	{ 
		int len1=this->Length(); 
		int len2=right.Length(); 
		int ret=0; 
		ListNode *p,*q; 
		if(len1==len2){ 
			for(p=this->first,q=right.first;p;p=p->link,q=q->link) 
			{	 
				if(q->data.string==p->data.string) continue; 
				if(q->data.string.IsEmpty()) continue; 
				if(p->data.Merge(q->data)==1) ret=1; 
			} 
		} 
		return ret; 
	} 
private: 
	ListNode *first,*last; 
};