广义表
参考：
广义表的定义
线性表 线性表指的是n≥0个元素a1, a2, a3...的有序数列，并且线性表的元素具有原子性，即结构上是不可分割的一个整体。
广义表(Generalized list，又称列表) 广义表则是线性表的一种扩展延伸。相对于线性表，广义表最大的特点在于其元素既可以是原子项，也可以是另一个有不定数量的元素组成的表（广义表）。 不难看出从广义表的定义是递归的。广义表是线性表的递归数据结构。
\[\text{LS}=(a_1,a_2,...a_n) \]- 通常用圆括号将广义表括起来，用逗号分隔其中的元素。
- 为了区别原子和广义表，书写时用大写字母表示广义表，用小写字母表示原子。
- 当 LS 非空时，称第一个元素 \(a_1\) 为 LS 的表头(head)，其余元素组成的表 \((a_2,a_3,...,a_n)\) 为表尾(tail)
A=( ):A是一个空表，其长度为0。
B=(b, c):B是一个长度为 2 的列表。
C=(a, (d, e, f)):C是一个长度为 2 的列表，其中第一个元素是原子 a，第二个元素是子表(d, e, f)。
D=(A, B, C):D是一个长度为 3 的列表，其中 3 个元素都是子表。
E=(a, E):E是一个长度为 2 的列表，它是一个递归表。
广义表的存储结构
广义表的存储采用链接存储结构
第一种存储结构
- tag 标记位用于区分此节点是原子还是子表，通常原子的 tag 值为 0，子表的 tag 值为 1
- 表结点中的
hp为表头指针，tp为表尾指针- 对于原子结点，把它看做一个子表，表头指针
hp指向该原子结点，表尾指针指向该原子结点后面的元素组成的子表。
- 对于原子结点，把它看做一个子表，表头指针
因此对于广义表 \((a,(b,c,d))\) ，存储结构如图所示：
- 除非 C 是一个空表，指针 C 的值为 NULL，否则指针 C 指向的一定是 tag 值为 1 的子表结点。
广义表的结点结构：
using Data = char;
struct GLNode
{
/// 用于区分表结点是原子元素还是子表的标志位
/// =0 是原子结点；=1 是表结点
int tag;
union {
Data data;///< 可能是原子结点
/// 可能是子表
struct
{
GLNode* hp;///< 指向表头的指针域
GLNode* tp;///< 指向表尾的指针域
}ptr;
};
};
- 由于同一时间结点不是原子结点，就是表结点，因此，使用了共用体
union
第二种存储结构
对于广义表 \((a,(b,c,d))\) ，存储结构如图所示：
广义表的数据类型
广义表的数据类型：
/// 广义表
class GList
{
private:
GLNode* first;///< 指向广义表第一元素的指针
/// 求输入字符串的表头和表尾
/// @param head 指向字符串的指针的引用
/// @param tail 指向字符串的指针的引用
static void getHandT(const char src[], char*& head, char*& tail);
/// 销毁广义表的递归算法
/// @param pNode 指向要销毁的广义表的指针的引用
static void DeleteAll(GLNode *&pNode);
public:
/// 拷贝广义表的递归算法
/// @param tar 目标广义表指针的引用
/// @param src 源广义表指针
static void copy(GLNode *&tar, const GLNode* src);
/// 由字符串创建广义表的递归算法
/// @param str 输入的字符串
/// @return 返回由字符串创建的广义表
static GLNode* CreatGList(const char str[]);
/// 输出广义表的递归算法
/// @param 要输出的广义表的头指针
static void PrintGList(GLNode* p);
/// 求广义表的深度的递归算法
/// @param 返回广义表的深度
static int GListDepth(GLNode* p);
public:
/// 默认构造
GList():first(nullptr) {}
/// 构造函数
/// 使用 GLNode* 类型的广义表构造广义表
/// @param src 源广义表指针
GList(const GLNode* src);
/// 拷贝构造
/// @param src 源广义表指针
GList(const GList& src);
/// 构造函数
/// 使用字符串构造广义表
/// @param str 广义表字符串形式
GList(const char str[]);
/// 输出广义表
void Print(void) const
{
GList::PrintGList(first);
}
/// 清空广义表
void Clear(void) {
GList::DeleteAll(first);
}
~GList() {
GList::DeleteAll(first);
}
/// 求长度
/// @param 返回广义表的长度
int Length() const;
/// 求深度
/// @return 返回广义表的深度
int Depth() const
{
return GList::GListDepth(first);
}
/// 在尾部插入一个结点
/// @param node 要插入的结点
void Push_Back(GLNode* node);
/// 在尾部插入一个表结点
/// @param glist 要插入的表结点
void Push_Back(const GList& glist);
/// 插入结点
/// 头插法插入节点
/// @param i 在第 i 个元素前面插入(i 从 1 开始)
/// @param node 要插入的结点
/// @return 插入成功返回 true，插入失败返回 false
bool Insert(const int& i, GLNode* node);
GLNode* GetHead() const; ///< 取广义表表头
GLNode* GetTail() const; ///< 取广义表表尾
GLNode* GetFirst() const; ///< 取广义表的第一个元素的子表结点
GLNode* GetLast() const; ///< 取广义表的最后一个元素的子表结点
GLNode* GetElement(const int& i) const; ///< 取广义表的第 i 个元素的子表结点
};
广义表的重要运算
以第一种存储结构为例。
1. 拷贝广义表
- 由于要修改指针的值，应采用指针传递（使用二级指针）或引用传递。这里使用引用传递。
/// 拷贝广义表的递归算法
/// @param tar 目标广义表指针的引用
/// @param src 源广义表指针
static void copy(GLNode *&tar, const GLNode* src);
/// 拷贝广义表的递归算法
/// 如果是原子结点，拷贝为原子结点；如果是表结点，拷贝为表结点
void GList::copy(GLNode *&tar, const GLNode* src)
{
// 如果源为空列表，那么目标也为空列表
if (src == nullptr)
{
tar = nullptr;
}
else
{
tar = new GLNode;
tar->tag = src->tag;
if (src->tag == 1)// 如为子表
{
GList::copy(tar->ptr.hp, src->ptr.hp);// 复制表头
GList::copy(tar->ptr.tp, src->ptr.tp);// 复制表尾
}
else// 如为原子结点
{
tar->data = src->data;
}
}
}
2. 销毁广义表
/// 销毁广义表的递归算法
/// @param pNode 指向要销毁的广义表的指针的引用
static void DeleteAll(GLNode *&pNode);
void GList::DeleteAll(GLNode*& pNode)
{
if (pNode->tag == 0)
{
// pNode
// |
// [ ]
delete pNode;
pNode = nullptr;
}
else if (pNode->ptr.tp == nullptr)
{
// pNode--->( )
// |
// ( )/[ ]
GList::DeleteAll(pNode->ptr.hp);
delete pNode;
pNode = nullptr;
}
else
{
// pNode--->( )---( )
// |
// ( )/[ ]
GList::DeleteAll(pNode->ptr.hp);
GList::DeleteAll(pNode->ptr.tp);
delete pNode;
pNode = nullptr;
}
}
3. 由字符串创建广义表
求字符串形式的广义表的表头和表尾
void GList::getHandT(const char str[], char*& head, char*& tail)
{
int len = strlen(str);
// 左括号和右括号匹配信息标志位
// tag = 0，表示遍历到的左右括号数量相等
// tag = i，表示遍历到的左括号数量比右括号多 i 个
int tag = 0;
int i;
for (i = 0;i < len; i++)
{
// 遍历完表头
// ((a,b,c),e,(n,f))
// |
// i
if (str[i] == ',' && tag == 1)
break;
if (str[i] == '(')// ='('+1
tag++;
if (str[i] == ')')// =')'-1
tag--;
}
if (i < len && str[i] == ',')// 如果表尾非空
{
// 求表头字符串
head = new char[i];// 减去一个多余的左括号，再 + '\0'
for (int j = 1; j < i; j++)
{
head[j - 1] = str[j];
}
head[i - 1] = '\0';// 字符串以 '\0' 结束
// 求表尾字符串
tail = new char[len - i + 1];// 减去表头的字符串，再 + '\0'
tail[0] = '(';
for (int j = i + 1; j < len; j++)
{
tail[j - i] = str[j];
}
tail[len - i] = '\0';// 字符串以 '\0' 结束
}
else
{
// 此时 i = 字符串长度
head = new char[i - 1];// 减去最外层的一对括号，再 + '\0'
for (int j = 1; j < i - 1; j++)
{
head[j - 1] = str[j];
}
head[i - 2] = '\0';// 字符串以 '\0' 结束
tail = new char[3];
strcpy_s(tail, 3, "()");// strcpy 会自动添加 '\0'
}
}
读取字符串创建广义表的递归算法
/// 读取字符串创建广义表的递归算法
/// @param str 输入的字符串
/// @return 返回由字符串创建的广义表
static GLNode* CreatGList(const char str[]);
GLNode* GList::CreatGList(const char str[])
{
// 如为空字符串，返回空指针
if (str == nullptr || str[0] == '\0')
{
return nullptr;
}
// 先为一个结点分配空间
GLNode* glist = new GLNode;
if (strlen(str) == 1)
{
// 假设 src 合法，如果 strlen(str) == 1，只有可能为原子结点
glist->tag = 0;
glist->data = str[0];
}
else
{
glist->tag = 1;
char* head;// 表头字符串
char* tail;// 表尾字符串
// 求出表头表尾字符串
GList::getHandT(str, head, tail);
// 由表头字符串构造子表结点的表头
glist->ptr.hp = GList::CreatGList(head);
if (strcmp(tail, "()") == 0)
{
// 如 tail = "()"，表尾为空
glist->ptr.tp = nullptr;
}
else
{
// 由表尾字符串构造子表结点的表尾
glist->ptr.tp = GList::CreatGList(tail);
}
}
return glist;
}