广义表简称表，是线性表的推广，表中元素可以是数据元素（原子），也可以是子表。
广义表的表头（head）是表中第一个表元素、表尾（tail）是除了表头外其它元素组成的表。
首先要对广义表结点类GenListNode和返还值的结构类Item进行定义。它们都有一个用来标明结点类型的标志域utype、一个信息域info。此外，广义表结点类还多了一个尾指针tlink指向下一个结点。
utype为0时为广义表专用的附加头结点，info存放引用计数ref
utype为1时为原子结点、info存放数据值value
utype为2时为子表结点，info存放指向子表表头的指针hlink
这种存储表示中，广义表中的所有表，无论是哪一层的子表，都带有一个附加头结点，空表也不例外
所有位于同一层的表元素，在其存储表示中也在同一层
最高一层的表结点个数（除附加头结点外）即为表的长度
#include <iostream>
#include <assert.h>
#include <stdlib.h>
using namespace std;
template <class T>
struct Items{ //返回值的类结构定义
int utype; //标志域
union{
int ref; //utype=0，存放引用计数
T value; //utype=1，存放数值
GenListNode<T> *hlink; //utype=2.存放指向子表的指针
} 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; //比返回值的类结构多了一个tlink指针
union{
int ref;
T value;
GenListNode<T> *tlink;
} info;
}
template <class T>
class Genlist{
public:
Genlist();
~Genlist();
bool Head(Items& x);
bool Tail(Genlist<T>& It);
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); //判断s和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);
}
//Head方法返回bool值，通过引用变量x返回是广义表第一个元素（Item类型的对象）；
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;
}
}
template <class T>
bool Genlist<T>::Tail(Genlist<T>& It){
//若广义表非空，则通过It返回广义表除表头元素以外其他元素组成的表，否则函数没有意义
if(first->tlink==NULL) return false;
else{
It.first->utype=0;
It.first->info.ref=0;
It.first->tlink=Copy(first->tlink->tlink);
return true;
}
}
//First方法返回的是指向广义表第一个元素（GenlistNode类型的对象）的指针
template <class T>
GenlistNode<T> *Genlist<T>::First(){
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>
struct Items {
int mark;
int utype;
union{
char *LName; //附加头结点的info域改为了表名
T value;
GenListNode<T> *hlink;
}info;
Items():mark(0),utype(0),info.LName('\0'){}
Items(Items<T>& RL){mark=Rl.mark;utype=RL.utypr;info=RL.info;}
}
template <class T>
struct GenListNode {
public:
GenListNode():mark(0),utype(0),tlink(NULL),info.LName('\0'){}
GenListNode(GenListNode<T>& RL){mark=RL.mark; utype=RL.utype; tlink=RL.tlink; info=RL.info;}
int getMark(GenListNode<T> *elem){return elem->mark;}
int getType(GenListNode<T> *elem){return elem->utype;}
int getListName(GenListNode<T> *elem){return elem->info.LName;}
T getValue(GenListNode<T>* elem){return elem->info.value;}
GenListNode* gettlink(GenListNode<T>* elem){return elem->tlink;}
GenListNode* gethlink(GenListNode<T>* elem){return elem->info.hlink;}
private:
int mark;
int utype;
GenListNode<T> *tlink;
union{
char *LName;
T value;
GenListNode<T> *hlink;
}info;
}
template GenList{
public:
GenList();
~GenList(){Remove(first);}
bool Head(Items& x);
bool Tail(GenList<T> <);
GenListNode<T> *First(){return first;}
GenListNode<T> *Next(GenListNode<T> *elem){return elem->tlink;}
void Traverse(); //非递归遍历
private:
GenListNode<T> *first;
void Traverse(GenListNode<T> *ls); //递归遍历
}
template <class T>
void GenList::Traverse(){
Stack<GenListNode<T>*> st;
GenListNode<T> *ls=first;
while (ls!=NULL) {
ls->mark=1;
if (ls->utype==2){ //子表结点
if (ls->info.hlink->mark==0){
st.Push(ls->tlink;) //暂时先把子表结点的右结点入栈
ls=ls->hlink;
}
else { //子表已经遍历过
cout<<ls->info.hlink->info.LName;
if(ls->tlink!=NULL){
cout<<',';
ls=ls->tlink;
}
}
}
else {
if (ls->utype==0) cout<<ls->info.LName<<'('; //表头结点
else if (ls->utype==1){ //原子结点
cout<<ls->info.value;
if(ls->tlink!=NULL) cout<<',';
}
if(ls->tlink==NULL){
cout<<')';
if(!st.isEmpty()){
st.Pop(ls);
if(ls!=NULL) cout<<',';
else cout<<')';
}
}
else ls=ls->tlink;
}
}
}
template <class T>
void GenList::Traverse(GenListNode<T> *ls){
if(ls!=NULL){
ls->mark=1;
if (ls->utype==0) cout<<ls->info.LName<<'('; //表头结点
else if (ls->utype==1) { //原子结点
cout<<ls->info.value;
if (ls->tlink!=NULL) cout<<',';
}
else if (ls->utype==2) { //子表结点
if (ls->info.hlink->mark==0) Traverse(ls->info.hlink);
else cout<<ls->info.hlink->info.LName; //子表已经遍历过
if (ls->tlink!=NULL) cout<<',';
}
Traverse(ls->tlink);
}
else cout<<')';
}
