1.定义:广义表是一种复杂的数据结构,是线性表的扩展,能够表示树结构和图结构。
2.细分定义:广义表是n个数据元素a0,a1,...,an-1组成的有限序列,记为
GList=(a0,a1,...,an-1)其中,(1)ai或为不可分的数据元素(称为原子),或为可再分的广义表(称为子表)。(2)广义表的元素个数n称为广义表长度(特殊:当n=0时,为空表。)(3)广义表的深度是指表格中所含括号的层数(特殊:原子的深度为0,空表的深度为1.)注意:如果广义表作为自身的一个元素,则称该广义表为递归表。递归的深度是无穷指,其长度是有限值。(4)为了区分原子和表,约定大写字母表示表,小写字母表示原子。(5)另一种广义表表示称为又名表,约定每个表都要有名称,将名称写在表组成的括号前。(6)广义表的语法:其中“()”作为广义表开始和结束的标记,“,”作为原子或子表的分隔符。3.广义表的特性。
(1)线性结构。(广义表是一种线性结构,数据元素之间是线性关系,只不过元素不一定都是原子了,如果元素都是原子,那么这个广义表就是线性表,所以说线性表是广义表的特例)(2)多层次结构,有深度。(注意:广义表是树的扩展。当限制表中成分不能共享和递归时,该广义树就是树,树中的叶子结点对应广义表中的原子,非叶结点对应子表)(3)可共享(一个广义表可作为其他广义表的子表,多个广义表可共享一些广义表。(4)可递归(广义表是一个递归表,当广义表中有共享或递归成分的子表时构成图结构,与有根,有序,有向图对应。4.广义表的图形表示
a.说明:(1)当广义表L(a,b)的数据元素全部都是原子时,L为线性结构的线性表。(2)当广义表L(c,L)的数据元素中有子表,但没有共享和递归成分时,T为树结构的纯表。(3)当广义表L(d,L,T)的数据元素中有子表,并且有共享成分时,G为结构的再入表。(4)当广义表L(e,Z)的数据元素中有子表且有递归成分时,Z为图结构的递归表。5.广义表的抽象数据类型
a.广义表的操作主要有:(1)创建广义表(2)判断广义表是否为空表(3)遍历广义表(4)求广义表长度和深度(5)插入和删除数据元素(6)查找指定原子所在结点(7)比较广义表是否相等(8)复制广义表等b.广义表接口GGenList
public interface GGenList<T>{ boolean isEmpty(); //判断广义表是否为空int length(); //返回广义表长度int depth(); //返回广义表深度GenListNode<T> insert(int i,T x); //返回原子x作为第i个元素 GenListNode<T> insert(int i,GenList<T> glist);//插入子表作为第i个元素void remove(int i); //删除第i个元素}6.广义表的存储结构
a.广义表的单链表示结点说明:其有三个域组成,分别为如下:atom:其是一个标志位,表示该元素是否为原子,atom=1,为原子。atom=0,为子表。data:当atom=1,data域的保存原子信息,atom=0,data域保存子表的第一个结点地址。next:保存后继结点地址,若没有后继元素,next=null。b.广义表的双链表示
结点说明:其有三个域组成,分别为如下:data:数据,可为原子,也可为子表child:只当data为原子,child为null。next:保存后继结点地址,若没有后继元素,next=null。注意:广义表的双链表示必须带头结点,否则对共享子表进行头插入和头删除操作将产生错误。c.广义表的双链表示的实现
(1).广义表双链表示的结点类public class GenListNode<T>{ public T data; //数据域public GenList<T> child; //地址域,指向子表public GenListNode<T> next; //地址域,指向后继结点// 构造结点,data指定元素,child指向子表,next指向后继结点public GenListNode(T data,GenList<T> child,GenListNode<T> next){ this.data=data;this.child=child;this.next=next;}public GenListNode(T data){ this(data,null,null);}//构造头结点public GenListNode(){ this(null,null,null);}}(2)双链表示的广义表类
public class GenList<T> //双链表示的广义表类{ public GenListNode<T> head; //头指针,指向头结点//构造空广义表。创建头结点,三个域值都为nullpublic GenList(){ head=new GenListNode<T>();}public GenList(T[] atoms)//构造广义表,由数组提供原子初值,算法同单链表,方法体暂忽略//判断广义表是否空public boolean isEmpty(){ return head.next==null;}public int length() //返回广义表长度,算法同单链表,方法体暂忽略public String toString(){ return this.toString("");} //返回广义表所有元素的描述字符串//返回广义表所有元素值对应的字符串,形式为"(,)",广义表遍历算法,递归算法public String toString(String str){ str+="(";GenListNode<T> p=this.head.next;while(p!=null){ if(p.child==null)str+=p.data.toString();else{ str.child.toString(); //递归调用,遍历子表添加子表描述字符串if(p.next!=null)str+=",";p=p.next;}return str+")"; //如果是空表,只返回()}public int depth() //返回广义表深度,递归方法{ int max=1;GenListNode<T> p=this.head.next;while(p!=null){ if(p.child!=null){ int d=p.child.depth(); //递归调用,返回子表深度if(max<=d) //记住最大子表深度{ max=d+1 ;//当前广义表深度为子表深度加一}p=p.next;}return max;}//插入原子作为第i个元素,算法同单链表,方法体暂忽略public GenListNode<T> insert(int i,T x)public GenListNode<T> insert(int i,GenList<T> glist) //插入子表作为第i个元素
{ if(glist==null)return null; //不能插入空对象GenListNode<T> p=this.head;for(int j=0;p.next!=null&&j<i;j++){ p=p.next;}p.next=new GenListNode<T>(null,glist,p.next);return p.next;}//广义表最后添加原子结点,算法同单链表public void append(T x){while(p.next!=null){ p=p.next;}p.next=new GenListNode<T>(x,null,null);}//在广义表最后添加子表public void append(GenList<T> glist){ insert(integer.MAX_VALUE,glist); }}
(3)由原子数组构造广义表。
public class GenList_ex{ public static void main(String[] args){ String[] glist={"b","c","e"};GenList<String> glist1=new Genlist<String>(glist); //由原子数组构造广义表glist1.insert(0,"a"); //头插入原子glist1.insert(3,"d"); //中间插入glist.append("f"); //尾插入}
(4)由广义表表示创建广义表
public class GenList_String{ private static int i=0;public static GenList<String> createGenList(String gliststr){ i++; //跳过‘(’GenList<String> glist=new GenList<String>(); //构造空广义表,只有头结点GenListNode<String> p=glist.head; //指向头结点while(i<gliststr.length()){ char ch=gilststr.charAt(i);switch(ch){ case ',':i++; break;case '(':{ p.next=new GenListNode<String>(); //创建子表结点p=p.next;p.child=create(gliststr); //创建子表,递归调用break;}case ')':i++;return gilst;default : //字符串表示原子{ int j=i+1;ch=gliststr.charAt(j);while(ch!='('&&ch!=','&&ch!=')'){ j++;ch=gliststr.charAt(j);}p.next=new GenListNode<String>(gilststr.substring(i,j)); //创建结点p=p.next;i=j;}}}return null;}