广义表学习笔记

1. 广义表的定义

广义表（Generalized List）是一种递归的数据结构，可以为空表或包含原子和子表的表。广义表中的元素可以是原子（不可再分的基本元素）也可以是广义表，这使得广义表能够表示具有复杂嵌套结构的数据。

2. 广义表的表示

广义表通常用括号表示，括号内的元素用逗号分隔。例如：

• 空表：()
• 原子表：(a, b, c)
• 嵌套表：(a, (b, c), d)

3. 广义表的基本操作

3.1 创建广义表

广义表的创建可以通过递归来实现。每个节点可以是原子或子表。

class GListNode:
    def __init__(self, data=None, sublist=None):
        self.data = data
        self.sublist = sublist

def create_glist(elements):
    if not elements:
        return None
    head = GListNode(elements[0])
    if isinstance(elements[0], list):
        head.sublist = create_glist(elements[0])
    current = head
    for element in elements[1:]:
        node = GListNode(element)
        if isinstance(element, list):
            node.sublist = create_glist(element)
        current.next = node
        current = node
    return head

3.2 访问广义表元素

访问广义表元素时需要递归地遍历每个节点。

def traverse_glist(glist):
    if glist is None:
        return
    if glist.data is not None:
        print(glist.data, end=' ')
    if glist.sublist is not None:
        traverse_glist(glist.sublist)
    traverse_glist(glist.next)

3.3 广义表的深度

广义表的深度是指广义表中嵌套层次的最大值，可以通过递归来计算。

def glist_depth(glist):
    if glist is None:
        return 0
    if glist.sublist is None:
        return 1
    return max(1 + glist_depth(glist.sublist), glist_depth(glist.next))

4. 广义表的应用

4.1 表达式树

广义表可以用来表示表达式树，其中每个节点可以是操作符或操作数。通过递归遍历表达式树，可以进行表达式的求值。

4.2 数据库

广义表可以用来表示复杂的嵌套数据结构，例如数据库中的多级表格结构。这使得广义表在表示和处理复杂数据时具有很大的灵活性。

5. 广义表的优缺点

5.1 优点

• 灵活性高：能够表示任意嵌套层次的数据结构。
• 表示能力强：可以表示复杂的嵌套关系和递归结构。

5.2 缺点

• 实现复杂：需要递归处理，增加了实现的复杂度。
• 操作成本高：由于需要递归遍历，某些操作的时间复杂度较高。