genlist.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

#ifndef GENLIST_H
#define GENLIST_H
#include <iostream>
#include <stdlib.h>
#include<string.h>
#include"SeqList.h"
using namespace std;
template <class T>
struct GenListNode {	          //广义表结点类定义
	int utype;			//＝0 / 1 / 2
	GenListNode<T> *tlink;	//同层下一结点指针
	union {				//等价变量
		int ref;	                     //存放引用计数
		T value;			//存放数值
		GenListNode<T> *hlink;	  //存放子表指针	
	} info;
	GenListNode(int u=0): utype(u), tlink(NULL) {} //构造函数
	GenListNode(GenListNode<T>& R) {
		//复制构造函数
		utype = R.utype;   tlink = R.tlink; 
		info = R.info;
	}
};

template <class T>
struct Items {		//返回值的类结构定义
	int utype;		//结点类型＝0/1/2
	union {			//联合
		int ref;		//utype=0,存放引用计数
		T value;		//utype=1,存放数值
		GenListNode<T> *hlink;	
		//utype=2,存放指向子表的指针
	} info;
	Items() : utype(0), info.ref(0) {}    //构造函数	
	Items(Items<T>& R)                     //复制构造函数
	{ utype = R.utype;  info = R.info; }	
};
template <class T>
class GenList {			  //广义表类定义
public:
	GenList();			          //构造函数
	~GenList();			//析构函数 
	GenList(GenList<T> & gl);
	bool Head (Items<T>& x);	   //x 返回表头元素
	bool Tail (GenList<T>& lt);	   //lt 返回表尾
	GenListNode<T> *First();	   //返回第一个元素
	GenListNode<T> *Next (GenListNode<T> *elem);
	//返回表元素elem的直接后继元素
	void Copy ( const GenList<T>& R);
	//广义表的复制
	int Length();    		          //计算广义表长度
	int depth();			//计算非递归表深度     
	void show() {show(first);}
	void delvalue(T x){delvalue(first, x);}
private:
	GenListNode<T> *first;	//广义表头指针
	GenListNode<T> *Copy (GenListNode<T> *ls);
	//复制一个ls指示的无共享非递归表
	int Length (GenListNode<T> *ls);
	//求由ls指示的广义表的长度
	int depth (GenListNode<T> *ls);		
	//计算由ls指示的非递归表的深度
	bool equal (GenListNode<T> *s, GenListNode<T> *t);
	//判以s和t为表头的两个表是否相等
	void Remove (GenListNode<T> *ls);
	//释放以ls为附加头结点的广义表
	void CreateList (istream& in, GenListNode<T> *&ls, SeqList<T>& L1, SeqList <GenListNode<T> *>& L2);
	//从输入流对象输入广义表的字符串描述,
	void show (GenListNode<T>* p);
	//建立一个带头结点的广义表结构
	void delvalue(GenListNode<T> *ls, T x);
	friend istream& operator >> (istream& in, GenList<T>& L){
		SeqList<T> Ls1;	   
		SeqList<GenListNode<T> *>  Ls2;
		L.CreateList (in, L.first, Ls1, Ls2);	//建立存储结构
		GenListNode<T> *p = L.first;
		L.first = L.first->info.hlink;
		delete p;
		return in;
	}; 
	friend ostream& operator << (ostream& out,GenList<T>& L){
		L.show (L.first);
		return out;
	}
};
//广义表输入格式为 A(b,D(s,z),F(#)); 注意中间无空格
template <class T>
GenList<T>::GenList() {		//构造函数
	first = new GenListNode<T>;
	if (first == NULL)
	{ cerr << "Error!\n";  exit(1); }	
};

template<class T>
GenList<T>::GenList(GenList<T> &gl){
	if (this != & gl)
		first = Copy(gl.first);
}

template <class T>
bool GenList<T>::Head (Items<T>& x) {
	//若广义表非空，则通过x返回其第一个元素的值
	//否则函数没有定义		
	if (first->tlink == NULL) return false;	//空表
	else {						//非空表
		x.utype = first->tlink->utype;
		x.info = first->tlink->info;
		return true;		                 //x返回表头的值
	}
};

template <class T>
bool GenList<T>::Tail(GenList<T>& lt) {
	//若广义表非空，则通过lt返回广义表除表头元素
	//以外其他元素组成的表，否则函数返回false
	if (first->tlink == NULL) return false;	    //空表
	else { 				//非空表
		lt.first->utype = 0;		//设置头结点
		lt.first->info.ref = 0;
		lt.first->tlink = Copy(first->tlink->tlink);
		return true; 
	}
};

template <class T>
GenListNode<T> *GenList<T>::First() {
	//返回广义表的第一个元素（若表空，则返回一个
	//特定的空值NULL）	
	if (first->tlink == NULL) return NULL;    //空表
	else return first->tlink;	 	 //非空表
};

template <class T>
GenListNode<T> *GenList<T>::
Next(GenListNode<T> *elem) {
	//返回表元素elem的直接后继元素
	if (elem->tlink == NULL) return NULL;
	else return elem->tlink;
};

template <class T>                 //公有函数
void GenList<T>::Copy(const GenList<T>& R) {
	first = Copy(R.first);          //调用私有函数
};

template <class T>                 //私有函数
GenListNode<T>* GenList<T>::
Copy(GenListNode <T> *ls) {
	//复制一个 ls 指示的无共享子表的非递归表
	GenListNode<T> *q = NULL;
	if (ls != NULL) {
		q = new GenListNode<T>;  //处理当前的结点q
		q->utype = ls->utype;	  //复制结点类型
		switch (ls->utype) {	  //根据utype传送信息
			  case 0: q->info.ref = ls->info.ref;  break;	        	    case 1: q->info.value = ls->info.value;  break;
			  case 2: q->info.hlink = Copy(ls->info.hlink);   
				  break;
		}
		q->tlink = Copy(ls->tlink);  //处理同层下一结点
	}
	return q;
};

//打印数据
template<class T>
void GenList<T>::show (GenListNode<T>* p){
	if (!p)
		return;
	if (p->utype==1)
		cout<<(p->info).value<<"   ";
	else if (p->utype == 0)
		while (p->tlink){
			show(p->tlink);
			p=p->tlink;
		}
	else
		show (p->info.hlink);
}


template <class T>
int GenList<T>::depth() {             //公有函数
	//计算一个非递归表的深度
	return depth(first);
};

template <class T>                      //私有函数
int GenList<T>::depth(GenListNode<T> *ls) {
	if(!ls) return 0;
	if (!ls->tlink) return 1;
	// ls->tlink ==NULL, 空表，深度为1
	GenListNode<T> *temp = ls->tlink;  
	int m = 0, n;

	while (temp != NULL) {	//在广义表顶层横扫
		if (temp->utype == 2) {	   //扫描到表结点 
			n = depth(temp->info.hlink);	
			//递归计算以子表深度
			if (m < n) m = n;	   //取最大深度
		}
		temp = temp->tlink;
	}
	return m+1;			  //返回深度
};

template <class T>
int GenList<T>::Length() {
	//共有函数，求当前广义表的长度
	return Length(first);
};
template <class T>
int GenList<T>::Length(GenListNode<T> *ls) {
	//私有函数，求以ls 为头指针的广义表的长度
	if (ls != NULL) return 1+Length(ls->tlink);
	else return 0;
};


template <class T>
bool equal(GenListNode<T> *s, GenListNode<T> *t) {
	//私有函数：设s 与t 是两个非递归广义表的表头指针, 若两表相等, 函数返回true, 否则返回
	//false。
	bool x;
	if (s->tlink == NULL && t->tlink == NULL) return true;
	//表s 与表t 都是空表
	if (s->tlink != NULL && t->tlink != NULL
		&& s->tlink->utype == t->tlink->utype) {
			//两表都非空且结点类型相同
			if (s->tlink->utype == 1) //原子结点, 比较对应数据
				x = (s->tlink->info.value == t->tlink->info.value) ? true:false;
			else if (s->tlink->utype == 2) //子表结点, 递归比较其子表
				x = equal(s->tlink->info.hlink, t->tlink->info.hlink);
			if (x == true) return equal(s->tlink, t->tlink);
			//相等, 递归比较同一层的下一个结点; 不等, 不再递归比较
	}
	return false; //不等，返回false
};

template <class T>
void GenList<T>::delvalue(GenListNode<T> *ls, T x) {
	if (ls->tlink != NULL) {		     //非空表 
		GenListNode<T> * p = ls->tlink;  //第一个结点
		while (p != NULL && (p->utype == 1 &&
			p->info.value == x)) {
				ls->tlink = p->tlink;  delete p;  
				p = ls->tlink;               //p指向同层下一结点
		}					
		if (p != NULL) {
			if (p->utype == 2)        //递归在子表中删除
				delvalue(p->info.hlink, x);	
			delvalue(p, x);	
			//在以p为表头的链表中递归删除
		}
	}
};
template <class T>
GenList<T>::~GenList() {
	//广义表的析构函数, 每个头结点都有引用计数
		Remove(first);
};

template <class T>
void GenList<T>::Remove(GenListNode<T> *ls) {
	//私有函数：释放以ls为表头指针的广义表  
	ls->info.ref--;	     	//头结点的引用计数减1
	if (ls->info.ref <= 0) {		//如果减到0
		GenListNode<T> *q;	
		while (ls->tlink != NULL) {	//横扫表顶层
			q = ls->tlink;			//到第一个结点
			if (q->utype == 2) {		//递归删除子表
				Remove(q->info.hlink);
				if (q->info.hlink->info.ref <= 0)
					delete q->info.hlink;   //删子表头结点
			}
			ls->tlink = q->tlink;  delete q;
		}
	}
};

template <class T>
void GenList<T>::CreateList(istream& in, GenListNode<T> *& ls, SeqList<T>& L1, SeqList <GenListNode<T> *>& L2) {
	//从广义表的字符串描述 ls 出发, 建立一个带头结
	//点的广义表，要求T为char类型。在表L1存储大
	//写字母的表名, 在表L2存储表名对应子表结点的
	//地址。
	T chr; 
	in >> chr;   
	//读入一个字符，只可能读入#、左括号和字母
	if (isalpha(chr) && isupper(chr) || chr == '('){
		//大写字母或'('
		ls = new GenListNode<T>;         //建子表结点
		ls->utype = 2;		
		if (isalpha(chr) && isupper(chr)) {  //表名处理
			int n = L1.Length();
			int m = L1.Search(chr);
			if (m != 0) {                  //该表已建立
				GenListNode<T> *p = *L2.getData(m);		            //查子表地址
				p->info.hlink->info.ref++;		//引用计数加1
			} 	
			else {       //该表未建立
				L1.Insert(n, chr);  L2.Insert(n, ls);	
				//保存表名及地址
			}
			in >> chr;
			if (chr != '(') exit(1);	           //表名后必跟'('
		}
		ls->info.hlink = new GenListNode<T>; 
		ls->info.hlink->utype = 0;         //建头结点
		ls->info.hlink->info.ref = 1;
		CreateList(in, ls->info.hlink->tlink, L1, L2);
		//递归建子表
		CreateList(in, ls, L1, L2);         //递归建后继表
	}
	else if (isalpha(chr) && islower(chr)) {	
		//建原子结点
		ls = new GenListNode<T>;
		ls->utype = 1;  ls->info.value = chr;
		CreateList(in, ls, L1, L2);
	}
	else if (chr == ','){ 		//建后继结点
		if (ls->tlink) delete ls->tlink;
		ls->tlink = new GenListNode<T>;
		CreateList(in, ls->tlink, L1, L2); 
	}
	else if (chr == ')')ls->tlink = NULL;  //链收尾
	else if (chr == '#') ls = NULL;	    //空表, 链收尾

};


#endif