资源描述：
《《数据结构广义表》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、广义表1广义表的定义2广义表的基本运算3广义表的存储结构1广义表的定义一、广义表定义广义表可定义为：数据元素可以是表的线性表。记为：LS＝(d1,d2,…,dn)LS为表名，di(i＝1,2,…,n)，可以是单元素(称为原子，用小写字母表示)，也可以是广义表(称为子表，用大写字母表示)；若广义表LS非空，则必有n大于0（即n>0）n为表的长度，当长度为0时称为空表；称非空表的第一个元素d1为表头，其余元素组成的表(d2,…,dn)称为表尾。注意：表尾可以可以是空表，而表头可以是原子，也可以是一个表。广义表的抽象类型定义采用递归定义如教材P.107。二、广义表的
2、表达方式及例子1．A=()A是一个空表，其长度为0。2．B=(e)列表B只有一个原子e，其长度为1。3．C=(a,(b,c,d))列表C的长度为2，表头为原子，第二个元素是一个列表(b,c,d)。4.D=(A,B,C)列表D的长度为3，表头也是一个列表A，表尾是列表（A,B）,注意：这里引用了已有的列表A、B、C作为该广义表D的元素。5．E=(a,E)这是一个递归列表，其元素中有自己。广义表也可以用图形表示，例如前述的广义表D和E可表示为：beacdaDABC广义表DE广义表E2广义表的基本运算广义表的基本运算⑴取表头HEAD(LS)；⑵取表尾TAIL(LS)
3、。3广义表的存储结构广义表中的数据元素可以是单元素，或是广义表，很难用顺序存储结构表示，常采用链式存储结构。1.表头表尾链存储结构有两类结点：表结点和单元素结点。┌───┬────┬───┐│tag=1│hp│tp│表结点└───┴────┴───┘┌───┬────────┐│tag=0│data│单元素结点└───┴────────┘tag标志域，0表示结点为单元素结点，1表示为表结点；hp：表头指针域；tp：表尾指针域；data：值域。3广义表的存储结构形式描述为：typedefenum{ATOM,LIST}ElemTagtypedefstructGLN
4、ode{//定义广义表结点ElemTagetag;//公共部分，用以区分原子结点和表结点Union{//原子结点和表结点的联合部分AtomTypeatom;//原子类型结点域，//AtomType由用户定义Struct{structGLNode*hp,*tp;}ptr;};//表结点的指针域，//ptr.hp与ptr.tp分别指向广义表的表头和表尾。}*Glist;//广义表类型3广义表的存储结构这种存储结构的特点是：最上层的表结点数即为广义表的长度；层次清楚；表结点数目多，与广义表中括号对的数目不匹配。例:C=(a,(b,c,d))111110a0b0c0d
5、＾＾((b,c,d))(b,c,d)(c,d)(d)C3广义表的存储结构2.同层结点链存储结构有两类结点：表结点和单元素结点。┌────┬───┬───┐│tag=1│hp│tp│表结点└────┴───┴───┘┌────┬───┬───┐│tag=0│data│tp│单元素结点└────┴───┴───┘结点结构是无论什么结点都有三个域：第一个域是结点类型标志tag；第二个域是指向一个列表的指针（当tag=1时）或一个原子（当tag=0时）；第三个域是指向下一个结点的指针tp。3广义表的存储结构形式描述为：typedefenum{ATOM,LIST}Ele
6、mTagtypedefstructGLNode{//定义广义表结点ElemTagetag;//公共部分，用以区分原子结点和表结点Unin{//原子结点和表结点的联合部分AtomTypeatom;//原子类型结点域，//AtomType由用户定义structGLNode*hp,;//表结点的表头指针域};structGLNode*tp;//指向下一个结点的指针}*Glist;//广义表类型3广义表的存储结构同层结点链结构的特点是：表结点的数目与广义表的括号对数目一致；写递归算法不方便。例:C=(a,(b,c,d))1C＾0a1＾0b0c0d＾(b,c,d)应用：
7、M元多项式的表示对任何一个M元多项式P，先确定一个主变元，于是它可看成主变元的一元多项式，但它的系数可能是一个多项式，也可能是一个常数。于是P可表为一个线性表P=((α1,expn1),(α2,expn2),…,(αn,expnn))其中每个αi可能是一个常数，也可能又是一个多项式；对于每一个多项式αj,又可以确定一个主变元（可称为原多项式的第二变元），从而，可表为下一级的一元多项式，其系数又可能性是常数，也可能是多项式；…；直到最后纯粹的一元多项式。所以M元多项式，最好用广义表来表示。其元素结点如下图：表结点（多项式结点）原子结点（常系数结点）tag=1ex
8、phptptag=0expcoeftp
