分享一下刚写完的广义表类实现的代码，全部通过测试了...
刚开始学到广义表的时候觉得代码很难写，当时就搁置了下来没有写了，后来写了BinaryTree<T>,Tree<T>,MidThreadBinTree<T>等几个数据结构后，觉得这种递归结构的数据结构还是有点共同点的，所以一下子就把
广义表的GenList<T>一口气就实现了，
有个体会，不知各位DX时候有同感，我觉得无论是BinaryTree<T>,Tree<T>,还是GenList<T>,最难写的算法反而
是通过描述字符串来创建相应的结构，例如我写的都是通过广义表字符串例如A(B(C,D(e,f),G(h,i),j),K(x,y))#
来创建树或者广义表的多级链表结构，只要这个搞定了编下面的算法就快多了，而且，有了这个，也便于后期的调试，
而且我都喜欢用写利用堆栈的非递归算法，
代码如下，代码毫无保留，可直接在main()中调用，我的心血，大家参考，多批评：
PS：以下的代码中CreateList(char* s)函数是最费了我心血的代码，大家可以参考一下，
还有就是本广义表是通过多级链表来实现的，因为我的代码没有考虑共享结点的情形，所有表头结点
本因该是存放引用数ref的，我改成存放表名了，这样便于遍历显示.
#ifndef GENLIST_H
#define GENLIST_H
#include<iostream.h>
#include<stdlib.h>
#include"LinkedStack.h"
////////////////////////////////////////////////////
//广义表的表结点结构GenListNode<T>
//该结点根据utype的值不同充当三个角色
//utype==0:广义表的附加表头结点,
//此时数据域存放表名,tlink指向广义表的表头元素
//utype==1:原子结点,
//此时数据域存放表数据,tlink指向下个元素结点
//utype==2:子表结点
//此时数据域指向子表的附加头结点,tlink指向下个表结点
////////////////////////////////////////////////////
template<class T>
struct GenListNode
{
int utype; //用于标记结点的类型
union
{
int ref; //作为表头结点时的引用数
T value; //作为原子结点时的数据域,或作为表头结点时的表名
GenListNode<T>* hlink; //作为子表结点时指向子表附加头结点的指针
} info;
GenListNode<T>* tlink; //指向同层次的表结点的指针
public:
GenListNode() //默认构造函数,构造一个空结点
{
utype=0; //先默认初始化为表头结点
info.ref=0;
tlink=NULL;
};
GenListNode(GenListNode<T>& R);//复制构造函数
~GenListNode(){}; //析构函数
};
///////////////////////////GenListNode表结点结构结束
////////////////////////////////////////////////////
//GenList<T>类模板 通过多级链表实现的广义表
//T是原子结点的数据类型
//大写字母表示表名,小写字母表示原子结点
////////////////////////////////////////////////////
template<class T>
class GenList
{
private:
GenListNode<T>* first; //广义表的表头指针
GenListNode<T>* Copy(GenListNode<T>* ls);//递归:把ls所指的广义表复制过来
int Depth(GenListNode<T>* ls); //递归:求ls所指的广义表的深度
int Atom(GenListNode<T>* subList); //递归:统计广义表中原子结点的个数
bool Equal(GenListNode<T>* s //递归:判断s,t指向的两个广义表是否相等
,GenListNode<T>* t);
bool Delete(GenListNode<T>* subList,T x);//在表subList中删除具有值x的原子结点
void Remove(GenListNode<T>* ls); //释放ls所指向的广义表的内存空间
GenListNode<T>* CreateList(char* s); //通过描述字符串来创建一个广义表
int CharKind(char x); //判断字符x的分类;
void Display(GenListNode<T>* subList); //递归:以描述字符串形式来显示当前广义表
public:
GenList() //默认构造函数
{first=NULL;};
GenList(char* s) //带参数的构造函数
{first=CreateList(s);};
GenList(GenList<T>& R) //复制构造函数
{first=Copy(R.first);};
~GenList() //析构函数
{Remove(first);};
bool Head(GenListNode<T>& h); //得到当前表的表头结点
bool Tail(GenList<T>& gl); //得到当前表的表尾
GenListNode<T>* First() //返回当前表的第一个元素
{if(first!=NULL)return first->tlink;};
GenListNode<T>* Next( //返回current所指向的结点的直接后继
GenListNode<T>* current)
{if(current!=NULL)return current->tlink;};
void Copy(const GenList<T>& R); //广义表的复制
int Atom() //计算广义表中原子结点的个数
{return Atom(first);};
int Length(); //得到当前广义表的长度
int Depth() //得到一个非递归表的深度
{return Depth(first);};
bool Equal(GenList<T>& R) //判断当前广义表与R广义表是否相等
{return Equal(first,R.first);};
bool Delete(T x) //在当前的广义表中删除具有给定值的原子结点
{return Delete(first,x);};
void Display()
{Display(first);};
friend ostream& operator<<( //友元重载<<输出运算符输出广义表
ostream& os,GenList<T>& R); //的描述字符串
};
////////////////////////////////GenList<T>类模板结束
////////////////////////////////////////////////////
//CharKind()私有成员函数
//判断字符的分类:1:大写字母,2:'(',3:小写字母,4:',',5:')'
////////////////////////////////////////////////////
template<class T>
int GenList<T>::CharKind(char x)
{
if(int(x)>=65 && int(x)<=90)//如果是大写字母
return 1;
else if(x=='(') //如果是左括号
return 2;
else if(int(x)>=97 //如果是小写字母
&& int(x)<=122)
return 3;
else if(x==',') //如果是逗号分隔符
return 4;
else if(x==')') //如果是右括号
return 5;
else
return -1;
};
//////////////////////////////////CharKind()函数结束
////////////////////////////////////////////////////
//CreateList()公有成员函数
//通过广义表的描述字符串s来创建一个广义表,
//该描述字符串以'#'作为结束符
////////////////////////////////////////////////////
template<class T>
GenListNode<T>* GenList<T>::CreateList(char* s)
{
/*先创建一个附加头结点*/
GenListNode<T>* newFirst; //整个广义表的头结点指针
GenListNode<T>* ptr; //指向当前刚创建的结点
GenListNode<T>* pre; //存放前一个结点的指针
/*从描述字符串中逐个取出字符建立广义表*/
LinkedStack<GenListNode<T>*> CS; //表结点堆栈
int i=0;
int flag=1;
while(s[i]!='#')
{
switch(CharKind(s[i]))
{
//如果是大写字母
case 1:
{
if(flag==1) //如果是第一个结点
{
ptr=new GenListNode<T>;//建立表头结点
ptr->info.value=s[i]; //存储表名
newFirst=ptr;
flag=0;
}
else //如果不是第一个结点
{
ptr=new GenListNode<T>;
ptr->utype=2; //先建立一个子表结点
ptr->info.hlink=
new GenListNode<T>;//在再该子表下建立表头结点
ptr->info.hlink->info.value
=s[i]; //存储表名
if(flag==2) //如果上个描述字符是'('
{
CS.getTop(pre); //从栈顶获取前个该挂接的结点指针
if(pre->utype==0) //如果堆栈中取出的是表头结点
pre->tlink=ptr;//链入到栈顶结点的后面
else //如果堆栈中取出的是子表结点
pre->info.hlink->tlink=ptr;
}
else if(flag==4) //如果上个描述字符是','
pre->tlink=ptr; //该结点ptr只是pre结点的后继元素
};
break;
}
//如果是'('
case 2:
{
CS.Push(ptr); //把当前的表结点指针压栈
flag=2; //为下一步作标记表示是从','来的
break;
}
//如果是小写字母
case 3:
{
ptr=new GenListNode<T>;
ptr->utype=1;
ptr->info.value=s[i];//创建一个原子结点并初始化数据域
if(flag==2) //如果上个描述字符是'('
{
CS.getTop(pre); //从栈顶获取前个该挂接的结点指针
if(pre->utype==2)//如果取出的是子表结点
pre->info.hlink->tlink
=ptr; //该结点ptr肯定是pre子表的第一个元素
else //如果取出的是表头结点
pre->tlink=ptr;
}
else if(flag==4) //如果上个描述字符是','
pre->tlink=ptr; //该结点ptr只是pre结点的后继元素
break;
}
//如果是','分隔符
case 4:
{
pre=ptr; //同级链表的指针传递
flag=4; //为下一步作标记
break;
}
//如果是')'
case 5:
CS.Pop(ptr); //从堆栈中弹出一个结点
break;
};
i++; //取下个描述字符
};
return newFirst; //返回整个表的表头指针
};
////////////////////////////CreateList()公有函数结束
////////////////////////////////////////////////////
//Head()公有成员函数
//得到当前当前广义表的表头
////////////////////////////////////////////////////
template<class T>
bool GenList<T>::Head(GenListNode<T>& R)
{
if(first==NULL) //空表没有表头
return false;
else
{
R.utype=first->tlink->utype;
R.info.value=first->tlink->info.value;
R.tlink=NULL;
return true;
};
};
//////////////////////////////////Head()公有函数结束
////////////////////////////////////////////////////
//Tail()公有成员函数
//得到当前广义表的表尾(表尾同样是个广义表)
////////////////////////////////////////////////////
template<class T>
bool GenList<T>::Tail(GenList<T>& GL)
{
if(first!=NULL)
{
GenListNode<T>* newFirst=new GenListNode<T>;
newFirst->info.value='T';
newFirst->tlink=first->tlink->tlink;
GL.first=Copy(newFirst);
return true;
}
else
return false;
};
//////////////////////////////Tail()公有成员函数结束
////////////////////////////////////////////////////
//Copy()私有成员函数
//递归:复制一个广义表,subList是一个表头结点指针
////////////////////////////////////////////////////
template<class T>
GenListNode<T>* GenList<T>::Copy(GenListNode<T>* subList)
{
if(subList!=NULL)
{
/*先复制表的附加头结点*/
GenListNode<T>* des=new GenListNode<T>;
GenListNode<T>* src=subList->tlink;
GenListNode<T>* head=des; //先新建一个表头结点
GenListNode<T>* ptr; //临时结点指针
head->info.value= //复制表名
subList->info.value;
/*复制附加头结点后的原子结点
和递归复制子表结点下的的子表*/
while(src!=NULL)
{
if(src->utype==1) //如果是原子结点
{
ptr=new GenListNode<T>;
ptr->utype=1; //新建一个原子结点
ptr->info.value=src->info.value;
des->tlink=ptr; //挂到复制的表中
des=ptr;
}
else if(src->utype==2) //如果是子表结点
{
ptr=new GenListNode<T>;
ptr->utype=2; //新建一个子表结点
ptr->info.hlink //递归创建子表
=Copy(src->info.hlink);
des->tlink=ptr;
des=ptr;
}
src=src->tlink; //遍历同层次其他表结点
};
return head;
}
else
return NULL;
};
//////////////////////////////Copy()私有成员函数结束
////////////////////////////////////////////////////
//Depth()私有成员函数
//递归:计算当前广义表的深度(即表的最大嵌套层数)
////////////////////////////////////////////////////
template<class T>
int GenList<T>::Depth(GenListNode<T>* subList)
{
if(subList!=NULL)
{
int max=0; //子表的最大深度
GenListNode<T>* ptr=subList->tlink;//游标指针
while(ptr!=NULL)
{
if(ptr->utype==2) //如果是子表结点
{
int p
=Depth(ptr->info.hlink); //递归求出子表的深度
if(p>max)
max=p; //求最大子表深度
};
ptr=ptr->tlink;
};
return max+1;
}
else
return 0;
};
/////////////////////////////Depth()私有成员函数结束
////////////////////////////////////////////////////
//Length()公有成员函数
//计算出当前的广义表的长度,即第一级链表的长度
////////////////////////////////////////////////////
template<class T>
int GenList<T>::Length()
{
int count=0;
GenListNode<T>* ptr=first;
while(ptr!=NULL)
{
count++; //同级结点的计数
ptr=ptr->tlink;
};
return count;
};
////////////////////////////////////////////Length()
////////////////////////////////////////////////////
//Atom()私有成员函数
//递归:统计当前的广义表中原子结点的个数
////////////////////////////////////////////////////
template<class T>
int GenList<T>::Atom(GenListNode<T>* subList)
{
if(subList!=NULL)
{
int sum=0;
GenListNode<T>* ptr=subList->tlink; //游标指针
while(ptr!=NULL) //遍历同级所有结点
{
if(ptr->utype==1) //如果是原子结点
sum++;
else if(ptr->utype==2) //如果是子表结点
sum=sum+Atom(ptr->info.hlink);//递归加入子表中的原子结点的个数
ptr=ptr->tlink;
};
return sum;
}
else
return 0;
};
//////////////////////////////////Atom()私有函数结束
////////////////////////////////////////////////////
//Equal()私有成员函数
//递归:判断以s,t为头结点的广义表是否相等
////////////////////////////////////////////////////
template<class T>
bool GenList<T>::Equal(GenListNode<T>* s,GenListNode<T>* t)
{
if(s!=NULL && t!=NULL)
{
GenListNode<T>* ptr1=s->tlink;
GenListNode<T>* ptr2=t->tlink;
if(s->info.value==t->info.value)//首先比对表头结点
{
while(ptr1!=NULL && ptr2!=NULL)
{ //再比对表里的内容
if(ptr1->utype==1 //作为原子结点相等
&& ptr2->utype==1
&& ptr1->info.value==ptr2->info.value
|| ptr1->utype==2 //递归:作为子表结点相等
&& ptr2->utype==2
&& Equal(ptr1->info.hlink,ptr2->info.hlink))
{
ptr1=ptr1->tlink; //继续看同级的下个结点
ptr2=ptr2->tlink;
}
else
return false;
}
return true; //跳出循环说明所有的都相等
}
else
return false; //表头就不相等
}
else
return false;
};
/////////////////////////////////Equal()私有函数结束
////////////////////////////////////////////////////
//Delete()私有成员函数
//递归:在指定的子树subList中删除具有给定值的结点
////////////////////////////////////////////////////
template<class T>
bool GenList<T>::Delete(GenListNode<T>* subList,T x)
{
if(subList!=NULL)
{
GenListNode<T>* ptr=subList;//游标指针
while(ptr->tlink!=NULL) //遍历同级所有的表结点
{
if(ptr->tlink->utype==1 //如果是原子结点
&& ptr->tlink->info.value==x)
{
ptr->tlink=ptr->tlink->tlink;
return true; //删除成功
}
else if(ptr->tlink->utype==2)
{ //如果是子表结点
bool b=Delete( //递归在子表中删除
ptr->tlink->info.hlink,x);
if(b)
return true;
};
ptr=ptr->tlink; //指针向后平级移动
};
return false; //如果全部遍历后没有找到,删除失败
}
else
return false; //表空则删除失败
};
////////////////////////////Delete()私有成员函数结束
////////////////////////////////////////////////////
//Remove()私有成员函数
//递归:释放广义表中所有的表结点的内存空间
////////////////////////////////////////////////////
template<class T>
void GenList<T>::Remove(GenListNode<T>* subList)
{
if(subList!=NULL)
{
GenListNode<T>* ptr=subList; //游标指针
GenListNode<T>* pre; //前个结点的指针
while(ptr!=NULL) //遍历同层次的结点
{
pre=ptr;
ptr=ptr->tlink;
if(pre->utype==1 //如果是原子结点
|| pre->utype==0) //或者如果是表头结点
delete pre; //直接删除
else if(pre->utype==2) //如果是子表结点
{
Remove(pre->info.hlink);//递归删除子表
delete pre; //删除子表结点
};
};
};
};
////////////////////////////////////Remove()函数结束
////////////////////////////////////////////////////
//Display()私有成员函数
//以递归的方式实现以广义表描述字符串的方式显示
//subList是表的附加头结点指针,不是子表结点指针
////////////////////////////////////////////////////
template<class T>
void GenList<T>::Display(GenListNode<T>* subList)
{
if(subList!=NULL)
{
cout<<subList->info.value;
GenListNode<T>* ptr=subList->tlink;//游标指针
cout<<'(';
while(ptr!=NULL)
{
if(ptr->utype==1) //如果ptr指向的是原子结点
cout<<ptr->info.value; //直接显示原子结点
else
Display(ptr->info.hlink); //递归显示子表
if(ptr->tlink!=NULL)
cout<<',';
ptr=ptr->tlink;
};
cout<<')';
};
};
///////////////////////////////////Display()函数结束
////////////////////////////////////////////////////
//友元重载<<输出运算符
////////////////////////////////////////////////////
template<class T>
ostream& operator<<(ostream& os,GenList<T>& R)
{
R.Display(R.first);
return os;
};
//////////////////////////////////////<<友元重载结束
#endif
[[it] 本帖最后由 geninsf009 于 2008-10-8 22:18 编辑 [/it]]
