广义表

用链表实现广义表时，每个表节点可由3个域组成：1.标志域utype用来表明该节点的类型。0是广义表专用的头节点；1是原子节点；2是子表节点。2.信息域info存放各种节点的内容。utype=0时存放引用计数；utype=1时存放数值；utype=2时存放指向子表表头的指针。 3.尾指针域tlink。

实现

类声明

template <class T>
struct Items {
	int utype;
	union {
		int ref;
		T value;
		GenLintNode<T> *hlink;
	} info;
	Items(): utype(0), info, ref(0) {}
	Items(Items<T>& RL) {
		utype = RL.utype;
		info = RL.info;
	}
};

template <class T>
struct GenListNode {
public:
	GenListNode(): utype(0), tlink(NULL), info.ref(0) {}
	GenListNode(GenListNode<T>& RL) {
		utype = RL.utype;
		tlink = RL.tlink;
		info = RL.info;
	}
private:
	int utype;
	GenListNode<T> *tlink;
	union {
		int ref;
		T value;
		GenListNode<T> *hlink;
	} info;
};

template <class T>
class GenList {
public:
	GenList();
	~GenList();
	bool Head(Items& x);
	bool Tail(GenList<T>& lt);
	GenListNode<T> *First();
	GenListNode<T> *Next(GenListNode<T> *elem);
	void Copy(const GenList<T>& R);
	int Length();
	int depth();
friend istream& operator >> (istream& in, GenList<T>& L);
private:
	GenListNode<T> *first;
	GenListNode<T> *Copy(GenListNode<T> *ls);
	int Length(GenListNode<T> *ls);
	int depth(GenListNode<T> *ls);
	bool equal(GenListNode<T> *s, GenListNode<T> *t);
	void Remove(GenListNode<T> *ls);
	void Createlist(istream& in, GenListNode<T> *&ls);
};

成员函数

构造函数。

template <class T>
GenList<T>::GenList() {
	first = new GenListNode;
	assert(first != NULL);
};

返回第一个元素的值。

template <class T>
bool GenList<T>::Head(Items<T>& x) {
	if (first->tlink == NULL) {
		return false;
	} else {
		x.utype = first->tlink->utype;
		x.info = first->tlink->info;
		return true;
	}
};

返回除表头元素以外其它元素组成的表。

template <class T>
bool GenList<T>::Tail(GenList<T>& lt) {
	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() {
	if (first->tlink == NULL) {
		return NULL;
	} else {
		return first->tlink;
	}
};

返回元素elem的直接后继元素。

template <class T>
GenListNode<T> *GenList<T>::Next(GenListNode<T> *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) {
	GenListNode<T> *q = NULL;
	if (ls != NULL) {
		q = new GenListNode<T>;
		q->utype = ls->utype;
		switch (ls->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>
int GenList<T>::Length() {
	return Length(first);
};

template <class T>
int GenList<T>::Length(GenListNode<T> *ls) {
	if (ls != NULL) {
		return 1 + Length(ls->tlink);
	} else {
		return 0;
	}
};

求深度

template <class T>
int GenList<T>::depth() {
	return depth(first);
};

template <class T>
int GenList<T>::depth(GenListNode<T> *ls) {
	if (ls->tlink == NULL) {
		return 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>
bool equal(GenListNode<T> *s, GenListNode<T> *t) {
	int x;
	if (s->tlink == NULL && t->tlink == NULL) {
		return true;
	}
	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) ? 1 : 0;
		} else if (s->tlink->utype == 2) {
			x = equal(s->tlink->info.hlink, t->tlink->info.hlink);
		}
		if (x == 1) {
			return equal(s->tlink, t->tlink);
		}
	}
	return false;
};

删除

template <class T>
void 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;
		}
		if (p != NULL) {
			if (p->utype == 2) {
				delvalue(p->info.hlink, x);
			}
			delvalue(p, x);
		}
	}
};

共享表做删除时是减引用计数。

template <class T>
GenList<T>::~GenList() {
	Remove(first);
};

template <class T>
void GenList<T>::Remove(GenListNode<T> *ls) {
	ls->info.ref --;
	if (ls->info.ref <= 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 p;
		}
	}
};

建表

template <class T>
void GenList<T>::CreateList(istream in, GenListNode<T> *&ls,
	SeqList<T>& L1, SeqList<GenListNode<T> *>& 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.Locate(m);
				p->ref ++;
			} 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->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 == ',') {
		CreateList(in, ls->tlink, L1, L2);
	} else if (chr == ')') {
		ls->tlink = NULL;
	} else if (chr == '#') {
		ls == NULL;
	}
};