广义表的运算

5.5　广义表的运算

由于广义表是线性表的一种推广和扩充,因此和线性表类似,可以对广义表进行定位、插入和删除等操作。但广义表在结构上较线性表复杂得多,在具体操作的实现上不如线性表简单。本节主要讨论几种广义表运算的算法。由于广义表的定义是递归的,因此相应的算法一般也都是递归算法。

5.5.1　广义表的创建与销毁

1.创建广义表

创建广义表就是按广义表的书写形式建立广义表的存储结构,即将广义表的数据元素存储起来。假设广义表中的原子类型为字符且广义表无共享子表,则可使用递归方式建立广义表,其算法基本思想如下。

（1）判断输入广义表的字符是否为空。如果是,则置表头指针为空；否则继续执行步骤（2）。

（2）判断广义表中字符串的字符:若为“（”,则表明其是一个子表的开始,将p结点的标志域置1,生成新结点,用指针p指向新结点,并将p结点的hp域作为子表的表头指针递归构造子表；当碰到“）”时,算法结束；当碰到英文字母时,表明它是一个原子,则建立一个原子结点；当碰到“,”时,表明存在后继元素,需要建立当前结点的后继表；当碰到一个字符“＃”时,表示其为一个空表。

采用扩展线性链表存储结构实现广义表创建的算法描述如下。

广义表创建算法的时间复杂度为O（n）。

2.销毁广义表

销毁广义表就是当一个广义表不再使用时,释放其所占用的动态存储空间。采用从前往后的方式销毁表中的每个元素,如果某个元素是子表,则通过递归调用销毁。其具体算法实现如下。

销毁广义表算法的时间复杂度为O（n）。

5.5.2　广义表的定位、插入和删除

广义表的定位、插入和删除操作需要知道广义表中元素的位置。假设x是一个原子或子表,则x在广义表中的位置可以用层次序号表（k₁,k₂,…,k_m）表示。其中,k₁表示x是广义表的第几个元素或位于广义表第几个元素中,如果x是子表,则k₂表示是子表的第几个元素或位于子表的第几个元素中,依此类推。m是x在广义表中所处的层次,例如广义表为（a,（b）,（（c,d）,e））,则原子d的层次序号表为（3,1,2）,子表（b）的层次序号表为（2,1）。

1.广义表定位

广义表的定位操作要求根据给定元素的层次序号表,确定广义表中某个元素的地址,即原子结点的地址或子表的表头地址。

假设使用数组w[m]存储元素的层次序号表,m表示广义表深度。如果要定位元素位于i层,则w₀～w_i－1均大于0,w_i～w_m－1均等于0。广义表采用扩展链表存储,相应算法描述如下。

该算法时间复杂度与所查找元素的位置有关。假设广义表的长度为n,深度为m,则该算法的时间复杂度为O（m×n）。

2.广义表插入

广义表插入的操作有以下两种方法。

（1）将元素e插入广义表,作为广义表的第一元素。该运算采用算法实现的基本思路为:先找到广义表L,然后将L的hp指针指向新插入元素结点,新结点的tp指针则指向原广义表的第一元素结点。采用扩展链表存储广义表,插入算法的具体实现如下。

该算法比较简单,其时间复杂度为O（1）。

（2）根据层次序号表w[m],将一个新的原子或子表插入到广义表L中的指定结点之后。该算法实现的基本思路为:先找到层次序号表w[m]所指示的结点p,然后将新原子或子表s插入在p结点之后。插入算法的具体实现如下。

该算法时间主要消耗在查找插入位置上,因此算法时间复杂度为O（m×n）。

3.广义表删除

广义表的删除是指将指定元素从广义表中删除。广义表的删除操作也分为以下两种方法。

（1）将广义表L中第一元素删除,即表头删除。该算法实现的基本思路为:将当前广义表L的hp指针指向L－＞hp所指结点的tp指针指示的结点,使用e返回其值。采用扩展链表存储广义表,其具体算法如下。

该算法时间复杂度为O（1）。

（2）删除据层次序号表w[m]所指示的原子或子表。实现该算法需要先找到层次序号表所指示位置的前一个位置,此处分为两种情况,如图5－19所示。

图5－19　删除广义表元素示意图

由图5－19可知,要删除w[m]所指示的元素,必须先找到最后一个非零元素w_k,并判断w_k－1是否为0。如果w_k－1＝0,则p结点的hp域指向被删除结点的后继结点；否则p结点的tp域指向被删除结点的后继结点。

其具体算法如下。

与插入算法相同,该算法的时间复杂度为O（m×n）。

5.5.3　判断两个广义表是否相等

两个广义表相等是指两个广义表具有相同的存储结构,对应的原子结点数据域值也相同。采用头尾链表判断广义表P和Q是否相等的基本思想如下。

（1）当P和Q均为空表时,两个广义表相等；当P和Q一个为空一个非空,两个广义表不相等；当P和Q一个指向原子结点,另一个指向表结点时,两个广义表不相等；当二者均指向原子结点,但其值域不相同时,两个广义表不相等。

（2）当P和Q均指向原子结点时,如果其数据域值相等,则再判断两个表的表尾是否相等；当P和Q均指向表结点时,先判断两个表的表头是否相等,如果相等则再判断两个表的表尾是否相等。

其具体算法实现如下。

该算法是一个递归算法,算法中时间主要消耗在P和Q对应结点的比较上。如果两个广义表相等,则需要比较次数为两表中元素的个数,因此时间复杂度为O（P.length）或O（Q.length）。

本章小结

1.矩阵,即二维数组,其中的每一个元素都是一个定长的线性表（一维数组）,都要受到两个关系即行关系和列关系的约束,也就是每个元素都同属于两个线性表。因此,当采用顺序存储结构存储矩阵时,按照存取方式不同,可分为以行为主序存储和以列为主序存储两种。在矩阵中,还有一些非零元素或零元素的分布有一定规律的特殊矩阵,为了节省存储空间,对这类矩阵的存储采用压缩存储。即对多个相同的非零元素只分配一个存储空间,对零元素不分配存储空间。

2.稀疏矩阵,其大部分元素为零,为了方便存储采用三元组的方式存储其数据元素。整体上,稀疏矩阵的存储结构分为三元组顺序表、行逻辑顺序表和十字链表三种。根据存储结构的不同,其基本操作的实现方法也不同。

3.广义表是线性表的扩展。广义表也是n（n≥0）数据元素a₁,a₂,a₃,…,a_n的有限序列,通常记作:LS＝（a₁,a₂,a₃,…,a_n）。与线性表不同的是,广义表中的a_i则既可以是单个元素（称为原子,用单个小写字母表示）,还可以是一个广义表。广义表可以采用头尾链表和扩展线性链表两种存储结构,在这两种存储结构下可以很方便地实现广义表的创建、销毁、定位、插入、删除、判断相等等操作。