广义表的存储结构详解包括2种存储方案

发布时间：2022-07-07 10:05 所属栏目：51 来源：互联网

导读：由于广义表中既可存储原子（不可再分的数据元素），也可以存储子表，因此很难使用顺序存储结构表示，通常情况下广义表结构采用链表实现。使用顺序表实现广义表结构，不仅需要操作 n 维数组（例如 {1,{2,{3,4}}} 就需要使用三维数组存储），还会造成存储空间

　　由于广义表中既可存储原子（不可再分的数据元素），也可以存储子表，因此很难使用顺序存储结构表示，通常情况下广义表结构采用链表实现。
　　使用顺序表实现广义表结构，不仅需要操作 n 维数组（例如 {1,{2,{3,4}}} 就需要使用三维数组存储），还会造成存储空间的浪费。

　　tag 标记位用于区分此节点是原子还是子表，通常原子的 tag 值为 0，子表的 tag 值为 1。子表节点中的 hp 指针用于连接本子表中存储的原子或子表，tp 指针用于连接广义表中下一个原子或子表。

　　因此，广义表中两种节点的 C 语言表示代码为：
　　typedef struct GLNode{
　　    int tag;//标志域
　　    union{
　　        char atom;//原子结点的值域
　　        struct{
　　            struct GLNode * hp,*tp;
　　        }ptr;//子表结点的指针域，hp指向表头；tp指向表尾
　　    }subNode;
　　}*Glist;
　　这里用到了 union 共用体，因为同一时间此节点不是原子节点就是子表节点，当表示原子节点时，就使用 atom 变量；反之则使用 ptr 结构体。

（编辑：ASP站长网）

广义表的存储结构详解 包括2种存储方案

广义表的存储结构详解包括2种存储方案