本文共 5724 字，大约阅读时间需要 19 分钟。

1.头文件

# include 
   
    using namespace std;struct GenListNode{        //广义表结点	int utype;         //结点类型：=0附加头结点；=1原子结点；=2子表结点	GenListNode *tlink; //尾指针	union {  //联合体：utype=0，该结点存引用计数ref；=1该结点存值value；=2该结点存子表的头指针		int ref;		int value;		GenListNode *hlink;	} info;	GenListNode():utype(0),tlink(NULL){ //结点构造函数		info.ref=0;	}	GenListNode(GenListNode& RL){ //复制构造函数		utype=RL.utype;		tlink=RL.tlink;		switch(utype){    //根据utype的值进行赋值操作		case'0':info.ref=RL.info.ref; break;		case'1':info.value=RL.info.value; break;		case'2':info.hlink=RL.info.hlink; break;		}	}};struct Items{  //该数据类型用于取表头，表尾函数，不包含tlink，与单链表比较即可理解。	int utype;	union{		int ref;		int value;		GenListNode *hlink;	}info;	Items():utype(0){     //构造函数		info.ref=0;	}	Items(Items& RL){  //复制构造函数		utype=RL.utype;		switch(utype){		case'0':info.ref=RL.info.ref; break;		case'1':info.value=RL.info.value; break;		case'2':info.hlink=RL.info.hlink; break;		}	}};class GenList{    //广义表类private:	GenListNode *first;   //头指针	GenListNode* Copy(GenListNode *ls); //复制ls指的广义表并返回该表的头指针	int Length(GenListNode *ls);//求ls指示的广义表的长度	int Depth(GenListNode *ls); //求ls所指的广义表的深度	bool Equal(GenListNode *s,GenListNode *t); //判断两个广义表是否相同	void Remove(GenListNode *ls); //释放ls所指的广义表	void Createlist(istream& istr,GenListNode *&ls); //根据输入流建立广义表	void delvalue(GenListNode *ls,int x); //删除广义表中原子结点值为x的结点public:	GenList(); //构造函数	~GenList(); //析构函数	bool Head(Items& x);  //取表头	bool Tail(GenList& lt);  //取表尾	GenListNode* First(); //求第一个元素的地址	GenListNode* Next(GenListNode *elem); //求elem所指的下一个元素的地址	void Copy(const GenList& R);  //复制广义表R给调用该函数的广义表	int Length();  //求调用该函数的广义表的长度	int Depth();  //求广义表深度	friend istream& operator>>(istream& istr,GenList& L);  //根据输入流建立广义表};
   

2.操作的实现

# include
   
    # include
    
     # include"GenList.h"using namespace std;GenList::GenList(){  //构造函数，构造一个空表	first=new GenListNode;	assert(first!=NULL);}bool GenList::Head(Items& x){ //取表头	if(first->tlink==NULL) return false;	else{		x.utype=first->tlink->utype;		switch(x.utype){		case'1':x.info.value=first->tlink->info.value; break;		case'2':x.info.hlink=first->tlink->info.hlink; break;		}		return true;	}};bool GenList::Tail(GenList& lt){  //取表尾	if(first->tlink==NULL) return false;	else{		lt.first->utype=0;  //设置附加头结点		lt.first->info.ref=0;		lt.first->tlink=Copy(first->tlink->tlink); //调用Copy函数取表尾		return true;	}}GenListNode* GenList::First(){  //取第一个元素的地址	if(first->tlink==NULL) return NULL;	else return first->tlink;}GenListNode* GenList::Next(GenListNode *elem){ //取elem下一个结点的地址	if(elem->tlink==NULL) return NULL;	else return elem->tlink;}void GenList::Copy(const GenList& R){ //把广义表R赋值给调用该函数的广义表	first=Copy(R.first);//调用了下面的Copy函数}GenListNode* GenList::Copy(GenListNode *ls){   //赋值ls所指的广义表并返回副本的头指针	GenListNode *p=NULL;	if(ls!=NULL){		p=new GenListNode; 		p->utype=ls->utype; //复制表头		switch(ls->utype){		case'0':p->info.ref=ls->info.ref; break;		case'1':p->info.value=ls->info.value; break;		case'2':p->info.hlink=Copy(ls->info.hlink); break;		}	p->tlink=Copy(ls->tlink); //复制表尾	}	return p;  //返回头指针}int GenList::Length(){  //返回广义表的长度	return Length(first);}int GenList::Length(GenListNode *ls){ //求广义表长度	if(ls==NULL) return 0;	else return 1+Length(ls->tlink);//递归求长度}int GenList::Depth(){  //返回广义表的深度	return Depth(first);}int GenList::Depth(GenListNode *ls){ //求广义表深度	if(ls->tlink==NULL)  //空表深度为一		return 1;	GenListNode *temp=ls->tlink;	int m=0,n;	while(temp!=NULL){  //求子表的最大深度		if(temp->utype==2){			n=Depth(temp->info.hlink);			if(m
     
      tlink;	}	return m+1; //广义表的深度就是子表的最大深度+1}bool GenList::Equal(GenListNode *s,GenListNode *t){  //判断两个广义表是否相等	int x;	if(s->tlink==NULL&&t->tlink==NULL) return true;//都为空表，相等	else 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;}void GenList::delvalue(GenListNode *ls,int x){  //删除广义表中所有原子值为x的结点	if(ls->tlink==NULL) return;    //ls为空表	GenListNode *temp=ls->tlink;	while(temp!=NULL){	       while(temp->utype==1){ //如果该点为原子结点，用while因为可能连续几个结点都是原子结点		         if(temp->info.value==x){ //值为x，删除该结点			          ls->tlink=temp->tlink;			          delete temp;		         }		   temp=ls->tlink; 	       }	       if(temp->utype==2){  //该点为子表结点		        delvalue(temp->info.hlink,x); //删除子表中所有原子值为x的结点	            temp=temp->tlink;		   }	}	return ; //删除完毕，返回到主函数}GenList::~GenList(){  //析构函数	Remove(first);}void GenList::Remove(GenListNode *ls){ //释放ls指示的广义表	if(ls->tlink==NULL)  //如果ls为空表，删除附加头结点		delete ls;	GenListNode *temp=ls->tlink;	while(temp!=NULL){			while(temp!=NULL&&temp->utype==1){ //原子结点		         ls->tlink=temp->tlink;		         delete temp;		         temp=ls->tlink;	        }			if(temp->utype==2&&temp!=NULL){ //子表结点	               Remove(temp->info.hlink); //删除该节点hlink指示的子表				   ls->tlink=temp->tlink; //删除该结点				   delete temp;	               temp=ls->tlink;			}	}	delete ls; //删除附加头结点	return ; //返回主函数}
     
    
   

3.阅读建议

（1）由于建立广义表的算法比较复杂，因此本文中并未包括CreateList函数的实现，过几天我再单独写一篇。

（2）本文中基本所有重要函数的实现都用到了递归算法，对对递归不熟悉的小伙伴帮助应该会比较大（包括我）。很多函数只看代码应该不太容易看懂，于是附加一张广义表的结构图，大家可以手动在纸上执行递归的过程：

（3）关于递归过程中创建局部变量的问题，跟大家分享一个百度知道的问题，相信对大家理解递归有帮助：（在此处谢谢答主）

问题：当函数发生递归调用时,同一个局部变量在不同程度上可以同时存在不同的取值,这在底层是如何做到的? 

解答：

你在源代码中看到的一个局部变量，其实在函数递归过程中是存在很多副本的。

比如，你在源代码中看到一个一个局部变量 a 其实在函数递归掉用的时候，每调用一次都会在所调用函数的运行空间里存储一个a的，所以其实存在很多很多的不同的a，他们各自的存储空间是不一样的，当然能存储不同的取值了。 如 开始调用t(),先为t()分配存储空间，存储空里有一个a 然后t()调用t()（我们称之为t1()），先为t1()分配存储空间，存储空间里有存一个a（与前面的a是不同的） t1()又调用t()（我们称之为t2()），先为t2分配存储空间，存储空间里存一个a（又是一个不同的a) .....................以此类推 所以，并不是“同一个局部变量在不同程度上可以同时存在不同的取值”  而是“不同的局部变量在不同的函数空间里存储了不同的值”