资源描述：
《数据结构广义表只是课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、数据结构广义表5．E=(a,E)这是一个递归列表，其元素中有自己。广义表也可以用图形表示，例如前述的广义表D和E可表示为：beacdaDABC广义表DE广义表E2广义表的基本运算广义表的基本运算⑴取表头HEAD(LS)；⑵取表尾TAIL(LS)。3广义表的存储结构广义表中的数据元素可以是单元素，或是广义表，很难用顺序存储结构表示，常采用链式存储结构。1.表头表尾链存储结构有两类结点：表结点和单元素结点。┌───┬────┬───┐│tag=1│hp│tp│表结点└───┴────┴───┘┌───┬───
2、─────┐│tag=0│data│单元素结点└───┴────────┘tag标志域，0表示结点为单元素结点，1表示为表结点；hp：表头指针域；tp：表尾指针域；data：值域。3广义表的存储结构形式描述为：typedefenum{ATOM,LIST}ElemTagtypedefstructGLNode{//定义广义表结点ElemTagetag;//公共部分，用以区分原子结点和表结点Union{//原子结点和表结点的联合部分AtomTypeatom;//原子类型结点域，//AtomType由用户定义St
3、ruct{structGLNode*hp,*tp;}ptr;};//表结点的指针域，//ptr.hp与ptr.tp分别指向广义表的表头和表尾。}*Glist;//广义表类型3广义表的存储结构这种存储结构的特点是：最上层的表结点数即为广义表的长度；层次清楚；表结点数目多，与广义表中括号对的数目不匹配。例:C=(a,(b,c,d))111110a0b0c0d＾＾((b,c,d))(b,c,d)(c,d)(d)C3广义表的存储结构2.同层结点链存储结构有两类结点：表结点和单元素结点。┌────┬───┬───┐
4、│tag=1│hp│tp│表结点└────┴───┴───┘┌────┬───┬───┐│tag=0│data│tp│单元素结点└────┴───┴───┘结点结构是无论什么结点都有三个域：第一个域是结点类型标志tag；第二个域是指向一个列表的指针（当tag=1时）或一个原子（当tag=0时）；第三个域是指向下一个结点的指针tp。3广义表的存储结构形式描述为：typedefenum{ATOM,LIST}ElemTagtypedefstructGLNode{//定义广义表结点ElemTagetag;//公共
5、部分，用以区分原子结点和表结点Unin{//原子结点和表结点的联合部分AtomTypeatom;//原子类型结点域，//AtomType由用户定义structGLNode*hp,;//表结点的表头指针域};structGLNode*tp;//指向下一个结点的指针}*Glist;//广义表类型3广义表的存储结构同层结点链结构的特点是：表结点的数目与广义表的括号对数目一致；写递归算法不方便。例:C=(a,(b,c,d))1C＾0a1＾0b0c0d＾(b,c,d)应用：M元多项式的表示对任何一个M元多项式P，先
6、确定一个主变元，于是它可看成主变元的一元多项式，但它的系数可能是一个多项式，也可能是一个常数。于是P可表为一个线性表P=((α1,expn1),(α2,expn2),…,(αn,expnn))其中每个αi可能是一个常数，也可能又是一个多项式；对于每一个多项式αj,又可以确定一个主变元（可称为原多项式的第二变元），从而，可表为下一级的一元多项式，其系数又可能性是常数，也可能是多项式；…；直到最后纯粹的一元多项式。所以M元多项式，最好用广义表来表示。其元素结点如下图：表结点（多项式结点）原子结点（常系数结点）
7、tag=1exphptptag=0expcoeftp其形式定义如下：typedefstructMPNode{ElemTagtag;//区分原子结点和表结点intexpn;//指数域union{//原子结点和表结点共享一个域floatcoef;//系数域structMPNode*hp;//表结点的表头指针}structMPNode*tp;//指向下一个元素结点}*MPList;//M元多项广义表类型M元多项式的表示例:P(x,y,z)=x10y3z2+2x6y3z2+3x5y2z2+x4y4z+6x3y4z
8、+2yz+15=(x10y3+2x6y3+3x5y2)z2+(x4y4+6x3y4+2y)z+15=((x10+2x6)y3+3x5y2)z2+((x4+6x3)y4+2y)z+15=Az2+Bz+15z0其中:A=Cy3+Dy2C=x10+2x6D=3x5可用广义表表示为:P(x,y,z)=z((A,2),(B,1),(15,0))A=y((C,3),(D,2))B=y((E,4),(2,1))C=x((1,10),(2,6
