当前位置：首页 > article >正文

嵌套之美：广义表，在数据层层叠叠之间，展现信息的层次

article 2025/1/18 20:06:47

一、基本概念

二、运行方式

三、运用场景

四、解题思路

五、代码实现

1. 广义表的存储结构

2. 广义表深度计算

六、易错提示

七、代码分析

八、深度剖析

九、总结

一、基本概念

广义表（Generalized List）是一种递归的数据结构，它可以包含零个或多个元素，每个元素可以是原子或另一个广义表。广义表可以看作是线性表的推广，它允许嵌套结构，使其能够表示更加复杂的数据关系。

二、运行方式

广义表通常使用递归的方式进行操作。例如，访问广义表中的元素，判断广义表是否为空，计算广义表的深度等操作，都需要递归算法。

三、运用场景

广义表在很多领域都有应用，例如：

表示树形结构： 广义表可以用来表示树形结构，例如文件目录结构、语法树等。
表示多维数组： 广义表可以用来表示多维数组，例如矩阵等。
表示表达式： 广义表可以用来表示表达式，例如数学表达式、逻辑表达式等。
表示程序代码： 广义表可以用来表示程序代码，例如语法树、符号表等。

四、解题思路

在使用广义表解决问题时，需要仔细分析问题的特点，并制定合适的算法。一般来说，需要考虑以下几个方面：

广义表的存储结构： 应该选择合适的存储结构来存储广义表，例如线性链表、树形结构等。
广义表的访问方式： 应该根据问题的要求，选择合适的访问方式，例如递归访问、迭代访问等。
广义表的运算方式： 应该根据问题的要求，选择合适的运算方式，例如求深度、求长度、求元素个数等。
广义表的转换： 应该根据问题的要求，将广义表转换为其他数据结构，例如树形结构、线性链表等。

五、代码实现

1. 广义表的存储结构

#include <stdio.h>
#include <stdlib.h>

typedef struct GListNode 
{
    char data; // 存放原子数据
    struct GListNode *next; // 指向下一个节点
    struct GListNode *subList; // 指向子表头节点
} GListNode;

typedef struct GList 
{
    GListNode *head; // 广义表头节点
} GList;

// 创建一个新的广义表节点
GListNode *createGListNode(char data) 
{
    GListNode *node = (GListNode *)malloc(sizeof(GListNode));
    if (node != NULL) 
    {
        node->data = data;
        node->next = NULL;
        node->subList = NULL;
    }
    return node;
}

// 创建一个新的广义表
GList *createGList() 
{
    GList *list = (GList *)malloc(sizeof(GList));
    if (list != NULL) 
    {
        list->head = NULL;
    }
    return list;
}

// 在广义表尾部添加一个节点
void addGListNode(GList *list, char data) 
{
    GListNode *node = createGListNode(data);
    if (list->head == NULL) 
    {
        list->head = node;
    } 
    else 
    {
        GListNode *p = list->head;
        while (p->next != NULL) 
        {
            p = p->next;
        }
        p->next = node;
    }
}

// 在广义表中插入一个子表
void insertSubList(GListNode *node, GList *subList) 
{
    node->subList = subList->head;
}

// 打印广义表
void printGList(GList *list) 
{
    GListNode *p = list->head;
    while (p != NULL) 
    {
        printf("%c", p->data);
        if (p->subList != NULL) 
        {
            printf("(");
            printGList(p->subList);
            printf(")");
        }
        p = p->next;
        if (p != NULL) 
        {
            printf(", ");
        }
    }
}

int main() 
{
    // 创建一个广义表
    GList *list = createGList();
    addGListNode(list, 'A');
    addGListNode(list, 'B');

    // 创建一个子表
    GList *subList = createGList();
    addGListNode(subList, 'C');
    addGListNode(subList, 'D');

    // 将子表插入到广义表中
    GListNode *p = list->head->next; // 指向第二个节点
    insertSubList(p, subList);

    // 打印广义表
    printGList(list);
    printf("\n");
    return 0;
}

2. 广义表深度计算

#include <stdio.h>
#include <stdlib.h>

typedef struct GListNode 
{
    char data;
    struct GListNode *next;
    struct GListNode *subList;
} GListNode;

typedef struct GList 
{
    GListNode *head;
} GList;

// 创建一个新的广义表节点
GListNode *createGListNode(char data) 
{
    GListNode *node = (GListNode *)malloc(sizeof(GListNode));
    if (node != NULL) 
    {
        node->data = data;
        node->next = NULL;
        node->subList = NULL;
    }
    return node;
}

// 创建一个新的广义表
GList *createGList() 
{
    GList *list = (GList *)malloc(sizeof(GList));
    if (list != NULL) 
    {
        list->head = NULL;
    }
    return list;
}

// 在广义表尾部添加一个节点
void addGListNode(GList *list, char data) 
{
    GListNode *node = createGListNode(data);
    if (list->head == NULL) 
    {
        list->head = node;
    } 
    else 
    {
        GListNode *p = list->head;
        while (p->next != NULL) 
        {
            p = p->next;
        }
        p->next = node;
    }
}

// 在广义表中插入一个子表
void insertSubList(GListNode *node, GList *subList) 
{
    node->subList = subList->head;
}

// 计算广义表的深度
int getDepth(GList *list) 
{
    if (list->head == NULL) 
    {
        return 0; // 空表深度为0
    }
    int maxDepth = 0; // 初始化最大深度
    GListNode *p = list->head;
    while (p != NULL) 
    {
        int subListDepth = 0; // 子表深度
        if (p->subList != NULL) 
        {
            subListDepth = getDepth(p->subList); // 递归计算子表深度
        }
        maxDepth = (subListDepth + 1) > maxDepth ? (subListDepth + 1) : maxDepth; // 更新最大深度
        p = p->next;
    }
    return maxDepth;
}

int main() 
{
    GList *list = createGList();
    addGListNode(list, 'A');
    addGListNode(list, 'B');

    GList *subList1 = createGList();
    addGListNode(subList1, 'C');
    addGListNode(subList1, 'D');

    GList *subList2 = createGList();
    addGListNode(subList2, 'E');
    addGListNode(subList2, 'F');

    GListNode *p = list->head->next; // 指向第二个节点
    insertSubList(p, subList1);

    p = p->next; // 指向第三个节点
    insertSubList(p, subList2);

    int depth = getDepth(list);
    printf("广义表深度为：%d\n", depth);
    return 0;
}