一、广义表在前面分析表的数据结构时就对广义表进行了初步的分析。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本身也是一个广义表。说明当n0 时 LS() 即空表。三、分析广义表可以使用表头和表尾递归的进行描述即表头非空广义表的第一个元素表尾非空广义靓号除表头外的其元素组成的新广义表如果以上面的例子“A (a,(b,©))”为例表头是Head(A) a;表尾是Tail(A)((b,©))。也就是说表头是一个元素可能是原子的也可能是广义表表尾则始终是一个广义表即使其只有一个元素它仍然是一个广义表。广义表中的元素ai,它可以是一个原子的元素也可以是一个子广义表。广义表的长度是指表中的元素的个数深度则是指广义表展开后所包含括号的最大重数就是有多少对大括号。通过分析就可以理解广义表在计算机的数据结构定义中也是具有递归的性质的。也就是说在定义广义表时需要定义其递归的方式和终止条件特别是后者切记。对于广义表来说由于其递归的特性所以其遍历等操作的时间复杂度为O(N)而空间复杂度则和其递归的深度有关系最坏的情况为O(D)D为深度。当广义表中的元素均为原子元素时其退化为线性表。如果其具备树的特点则可以用来描述树同样也可以描述图。四、特点和应用对于广义表来说它的特点主要包括复杂性广义表无论从定义、操作还是元素内容表示都具体很强的复杂性。这对实际应用其实有一个很高的要求不如其它一些单一的数据结构更容易学习和应用可扩展性由于广义表可以自由的进行各种形式的嵌套定义这就使其具有了强大的可扩展性可以随时对其进行相关数据定义的扩展和完善。也就是说单纯从形式描述和定义上广义表的扩展性更容易为开发者所接受灵活性多样性它可以灵活的应用在各种不同类型的数据结构的定义中既可以表示数组、链表也可以表示图和树等。甚至还可以自己存储自己形成嵌套。从而更加灵活多样的描述各种数据结构广义表的这些特点在不同的场景下应用既可能是优点也可能是缺点这就需要设计开发者灵活的进行分析把握合理的应用广义表。从实际的情况来看广义表更适合于复杂的数据结构应用特别是树和图以及ADT等的抽象数据结构等。它在编译器底层处理、大数据处理以及AI和大模型的应用中有着较好的前景。其实说句简单一些的广义表更适合于一些普通的数据结构不好解决的应用场景一般是底层或较为特定的复杂场景下。五、例程下面看一个广义表的例程#includeiostream#includememory#includevectorclass GList{public:enumclassNodeType{Single,List};structNode{NodeType type;intsValue{};std::shared_ptrNodehead_;std::shared_ptrNodetail_;explicitNode(intvalue):type(NodeType::Single),sValue(value){}Node(std::shared_ptrNodeh,std::shared_ptrNodet):type(NodeType::List),head_(h),tail_(t){}};staticstd::shared_ptrNodesingle(intvalue){returnstd::make_sharedNode(value);}staticstd::shared_ptrNodecons(std::shared_ptrNodehead,std::shared_ptrNodetail){returnstd::make_sharedNode(head,tail);}staticstd::shared_ptrNodemakeList(conststd::vectorstd::shared_ptrNodeelems){std::shared_ptrNodelistnullptr;for(autoitelems.rbegin();it!elems.rend();it){listcons(*it,list);}returnlist;}staticstd::shared_ptrNodehead(conststd::shared_ptrNodelist){listCheck(list);returnlist-head_;}staticstd::shared_ptrNodetail(conststd::shared_ptrNodelist){listCheck(list);returnlist-tail_;}staticintlength(conststd::shared_ptrNodelist){intcount0;std::shared_ptrNodecurlist;while(cur!nullptr){listCheck(cur);count;curcur-tail_;}returncount;}staticintdepth(conststd::shared_ptrNodelist){if(listnullptr){return1;}if(list-typeNodeType::Single){return0;}intmaxDepth1;std::shared_ptrNodecurlist;while(cur!nullptr){listCheck(cur);maxDepthstd::max(maxDepth,depth(cur-head_)1);curcur-tail_;}returnmaxDepth;}staticvoiddisplay(conststd::shared_ptrNodelist){if(listnullptr){std::cout();return;}if(list-typeNodeType::Single){std::coutlist-sValue;return;}std::cout(;std::shared_ptrNodecurlist;bool firsttrue;while(cur!nullptr){listCheck(cur);if(!first){std::cout, ;}display(cur-head_);firstfalse;curcur-tail_;}std::cout);}private:staticvoidlistCheck(conststd::shared_ptrNodenode){if(nodenullptr||node-type!NodeType::List){std::coutnot a non-empty generalized list!std::endl;}}};intmain(){autosubListGList::makeList({GList::single(3),GList::single(4)});autolistGList::makeList({GList::single(1),GList::single(2),subList,GList::single(5)});std::coutlist ;GList::display(list);std::coutstd::endl;std::couthead(list) ;GList::display(GList::head(list));std::coutstd::endl;std::couttail(list) ;GList::display(GList::tail(list));std::coutstd::endl;std::coutcur length(list) GList::length(list)std::endl;std::coutcur depth(list) GList::depth(list)std::endl;return0;}六、总结其实广义表对于大多数的开发者来说应用的并不多。原因其实也很简单就是它太复杂了。过于复杂的东西不是说不好用但对于大多数的开发者的大多数开发场景来说往往意味着设计上的缺陷。正如前面所说的多级指针和多继承等。一个良好的设计一定是在所有需求和实际条件下的平衡绝对不是说使用哪种先进技术就是一个好的设计。与诸君共勉