C++编程实践—广义表分析
一、广义表
在前面分析表的数据结构时，就对广义表进行了初步的分析。Generalized Table作为线性表的一种扩展，其内容有点类似于循环嵌套的调用。即“自己包含自己”的一种情况，也可以认为是一种递归定义的方式。总之，目的是为了容易理解广义表而采用何种方式来理解就因人而异即可。
广义表的定义一般类似于下面的情况：
A = (a,(b,(c))) B =(a,(b,c)) C =(a,C)正是因为这种表示多层嵌套的数据结构，所以其在AI和LISP及数据库及编译器（如ADT数据结构）等领域，应用非常广泛。
二、数学定义
在数学上，广义表有着严格的定义：
广义表LS是由n(n≥0)个元素 a1,a2,…,an组成的有限序列，记作：
LS=(a1,a2,…,an )
其中，每个元素ai必须满足以下条件之一：
- ai是原子（Atom），即不可再分的基本数据元素；
- ai是广义表（Generalized List），即ai本身也是一个广义表。
说明：当n=0 时， LS=() ，即空表。
三、分析
广义表可以使用表头和表尾递归的进行描述，即：
表头：非空广义表的第一个元素
表尾：非空广义靓号，除表头外的其元素组成的新广义表
如果以上面的例子“A = (a,(b,©))”为例，表头是Head(A) =a;表尾是Tail(A)=((b,©))。也就是说，表头是一个元素（可能是原子的也可能是广义表），表尾则始终是一个广义表，即使其只有一个元素，它仍然是一个广义表。
广义表中的元素ai,它可以是一个原子的元素，也可以是一个子广义表。广义表的长度是指表中的元素的个数，深度则是指广义表展开后所包含括号的最大重数（就是有多少对大括号）。
通过分析就可以理解，广义表在计算机的数据结构定义中，也是具有递归的性质的。也就是说，在定义广义表时，需要定义其递归的方式和终止条件，特别是后者，切记。
对于广义表来说，由于其递归的特性，所以其遍历等操作的时间复杂度为O(N)，而空间复杂度则和其递归的深度有关系，最坏的情况为O(D)（D为深度）。
当广义表中的元素均为原子元素时，其退化为线性表。如果其具备树的特点则可以用来描述树，同样也可以描述图。
四、特点和应用
对于广义表来说，它的特点主要包括：
- 复杂性
广义表无论从定义、操作还是元素内容表示，都具体很强的复杂性。这对实际应用其实有一个很高的要求，不如其它一些单一的数据结构更容易学习和应用 - 可扩展性
由于广义表可以自由的进行各种形式的嵌套定义，这就使其具有了强大的可扩展性，可以随时对其进行相关数据定义的扩展和完善。也就是说，单纯从形式描述和定义上，广义表的扩展性更容易为开发者所接受 - 灵活性多样性
它可以灵活的应用在各种不同类型的数据结构的定义中，既可以表示数组、链表也可以表示图和树等。甚至还可以自己存储自己，形成嵌套。从而更加灵活多样的描述各种数据结构
广义表的这些特点，在不同的场景下应用，既可能是优点也可能是缺点，这就需要设计开发者灵活的进行分析把握，合理的应用广义表。
从实际的情况来看，广义表更适合于复杂的数据结构应用，特别是树和图以及ADT等的抽象数据结构等。它在编译器底层处理、大数据处理以及AI和大模型的应用中有着较好的前景。其实说句简单一些的，广义表更适合于一些普通的数据结构不好解决的应用场景，一般是底层或较为特定的复杂场景下。
五、例程
下面看一个广义表的例程：
#include<iostream>#include<memory>#include<vector>class GList{public:enumclassNodeType{Single,List};structNode{NodeType type;intsValue{};std::shared_ptr<Node>head_;std::shared_ptr<Node>tail_;explicitNode(intvalue):type(NodeType::Single),sValue(value){}Node(std::shared_ptr<Node>h,std::shared_ptr<Node>t):type(NodeType::List),head_(h),tail_(t){}};staticstd::shared_ptr<Node>single(intvalue){returnstd::make_shared<Node>(value);}staticstd::shared_ptr<Node>cons(std::shared_ptr<Node>head,std::shared_ptr<Node>tail){returnstd::make_shared<Node>(head,tail);}staticstd::shared_ptr<Node>makeList(conststd::vector<std::shared_ptr<Node>>&elems){std::shared_ptr<Node>list=nullptr;for(autoit=elems.rbegin();it!=elems.rend();++it){list=cons(*it,list);}returnlist;}staticstd::shared_ptr<Node>head(conststd::shared_ptr<Node>&list){listCheck(list);returnlist->head_;}staticstd::shared_ptr<Node>tail(conststd::shared_ptr<Node>&list){listCheck(list);returnlist->tail_;}staticintlength(conststd::shared_ptr<Node>&list){intcount=0;std::shared_ptr<Node>cur=list;while(cur!=nullptr){listCheck(cur);++count;cur=cur->tail_;}returncount;}staticintdepth(conststd::shared_ptr<Node>&list){if(list==nullptr){return1;}if(list->type==NodeType::Single){return0;}intmaxDepth=1;std::shared_ptr<Node>cur=list;while(cur!=nullptr){listCheck(cur);maxDepth=std::max(maxDepth,depth(cur->head_)+1);cur=cur->tail_;}returnmaxDepth;}staticvoiddisplay(conststd::shared_ptr<Node>&list){if(list==nullptr){std::cout<<"()";return;}if(list->type==NodeType::Single){std::cout<<list->sValue;return;}std::cout<<"(";std::shared_ptr<Node>cur=list;bool first=true;while(cur!=nullptr){listCheck(cur);if(!first){std::cout<<", ";}display(cur->head_);first=false;cur=cur->tail_;}std::cout<<")";}private:staticvoidlistCheck(conststd::shared_ptr<Node>&node){if(node==nullptr||node->type!=NodeType::List){std::cout<<"not a non-empty generalized list!"<<std::endl;}}};intmain(){autosubList=GList::makeList({GList::single(3),GList::single(4)});autolist=GList::makeList({GList::single(1),GList::single(2),subList,GList::single(5)});std::cout<<"list = ";GList::display(list);std::cout<<std::endl;std::cout<<"head(list) = ";GList::display(GList::head(list));std::cout<<std::endl;std::cout<<"tail(list) = ";GList::display(GList::tail(list));std::cout<<std::endl;std::cout<<"cur length(list) = "<<GList::length(list)<<std::endl;std::cout<<"cur depth(list) = "<<GList::depth(list)<<std::endl;return0;}六、总结
其实广义表对于大多数的开发者来说，应用的并不多。原因其实也很简单，就是它太复杂了。过于复杂的东西不是说不好用，但对于大多数的开发者的大多数开发场景来说，往往意味着设计上的缺陷。正如前面所说的多级指针和多继承等。
一个良好的设计一定是在所有需求和实际条件下的平衡，绝对不是说使用哪种先进技术就是一个好的设计。与诸君共勉！