数据结构（C语言版）ppt-第5章广义表的概念及运算.pptxVIP

广义表的概念及运算 （C语言版） 《数据结构》在线开放课程 主讲人：李刚 Email:191290281@ 1.顺序栈实例演示 广义表的定义 1 基本定义 广义表(Lists，又称列表)是线性表的推广，也可以说是线性和非线性之间的一种过渡结构。广义表是n(n≥0)个元素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=(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，b))，y) //B是深度为3的。 ④ C=((x，(a，b))，((x，(a，b))，y)) //C的深度为4。 ⑤ D=(a，(a，(a，(…)))) //D的深度为∞。 L 1.顺序栈实例演示 广义表的表示 2 图形表示 图形中的分支结点对应广义表，非分支结点一般是原子。 ① L=(a，b) a b L 1.顺序栈实例演示 广义表的表示 2 图形表示 图形中的分支结点对应广义表，非分支结点一般是原子。 ① L=(a，b) a b ② A=(x，(a，b)) x A L 1.顺序栈实例演示 广义表的表示 2 图形表示 图形中的分支结点对应广义表，非分支结点一般是原子。 ① L=(a，b) a b ② A=(x，(a，b)) ③ B=((x，(a，b))，y) x A y B L 1.顺序栈实例演示 广义表的表示 2 图形表示 图形中的分支结点对应广义表，非分支结点一般是原子。 ① L=(a，b) a b ④ C=((x,(a,b)),((x,(a,b)),y)) ② A=(x，(a，b)) ③ B=((x，(a，b))，y) x A y B C D 1.顺序栈实例演示 广义表的表示 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) ② C=((x，(a，b))，y，z) //tail(L)=(b) 取表尾运算 //tail(C)=(y，z) 《数据结构》在线开放课程 谢 谢！ 主讲人：李刚 Email:191290281@