list.h

lalr1编译器

/********************/
/*	  链表模板类	*/
/********************/

#include <stdlib.h>
#include <iostream.h>

template<class Type> class List;				

template<class Type>
class ListNode
{
friend class List<Type>;
friend class CGRAMA;						
public:
	ListNode():link(NULL){ }							//默认构造函数
	ListNode(const Type &item):data(item),link(NULL){ }	//带参数的构造函数
private:
	Type data;
	ListNode<Type> *link;
};

template<class Type>
class List
{
friend class CGRAMA;
public:
	List():first(NULL),last(NULL){ }					//默认构造函数

	void MakeEmpty()									//链表置空
	{
		ListNode<Type> *q;
		while(first!=NULL){
			q=first;
			first=q->link;
			delete q;
		}
		delete first;
	}

	int Length() const									//返回链表长度
	{
		int i(0);
		for(ListNode<Type> *p=first;p;p=p->link) i++;
		return i;
	}

	ListNode<Type> *Find(Type value)
	{
			ListNode<Type> *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<Type>(value);
			last->link=NULL;
		}
		else
		{
			ListNode<Type> *temp=new ListNode<Type>(value);
			last->link=temp;
			last=last->link;
			last->link=NULL;
		}
	}

	void Remove(Type value)								//删除结点
	{
		ListNode<Type> *p;
		if(first==NULL) return;
		if(first->data==value){							//要删除的结点是头结点
			p=first;							
			first=first->link;
			delete p;
			return ;
		}
		else{											//要删除的结点不是头结点
			for(ListNode<Type> *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<Type> *p=first;p;p=p->link)
			cout<<p->data;
	}

	void PutToArray(char *&buf)							//输出到数组
	{
		int len=Length();
		buf=new char[len];
		int i=0;
		for(ListNode<Type> *p=first;p;p=p->link)
		{
			buf[i]=p->data;
			i++;
		}
	}

	void DelRepeated()									//删除重复元素
	{
		ListNode<Type> *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<Type> *p=first;p;p=p->link)
			if(p->data==value)
				return 1;
		return 0;
	}

	int GetCode(Type value)								//返回元素在链表中的位置
	{
		int i=0;
		for(ListNode<Type> *p=first;p;p=p->link,i++)
			if(p->data==value)
				return i;
		return 0;
	}

	int operator == (List<Type> &right)					//重载"=="
	{
		ListNode<Type> *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<Type> &operator = (const List<Type> &right)	//重载"="
	{
		MakeEmpty();
		Add(right);
		return *this;
	}

	int IsEmpty()										//判断链表是否为空
	{
		if(Length()==0)
			return 1;
		return 0;
	}

	void Add(const List<Type> &right)							//加入一个链表所有元素
	{
		for(ListNode<Type> *p=right.first;p;p=p->link)
		{
			if(!Contains(p->data))
			 Insert(p->data);
		}
	}

	int MergeString(List<Type> &right)
	{
		int len1=this->Length();
		int len2=right.Length();
		int ret=0;
		ListNode<Type> *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<Type> *first,*last;
};