数据结构（c语言版）第5章广义表的概念及运算

1、广义表的概念及运算（C语言版）数据结构在线开放课程主讲人：李刚 广义表的定义01 广义表的表示02 广义表的运算031.顺序栈实例演示 广义表的定义1基本定义广义表(Lists，又称列表)是线性表的推广，也可以说是线性和非线性之间的一种过渡结构。广义表是n(n0)个元素a1，a2，ai，an组成的有限序列。 ai可以是原子或者是一个广义表。 广义表通常记作：Ls=(a1，a2，ai，an)。 若ai是广义表，则称它为Ls的子表。 Ls是广义表的名字，n为它的长度。1.顺序栈实例演示 广义表的表示2常用表示 E=() /E是一个空表，其长度为0。 L=(a，b) /L是长度为2的广义表。 A=(

2、x，L)=(x，(a，b) /A是长度为2的广义表，第一个元素是原子x，第二个元素是子表L。 B=(A，y)=(x，(a，b)，y) /B是长度为2的广义表，第一个元素是子表A，第二个元素是原子y。 C=(A，B)=(x，(a，b)，(x，(a，b)，y) /C的长度为2，两个元素都是子表。 D=(a，D)=(a，(a，(a，() /D的长度为2，第一个元素是原子，第二个元素是D自身，展开后它是一个无限的广义表。1.顺序栈实例演示 广义表的表示2广义表深度广义表的“深度”是指广义表展开后所含括号的层数。 L=(a，b) /L是深度为1。 A=(x，(a，b) /A是深度为2。 B=(x，(a，

3、b)，y) /B是深度为3的。 C=(x，(a，b)，(x，(a，b)，y) /C的深度为4。 D=(a，(a，(a，() /D的深度为。L1.顺序栈实例演示 广义表的表示2图形表示图形中的分支结点对应广义表，非分支结点一般是原子。 L=(a，b)abL1.顺序栈实例演示 广义表的表示2图形表示图形中的分支结点对应广义表，非分支结点一般是原子。 L=(a，b)ab A=(x，(a，b) xAL1.顺序栈实例演示 广义表的表示2图形表示图形中的分支结点对应广义表，非分支结点一般是原子。 L=(a，b)ab A=(x，(a，b) B=(x，(a，b)，y) xAyBL1.顺序栈实例演示 广义表的表

4、示2图形表示图形中的分支结点对应广义表，非分支结点一般是原子。 L=(a，b)ab C=(x,(a,b),(x,(a,b),y) A=(x，(a，b) B=(x，(a，b)，y) xAyBCD1.顺序栈实例演示 广义表的表示2图形表示图形中的分支结点对应广义表，非分支结点一般是原子。 L=(a，b)a C=(x,(a,b),(x,(a,b),y) D=(a，(a，(a，() A=(x，(a，b) B=(x，(a，b)，y) 1.顺序栈实例演示 广义表的运算3任何一个非空广义表的表头是表中第一个元素，它可以是原子，也可以是子表，运算符为head。 L=(a，b) B=(x，(a，b)，y) /head(L)=a取表头运算 /head(B)=(x，(a，b)1.顺序栈实例演示 广义表的运算3任何一个非空广义表的表尾必定是子表（除了第一个元素以外其他元素的集合），运算符为tail 。 L=(a，b)