01广义表的定义
1、广义表是线性表的推广,也有人称其为列表(lists,用复数形式以示与统称的表list的区别)。广泛地用于人工智能等领域的表处理语言LISP语言,把广义表作为基本的数据结构。
02广义表的存储结构
1、由广义表(a1,a2,a3…an)中的数据元素可以具有不同的结构(或是原子,或是列表),因此难以用顺序存储结构表示,通常采用链式存储结构,每个数据元素可用一个结点表示。
2、由于列表中的数据元素可能为原子或列表,由此需要两种数据结构的结点:一种是表结点,用以表示列表;一种是原子结点,用以表示原子。
3、若列表不空,则可分解成表头和表尾。由此,一个表结点可由3个域组成:标志域、指示表头的指针域和指示表尾的指针域;而原子结点只需两个域:标志域和值域。
03广义表
1、递归函数结构清晰、程序易读,且容易证明正确性,因此是程序设计的有力工具。
2、有时递归函数的执行效率很低,因此使用递归应该扬长避短。在程序设计中,不应该一味追求递归。
3、如果一个问题的求解过程有明显的递推规律,我们也很容易写出它的递推过程,则不必要使用递归。
4、以广义表为例,如何利用分治法进行递归算法设计。通常可以先写出问题求解的递归定义,和第二数学归纳法类似,递归定义由基本项和归纳项两部分组成。
5、递归定义的基本项描述了一个或几个递归过程的终结状态。
6、广义表的深度定义为广义表中括弧的重数,是广义表的一种量度。
7、任何一个非空广义表均可分解成表头和表尾,反之,一对确定的表头和表尾可唯一确定一个广义表。
更多案例可以go公众号:C语言入门到精通
正文完